1+ // dsh-mneme/src/graph/anchoring.js
2+ // 图谱锚定层(issue #24 · 块1 Activation Anchoring)。
3+ import assert from "node:assert/strict" ;
4+ // 纯函数模块:把「查询命中实体的多路激活信号」归一化、合并成种子集、再沿
5+ // entity_relations 级联扩散。零数据库依赖——store 侧查询由调用方注入,
6+ // 本模块只做信号处理,便于单测与与其他召回通路(BM25/向量)同等对待。
7+ //
8+ // 设计输入来自 #24 合议 + heptaspirit serendipity-engine 实战(#24 评论):
9+ // - 归一化二分法:连续分(cos/PPR)走 min-max;匹配通路(精确/tag/别名)
10+ // 走离散级别,不用 min-max——布尔通路用 min-max 会把「中 1 个」和「中
11+ // 20 个」都拉平到 1.0,级别信息被压平。
12+ // - 级联扩散加「跳数配额」:λ/θ 只管可及性,可见性由配额决定——直接按 hop
13+ // 深度打 0.5/0.3/0.2 权重,配桶内 round-robin,防深跳被 1-hop 完全压住。
14+ // - graphSeedCap:防「多锚点命中 + 模糊通路」把种子集撑爆成整库。
15+ // - 排序稳定:并列按实体 ID 破序(同输入两次结果不同会让 A/B 调参白做)。
16+
17+ /** 匹配通路的离散级别(heptaspirit 建议:布尔/计数通路不用 min-max)。 */
18+ export const DISCRETE_LEVELS = Object . freeze ( {
19+ exact : 1.0 , // 名称精确含于查询(布尔 1.0)
20+ title : 0.8 , // 实体名匹配记忆标题(tag/别名层)
21+ alias : 0.6 ,
22+ tag : 0.4 , // tag 共现
23+ substring : 0.2 , // 子串命中(最弱,纯计数不级联)
24+ } ) ;
25+
26+ /** 级联每跳的权重(跳数配额:1:2:3-hop = 0.5/0.3/0.2)。 */
27+ export const HOP_QUOTA = Object . freeze ( { 1 : 0.5 , 2 : 0.3 , 3 : 0.2 } ) ;
28+
29+ /**
30+ * 连续分 min-max 归一化(向量 cos 相似度、PPR 激活分等)。
31+ * 输入 [] 或全同值时返回原样(无尺度可压平,防除零)。
32+ */
33+ export function minMax ( scores ) {
34+ const arr = Array . isArray ( scores ) ? scores : [ ] ;
35+ if ( arr . length === 0 ) return [ ] ;
36+ let min = Infinity ;
37+ let max = - Infinity ;
38+ for ( const v of arr ) {
39+ if ( v < min ) min = v ;
40+ if ( v > max ) max = v ;
41+ }
42+ if ( max - min < 1e-12 ) return arr . map ( ( ) => 1 ) ; // 平局视为满权
43+ return arr . map ( ( v ) => ( v - min ) / ( max - min ) ) ;
44+ }
45+
46+ /**
47+ * 把一条检测通路的结果归一化成 0..1 的打分表。
48+ * path 是离散通路名(exact/tag/...)→ 查 DISCRETE_LEVELS;是连续通路
49+ * (continuous=true)→ min-max。返回 { byId: Map<id, score>, order: [id...] }。
50+ */
51+ export function normalizePath ( hits , { path = "exact" , continuous = false } = { } ) {
52+ const ids = Array . isArray ( hits ) ? hits : [ ] ;
53+ const byId = new Map ( ) ;
54+ if ( continuous ) {
55+ const raw = ids . map ( ( h ) => ( typeof h === "number" ? h : h ?. score ?? 0 ) ) ;
56+ const norm = minMax ( raw ) ;
57+ ids . forEach ( ( h , i ) => {
58+ const id = typeof h === "object" ? h . id : h ;
59+ byId . set ( id , norm [ i ] ) ;
60+ } ) ;
61+ } else {
62+ const level = DISCRETE_LEVELS [ path ] ?? DISCRETE_LEVELS . substring ;
63+ for ( const id of ids ) byId . set ( id , level ) ;
64+ }
65+ return { byId, order : [ ...byId . keys ( ) ] } ;
66+ }
67+
68+ /**
69+ * 合并多路激活成种子集:每路先归一化(调用方负责通路分类),再累加。
70+ * seedsCap 上限(graphSeedCap,默认 12);封顶前按总分排序取前 N——保证
71+ * 扩散的是活跃子图而非冷启动点爆整库。
72+ * 返回 { id, name, score, paths: Set } 列表,按 score 降序、name 升序(稳定)。
73+ */
74+ export function anchorSeeds ( { paths = [ ] , cap = 12 } = { } ) {
75+ const score = new Map ( ) ;
76+ const nameOf = new Map ( ) ;
77+ const pathSet = new Map ( ) ;
78+ for ( const p of paths ) {
79+ for ( const [ id , s ] of p . byId ?? [ ] ) {
80+ score . set ( id , ( score . get ( id ) ?? 0 ) + s ) ;
81+ if ( ! pathSet . has ( id ) ) pathSet . set ( id , new Set ( ) ) ;
82+ pathSet . get ( id ) . add ( p . path ?? "?" ) ;
83+ if ( p . nameOf ?. has ?. ( id ) ) nameOf . set ( id , p . nameOf . get ( id ) ) ;
84+ }
85+ }
86+ let seeds = [ ...score . entries ( ) ] . map ( ( [ id , s ] ) => ( {
87+ id,
88+ name : nameOf . get ( id ) ?? id ,
89+ score : s ,
90+ paths : pathSet . get ( id ) ?? new Set ( )
91+ } ) ) ;
92+ seeds . sort ( ( a , b ) => b . score - a . score || ( a . name < b . name ? - 1 : a . name > b . name ? 1 : 0 ) ) ;
93+ if ( cap > 0 && seeds . length > cap ) seeds = seeds . slice ( 0 , cap ) ;
94+ return seeds ;
95+ }
96+
97+ /**
98+ * 级联扩散:从种子实体出发沿 adjacency 走 BFS,为每个可达实体贴最短深度。
99+ * depth 上界默认 2([1,3] 配置范围)。返回 Map<entityId, minDepth>——
100+ * 调用方据此取 HOP_QUOTA[minDepth] 权重 + 桶内 round-robin(见 pickByHopQuota)。
101+ * adjacency 由调用方提供(store.getEntityNeighbors(id) 或全量邻接矩阵),
102+ * 本模块不感知存储。
103+ */
104+ export function cascadeDepths ( { seeds, adjacencyOf, maxDepth = 2 } = { } ) {
105+ const depths = new Map ( ) ;
106+ const idOfSeeds = ( seeds ?? [ ] ) . map ( ( s ) => ( typeof s === "object" ? s . id : s ) ) ;
107+ const queue = [ ] ;
108+ for ( const id of idOfSeeds ) {
109+ if ( ! depths . has ( id ) ) {
110+ depths . set ( id , 0 ) ;
111+ queue . push ( [ id , 0 ] ) ;
112+ }
113+ }
114+ for ( let i = 0 ; i < queue . length ; i ++ ) {
115+ const [ id , d ] = queue [ i ] ;
116+ if ( d >= maxDepth ) continue ;
117+ let neighbors = [ ] ;
118+ try {
119+ neighbors = typeof adjacencyOf === "function" ? adjacencyOf ( id ) : ( adjacencyOf ?. get ?. ( id ) ?? [ ] ) ;
120+ } catch { /* single neighbor fetch failure: keep spreading from the rest */ }
121+ for ( const nb of neighbors ) {
122+ const nid = typeof nb === "object" ? nb . id : nb ;
123+ if ( ! nid || depths . has ( nid ) ) continue ;
124+ depths . set ( nid , d + 1 ) ;
125+ queue . push ( [ nid , d + 1 ] ) ;
126+ }
127+ }
128+ return depths ;
129+ }
130+
131+ /**
132+ * 跳数配额选取:候选实体按深度分层,层内按(分,ID)稳定排序后取额度。
133+ * quota 形如 { 1: 0.5, 2: 0.3, 3: 0.2 }——每层最多取 ceil(depthCap * quota[d]) 个,
134+ * 桶内按 score 降序(并列按 ID)。返回 { ids, scoreOf, depthOf }。
135+ * 这一步把「级联可及性」与「最终可见性」解耦(heptaspirit:λ/θ 只管前者)。
136+ */
137+ export function pickByHopQuota ( {
138+ depths = new Map ( ) ,
139+ scoreOf = ( ) => 0 ,
140+ maxDepth = 2 ,
141+ depthCap = 12
142+ } = { } ) {
143+ const buckets = new Map ( ) ; // depth -> [{id, score}]
144+ for ( const [ id , d ] of depths ) {
145+ if ( d === 0 || d > maxDepth ) continue ;
146+ const key = Math . min ( d , 3 ) ;
147+ if ( ! buckets . has ( key ) ) buckets . set ( key , [ ] ) ;
148+ buckets . get ( key ) . push ( { id, score : scoreOf ( id ) ?? 0 } ) ;
149+ }
150+ const picked = [ ] ;
151+ for ( const [ d , items ] of buckets ) {
152+ items . sort ( ( a , b ) => b . score - a . score || ( a . id < b . id ? - 1 : a . id > b . id ? 1 : 0 ) ) ;
153+ const quota = HOP_QUOTA [ d ] ?? 0.2 ;
154+ const n = Math . max ( 1 , Math . floor ( depthCap * quota ) ) ;
155+ picked . push ( ...items . slice ( 0 , n ) . map ( ( x ) => x . id ) ) ;
156+ }
157+ // 队内稳定序:按深度升序(1-hop 优先),保证可感知的扩散次序。
158+ picked . sort ( ( a , b ) => ( depths . get ( a ) - depths . get ( b ) ) || ( a < b ? - 1 : a > b ? 1 : 0 ) ) ;
159+ return { ids : picked , scoreOf, depthOf : depths } ;
160+ }
161+
162+ // Lightweight self-check (ponytail: 非平凡逻辑留一个可运行断言)。
163+ export function _selfCheck ( ) {
164+ const exact = normalizePath ( [ "e1" , "e2" ] , { path : "exact" } ) ;
165+ const tag = normalizePath ( [ "e2" , "e3" ] , { path : "tag" } ) ;
166+ assert ( exact . byId . get ( "e1" ) === 1.0 && exact . byId . get ( "e2" ) === 1.0 , "exact level" ) ;
167+ assert ( tag . byId . get ( "e2" ) === 0.4 && tag . byId . get ( "e3" ) === 0.4 , "tag level" ) ;
168+ const seeds = anchorSeeds ( { paths : [ exact , tag ] , cap : 10 } ) ;
169+ assert ( seeds [ 0 ] . id === "e2" , "merged highest first" ) ; // e2: 精确+tag = 1.4
170+ assert ( seeds [ 0 ] . score >= 1.4 - 1e-9 , "score accumulates" ) ;
171+ const adj = new Map ( [
172+ [ "e2" , [ "n1" , "n2" ] ] ,
173+ [ "n1" , [ "n2" , "deep3" ] ] ,
174+ ] ) ;
175+ const depths = cascadeDepths ( { seeds, adjacencyOf : ( id ) => adj . get ( id ) ?? [ ] , maxDepth : 2 } ) ;
176+ assert ( depths . get ( "n1" ) === 1 && depths . get ( "n2" ) === 1 && depths . get ( "deep3" ) === 2 , "bfs depth" ) ;
177+ const { ids } = pickByHopQuota ( { depths, maxDepth : 2 , depthCap : 12 } ) ;
178+ assert ( ids . includes ( "n1" ) && ids . includes ( "n2" ) && ids . includes ( "deep3" ) , "quota picks all" ) ;
179+ return "anchoring self-check ok" ;
180+ }
0 commit comments