arXiv:2603.18582cs.DScs.DM2026-03

用确定性方法解决图同构难题,指纹唯一性超99%。

Breaking Hard Isomorphism Benchmarks with DRESS

  • 基于顶点删除的动态系统迭代生成唯一图指纹
  • 在5万+图上实现33类中32类无碰撞,仅1对例外
  • 突破3阶沃尔夫逻辑界限,适合图结构分析研究者

DRESS 是一种确定性、无参数的图结构精炼框架,通过迭代优化边的结构相似性,将图转化为一个实值边向量(即规范指纹),该指纹是某个非线性动力系统收敛到唯一不动点的结果。Δ-DRESS 是 DRESS 家族中采用单层顶点删除的方法。我们在包含 51,813 个不同图的 34 个困难图族基准上测试该方法,涵盖完整斯彭斯强正则图集合(43,703 个 SRG,12 个家族)、4 个额外的 SRG 家族(8,015 个图)以及 18 种经典难构造(102 个家族条目对应 99 个不同图)。Δ-DRESS 在 k=1 删除深度下,在 33/34 个家族中产生唯一指纹,解决了超过 5.76 亿对非同构图中的绝大多数族内碰撞问题。仅在一个族内存在真实碰撞:两个顶点传递的强正则图在 SRG(40,12,2,4) 中,可通过一步退回到 Δ²-DRESS 解决。对于所有具有可比较全排序多重集指纹的家族,最小观测分离间距不低于 137×ε,表明结果数值稳健,非收敛阈值伪影。此外,Δ-DRESS 成功区分了棋盘图 L₂(4) 与希里坎德图,证明其突破了 3-维沃尔夫逻辑理论边界。该方法每图时间复杂度为 𝒪(n·I·m·d_max)。

原文摘要 · Abstract (English)

DRESS is a deterministic, parameter-free framework for structural graph refinement 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 nonlinear dynamical system to its unique fixed point. $Δ$-DRESS is a member of the DRESS family of graph fingerprints that applies a single level of vertex deletion. We test it on a benchmark of 51,813 distinct graphs across 34 hard families, including the complete Spence collection of strongly regular graphs (43,703 SRGs, 12 families), four additional SRG families (8,015 graphs), and 18 classical hard constructions (102 family entries corresponding to 99 distinct graphs). $Δ$-DRESS produces unique fingerprints in 33 of 34 benchmark families at $k=1$, resolving all but one within-family collision among over 576 million non-isomorphic pairs. One genuine collision exists at deletion depth $k=1$, between two vertex-transitive SRGs in SRG(40,12,2,4), which is resolved by a single-step fallback to $Δ^2$-DRESS. For every family with pairwise-comparable full sorted-multiset fingerprints, the minimum observed separation margin remains at least $137 \times ε$, confirming that the reported separations are numerically robust and not artifacts of the convergence threshold. We also show that $Δ$-DRESS separates the Rook $L_2(4)$/Shrikhande pair, proving it escapes the theoretical boundary of 3-WL. The method runs in $\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ time per graph.

图同构指纹生成强正则图算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。