# On Classification Thresholds for Graph Attention with Edge Features

arXiv: https://arxiv.org/abs/2210.10014 · HTML: https://mlsanity.com/paper/2210.10014/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 41 references that are in the map.
- First posted on arXiv 18 Oct 2022.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)

## Built on by (most cited first, 5 of 5)

- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding](https://mlsanity.com/paper/2305.14814/) (2023)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Neural-prior stochastic block model](https://mlsanity.com/paper/2303.09995/) (2023)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)

## Abstract (arXiv)

The recent years we have seen the rise of graph neural networks for prediction tasks on graphs. One of the dominant architectures is graph attention due to its ability to make predictions using weighted edge features and not only node features. In this paper we analyze, theoretically and empirically, graph attention networks and their ability of correctly labelling nodes in a classic classification task. More specifically, we study the performance of graph attention on the classic contextual stochastic block model (CSBM). In CSBM the nodes and edge features are obtained from a mixture of Gaussians and the edges from a stochastic block model. We consider a general graph attention mechanism that takes random edge features as input to determine the attention coefficients. We study two cases, in the first one, when the edge features are noisy, we prove that the majority of the attention coefficients are up to a constant uniform. This allows us to prove that graph attention with edge features is not better than simple graph convolution for achieving perfect node classification. Second, we prove that when the edge features are clean graph attention can distinguish intra- from inter-edges and this makes graph attention better than classic graph convolution.