Search papers, labs, and topics across Lattice.
This paper introduces DRESS, a family of continuous dynamical systems for structural graph refinement, starting from the Original-DRESS equation and generalizing it to Motif-DRESS and Generalized-DRESS. The authors demonstrate that DRESS distinguishes the prism graph from K_{3,3}, a limitation of 1-WL, and further introduce Delta-DRESS, connecting the framework to the Kelly-Ulam reconstruction conjecture. Empirically, Motif-DRESS and Delta-DRESS outperform both 1-WL and 3-WL on Strongly Regular Graphs, offering a scalable alternative to computationally expensive higher-order WL tests.
Forget cubic scaling: DRESS offers a surprisingly scalable way to beat 3-WL at distinguishing notoriously difficult graph structures.
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 Shrikhande graphs--that confound 3-WL. Our results establish the DRESS family as a highly scalable framework that empirically surpasses both 1-WL and 3-WL on well-known benchmark graphs, without the prohibitive O(n^4) computational cost.
