.png){kind=icon}
返回
Representing Tuple in Graph with Trail Structure
.png){kind=icon}
PRE
AI
DOI：10.1145/3795689.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
近年来，消息传递神经网络（MPNNs）因其简单的架构和出色的可扩展性，已成为学习图结构数据的主流范式。然而，其表达能力严格受限于一维Weisfeiler-Leman（1-WL）测试。增强表达能力的一种常见方法是设计基于高阶k-WL和k-Folklore WL（k-FWL）测试的模型，统称为基于元组的GNNs。尽管这些方法具有更强的表达能力，但它们面临两大挑战：（1）k-WL/FWL中的邻近元组是通过替换图中的任意节点生成的，忽略了邻接关系，从而无法捕捉元组之间的结构依赖；（2）k-WL/FWL的设计缺乏灵活性，虽然增加k能提升表达能力，但也导致时间和空间复杂度呈指数级激增。为克服这些限制，我们提出了Trail-WL，即WL测试的一个更具表达力的变体，以及其神经网络对应模型——基于Trail的元组神经网络（TTNN）。我们将节点元组重新定义为Trail结构的集合，相比先前的基于元组的方法，提供了更直观的图连通性表示。通过引入可变Trail长度和节点距离约束，我们的模型在保持关键结构特征的同时，自适应地平衡了表达力和可扩展性。此外，我们提出了并严格证明了Trail-WL的三个理论表达能力定理。最后，我们在合成数据集和真实数据集上进行了全面实验，表明我们的方法始终能达到或超越基线方法，从而验证了其有效性。
Keyword:
Graph Neural Networks
Graph Representation Learning
Expressive Power of GNNs
期刊
IF:
4.8
论文数:
1.3K
被引数:
4.4K
机构
引用论文
.png){kind=icon}
没有更多内容
没有更多内容