qualia_core_db/solvers/graph_match/
fuzzy_similarity.rs

1//! Fuzzy RDF graph similarity (Ma, Li & Ma ch 3.4) — a degree-aware similarity
2//! between two fuzzy RDF graphs (triples carrying a membership degree). The fuzzy
3//! Jaccard generalizes set overlap to graded membership: shared structure counts in
4//! proportion to *how strongly* both graphs assert it. Kernel-class `Reduction`.
5
6use std::collections::HashMap;
7
8/// An RDF triple `(s, p, o)` with a membership degree in `[0,1]`. Terms are term
9/// ids (interned URIs).
10#[derive(Debug, Clone, Copy, PartialEq)]
11pub struct FuzzyTriple {
12    pub s: usize,
13    pub p: usize,
14    pub o: usize,
15    pub degree: f64,
16}
17
18fn to_map(g: &[FuzzyTriple]) -> HashMap<(usize, usize, usize), f64> {
19    let mut m = HashMap::new();
20    for t in g {
21        // Keep the strongest degree if a triple repeats.
22        let e = m.entry((t.s, t.p, t.o)).or_insert(0.0);
23        if t.degree > *e {
24            *e = t.degree.clamp(0.0, 1.0);
25        }
26    }
27    m
28}
29
30/// Fuzzy Jaccard similarity `Σ min(d₁,d₂) / Σ max(d₁,d₂)` over the union of triples
31/// (a missing triple has degree 0). Returns `[0,1]`; `1.0` for identical graphs,
32/// `0.0` for disjoint ones. Two empty graphs are defined as similarity `1.0`.
33pub fn fuzzy_jaccard(g1: &[FuzzyTriple], g2: &[FuzzyTriple]) -> f64 {
34    let m1 = to_map(g1);
35    let m2 = to_map(g2);
36    let mut keys: std::collections::HashSet<(usize, usize, usize)> = m1.keys().copied().collect();
37    keys.extend(m2.keys().copied());
38    if keys.is_empty() {
39        return 1.0;
40    }
41    let mut num = 0.0;
42    let mut den = 0.0;
43    for k in keys {
44        let a = *m1.get(&k).unwrap_or(&0.0);
45        let b = *m2.get(&k).unwrap_or(&0.0);
46        num += a.min(b);
47        den += a.max(b);
48    }
49    if den > 0.0 {
50        num / den
51    } else {
52        1.0
53    }
54}
55
56/// Degree-weighted overlap (Dice-style): `2·Σ min / (Σd₁ + Σd₂)`. An alternative
57/// emphasizing shared mass. Returns `[0,1]`.
58pub fn fuzzy_dice(g1: &[FuzzyTriple], g2: &[FuzzyTriple]) -> f64 {
59    let m1 = to_map(g1);
60    let m2 = to_map(g2);
61    let sum1: f64 = m1.values().sum();
62    let sum2: f64 = m2.values().sum();
63    if sum1 + sum2 == 0.0 {
64        return 1.0;
65    }
66    let mut inter = 0.0;
67    for (k, &a) in &m1 {
68        if let Some(&b) = m2.get(k) {
69            inter += a.min(b);
70        }
71    }
72    2.0 * inter / (sum1 + sum2)
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    fn t(s: usize, p: usize, o: usize, d: f64) -> FuzzyTriple {
80        FuzzyTriple { s, p, o, degree: d }
81    }
82
83    #[test]
84    fn identical_graphs_are_one() {
85        let g = [t(0, 1, 2, 0.8), t(2, 1, 3, 0.5)];
86        assert!((fuzzy_jaccard(&g, &g) - 1.0).abs() < 1e-12);
87        assert!((fuzzy_dice(&g, &g) - 1.0).abs() < 1e-12);
88    }
89
90    #[test]
91    fn disjoint_graphs_are_zero() {
92        let g1 = [t(0, 1, 2, 0.9)];
93        let g2 = [t(5, 6, 7, 0.9)];
94        assert!(fuzzy_jaccard(&g1, &g2).abs() < 1e-12);
95    }
96
97    #[test]
98    fn partial_overlap_with_degrees() {
99        // Shared triple at degrees 0.8 vs 0.4; one extra in each.
100        let g1 = [t(0, 1, 2, 0.8), t(3, 1, 4, 0.6)];
101        let g2 = [t(0, 1, 2, 0.4), t(5, 1, 6, 0.7)];
102        let j = fuzzy_jaccard(&g1, &g2);
103        // num = min(.8,.4)=0.4 ; den = max(.8,.4)+0.6+0.7 = 0.8+0.6+0.7 = 2.1 → 0.19.
104        assert!((j - 0.4 / 2.1).abs() < 1e-9, "jaccard {j}");
105        assert!(j > 0.0 && j < 1.0);
106    }
107
108    #[test]
109    fn empty_graphs_are_similar() {
110        assert!((fuzzy_jaccard(&[], &[]) - 1.0).abs() < 1e-12);
111    }
112}
qualia_core_db/solvers/graph_match/fuzzy_similarity.rs

qualia_core_db/solvers/graph_match/
fuzzy_similarity.rs
