DRESS通过迭代优化图边结构，生成稳定且唯一的图指纹，可高效区分复杂图结构。
DRESS: A Continuous Framework for Structural Graph Refinement
- 基于非线性动力系统迭代收敛，生成不受同构影响的实值边向量指纹
- 在7983个强正则图上实现完全区分，且$\Delta^k$-DRESS逼近$(k+2)$-WL判别能力
- 无需参数、计算并行度高，适合大规模图结构分析与对比
我们提出DRESS，一种确定性、无参数的连续图结构精炼框架，通过迭代优化图中边的结构相似性，生成一个标准指纹：由非线性动力系统收敛至唯一不动点得到的实值边向量。该指纹在构造上具有同构不变性，数值稳定（严格有界、精度保持、数学良定），计算快速且可极度并行化：总运行时间为$\mathcal{O}(I \cdot m \cdot d_{\max})$，其中$I$为收敛迭代次数，收敛性由Birkhoff压缩保证。我们进一步将原方程推广至Motif-DRESS（任意结构模式）和Generalized-DRESS（抽象聚合模板），并引入$\Delta$-DRESS，对每个顶点删除子图运行DRESS以增强表达能力。$\Delta$-DRESS在涵盖7,983个图的强正则图基准上实现完全区分，在测试的CFI实例（$k = 0,1,2,3$）中，$k$-删除版本（$\Delta^k$-DRESS）经验上达到$(k{+}2)$-WL边界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。