rust_igraph/algorithms/isomorphism/
wl_hash.rs

1//! Weisfeiler-Lehman graph hashing (ALGO-ISO-007).
2//!
3//! Computes a structural fingerprint for vertices and for the entire graph
4//! using the 1-WL (color refinement) algorithm. Two graphs that are NOT
5//! isomorphic are guaranteed to produce different hashes (with high
6//! probability). Isomorphic graphs MAY hash to the same value, but
7//! non-isomorphic graphs that 1-WL cannot distinguish will also collide.
8//!
9//! This is the standard technique for graph-level classification kernels
10//! and GNN expressiveness bounds.
11
12use crate::core::{Graph, IgraphResult};
13
14/// Result of Weisfeiler-Lehman hashing.
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct WlHashResult {
17    /// Per-vertex hash after the final iteration.
18    pub vertex_hashes: Vec<u64>,
19    /// Graph-level hash (aggregation of sorted vertex hashes).
20    pub graph_hash: u64,
21    /// Number of iterations actually performed (may be less than
22    /// `max_iterations` if colors stabilized early).
23    pub iterations: u32,
24}
25
26/// Compute the Weisfeiler-Lehman hash of a graph.
27///
28/// Uses 1-WL (color refinement): each vertex starts with an initial color
29/// derived from its label (or degree if no labels provided), then
30/// iteratively updates its color by hashing the sorted multiset of
31/// neighbor colors together with its own color.
32///
33/// # Parameters
34///
35/// - `graph` — The input graph.
36/// - `labels` — Optional initial vertex labels. If `None`, vertex degrees
37///   are used as initial colors.
38/// - `max_iterations` — Maximum number of WL iterations. The algorithm
39///   stops early if the coloring stabilizes (no new colors created).
40///
41/// # Returns
42///
43/// A [`WlHashResult`] containing per-vertex hashes, the graph-level hash,
44/// and the number of iterations performed.
45///
46/// # Examples
47///
48/// ```
49/// use rust_igraph::{Graph, wl_hash};
50///
51/// // Two triangles — same WL hash
52/// let g1 = Graph::from_edges(&[(0,1),(1,2),(2,0)], false, Some(3)).unwrap();
53/// let g2 = Graph::from_edges(&[(0,1),(1,2),(2,0)], false, Some(3)).unwrap();
54/// let h1 = wl_hash(&g1, None, 5).unwrap();
55/// let h2 = wl_hash(&g2, None, 5).unwrap();
56/// assert_eq!(h1.graph_hash, h2.graph_hash);
57///
58/// // Triangle vs path — different WL hash
59/// let g3 = Graph::from_edges(&[(0,1),(1,2)], false, Some(3)).unwrap();
60/// let h3 = wl_hash(&g3, None, 5).unwrap();
61/// assert_ne!(h1.graph_hash, h3.graph_hash);
62/// ```
63pub fn wl_hash(
64    graph: &Graph,
65    labels: Option<&[u32]>,
66    max_iterations: u32,
67) -> IgraphResult<WlHashResult> {
68    let n = graph.vcount() as usize;
69
70    if n == 0 {
71        return Ok(WlHashResult {
72            vertex_hashes: Vec::new(),
73            graph_hash: 0,
74            iterations: 0,
75        });
76    }
77
78    if let Some(l) = labels {
79        if l.len() != n {
80            return Err(crate::core::IgraphError::InvalidArgument(format!(
81                "labels length {} != vcount {}",
82                l.len(),
83                n
84            )));
85        }
86    }
87
88    let mut colors: Vec<u64> = if let Some(l) = labels {
89        l.iter().map(|&x| u64::from(x)).collect()
90    } else {
91        let mut c = Vec::with_capacity(n);
92        for v in 0..graph.vcount() {
93            c.push(graph.degree(v)? as u64);
94        }
95        c
96    };
97
98    let mut iterations = 0u32;
99    let mut prev_num_colors = count_distinct(&colors);
100
101    for _ in 0..max_iterations {
102        let mut new_colors: Vec<u64> = Vec::with_capacity(n);
103
104        for v in 0..graph.vcount() {
105            let neighbors = graph.neighbors(v)?;
106            let mut neighbor_hashes: Vec<u64> =
107                neighbors.iter().map(|&u| colors[u as usize]).collect();
108            neighbor_hashes.sort_unstable();
109
110            let new_hash = hash_multiset(colors[v as usize], &neighbor_hashes);
111            new_colors.push(new_hash);
112        }
113
114        colors = new_colors;
115        iterations += 1;
116
117        let num_colors = count_distinct(&colors);
118        if num_colors == prev_num_colors {
119            break;
120        }
121        prev_num_colors = num_colors;
122    }
123
124    let graph_hash = compute_graph_hash(&colors);
125
126    Ok(WlHashResult {
127        vertex_hashes: colors,
128        graph_hash,
129        iterations,
130    })
131}
132
133/// Compute WL hashes at each iteration level (subtree patterns of depth 0..k).
134///
135/// Returns a vector of [`WlHashResult`] for iterations 0 through
136/// `max_iterations` (or until stabilization). This is useful for
137/// WL subtree kernel computation where you need hashes at every depth.
138///
139/// # Examples
140///
141/// ```
142/// use rust_igraph::{Graph, wl_hash_iterations};
143///
144/// let g = Graph::from_edges(&[(0,1),(1,2),(2,3),(3,0)], false, Some(4)).unwrap();
145/// let iters = wl_hash_iterations(&g, None, 3).unwrap();
146/// assert!(!iters.is_empty());
147/// assert!(iters.len() <= 4); // initial + up to 3 iterations
148/// ```
149pub fn wl_hash_iterations(
150    graph: &Graph,
151    labels: Option<&[u32]>,
152    max_iterations: u32,
153) -> IgraphResult<Vec<WlHashResult>> {
154    let n = graph.vcount() as usize;
155
156    if n == 0 {
157        return Ok(vec![WlHashResult {
158            vertex_hashes: Vec::new(),
159            graph_hash: 0,
160            iterations: 0,
161        }]);
162    }
163
164    if let Some(l) = labels {
165        if l.len() != n {
166            return Err(crate::core::IgraphError::InvalidArgument(format!(
167                "labels length {} != vcount {}",
168                l.len(),
169                n
170            )));
171        }
172    }
173
174    let mut colors: Vec<u64> = if let Some(l) = labels {
175        l.iter().map(|&x| u64::from(x)).collect()
176    } else {
177        let mut c = Vec::with_capacity(n);
178        for v in 0..graph.vcount() {
179            c.push(graph.degree(v)? as u64);
180        }
181        c
182    };
183
184    let mut results: Vec<WlHashResult> = Vec::with_capacity((max_iterations + 1) as usize);
185
186    results.push(WlHashResult {
187        vertex_hashes: colors.clone(),
188        graph_hash: compute_graph_hash(&colors),
189        iterations: 0,
190    });
191
192    let mut prev_num_colors = count_distinct(&colors);
193
194    for iter in 0..max_iterations {
195        let mut new_colors: Vec<u64> = Vec::with_capacity(n);
196
197        for v in 0..graph.vcount() {
198            let neighbors = graph.neighbors(v)?;
199            let mut neighbor_hashes: Vec<u64> =
200                neighbors.iter().map(|&u| colors[u as usize]).collect();
201            neighbor_hashes.sort_unstable();
202
203            let new_hash = hash_multiset(colors[v as usize], &neighbor_hashes);
204            new_colors.push(new_hash);
205        }
206
207        colors = new_colors;
208
209        results.push(WlHashResult {
210            vertex_hashes: colors.clone(),
211            graph_hash: compute_graph_hash(&colors),
212            iterations: iter + 1,
213        });
214
215        let num_colors = count_distinct(&colors);
216        if num_colors == prev_num_colors {
217            break;
218        }
219        prev_num_colors = num_colors;
220    }
221
222    Ok(results)
223}
224
225/// Check if two graphs have equal WL hash (necessary but not sufficient
226/// for isomorphism).
227///
228/// # Examples
229///
230/// ```
231/// use rust_igraph::{Graph, wl_isomorphic};
232///
233/// let g1 = Graph::from_edges(&[(0,1),(1,2),(2,0)], false, Some(3)).unwrap();
234/// let g2 = Graph::from_edges(&[(0,1),(1,2),(2,0)], false, Some(3)).unwrap();
235/// assert!(wl_isomorphic(&g1, &g2, None, None, 5).unwrap());
236///
237/// let g3 = Graph::from_edges(&[(0,1),(1,2)], false, Some(3)).unwrap();
238/// assert!(!wl_isomorphic(&g1, &g3, None, None, 5).unwrap());
239/// ```
240pub fn wl_isomorphic(
241    g1: &Graph,
242    g2: &Graph,
243    labels1: Option<&[u32]>,
244    labels2: Option<&[u32]>,
245    max_iterations: u32,
246) -> IgraphResult<bool> {
247    if g1.vcount() != g2.vcount() || g1.ecount() != g2.ecount() {
248        return Ok(false);
249    }
250
251    let h1 = wl_hash(g1, labels1, max_iterations)?;
252    let h2 = wl_hash(g2, labels2, max_iterations)?;
253
254    if h1.graph_hash != h2.graph_hash {
255        return Ok(false);
256    }
257
258    let mut s1 = h1.vertex_hashes;
259    let mut s2 = h2.vertex_hashes;
260    s1.sort_unstable();
261    s2.sort_unstable();
262    Ok(s1 == s2)
263}
264
265// --- Internal helpers ---
266
267fn count_distinct(colors: &[u64]) -> usize {
268    let mut sorted = colors.to_vec();
269    sorted.sort_unstable();
270    sorted.dedup();
271    sorted.len()
272}
273
274fn hash_multiset(self_color: u64, neighbor_colors: &[u64]) -> u64 {
275    let mut h = self_color;
276    h = mix(h, 0x9e37_79b9_7f4a_7c15);
277    for &c in neighbor_colors {
278        h = mix(h, c);
279    }
280    finalize(h)
281}
282
283fn compute_graph_hash(colors: &[u64]) -> u64 {
284    let mut sorted: Vec<u64> = colors.to_vec();
285    sorted.sort_unstable();
286
287    let mut h: u64 = sorted.len() as u64;
288    for &c in &sorted {
289        h = mix(h, c);
290    }
291    finalize(h)
292}
293
294#[inline]
295fn mix(mut h: u64, k: u64) -> u64 {
296    h ^= k;
297    h = h.wrapping_mul(0x517c_c1b7_2722_0a95);
298    h ^= h >> 33;
299    h
300}
301
302#[inline]
303fn finalize(mut h: u64) -> u64 {
304    h ^= h >> 33;
305    h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
306    h ^= h >> 33;
307    h = h.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
308    h ^= h >> 33;
309    h
310}
311
312#[cfg(test)]
313mod tests {
314    use super::*;
315
316    fn triangle() -> Graph {
317        Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], false, Some(3)).unwrap()
318    }
319
320    fn path3() -> Graph {
321        Graph::from_edges(&[(0, 1), (1, 2)], false, Some(3)).unwrap()
322    }
323
324    fn cycle4() -> Graph {
325        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
326    }
327
328    fn complete4() -> Graph {
329        Graph::from_edges(
330            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
331            false,
332            Some(4),
333        )
334        .unwrap()
335    }
336
337    #[test]
338    fn same_graph_same_hash() {
339        let g1 = triangle();
340        let g2 = triangle();
341        let h1 = wl_hash(&g1, None, 5).unwrap();
342        let h2 = wl_hash(&g2, None, 5).unwrap();
343        assert_eq!(h1.graph_hash, h2.graph_hash);
344        assert_eq!(h1.vertex_hashes, h2.vertex_hashes);
345    }
346
347    #[test]
348    fn different_structure_different_hash() {
349        let g1 = triangle();
350        let g2 = path3();
351        let h1 = wl_hash(&g1, None, 5).unwrap();
352        let h2 = wl_hash(&g2, None, 5).unwrap();
353        assert_ne!(h1.graph_hash, h2.graph_hash);
354    }
355
356    #[test]
357    fn cycle_vs_complete() {
358        let g1 = cycle4();
359        let g2 = complete4();
360        let h1 = wl_hash(&g1, None, 5).unwrap();
361        let h2 = wl_hash(&g2, None, 5).unwrap();
362        assert_ne!(h1.graph_hash, h2.graph_hash);
363    }
364
365    #[test]
366    fn triangle_vertices_all_same() {
367        let g = triangle();
368        let h = wl_hash(&g, None, 5).unwrap();
369        assert_eq!(h.vertex_hashes[0], h.vertex_hashes[1]);
370        assert_eq!(h.vertex_hashes[1], h.vertex_hashes[2]);
371    }
372
373    #[test]
374    fn path_endpoints_same_center_different() {
375        let g = path3();
376        let h = wl_hash(&g, None, 5).unwrap();
377        assert_eq!(h.vertex_hashes[0], h.vertex_hashes[2]);
378        assert_ne!(h.vertex_hashes[0], h.vertex_hashes[1]);
379    }
380
381    #[test]
382    fn with_labels() {
383        let g = triangle();
384        let labels1 = vec![0, 0, 0];
385        let labels2 = vec![0, 1, 0];
386        let h1 = wl_hash(&g, Some(&labels1), 5).unwrap();
387        let h2 = wl_hash(&g, Some(&labels2), 5).unwrap();
388        assert_ne!(h1.graph_hash, h2.graph_hash);
389    }
390
391    #[test]
392    fn deterministic() {
393        let g = cycle4();
394        let h1 = wl_hash(&g, None, 10).unwrap();
395        let h2 = wl_hash(&g, None, 10).unwrap();
396        assert_eq!(h1, h2);
397    }
398
399    #[test]
400    fn stabilization() {
401        let g = triangle();
402        let h = wl_hash(&g, None, 100).unwrap();
403        assert!(h.iterations <= 2);
404    }
405
406    #[test]
407    fn empty_graph() {
408        let g = Graph::with_vertices(0);
409        let h = wl_hash(&g, None, 5).unwrap();
410        assert!(h.vertex_hashes.is_empty());
411        assert_eq!(h.graph_hash, 0);
412        assert_eq!(h.iterations, 0);
413    }
414
415    #[test]
416    fn single_vertex() {
417        let g = Graph::with_vertices(1);
418        let h = wl_hash(&g, None, 5).unwrap();
419        assert_eq!(h.vertex_hashes.len(), 1);
420        assert!(h.iterations >= 1);
421    }
422
423    #[test]
424    fn disconnected_components() {
425        // Two isolated edges: 0-1 and 2-3
426        let g = Graph::from_edges(&[(0, 1), (2, 3)], false, Some(4)).unwrap();
427        let h = wl_hash(&g, None, 5).unwrap();
428        assert_eq!(h.vertex_hashes[0], h.vertex_hashes[2]);
429        assert_eq!(h.vertex_hashes[1], h.vertex_hashes[3]);
430    }
431
432    #[test]
433    fn wl_isomorphic_same() {
434        let g1 = cycle4();
435        let g2 = cycle4();
436        assert!(wl_isomorphic(&g1, &g2, None, None, 5).unwrap());
437    }
438
439    #[test]
440    fn wl_isomorphic_different() {
441        let g1 = triangle();
442        let g2 = path3();
443        assert!(!wl_isomorphic(&g1, &g2, None, None, 5).unwrap());
444    }
445
446    #[test]
447    fn wl_isomorphic_different_size() {
448        let g1 = triangle();
449        let g2 = cycle4();
450        assert!(!wl_isomorphic(&g1, &g2, None, None, 5).unwrap());
451    }
452
453    #[test]
454    fn wl_hash_iterations_count() {
455        let g = cycle4();
456        let iters = wl_hash_iterations(&g, None, 5).unwrap();
457        assert!(iters.len() >= 2);
458        assert_eq!(iters[0].iterations, 0);
459        assert_eq!(
460            iters.last().unwrap().iterations,
461            u32::try_from(iters.len()).unwrap() - 1
462        );
463    }
464
465    #[test]
466    fn isomorphic_relabeled() {
467        // C4: 0-1-2-3-0 vs relabeled: 0-2-1-3-0
468        let g1 = Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap();
469        let g2 = Graph::from_edges(&[(0, 2), (2, 1), (1, 3), (3, 0)], false, Some(4)).unwrap();
470        assert!(wl_isomorphic(&g1, &g2, None, None, 5).unwrap());
471    }
472
473    #[test]
474    fn directed_graph() {
475        let g1 = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true, Some(3)).unwrap();
476        let g2 = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true, Some(3)).unwrap();
477        let h1 = wl_hash(&g1, None, 5).unwrap();
478        let h2 = wl_hash(&g2, None, 5).unwrap();
479        assert_eq!(h1.graph_hash, h2.graph_hash);
480    }
481
482    #[test]
483    fn labels_length_mismatch() {
484        let g = triangle();
485        let result = wl_hash(&g, Some(&[0, 1]), 5);
486        assert!(result.is_err());
487    }
488}
rust_igraph/algorithms/isomorphism/wl_hash.rs

rust_igraph/algorithms/isomorphism/
wl_hash.rs
