提出新方法生成带节点特征相关性的随机图，发现GNN在真实图上可能更强大
Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlations
- 设计新采样方案使邻近节点特征相关，模拟真实网络
- 理论与实验表明部分情况下GNN能避免收敛，出现发散行为
- 为理解GNN在真实图上的表达能力提供新视角，适合图学习研究者
现有研究多在大型随机图上分析图神经网络（GNN）的收敛行为，但多数未考虑节点特征间的相关性——这在真实网络中普遍存在。由此得出的GNN局限性并不能真实反映其在现实图上的表达能力。本文提出一种新方法，生成具有邻近节点特征相关性的随机图：通过特定采样策略确保相邻节点特征相关，其设计基于真实网络特性，尤其是Barabási-Albert模型所体现的性质。理论分析强烈表明，在某些情况下可避免收敛；我们通过大规模随机图实证了这一发散行为。结果表明，GNN在真实图上可能比早期研究认为的更具表达力。
原文摘要 · Abstract (English)
There are a number of existing studies analysing the convergence behaviour of graph neural networks on large random graphs. Unfortunately, the majority of these studies do not model correlations between node features, which would naturally exist in a variety of real-life networks. Consequently, the derived limitations of GNNs, resulting from such convergence behaviour, is not truly reflective of the expressive power of GNNs when applied to realistic graphs. In this paper, we will introduce a novel method to generate random graphs that have correlated node features. The node features will be sampled in such a manner to ensure correlation between neighbouring nodes. As motivation for our choice of sampling scheme, we will appeal to properties exhibited by real-life graphs, particularly properties that are captured by the Barabási-Albert model. A theoretical analysis will strongly indicate that convergence can be avoided in some cases, which we will empirically validate on large random graphs generated using our novel method. The observed divergent behaviour provides evidence that GNNs may be more expressive than initial studies would suggest, especially on realistic graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。