提出PRiSM算法，实现简单谱图的完全规范表示。
Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
- 设计PRiSM框架，基于分治与精炼策略完成简单谱图规范
- 证明所有k-WL无法区分所有简单谱非同构图，而PRiSM可做到完全区分
- 适合需要完全表达能力的图学习任务，如图分类与回归
具有简单谱的图可在三次时间内进行同构测试，但我们证明：对任意自然数k，k-Weisfeiler-Leman（k-WL）测试无法区分所有非同构的简单谱图。由于WL层级上界了广泛使用的图神经网络（GNNs）的区分能力，这一不完备性适用于所有此类GNN。为弥补此缺口，我们提出PRiSM（Partition, Refine, Solve, Match），首个在简单谱特征分解上可证明完全性的规范方法。PRiSM获得了先前规范方法无法保证的完备性，解决了在简单谱图上实现完全表达力的开放问题。当与DeepSets或Transformer结合时，PRiSM在简单谱图上实现了通用逼近，验证了规范化拉普拉斯位置编码的有效性。实验表明，PRiSM在图回归、分类及表达力方面表现媲美或优于现有谱规范方法。
原文摘要 · Abstract (English)
Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every $k$-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。