揭示图神经网络性能差异的根源,发现数据集偏差导致评估结果失真。
Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)
- 从信号处理视角推导出多种线性图神经网络的精确泛化误差。
- 发现现有数据集特征与结构高度对齐,导致模型性能评估产生偏差。
- 提出同质性是决定模型适用性的关键,适合关注模型可解释性的研究者。
图神经网络(GNN)已成为从生物到社交系统等领域的网络学习标准方法,但其为何能提取有意义表示,或为何相似模型表现差异显著,仍缺乏系统理解。泛化误差可衡量模型预测与真实值的差距,是解答上述问题的关键。尽管已有研究推导泛化误差界,但这些理论边界通常松散、仅限单一架构,难以解释实际表现。本文提出全新方法,通过信号处理视角,推导出包括卷积型、PageRank型和注意力型在内的广泛线性GNN的精确泛化误差。结果揭示:现有文献中的基准数据集存在强偏差——节点特征与图结构高度对齐,天然偏向依赖此类结构的模型。进一步表明,连通节点间的相似性(同质性)决定了何种架构最适合特定图,从而解释了文献中报告性能受基准特性系统性影响的原因。这些发现阐明了GNN在何时何地能有效利用结构与特征信息,为可靠应用提供依据。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) have become the standard method for learning from networks across fields ranging from biology to social systems, yet a principled understanding of what enables them to extract meaningful representations, or why performance varies drastically between similar models, remains elusive. These questions can be answered through the generalisation error, which measures the discrepancy between a model's predictions and the true values it is meant to recover. Although several works have derived generalisation error bounds, learning theoretical bounds are typically loose, restricted to a single architecture, and offer limited insight into what governs generalisation in practice. In this work, we take a fundamentally different approach by deriving the exact generalisation error for a broad range of linear GNNs, including convolutional, PageRank-based, and attention-based models, through the lens of signal processing. Our exact generalisation error exposes a strong benchmark bias in existing literature: commonly used datasets exhibit high alignment between node features and the graph structure, inherently favouring architectures that rely on it. We further show that the similarity between connected nodes (homophily) decisively governs which architectures are best suited for a given graph, thereby explaining how specific benchmark properties systematically shape the reported performance in the literature. Together, these results explain when and why GNNs can effectively leverage structure and feature information, supporting the reliable application of GNNs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。