mlsanityData to 7 Oct 2026

What makes a good feedforward computational graph?

arXiv 2502.06751 ↗First posted 10 Feb 2025cs.LG cs.AI cs.SIcited by 5

Not on the map. Why?

Abstract (arXiv)

As implied by the plethora of literature on graph rewiring, the choice of computational graph employed by a neural network can make a significant impact on its downstream performance. Certain effects related to the computational graph, such as under-reaching and over-squashing, may even render the model incapable of learning certain functions. Most of these effects have only been thoroughly studied in the domain of undirected graphs; however, recent years have seen a significant rise in interest in feedforward computational graphs: directed graphs without any back edges. In this paper, we study the desirable properties of a feedforward computational graph, discovering two important complementary measures: fidelity and mixing time, and evaluating a few popular choices of graphs through the lens of these measures. Our study is backed by both theoretical analyses of the metrics' asymptotic behaviour for various graphs, as well as correlating these metrics to the performance of trained neural network models using the corresponding graphs.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 35 of its 49 references that are in the map. First posted on arXiv 10 Feb 2025.

Builds on

35 of 49 references.

References · 35

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2017Graph Attention Networkscited by 8,854
  3. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  4. 2016WaveNet: A Generative Model for Raw Audiocited by 1,710
  5. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  6. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  7. 2018Adafactor: Adaptive Learning Rates with Sublinear Memory Costcited by 896
  8. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  9. 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 521
  10. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  11. 2019Diffusion Improves Graph Learningcited by 414
  12. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
23 more
  1. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
  2. 2023Exphormer: Sparse Transformers for Graphscited by 166
  3. 2023Temporal Graph Benchmark for Machine Learning on Temporal Graphscited by 137
  4. 2022Graph-Coupled Oscillator Networkscited by 123
  5. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  6. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  7. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  8. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  9. 2022Expander Graph Propagationcited by 75
  10. 2021Directed Acyclic Graph Neural Networkscited by 70
  11. 2022Understanding convolution on graphs via energiescited by 58
  12. 2023Graph Metanetworks for Processing Diverse Neural Architecturescited by 55
  13. 2023How does over-squashing affect the power of GNNs?cited by 53
  14. 2024Transformers Provably Solve Parity Efficiently with Chain of Thoughtcited by 49
  15. 2023A Fractional Graph Laplacian Approach to Oversmoothingcited by 45
  16. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  17. 2024Cayley Graph Propagationcited by 21
  18. 2020LaProp: Separating Momentum and Adaptivity in Adamcited by 16
  19. 2022Learnable Commutative Monoids for Graph Neural Networkscited by 13
  20. 2023Half-Hop: A graph upsampling approach for slowing down message passingcited by 13
  21. 2024Even Sparser Graph Transformerscited by 12
  22. 2023Higher-Order Expander Graph Propagationcited by 4
  23. 2024Commute-Time-Optimised Graphs for GNNscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 1.

5 papers.

  1. 2025Why do LLMs attend to the first token?cited by 122
  2. 2026Perplexity Cannot Always Tell Right from Wrongcited by 8
  3. 2025Neural Message-Passing on Attention Graphs for Hallucination Detectioncited by 5
  4. 2025Beyond Parallelism: Synergistic Computational Graph Effects in Multi-Head Attentioncited by 1
  5. 2025Caterpillar GNN: Replacing Message Passing with Efficient Aggregationcited by 0