qualia_core_db/solvers/graph_opt/
spreading_activation.rs

1//! Spreading activation (Kornai, *Vector Semantics* ch 7.4) — propagate an
2//! activation level from seed concepts through the semantic-network edges, decaying
3//! with distance. The classic associative-retrieval mechanism: given a query's seed
4//! concepts, it ranks which graph regions are most relevant.
5//!
6//! Mission fit: a natural engine for the 10D→5D NQuin **relevance router**
7//! ("streaming lives in retrieval, not attention; we own the cache") — complementary
8//! to PCA and mutual information on the same router. Kernel-class `Reduction` (the
9//! per-hop weighted sums); bounded iteration, CPU reference.
10
11use std::collections::HashMap;
12
13/// A directed weighted edge `from → to` with non-negative `weight`.
14#[derive(Debug, Clone, Copy)]
15pub struct Edge {
16    pub from: usize,
17    pub to: usize,
18    pub weight: f64,
19}
20
21/// Spread activation from `seeds` (node, initial activation) over `n_nodes` through
22/// `edges`, decaying by `decay ∈ (0,1]` each hop and pruning contributions below
23/// `threshold`. Runs at most `max_hops`. Returns total accumulated activation per
24/// node (the relevance score).
25pub fn spreading_activation(
26    n_nodes: usize,
27    edges: &[Edge],
28    seeds: &[(usize, f64)],
29    decay: f64,
30    threshold: f64,
31    max_hops: usize,
32) -> Vec<f64> {
33    let mut total = vec![0.0; n_nodes];
34    if n_nodes == 0 {
35        return total;
36    }
37    // Outgoing adjacency.
38    let mut adj: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n_nodes];
39    for e in edges {
40        if e.from < n_nodes && e.to < n_nodes && e.weight > 0.0 {
41            adj[e.from].push((e.to, e.weight));
42        }
43    }
44    // Wavefront of "newly activated this hop".
45    let mut current: HashMap<usize, f64> = HashMap::new();
46    for &(node, a) in seeds {
47        if node < n_nodes && a > 0.0 {
48            *current.entry(node).or_insert(0.0) += a;
49            total[node] += a;
50        }
51    }
52    let decay = decay.clamp(0.0, 1.0);
53    for _ in 0..max_hops {
54        if current.is_empty() {
55            break;
56        }
57        let mut next: HashMap<usize, f64> = HashMap::new();
58        for (&node, &a) in &current {
59            for &(to, w) in &adj[node] {
60                let contrib = a * w * decay;
61                if contrib > threshold {
62                    *next.entry(to).or_insert(0.0) += contrib;
63                }
64            }
65        }
66        for (&node, &a) in &next {
67            total[node] += a;
68        }
69        current = next;
70    }
71    total
72}
73
74/// Indices of the top-`k` most-activated nodes (relevance ranking), highest first.
75pub fn top_k(activation: &[f64], k: usize) -> Vec<usize> {
76    let mut idx: Vec<usize> = (0..activation.len()).collect();
77    idx.sort_by(|&a, &b| {
78        activation[b]
79            .partial_cmp(&activation[a])
80            .unwrap_or(core::cmp::Ordering::Equal)
81    });
82    idx.truncate(k.min(activation.len()));
83    idx
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    fn e(from: usize, to: usize, w: f64) -> Edge {
91        Edge {
92            from,
93            to,
94            weight: w,
95        }
96    }
97
98    #[test]
99    fn activation_decays_along_a_chain() {
100        // 0 → 1 → 2 → 3, all weight 1. Seed node 0.
101        let edges = [e(0, 1, 1.0), e(1, 2, 1.0), e(2, 3, 1.0)];
102        let act = spreading_activation(4, &edges, &[(0, 1.0)], 0.5, 1e-6, 10);
103        // Strictly decreasing activation with distance from the seed.
104        assert!(act[0] > act[1] && act[1] > act[2] && act[2] > act[3]);
105        assert!(act[3] > 0.0);
106    }
107
108    #[test]
109    fn closer_nodes_rank_higher() {
110        // Star: 0 → {1,2,3}; and 1 → 4 (one hop further).
111        let edges = [e(0, 1, 1.0), e(0, 2, 1.0), e(0, 3, 1.0), e(1, 4, 1.0)];
112        let act = spreading_activation(5, &edges, &[(0, 1.0)], 0.6, 1e-9, 10);
113        // Direct neighbours outrank the two-hop node.
114        assert!(act[1] > act[4]);
115        let ranking = top_k(&act, 3);
116        assert_eq!(ranking[0], 0); // the seed itself is most active
117    }
118
119    #[test]
120    fn weights_bias_the_spread() {
121        // 0 → 1 (strong), 0 → 2 (weak): node 1 should out-activate node 2.
122        let edges = [e(0, 1, 0.9), e(0, 2, 0.1)];
123        let act = spreading_activation(3, &edges, &[(0, 1.0)], 1.0, 1e-9, 5);
124        assert!(act[1] > act[2]);
125    }
126
127    #[test]
128    fn empty_and_threshold() {
129        assert_eq!(spreading_activation(0, &[], &[], 0.5, 0.0, 5).len(), 0);
130        // A high threshold prunes everything beyond the seed.
131        let edges = [e(0, 1, 0.01)];
132        let act = spreading_activation(2, &edges, &[(0, 1.0)], 0.5, 0.1, 5);
133        assert_eq!(act[1], 0.0);
134    }
135}
qualia_core_db/solvers/graph_opt/spreading_activation.rs

qualia_core_db/solvers/graph_opt/
spreading_activation.rs
