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

GNNs struggle with fundamental graph properties: The study found that Graph Neural Networks have difficulty reliably capturing basic structural properties of graphs—a critical gap for applications in distributed systems, knowledge graphs, and biological networks where understanding these properties is essential for trustworthy predictions.

Different pooling methods create trade-offs in reliability: The research identified that attention-based pooling methods are better at generalizing to new data and resisting adversarial changes, while second-order pooling methods are more sensitive to detecting specific graph properties, meaning organizations must choose which type of reliability matters most for their use case.

Systematic testing frameworks are necessary for AI evaluation: By creating 336 new datasets with over 10,000 labeled graphs each, the authors demonstrated that rigorous, property-based testing—similar to software engineering practices—is essential for understanding what AI models can and cannot do reliably before deployment.

No single GNN approach works universally: The finding that "no single approach consistently performs well across all properties" highlights an important reality for responsible AI: organizations cannot assume one model architecture will be trustworthy for all applications and must validate performance for their specific use case.

Formal specification improves AI accountability: Using Alloy, a formal specification language, to define and test graph properties provides a more rigorous, auditable approach to evaluating AI systems—supporting the transparency and documentation needed for responsible AI deployment.