Almost Surely Asymptotically Constant Graph Neural Networks

2024/03/06 by Sam Adam-Day, Michael Benedikt, Adam-Day, Sam +5 · 3 citations
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Machine Learning (cs.LG) #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2403.03880

openalex publication_date 2024/03/06 · openalex created_date 2024/03/08 · openalex updated_date 2026/07/28

Abstract

We present a new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of real-valued GNN classifiers, such as those classifying graphs probabilistically, evolve as we apply them on larger graphs drawn from some random graph model. We show that the output converges to a constant function, which upper-bounds what these classifiers can uniformly express. This strong convergence phenomenon applies to a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. Our results apply to a broad class of random graph models, including sparse and dense variants of the Erdős-Rényi model, the stochastic block model, and the Barabási-Albert model. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.

Cited by

• Sound Logical Explanations for Mean Aggregation Graph Neural Networks
• On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
• Domain size asymptotics for Markov logic networks

Related

• On the Universality of Graph Neural Networks on Large Random Graphs
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
• Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
• Random Features Strengthen Graph Neural Networks