DRESS: A Continuous Framework for Structural Graph Refinement

Abstract

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 d_) 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 Δ-DRESS, which runs DRESS on each vertex-deleted subgraph to boost expressiveness. Δ-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 (Δ^k-DRESS) empirically matches the (k+2)-WL boundary.

Reproductions