mlsanityData to 14 Oct 2026

On Classification Thresholds for Graph Attention with Edge Features

arXiv 2210.10014 ↗First posted 18 Oct 2022cs.LG cs.AIcited by 5

Not on the map. Why?

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.

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

27 of 41 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  9. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  10. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  11. 2021How Attentive are Graph Attention Networks?cited by 835
  12. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
15 more
  1. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  2. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  3. 2017Community Detection and Stochastic Block Modelscited by 319
  4. 2015Diffusion-Convolutional Neural Networkscited by 268
  5. 2015Deep Convolutional Networks on Graph-Structured Datacited by 246
  6. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  7. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  8. 2019Understanding Attention and Generalization in Graph Neural Networkscited by 169
  9. 2018Contextual Stochastic Block Modelscited by 134
  10. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  11. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  12. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  13. 2014Covariate-assisted spectral clusteringcited by 29
  14. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  15. 2022Graph Attention Retrospectivecited by 24

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 1.

5 papers.

  1. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  2. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 12
  3. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 12
  4. 2023Neural-prior stochastic block modelcited by 4
  5. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0