DRESS: A Continuous Framework for Structural Graph Refinement
Not on the map. Why?
Abstract (arXiv)
We introduce DRESS, a deterministic, parameter-free framework that iteratively refines the structural similarity of edges in a graph to produce a canonical fingerprint: a real-valued edge vector, obtained by converging a non-linear dynamical system to its unique fixed point. The fingerprint is isomorphism-invariant by construction, numerically stable (strictly bounded, precision-preserving, and mathematically well-posed), fast and embarrassingly parallel to compute: DRESS total runtime is O(I · m · dmax) for I iterations to convergence, and convergence is guaranteed by Birkhoff contraction. We generalize the original equation to Motif-DRESS (arbitrary structural motifs) and Generalized-DRESS (abstract aggregation template), and introduce Delta-DRESS, which runs DRESS on each vertex-deleted subgraph to boost expressiveness. Delta-DRESS empirically separates all 7,983 graphs in a comprehensive Strongly Regular Graph benchmark, and on the tested CFI instances (k = 0,1,2,3), k-deletion (Deltak-DRESS) empirically matches the (k+2)-WL boundary.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 8 of its 21 references that are in the map. First posted on arXiv 24 Feb 2026.
Builds on
8 of 21 references.
References · 8
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2019Provably Powerful Graph Networkscited by 385
- 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
- 2021Equivariant Subgraph Aggregation Networkscited by 154
- 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
- 2018Dynamic Structural Similarity on Graphscited by 4
- 2018High-Quality Disjoint and Overlapping Community Structure in Large-Scale Complex Networkscited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.
- 2026Breaking Hard Isomorphism Benchmarks with DRESScited by 0
- 2026Breaking Hard Isomorphism Benchmarks with DRESS19 Mar 2026