mlsanityData to 14 Oct 2026

Effects of Graph Convolutions in Multi-layer Networks

arXiv 2204.09297 ↗First posted 20 Apr 2022cs.LG stat.MLcited by 24

Not on the map. Why?

Abstract (arXiv)

Graph Convolutional Networks (GCNs) are one of the most popular architectures that are used to solve classification problems accompanied by graphical information. We present a rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We study these effects through the node classification problem of a non-linearly separable Gaussian mixture model coupled with a stochastic block model. First, we show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data by a factor of at least 1/√[4]mathbbErm deg, where mathbbErm deg denotes the expected degree of a node. Second, we show that with a slightly stronger graph density, two graph convolutions improve this factor to at least 1/√[4]n, where n is the number of nodes in the graph. Finally, we provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a network, concluding that the performance is mutually similar for all combinations of the placement. We present extensive experiments on both synthetic and real-world data that illustrate our results.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). Builds on 34 of its 62 references that are in the map. First posted on arXiv 20 Apr 2022.

Builds on

34 of 62 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  8. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  9. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  10. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  11. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  12. 2017Community Detection and Stochastic Block Modelscited by 319
22 more
  1. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  2. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  3. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  4. 2021Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Predictioncited by 138
  5. 2018Contextual Stochastic Block Modelscited by 134
  6. 2021Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?cited by 82
  7. 2014Exact Recovery in the Stochastic Block Modelcited by 78
  8. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  9. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  10. 2014Community Detection in Networks with Node Attributescited by 44
  11. 2019Stochastic Blockmodels meet Graph Neural Networkscited by 39
  12. 2013A Proof Of The Block Model Threshold Conjecturecited by 36
  13. 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
  14. 2014Covariate-assisted spectral clusteringcited by 29
  15. 2015Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphscited by 26
  16. 2014Consistency Thresholds for the Planted Bisection Modelcited by 24
  17. 2022Graph Attention Retrospectivecited by 24
  18. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  19. 2017The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardnesscited by 20
  20. 2016Information-theoretic thresholds for community detection in sparse networkscited by 17
  21. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
  22. 2016Block Models and Personalized PageRankcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 9; 2024: 7; 2025: 1; 2026: 3.

24 papers.

Sort:

By area:

  1. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  2. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  3. 2024Understanding Heterophily for Graph Neural Networkscited by 15
  4. 2022Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graphcited by 14
  5. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  6. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 12
  7. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  8. 2024Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learningcited by 12
  9. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  10. 2023Non-backtracking Graph Neural Networkscited by 7
  11. 2026Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guaranteescited by 7
  12. 2025Cooperation of Experts: Fusing Heterogeneous Information with Large Margincited by 6
12 more
  1. 2022A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphscited by 5
  2. 2022Tackling Provably Hard Representative Selection via Graph Neural Networkscited by 2
  3. 2023Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Modelscited by 2
  4. 2023A Local Graph Limits Perspective on Sampling-Based GNNscited by 2
  5. 2024Analysis of Corrected Graph Convolutionscited by 2
  6. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2
  7. 2024Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variantscited by 1
  8. 2023On the Equivalence of Graph Convolution and Mixupcited by 0
  9. 2023Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNScited by 0
  10. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  11. 2026A Spectral Theory of Normalized Corrected GNN Propagationcited by 0
  12. 2026The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomycited by 0