DRESS Graph¶

A Continuous Framework for Structural Graph Refinement

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 (all values lie in [0, 2]), fast and embarrassingly parallel to compute: each iteration costs O(m · d_max) and convergence is guaranteed by Birkhoff contraction. As a direct consequence of these properties, DRESS is provably at least as expressive as the 2-dimensional Weisfeiler–Leman (2-WL) test, at a fraction of the cost (O(m · d_max) vs. O(n³) per iteration). We generalize the original equation (Castrillo, León, and Gómez, 2018) 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 51,816 graphs across 34 hard benchmark families (16 SRG families totaling 51,718 graphs from the complete Spence collection and McKay's additional SRG data, plus 18 constructed hard families), resolving over 576 million within-family non-isomorphic pairs, and is the cheapest known method that strictly exceeds 3-WL. Iterated deletion (Δᵏ-DRESS) climbs the CFI staircase, achieving (k+2)-WL expressiveness at each depth k. The algorithm is embarrassingly parallel in two orthogonal ways - across the vertex-deleted subgraphs and across edge updates within each iteration - enabling distributed/cloud plus multi-core/GPU/SIMD implementations. Successfully applied to a handful of downstream applications.

For the theory and generalizations (DRESS Family), see the research papers:

• DRESS: A Continuous Framework for Structural Graph Refinement — the DRESS equation, Motif-DRESS, Generalized-DRESS, Δᵏ-DRESS, convergence proofs, CFI staircase experiments.
• The CFI Staircase Theorem — unconditional proof that Δᵏ-DRESS distinguishes every CFI(K_{k+3}) pair; conditional proof that Δᵏ-DRESS ≥ (k+2)-WL for all graphs.
• Δ¹-DRESS Separates All Known Hard Families — 100% separation on 51,816 hard graphs across 34 benchmark families; Δ¹-DRESS strictly exceeds 3-WL.

This work is an independent continuation of research from the author's master's thesis:

A fast heuristic algorithm for community detection in large-scale complex networks Eduar Castrillo, Universidad Nacional de Colombia, 2018 bdigital.unal.edu.co/69933

DRESS emerged from intuition while developing algorithms for community detection. What started as an edge scoring function turned out to be a fundamental structural object: a single algorithm that simultaneously enables graph isomorphism testing, community detection, classification, retrieval, and edge-importance ranking.

Key properties¶

The equation at a glance¶

For each edge \((u, v)\) in the graph, the fixed-point equation is:

The corresponding discrete-time iteration is:

where \(\|u\|^{(t)} = \sqrt{\displaystyle\sum_{x \in N[u]} \bar{w}_{ux}\, d_{ux}^{(t)}}\), \(N[u] = N(u) \cup \{u\}\) is the closed neighborhood (including a self-loop with \(\bar{w}_{uu} = 2\), \(d_{uu} = 2\)), and \(\bar{w}\) is the combined weight for the chosen variant.

See The DRESS Equation for the full derivation.

Current Experimented Applications¶

• Graph Isomorphism: sorting DRESS edge values produces a canonical fingerprint. 100 % accuracy on MiVIA and IsoBench benchmarks. Δ¹-DRESS achieves 100 % within-family separation on all 51,816 graphs across 34 hard benchmark families (16 SRG families, 18 constructed families), resolving over 576 million non-isomorphic pairs. See paper.
• Community Detection: DRESS values classify edges as intra- or inter-community, improving SCAN and enabling agglomerative hierarchical clustering.
• Classification: percentile-based DRESS fingerprints fed to standard classifiers match or exceed Weisfeiler-Leman baselines on TU benchmark datasets.
• Retrieval: DRESS fingerprint distances correlate strongly with graph edit distance, achieving state-of-the-art precision on GED-based retrieval benchmarks.
• GED Regression: DRESS fingerprint differences fed to a simple regressor predict graph edit distance with 15× lower MSE than TaGSim on LINUX graphs - no GNN required.
• Edge Robustness: DRESS edge values double as an O(km) edge-importance ranking that outperforms O(nm) betweenness centrality and four other baselines (65–97% win rates, p < 0.0001 across 224 graphs).

See Applications Overview for details.

Experiments¶

All benchmarks, datasets, and reproducible scripts live in a dedicated repository:

dress-experiments - isomorphism (SRG, CFI, constructed families), classification, retrieval, GED regression, and more.

Language bindings¶

DRESS is implemented in C with bindings for:

• C / C++: static and shared libraries
• Python: pybind11 (pip install dress-graph)
• Rust: dress-graph crate
• Go: CGo bindings
• Julia: native FFI module
• R: .Call interface
• MATLAB / Octave: MEX gateway
• JavaScript / WASM: browser and Node.js (CPU only)

All backends (CPU, CUDA (GPU), MPI (distributed), and MPI+CUDA) are supported across all native language bindings. An igraph C wrapper (libdress-igraph) is also available with the same CPU / CUDA / MPI / MPI+CUDA backend matrix. JavaScript / WASM is CPU-only (browser).

See Installation to get started.