Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.20833 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917332625915904 |
|---|---|
| author | Velilla, Eduar Castrillo |
| author_facet | Velilla, Eduar Castrillo |
| contents | 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 $\mathcal{O}(I \cdot m \cdot d_{\max})$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20833 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | DRESS: A Continuous Framework for Structural Graph Refinement Velilla, Eduar Castrillo Data Structures and Algorithms Machine Learning 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 $\mathcal{O}(I \cdot m \cdot d_{\max})$ 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. |
| title | DRESS: A Continuous Framework for Structural Graph Refinement |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2602.20833 |