In contextual stochastic block models, graph attention improves node classification when structure noise dominates feature noise, but plain convolution is better in the opposite regime, and multi-layer attention achieves perfect classification with SNR as low as ω(√log n/n^{1/3}).
Almost Surely Asymptotically Constant Graph Neural Networks
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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\H{o}s-R\'enyi model, the stochastic block model, and the Barab\'asi-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.
fields
cs.LG 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models
In contextual stochastic block models, graph attention improves node classification when structure noise dominates feature noise, but plain convolution is better in the opposite regime, and multi-layer attention achieves perfect classification with SNR as low as ω(√log n/n^{1/3}).