qualia_core_db/solvers/graph_match/
approximate.rs

1//! Approximate fuzzy subgraph matching (Ma, Li & Ma ch 5.3) — find the mapping of a
2//! query pattern's nodes onto a data graph that best matches it, tolerantly and
3//! ranked by a fuzzy score. This is the **machine-proposes** half of "machine
4//! proposes `closeMatch`, signed human ratifies `exactMatch`": it returns a mapping
5//! **and a degree**, never a resolved identity (the out-of-band-remainder invariant).
6//!
7//! The search reuses `optimization::metaheuristics::hill_climbing` over node
8//! assignments (no new optimizer). Kernel-class `Divergent`.
9
10use crate::solvers::graph_match::fuzzy_similarity::FuzzyTriple;
11use crate::solvers::optimization::metaheuristics::{hill_climbing, Rng};
12use std::collections::HashMap;
13
14/// A proposed (never asserted) correspondence: which data node each pattern node
15/// maps to, and the fuzzy match score that earned it.
16#[derive(Debug, Clone, PartialEq)]
17pub struct MatchResult {
18    /// `mapping[pattern_node] = data_node`.
19    pub mapping: Vec<usize>,
20    /// Total fuzzy match score (sum of matched-triple `t-norm` degrees). Higher is
21    /// a stronger correspondence; the caller treats it as a `closeMatch` *proposal*.
22    pub score: f64,
23}
24
25/// Index data triples for O(1) `(s,p,o) → degree` lookup.
26fn index(data: &[FuzzyTriple]) -> HashMap<(usize, usize, usize), f64> {
27    let mut m = HashMap::new();
28    for t in data {
29        let e = m.entry((t.s, t.p, t.o)).or_insert(0.0);
30        if t.degree > *e {
31            *e = t.degree;
32        }
33    }
34    m
35}
36
37/// Fuzzy match score of a `pattern_node → data_node` mapping: for each pattern
38/// triple `(s,p,o,d_p)`, if the data graph has `(map[s], p, map[o])` with degree
39/// `d_d`, add `d_p · d_d` (product t-norm).
40fn score(
41    pattern: &[FuzzyTriple],
42    idx: &HashMap<(usize, usize, usize), f64>,
43    mapping: &[usize],
44) -> f64 {
45    let mut s = 0.0;
46    for tr in pattern {
47        let key = (mapping[tr.s], tr.p, mapping[tr.o]);
48        if let Some(&dd) = idx.get(&key) {
49            s += tr.degree * dd;
50        }
51    }
52    s
53}
54
55/// Find the best correspondence of `n_pattern_nodes` pattern nodes onto
56/// `n_data_nodes` data nodes by `restarts` hill-climbing runs from random seeds.
57/// Returns the highest-scoring mapping. `None` on a degenerate problem.
58pub fn approximate_match(
59    pattern: &[FuzzyTriple],
60    data: &[FuzzyTriple],
61    n_pattern_nodes: usize,
62    n_data_nodes: usize,
63    restarts: usize,
64    seed: u64,
65) -> Option<MatchResult> {
66    if n_pattern_nodes == 0 || n_data_nodes == 0 {
67        return None;
68    }
69    let idx = index(data);
70    let objective = |m: &Vec<usize>| -score(pattern, &idx, m); // minimize negative score
71    let neighbors = |m: &Vec<usize>| {
72        let mut out = Vec::new();
73        for i in 0..m.len() {
74            for d in 0..n_data_nodes {
75                if d != m[i] {
76                    let mut c = m.clone();
77                    c[i] = d;
78                    out.push(c);
79                }
80            }
81        }
82        out
83    };
84
85    let mut rng = Rng(seed ^ 0x9E3779B97F4A7C15);
86    let mut best: Option<MatchResult> = None;
87    for _ in 0..restarts.max(1) {
88        let init: Vec<usize> = (0..n_pattern_nodes)
89            .map(|_| rng.below(n_data_nodes))
90            .collect();
91        let (m, neg) = hill_climbing(init, &neighbors, &objective, 200);
92        let sc = -neg;
93        if best.as_ref().map(|b| sc > b.score).unwrap_or(true) {
94            best = Some(MatchResult {
95                mapping: m,
96                score: sc,
97            });
98        }
99    }
100    best
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    fn t(s: usize, p: usize, o: usize, d: f64) -> FuzzyTriple {
108        FuzzyTriple { s, p, o, degree: d }
109    }
110
111    #[test]
112    fn finds_an_embedded_pattern() {
113        // Data: a "knows" chain  A-knows->B-knows->C  (predicate 0), strong degrees.
114        // Pattern: x-knows->y-knows->z. The best mapping is x→A, y→B, z→C.
115        let data = [t(10, 0, 11, 0.9), t(11, 0, 12, 0.9), t(99, 0, 98, 0.2)];
116        let pattern = [t(0, 0, 1, 1.0), t(1, 0, 2, 1.0)]; // 3 pattern nodes 0,1,2
117        let r = approximate_match(&pattern, &data, 3, 13, 8, 1).unwrap();
118        assert!(r.score > 1.5, "score {}", r.score);
119        // Pattern node 0→10, 1→11, 2→12 (or an equally-scoring relabel).
120        assert_eq!(r.mapping[0], 10);
121        assert_eq!(r.mapping[1], 11);
122        assert_eq!(r.mapping[2], 12);
123    }
124
125    #[test]
126    fn partial_match_scores_lower_than_full() {
127        let data = [t(10, 0, 11, 0.9)]; // only one edge
128        let pattern = [t(0, 0, 1, 1.0), t(1, 0, 2, 1.0)]; // wants two edges
129        let r = approximate_match(&pattern, &data, 3, 12, 6, 2).unwrap();
130        // At most one pattern edge can match → score ≤ ~0.9.
131        assert!(r.score <= 0.9 + 1e-9 && r.score > 0.0);
132    }
133
134    #[test]
135    fn returns_a_degree_not_an_assertion() {
136        // The result is a score-bearing proposal; the API never claims identity.
137        let data = [t(0, 0, 1, 0.5)];
138        let pattern = [t(0, 0, 1, 0.5)];
139        let r = approximate_match(&pattern, &data, 2, 2, 4, 3).unwrap();
140        assert!(r.score > 0.0 && r.score <= 1.0);
141        assert_eq!(r.mapping.len(), 2);
142    }
143
144    #[test]
145    fn guards() {
146        assert!(approximate_match(&[], &[], 0, 0, 1, 0).is_none());
147    }
148}
qualia_core_db/solvers/graph_match/approximate.rs

qualia_core_db/solvers/graph_match/
approximate.rs
