[2603.00044] Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study

Computer Science > Machine Learning arXiv:2603.00044 (cs) [Submitted on 9 Feb 2026] Title:Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study Authors:Sicong Che, Jiayi Yang, Sarfraz Khurshid, Wenxi Wang View a PDF of the paper titled Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study, by Sicong Che and 3 other authors View PDF HTML (experimental) Abstract: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 expressivenes...