构建可扩展的图神经网络表达能力评估体系,揭示不同池化方法的优劣。
Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study
- 基于形式化规范设计可配置图数据生成器,支持属性验证与结构扰动。
- 覆盖16种关键图属性的336个数据集,每集含超万张标签图,首次系统评估全局池化影响。
- 发现注意力池化在泛化与鲁棒性上更优,二阶池化敏感度更高,无单一方法通吃所有场景。
可信人工智能的发展需要有原则的软件工程方法来评估模型。图神经网络(GNN)在处理图结构数据方面取得显著成功,但其对基本图属性的表达能力仍面临挑战。为此,我们提出一种基于形式化规范的属性驱动评估方法,涵盖系统性评估与实证研究。利用Alloy(一种软件规范语言与分析工具),我们设计了一个可配置的图数据生成器,生成两类数据集:GraphRandom(包含满足或违反特定属性的多样化图)和GraphPerturb(引入可控结构变异)。这些基准涵盖336个新数据集,每个至少包含10,000张带标签图,覆盖分布式系统、知识图谱与生物网络中至关重要的16种基础图属性。我们提出一个通用评估框架,用于衡量GNN表达力的三个核心维度:泛化性、敏感性与鲁棒性,并引入两项新量化指标。基于该框架,我们首次全面研究全局池化方法对GNN表达力的影响。结果揭示显著权衡:注意力池化在泛化性和鲁棒性上表现优异,而二阶池化具有更强敏感性,但无一种方法在所有属性上始终领先。这些发现揭示了根本性局限,并指明了自适应属性感知池化、尺度敏感架构与鲁棒训练等开放研究方向。通过将软件工程严谨性嵌入AI评估,本工作为开发更具表达力与可靠性的一流GNN架构奠定了坚实基础。
原文摘要 · Abstract (English)
Advancing trustworthy AI requires principled software engineering approaches to model evaluation. Graph Neural Networks (GNNs) have achieved remarkable success in processing graph-structured data, however, their expressiveness in capturing fundamental graph properties remains an open challenge. We address this by developing a property-driven evaluation methodology grounded in formal specification, systematic evaluation, and empirical study. Leveraging Alloy, a software specification language and analyzer, we introduce a configurable graph dataset generator that produces two dataset families: GraphRandom, containing diverse graphs that either satisfy or violate specific properties, and GraphPerturb, introducing controlled structural variations. Together, these benchmarks encompass 336 new datasets, each with at least 10,000 labeled graphs, covering 16 fundamental graph properties critical to distributed systems, knowledge graphs, and biological networks. We propose a general evaluation framework that assesses three key aspects of GNN expressiveness: generalizability, sensitivity, and robustness, with two novel quantitative metrics. Using this framework, we conduct the first comprehensive study on global pooling methods' impact on GNN expressiveness. Our findings reveal distinct trade-offs: attention-based pooling excels in generalization and robustness, while second-order pooling provides superior sensitivity, but no single approach consistently performs well across all properties. These insights highlight fundamental limitations and open research directions including adaptive property-aware pooling, scale-sensitive architectures, and robustness-oriented training. By embedding software engineering rigor into AI evaluation, this work establishes a principled foundation for developing expressive and reliable GNN architectures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。