Research map / Graph learning / Graph algorithms and clustering
What Makes a Good Feedforward Computational Graph?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes two metrics (averaged mixing time and normalised minimax fidelity) for feedforward computational graphs, uses FunSearch to discover a sparse, self-similar "FS graph" generator, and shows it performs well on max, second-max, and parity tasks.
Problem
Choosing a good feedforward (causal) computational graph for sequential neural networks: prior graph rewiring theory assumes undirected graphs, and fully connected or sliding-window feedforward graphs are the default despite issues like over-squashing and dispersion.
Approach
Define two complementary measures for feedforward graphs, averaged mixing time (random walk toward the sink) and minimax fidelity (how sharply each node's signal reaches the sink under averaging diffusion), derive their asymptotics for several graph families, and use FunSearch to discover a recursive, expander-based FS graph with O(polylog n) mixing time and high fidelity.
Key results
- The FS graph matches the fully connected graph on the parity task while using substantially fewer edges, and generalises best out of distribution among sparse graphs on max, second-max and parity.
- Line graphs have normalised minimax fidelity growing as sqrt(n/pi), while the fully connected graph has minimax fidelity 1/n (normalised to 1).
- Theorem: FS graph with ceil(log n) blocks per level has O(polylog n) mixing time, specifically O(log^2 n / log log n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the FS graph instead of other sparse graphs | Graph attention network · Maximum retrieval | accuracy | Helped |
| use the FS graph instead of other sparse graphs | Graph attention network · Second maximum retrieval | accuracy | Helped |
| use the FS graph instead of other sparse graphs | Graph attention network · Parity | accuracy | Helped |
| replace the fully connected graph with the FS graph | Graph attention network · Parity | accuracy | No clear effect |
| replace the FS graph with Poisson(0.8) | Graph attention network · Maximum retrieval | accuracy | No clear effect |
| use the FS graph instead of the line graph | Gemma 2B fine-tuned on Wikipedia · Wikipedia | perplexity | Helped |
| replace the fully connected graph with the FS graph | Gemma 2B fine-tuned on Wikipedia · Wikipedia | perplexity | No clear effect |
| add self-edges (ablation) | Graph models using the tested graph generators · Maximum retrieval | accuracy | Helped |
| add self-edges (ablation) | Graph models using the tested graph generators · Second maximum retrieval | accuracy | Helped |
| add self-edges (ablation) | Graph models using the tested graph generators · Parity | accuracy | Helped |
| increase expander indegree from log n to 4 log n (ablation) | FS graph · Maximum retrieval | accuracy | Helped |
| increase expander indegree from log n to 4 log n (ablation) | FS graph · Second maximum retrieval | accuracy | Helped |
Surprising findings
- The fully connected graph does not have optimal mixing time; a feedforward star graph optimises it, because extra paths act as a distraction.
- Erdős-Rényi and oriented expander graphs perform worse than the fully connected graph on both proposed metrics.
Limitations
- FS graph's in-degree is O(log n) rather than fully sparse, and self-similarity required a recursive construction; the mixing-time proof requires an assumption on cross-block edge proportion.
- Empirical evaluation uses small synthetic tasks and a single GAT-style model plus a fine-tuned Gemma 2B on Wikipedia only briefly.
- Mixing time is not nearly as controllable for Poisson graphs and no graph dominates on all metrics.
Experimental setup
Datasets: synthetic maximum retrieval synthetic second maximum retrieval synthetic parity Wikipedia
Benchmarks: maximum retrieval second maximum retrieval parity Wikipedia perplexity
Metrics: test accuracy perplexity averaged mixing time normalised minimax fidelity
Baselines: fully connected feedforward graph line graph Erdős-Rényi graphs oriented expanders Poisson(p) graphs
Builds on: FunSearch graph attention networks Gemma 2
Closest papers by meaning
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.86)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.86)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.85)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.85)
- Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning (ICLR 2025 · similarity 0.85)
- DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.