![[2602.20833] DRESS: A Continuous Framework for Structural Graph Refinement](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.20833] DRESS: A Continuous Framework for Structural Graph Refinement
Summary
The paper presents DRESS, a scalable framework for structural graph refinement that outperforms traditional methods in distinguishing complex graph structures without high computational costs.
Why It Matters
This research addresses the limitations of existing graph isomorphism testing frameworks, particularly the Weisfeiler-Lehman hierarchy, by introducing a more efficient method for analyzing large graphs. The implications are significant for fields relying on graph theory, such as network analysis and machine learning.
Key Takeaways
- DRESS framework offers a continuous approach to graph refinement.
- It effectively distinguishes complex graph structures that traditional methods cannot.
- The framework scales efficiently, avoiding high computational costs associated with tensor operations.
- Motif-DRESS and Delta-DRESS enhance the framework's applicability to various graph types.
- Empirical results show DRESS surpasses 1-WL and 3-WL benchmarks.
Computer Science > Data Structures and Algorithms arXiv:2602.20833 (cs) [Submitted on 24 Feb 2026] Title:DRESS: A Continuous Framework for Structural Graph Refinement Authors:Eduar Castrillo Velilla View a PDF of the paper titled DRESS: A Continuous Framework for Structural Graph Refinement, by Eduar Castrillo Velilla View PDF HTML (experimental) Abstract:The Weisfeiler-Lehman (WL) hierarchy is a cornerstone framework for graph isomorphism testing and structural analysis. However, scaling beyond 1-WL to 3-WL and higher requires tensor-based operations that scale as O(n^3) or O(n^4), making them computationally prohibitive for large graphs. In this paper, we start from the Original-DRESS equation (Castrillo, Leon, and Gomez, 2018)--a parameter-free, continuous dynamical system on edges--and show that it distinguishes the prism graph from K_{3,3}, a pair that 1-WL provably cannot separate. We then generalize it to Motif-DRESS, which replaces triangle neighborhoods with arbitrary structural motifs and converges to a unique fixed point under three sufficient conditions, and further to Generalized-DRESS, an abstract template parameterized by the choice of neighborhood operator, aggregation function and norm. Finally, we introduce Delta-DRESS, which runs DRESS on each node-deleted subgraph G\{v}, connecting the framework to the Kelly-Ulam reconstruction conjecture. Both Motif-DRESS and Delta-DRESS empirically distinguish Strongly Regular Graphs (SRGs)--such as the Rook and Shrik...
