# What makes a good feedforward computational graph?

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

## Key facts

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

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Adafactor: Adaptive Learning Rates with Sublinear Memory Cost](https://mlsanity.com/paper/1804.04235/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [Graph-Coupled Oscillator Networks](https://mlsanity.com/paper/2202.02296/) (2022)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Expander Graph Propagation](https://mlsanity.com/paper/2210.02997/) (2022)
- [Directed Acyclic Graph Neural Networks](https://mlsanity.com/paper/2101.07965/) (2021)
- [Understanding convolution on graphs via energies](https://mlsanity.com/paper/2206.10991/) (2022)
- [Graph Metanetworks for Processing Diverse Neural Architectures](https://mlsanity.com/paper/2312.04501/) (2023)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Transformers Provably Solve Parity Efficiently with Chain of Thought](https://mlsanity.com/paper/2410.08633/) (2024)
- [A Fractional Graph Laplacian Approach to Oversmoothing](https://mlsanity.com/paper/2305.13084/) (2023)
- [Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature](https://mlsanity.com/paper/2309.09384/) (2023)
- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [LaProp: Separating Momentum and Adaptivity in Adam](https://mlsanity.com/paper/2002.04839/) (2020)

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

- [Why do LLMs attend to the first token?](https://mlsanity.com/paper/2504.02732/) (2025)
- [Perplexity Cannot Always Tell Right from Wrong](https://mlsanity.com/paper/2601.22950/) (2026)
- [Neural Message-Passing on Attention Graphs for Hallucination Detection](https://mlsanity.com/paper/2509.24770/) (2025)
- [Beyond Parallelism: Synergistic Computational Graph Effects in Multi-Head Attention](https://mlsanity.com/paper/2507.02944/) (2025)
- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)

## 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.