提出首个全双利普希茨的图神经网络，解决传统模型难以区分相似图的问题。
FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network
- 设计全双利普希茨结构，确保图表示在距离度量下严格可区分
- 在长程任务中显著优于标准MPNN，避免过度平滑与压缩
- 适合需要高精度图区分的场景，如分子结构分析
众所周知，消息传递神经网络（MPNN）的图区分能力受限于魏斯费勒-莱曼（WL）同构测试，最强的MPNN在分离能力上与WL等价。然而，已有研究发现，标准的WL等价MPNN提供的分离质量可能很低，导致能被WL区分的图映射到几乎无法区分的输出。这一现象可归因于标准MPNN并非下利普希茨。本文提出FSW-GNN，首个在标准WL等价图度量下完全双利普希茨的MPNN。实验表明，该模型在多个图学习任务中表现与标准MPNN相当，但在长程任务中显著更优，因其能有效避免过度平滑与过度压缩。代码已开源。
原文摘要 · Abstract (English)
Famously, the ability of Message Passing Neural Networks (MPNN) to distinguish between graphs is limited to graphs separable by the Weisfeiler-Lemann (WL) graph isomorphism test, and the strongest MPNNs, in terms of separation power, are WL-equivalent. However, it was demonstrated that the quality of separation provided by standard WL-equivalent MPNN can be very low, resulting in WL-separable graphs being mapped to very similar, hardly distinguishable outputs. This phenomenon can be explained by the recent observation that standard MPNNs are not lower-Lipschitz. This paper addresses this issue by introducing FSW-GNN, the first MPNN that is fully bi-Lipschitz with respect to standard WL-equivalent graph metrics. Empirically, we show that our MPNN is competitive with standard MPNNs for several graph learning tasks and is far more accurate in long-range tasks, due to its ability to avoid oversmoothing and oversquashing. Our code is available at https://github.com/yonatansverdlov/Over-squashing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。