I've been experimenting with graph algorithms as a hobby (I'm a backend dev, not a theorist), and I ended up working with ChatGPT to try building a new fingerprinting method for graph isomorphism — based on how information spreads across the graph.
We called it a “gossip fingerprint”: each node tracks when it hears about every edge, how redundantly, and in what order. This encodes structural dynamics rather than just neighborhood info like Weisfeiler-Leman (WL).
The kicker? It seems to pass every known trap we throw at it:
- WL-1 and WL-2 counterexamples (including CFI)
- Recursive CFI (WL-3+)
- Strongly regular graphs (Paley, Clebsch)
- Cospectral and Tutte polynomial twins
- Degree-preserving rewires
- Edit-distance-1 perturbations
- Functionally similar logic graphs
It’s deterministic, polynomial-time (O(nm)), relabeling-invariant, and seems pretty damn strong.
I’m not sure what this is yet — curiosity or something deeper — but I thought the raw conversation itself might be interesting to share.
Here’s the whole transcript, including code, results, and breakdowns:
Would love thoughts. Is this worth a deeper dive, or just a fun anomaly?
We called it a “gossip fingerprint”: each node tracks when it hears about every edge, how redundantly, and in what order. This encodes structural dynamics rather than just neighborhood info like Weisfeiler-Leman (WL).
The kicker? It seems to pass every known trap we throw at it: - WL-1 and WL-2 counterexamples (including CFI) - Recursive CFI (WL-3+) - Strongly regular graphs (Paley, Clebsch) - Cospectral and Tutte polynomial twins - Degree-preserving rewires - Edit-distance-1 perturbations - Functionally similar logic graphs
It’s deterministic, polynomial-time (O(nm)), relabeling-invariant, and seems pretty damn strong.
I’m not sure what this is yet — curiosity or something deeper — but I thought the raw conversation itself might be interesting to share.
Here’s the whole transcript, including code, results, and breakdowns:
Would love thoughts. Is this worth a deeper dive, or just a fun anomaly?