What Makes a Good Feedforward Computational Graph?
Authors: Alex Vitvitskyi
João Guilherme Madeira Araújo
Marc Lackenby
Petar Veličković
Venue: ICML 2025 poster (2025)
Keywords: graphs
graph neural networks
random walks
mixing time
Primary area: deep_learning->graph_neural_networks
TL;DR: We study the desirable traits for a feedforward computational graph used by a neural network, finding fidelity and mixing time to be important complementary metrics to optimise.

Abstract: 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.

What Makes a Good Feedforward Computational Graph?
Alex Vitvitskyi
João G.M. Araújo' Mare Lackenby² 2 Petar Veličkovié
Abstract
What makes good feedforward computational graph?
As implied by the plethora of literature on graph rewiring, the choice of computational graph em- ployed by a neural network can make a significant impact on its downstream performance. Certain effects related 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 signifi- cant rise interest in feedforward computational graphs: directed graphs without any back edges. In this paper, we study the desirable properties of 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 mea- sures. Our study is backed by both theoretical analyses of the metrics' asymptotic behaviour for various graphs, as well as correlating these met- rics to the performance of trained neural network models using the corresponding graphs.
Normalised iisde minimax fidelity
Erdös-Rényí
Fully connected
Poiss
FS
Expander
10
20
Mixing time
Figure I. In this paper, we propose two measures which can be used assess suitability of feedforward computational graphs for neural networks mixing time (lower is better, Sec. 4) and (normalised) minimax fidelity (higher is better; See. 5). Here we plot these metrics as attained by various graph generators at each point in sequence, the number of nodes doubles. starting from 16. Using FunSearch
Coomera-Paredes et al., 2023), we discover FS graphs, which have favourable (polylog n)) mixing time, while retaining higher fidelity compared to fully connected graph (Sec. 6). Several of these graphs may be viewed Appendix D.
models scalably and without leaking ground-truth data about the future input parts that need to be predicted. As such, many modern architectures resort to feedforward computa- tional graphs, wherein information may only flow from older samples towards newer ones never in reverse! Applying such graph - also known as a "causal mask" (Srambical, 2024) allows for scalable training over entire chunks of the input at the same time.
1. Introduction
Modern deep learning workloads frequently necessitate pro- cessing of sequential inputs, such as words in a sentence (Sutskever et al., 2014), samples of an audio recording (Van Den Oord al., 2016). partially ordered nodes in graph (Thost& & Chen, 2021), execution steps of algo- rithm (Veličković et al., 2022), snapshots of edits made to temporal graphs (Rossi et al., 2020). In addition, many important self-supervised learning tasks require efficiently predicting future evolution of such inputs, with examples ranging from temporal link prediction (Huang et al., 2024) to next token prediction (Radford al., 2018).
This naturally invites the question: what makes good feedforward computational graph? Alternatey worded, which considerations need to be taken into account when deciding which feedforward graph to use (see Figure 1)?
Here we propose two suitable and complementary ways to measure suitability of feedforward graphs: mixing time- the speed which input data converges towards stationary distribution-aa and minimax fidelity sharpness of the data is as it propagates through the graph. We supplement our measures with thorough theoretical derivations across several graph generators, and correlate them to empirical performance, paving the way to future studies in the area.
In regimes like this, it is important be able to train such
'Google DeepMind ' University Oxford. Correspondence to: Alex Vitvitskyi <avlife corlife@@googl..com google.com>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

What Makes a Good Feedforward Computational Graph?
Note that by "feedforward" we imply a statement about our input data-not the neural network processing it! That is, the assumption that our input nodes have a sequential ordering to them which must be respected when processing them-see Section 3. We therefore do not design our frame- work with more general feedforward neural networks (such as MLPs) in mind ninnerrowveer we believe some of the ideas explored here could be used to study propagation in such unrestricted networks well.
feedforward graph. In terms of practical usage, most of the heavy lifting is done either by fully connected feed- forward graphs or locally-connected Sliding-window graphs. And while recent work has identified limitations of high- indegree feedforward graphs through over-squashing (Bar- bero et al., 2024) and dispersion (Veličković et al., 2024), most such works do not actively offer a different computa- tional graph structure, nor do they offer any principles that can be used to derive one. We seek to fill this gap.
What's in a good metric? Both of the above papers make it clear-at at least if size generalisation is a desirable property- that it is beneficial to limit the in-degree of each node in the feedforward graph.
2. Motivation
We were inspired to seek an answer to this question, given that there is already a rich, extensive body of work on study- ing undirected computational graphs (commonly referred to as graph rewiring). Therein, important issues such as over- smoothing (Li et al., 2018: Oono & Suzuki, 2019; Keriven, 2022), oversquashing (Alon & Yahav, 2021; Di Giovanni et al., 2024) and under-reaching (Barceló et al., 2020) have all been identified, and related to the input graph topology. In response, a substantial amount of methods have been proposed to modify the provided input graph for improved diffusion (Gasteiger et al., 2019), curvature (Topping al., 2022; Fesser & Weber, 2024), effective resistance (Arnaiz- Rodríguez et al., 2022), or reducing smoothing (Azabou et al., 2023) and commute time (Sterner et al., 2024). While efforts were made to generalise these techniques to directed graphs (Maskey et al., 2023), as well as for sparsifying attention-based architectures (Zaheer et al., 2020; Liao & Póczos, 2024), in all previous cases they focussed on graphs where backwards edges are explicitly allowed.
A good metric should be able to help us, in the very least, compare against different graph distributions with same asymptotic in-degree budget.
It might also be helpful if the metric would be able to hint to practitioners at what point the in-degree budgets become cobblmmttic-secifiicllyy this means they shouldn't be optimised for the fully connected graph. This is not strictly necessary, as the papers above already provide ample proof.
3. Theoretical Foundations
In this work, we study feedforward graphs, 9 = E), i.e., graphs where nodes are given by an ordered set of n integers (V = Znd) and edges are constrained to only go forwards; that is, ba. E E = a as b. We will denote by T E V the sink vertex of that graph (T which is used to drive decision-making and which is not allowed to have any outward edges (except to itself).
1), node
Eventually, the focus of study expanded beyond "how to modify an input graph to be better?" towards "what makes a good input graph?", propelling the discovery of task- agnostic graphs that are guaranteed to have good topological properties. This question is well-studied in mathematics, where had led to the advent of expander graphs (Kowalski, 2019); graphs with highly sparse topologies but incredibly good information propagation. Once expanders have been discovered in the context of graph machine learning, they have seen equal application among graph neural networks (Deac et al., 2022: Christie & He, 2023; Wilson et al., 2024) and graph Transformers (Shirzad et al., 2023; 2024).
Much like a degree in an undirected graph, a node i in a feedforward graph has an indegree d' and an outdegree 8, counting the number of incoming and outgoing edges to/from node i.
As illustrative example, two types of feedforward graph are commonly used for machine learning tasks today:
The fully connected feedforward graph, which draws an edge between every allowed pair of nodes; & = {(a, b) | a < b}. Indegrees and outdegrees in this graph are _,,_ = i 1, 8 = (n)
Unfortunately, to the best of our knowledge, the state-of-the- art is not as rich in the domain of feedforward graphs This includes the domain of mathematics, wherein many impor- tant concepts have not been generalised to the directed case' as they may rely on spectral properties of the graph structure (Chung, 1997). and many spectral properties are ill-defined
The locally connected feedforward graph, which draws an edge between all allowed pairs of nodes up to a distance K 2 0 apart: & = {(a, b) 6 K S a S b}. A special case of k = 1 is known as line graph. Inde- grees and outdegrees are 8 = 8in = K + provided K S i 5 n
'We are aware of one prior work generalising undirected expanders to the concept of a feedforward extender (Csóka & Grabowski, 2022>-we leave making any connections of extender graphs to the propagation properties studied here for future work.
We now outline three desirable properties which we will typically assume during our exploration:
2

---

What Makes a Good Feedforward Computational Graph?
Self-Edges. We will always assume all self-edges are present in the graph that is, (i, & for all i E V. un- less otherwise stated. This is generally an important design decision for improving data retention.
Hence, in this case, the spectrum of the walk matrix is obtained from the spectrum of A by scalar multiplication.
4.2. Stationary Distributions
A probability distribution л E IR" on the vertices station- ary if W T ग. In other words, π is unchanged by one step of the random walk.
Unique Sinks. As we will be tracking how easily informa- tion from each node can reach the designated sink node, T, is highly desirable that our graph generator does not create additional sink nodes of any kind (beyond the final node, of course). Any additional sink nodes imply an impossibility to reach the final sink from such nodes, and they are hence effectively excluded from decision making.
It is a well-known result that a strongly connected graph has a unique stationary distribution. Here, a graph is strongly connected if, for any ordered pair of vertices, there is an oriented path joining them. However, the graphs we will consider will be feedforward and hence not strongly con- nected. In that case, we have the following useful result.
Seffliimilarit. While most of our theory will concern the flow of information specifically into T, is important to note that in real workloads, any node might be used as sink node (over an appropriately sampled sub-input). As such, we focus our attention on self-similar feedforward graphs, wherein we can expect similar flow properties to all nodes (including ones in the middle).
Lemma 4.1. Let G be feedforward graph with a unique sink vertex T. Then there is a unique stationary distribution for W, namely 1,, the probability distribution taking the value at I and elsewhere.
Proof. Certainly 1, is stationary. To see that it is unique, consider distribution other than 1, Let i < n be its smallest vertex with o O. When applying the random walk matrix W, we can see that the probability of being at after one step is ///5, Since ب, >> 1, we deduce that π is not stationary.
4. Mixing Time: Tracking Path Complexity
We are now ready to work our way towards defining the first of our two measures, the averaged mixing time of the feedforward graph. This measure tracks how quickly infor- mation travels towards the sink, by carefully analysing the expected path length from each node to the sink. Clearly, the aim is to keep this value within reasonable upper bounds.
4.3. Mixing Times
There are several definitions of mixing time in the literature. Here is one. The mixing time is the smallest value of t such that for any starting distribution x,
4.1. Basic Notions
For feedforward graph of n nodes, == (Zn, E), let A E Raxa be its adjacency matrix, defined in the usual way:
| T < 1/4.
Here, the L norm is used on probability distributions, i.e., for two probability distributions and y,
{
(i,0) E
Gij
(1)
( 3
xx - yll1 = Σ
Jx val-
keeping in mind that A must be lower-triangular due to the feedforward constraint.
There is nothing special in the use of 1/4 here. Any fixed < E < 1/2 would work. In our set-up, is reasonable not consider a minimum over starting distributions x but an 'averaged' version:
Its walk matrix W is given by
1/8
(1 E
Wi
(j.1) & E.
1 n
W'e - π
So W is the transition matrix for the (lazy) random walk where there is an equal probability of leaving vertex j along any of its outgoing edges. This will be well defined as long as ب,ور 0 for all j E Zn; we are guaranteeing this condition by requiring all self-edges within the graph.
where e, is the probability distribution concentrated on ver- tex i. If we let II be the square matrix that has π in each column, then this is
1
W II 11
Note that for graphs where, for all; j E Zn, سبر = for some constant, K, the walk matrix is related to the usual adjacency matrix A. Specifically
where now we are taking the L norm on matrices:
|| [B|
Σ 1bul
W = A.
3

---

What Makes a Good Feedforward Computational Graph?
We call this quantity the averaged mixing time (Espuny Díaz et al., 2024). We will now demonstrate its behaviour is expected on two commonly used graph distributions.
is
h-2
Σ
ir
fe-1((e-
(06-++1)/2
4-1
+
f--1=
and inductively, we can show that this is
4.3.1. . LINE GRAPHS
Let 9 be the line graph from vertex 0 to vertex n - 1, as previously defined. Suppose that we start a random walk at vertex n2 i 1, i.e., the initial probability distribution is e- We want to consider the probabilty of not reaching the terminal vertex after t steps. We can think of flipping coin & times and we step right only if we get a head. We reach the terminal vertex if and only if we get at least heads. So the probability of not reaching it in L steps is
2
When >> log2 4n², this expectation is at most 1/(4n). This implies that the probability of being on the terminal vertex 0 is least 3/ 4. Hence, the mixing time is at most log, 4n = 2 + 2 log... n.
4.4. Discussion About Mixing Time as a Good Measure
Σ
When the graph has fixed out-degree n. then as observed before,
jAi
The average of this value, over all between 0 and n 1, is
W A. K
ΣΣ
R-1
2 2-
- Σ (n-i- 10-i-113 1) 11) 2-
()
Hence A W is the adjacency matrix A for the graph. Mixing time measures how close W'e, is to the stationary distribu- tion. In other words, it measures the size of W W This is 1/K" times the an-1.; entry of A'. Now this entry of A counts the number of oriented paths of length in G from vertex i to the terminal vertex. So, we have the conjectured equivalence: mixing time is small (e.g. Oloog n)) if and only if there are 'lots' of paths from 'most' vertices to T. In fact, we can formally prove the following proposition:
76
jii
When n 2 4
n-1
(n- 1) ()) 2- = (n -1)
2- =t/2
Proposition 4.2. Suppose that the ouidegree of every vertex other than T is at least 2. Let t be the average mixing time. Then for some 8 S. t, the average number of paths from vertex to T with length s is at least (3/4t)2", where the average is taken over all vertices between 0 and n.
So, the average value of the probability of not reaching the terminal vertex is
1 n
n (
t+ 2
2) =1
2n
One way to interpret this is for the mixing time of G to be 'small', then there must be exponentially many paths from a typical vertex to T with length less than the mixing time. We prove this statement in Appendix A. As having many paths seems useful for efficient data propagation, mixing time seems good measure of how efficient our network will be under this computational graph.
This is less than 1/4 when >> 3n/2.. Hence, the averaged mixing time is 3n/2, which is O(n).
4.3.2. FULLY CONNECTED GRAPHS
Now consider the case when G is the fully connected feed- forward graph. For convenience, we will label the graph with vertices [0....,,.) n.] where every pair of vertices i and j with < j are joined by an oriented edge from j to i. (Hence, in this scenario, 0 is the terminal vertex.) Then the average mixing time of the order Ologn).
Typically, we will treat mixing time as a cutoff, determining which graphs would require too many layers layers-much like the under-reaching problem (Barceló et al., 2020). It is also interesting to note that the fully connected graph does not have optimal mixing time-in in fact, the additional paths create a distraction, and the mixing time optimised by the "feedforward star" graph with edges & {ii, 7) E V}. This relates to an observation by Di Giovanni et al. (2024), showing how fully-connected undirected graphs do not have optimal commute time due to distracting additional edges. However, we will not favour such solutions due to a lack of self-similarity.
To prove this, say that we start at position ig and then move to position é,, ending at i, after steps. Then the expected value of the vertex after steps is
Σ 6-
4
n
10
=0=0
4

---

What Makes a Good Feedforward Computational Graph?
4.5. Discussion About the Spectrum
resenting its weight may be expressed as e, E R", which is one-hot vector that is one in position i and zero elsewhere.
In the usual theory of random walks on strongly connected graphs, mixing time is related to d₁. This is the maximal eigenvalue of the normalised adjacency matrix (other than the eigenvalue 1).
One step of diffusion corresponds to matrix multiplication by A:
(Ax), Σ AUj
(3)
However, in our case, there is not an obvious interpretation of mixing time in terms of the spectrum of W. This is because W is lower-trianglla. Hence, its spectrum is equal to its diagonal entries. Hence, as a set, the spectrum is just
(NB: this does not always yield a probability distribution!)
We can simultaneously estimate the diffusion properties for all possible initial vertices by stacking the e; vectors, recovering the identity matrix, I. Accordingly, after t 2 0 layers of propagation, we can read off the coefficients of each item in each receiver by computing A
(1/6,, 0 S i S n nn-nnnn 13.
In general, these matrices are not diagonalisable, and so the total multiplicity of these eigenvalues may be less than n. For example, suppose that G has constant out-degree R, apart from the terminal vertex. Then W just has two eigenvalues: 1 and 1/k.
Since we take particular care on how much information has reached the sink vertex, we can define the fidelity of node i at l steps as A This can be interpreted as: "what is the coefficient of node i in the weighted sum within after t steps of averaging diffusion?"
5. Minimax Fidelity: Information Sharpness
An important point about the fidelity measure is that it does not always grow with increasing t-this is easy to observe in nodes near the end the sequence:
Mixing time provides an excellent estimate of how long will information need to travel in graph-it is generally good idea to keep it low. However, it is not the whole story: it is irrelevant if information from a given node travels fast to the sink if only a small proportion of it makes it through. To quantify the extent to which information sharply reaches the sink, we will be using the minimax fideiity metric.
Proposition 5.1. Let G = =Zn, E) be a feedfoorward graph of n > 1 nodes with all self-edges and a unique sink vertex T= n 1; that is, every node i Z, is connected to by a path in E. Then, if 6(n-2)= > 1, as 1 + oG, A + O, that is, the fidelity of node adjacent to the sink eventually vanishes if it has at least one nontrivial incoming edge.
Additionally, require that every node must have a positive in-degree; that is, 8 >0 0 for all E V. Note that this will be guaranteed by the self-edge property.
Proof. Initially, 2 = 1, and A J,n-2 = for all 1 n - 2. Since information can only travel forwards in the graph,
We want to track how "pre-disposed" this graph is to al- lowing information to travel freely in it. This relates to the over-squashing theorem in Barbero et al. (2024), but unlike them, we do not assume any degree of sharpness in choos- ing how information travels: specifically, at every step, we assume each node intakes the average value of all of the nodes over its incoming edges.
conclude that, if < i, Aj. 0 for all t. Hence, will be sufficient to track A n-2.n-2 and A , over time for the purpose of this proof.
Following the formula,
conclude A [+1
n-2,n-2 - 2 2 = (6(n-2)-) 1 2-2nn2 n-
(d(n-2)=) )-t Since we assumed ((n > 1, this value will certainly decay towards zero
oc.
5.1. Fidelity
Since there is only one sink vertex, т, it must have an in- degree 8- > 1: it must have a self-edge (by assumption) and it must have a direct incoming connection from at least one other preceding node. Further, at least one of those nodes must be n - 2, otherwise it would introduce another sink. The fidelity of node n 2 at ++1 layers can hence be ex- pressed as A , A -, A 22 + A A 7- = (6r=)) ((6mn-2)-) + 2.
Starting from our adjacency matrix as before, we now derive a "diffusion" process specified by the following matrix A:
{ 1/8te 0
(E E
A,
(2)
n-2
Note that this is complementary computation to the mixing time metrie: while one normalises by row, the other nor- malises by column. And, further, we are interested in how sharply represented can particular node be in the diffused representations, especially ones that reach the sink vertex.
Now, note that this expression is maximal when 8, ( = 2. As such, we can bound A T 2 2 2 + A t r.n 2/ 2. From this, we can prove by induction that
To simulate this, we start with an idealised setting where all the mass concentrates in a specific vertex, i. The vector rep-
A 7n- < 1/2². The base case (t 0) clearly holds,
as A - = S 0. From there, assuming the bound
5

---

What Makes a Good Feedforward Computational Graph?
holds for I, we can show it holds for + 1 by substituting (t + 1)/2
5.2.2. LINE GRAPHS
A [+1 r S 2- + (2/29)/2-
What line graphs sacrifice in mixing time (and hence tractability of certain problems) they make up for in fi- delity. Indeed, line graphs among the graph families with highest minimax fidelity. Their minimax fidelity can be expressed as follows', for graph of n elements:
This upper bound on A - also decays towards zero as ++ 0o, settling the proof.
5.2. (Mini)max Fidelity
(1-1) 2
Given this result, it does not make sense to study long- term dynamics of fidelity for most nodes. Rather, we can track the "best-case" scenario for node i, the maximal fidelity it achieves over the lifetime of the diffusion; that is, di max, A A This is the most sharp we can ever extract node i's features in the sink node?.
max
(6)
This quantity also decays to zero as n + oo (see Appendix B for proof using Stirling's approximation), but its nor- malised minimax fidelity consistently grows vn/T T (see Figure 1-indeed, line graphs have the highest initial fidelity of all considered graphs).
Out of all of these sharpness measures, we are hunting for the "weakest points". where the model is particularly vulnerable to extracting particular node's s features, any layer. As such, we compute the minimax fidelity as
5.2.3. ERDÖS-RÉNYT GRAPHS AND ORIENTED EXPANDERS
So far, we have mainly examined line graphs and fully con- nected graphs which in ways correspond to two extremes with respect to the metrics proposed.
min di min max A
(4)
We will now deploy this measure on some graph generators of interest, just as we did for mixing time.
We may further see from Figure I that creating oriented ver- sions of Erdós-Rényi (Erdós et al., 1960) graphs (keeping indegrees fixed) as well as orienting graphs that are known to be undirected expanders (by assigning a random permuta- tion to their nodes) results in negative performance on both of our metrics compared to the fully connected graph.
It is worth noting that tracking how the signal evolves over time in this way is similar to the Dirichlet energy, which has been used extensively to study the over-smoothing effect in GNNs (Cai& & Wang, 2020; Zhou al., 2021; ; Rusch al., 2022; Di Giovanni et al., 2022). One key difference is in the fact that the measure at hand here involves taking maxima and minima and hence is not as smooth to work with.
We will not study these graphs in more depth here, though it is worth remarking that fixed-indegree Erdös-Rényi graphs are very likely to introduce additional sinks, breaking one of our thcory's s key assumptions. Another reason why both of these distributions are likely to fail is that they are effectively unbiased in terms of which incoming edges they sample an earlier node is equally likely to be assigned as an indegree neighbour as a latter one. As we've seen in Proposition 5.1, latter nodes are particularly vulnerable to losing fidelity quickly. This motivates our next distribution under study.
5.2.1. FULLY CONNECTED GRAPHS (AND NORMALISED MINIMAX FIDELITY)
While fully connected graphs had highly favourable log- arithmic mixing time, they immediately fully average in- formation, and therefore their minimax fidelity is always 1/n. This is potentially problematic, especially if hit with dispersion issues at inference time (Veličković et al., 2024).
5.2.4. PoISSON(p) GRAPHS
Taking this into account, and given the ubiquitous use of the fully connected feedforward graphs in contemporary architectures, we will often opt to report the normalised minimax fidelity:
Guided by this observation, we set out to construct graph generator which is biased to create edges towards the end of the sequence (so it preserves fidelity better) while still having a chance of generating an edge which is further away from the target node (so it shortens mixing time).
n min de n2 min max A
(5)
This combination of constraints led us to consider graph which samples edges by going right-to-left, simulating a Poisson process with probability p. samples in in-degree neighbours of node i (given an indegree budget) as follows:
which ensures that the fidelity of the fully connected graph is always 1 (see Figure 1), and provides intuitive threshold for whether the fidelity is more or less favourable than fully connected graphs
E U E-E((()))) i))
PI is assumed implicitly that neural networks deeper than opti- mal may still he able preserve this level of information of node i by leveraging their residual connections (He et al., 2016).
Diffussing along the line graph basically involves generat- ing normalised entries of (trimmed) Pascal's triangle, which is why the hinomial coefficients appear in this formula.
6

---

What Makes Good Feedforward Computational Graph?
50
100
150
200
250
0
50
100
150
200
250
50
100
150
200
250
0-
0
50
50
50
100
100
100
150
150
150
200
200
250
Figure 2. The evolution of the adjacency matrices generated by the FS graph generator. (Left::) The original solution found by FunSearch. when asked optimise minimax fidelity while keeping the mixing time under 2 loga n. (Middle:) Adapting the initial solution bound the in-degrec within each cluster. Each pair of successive blocks are now connected by a random bipartite expander. (Right:) The final FS graph generator, leveraging recursive construction ensure self-similarity and sufficient sparsity.
edges t-1 1 t i-1
successive chunks. Since there aren't 't almost any intra- cluster edges, random walks almost certainly always move from one cluster to the next, mixing in logarithmic time. And since each chunk only attends over smaller number of nodes (mn/ log n). this improves fidelity.
while A edges budget do 10)
if p p then & - EU EU (() edges + edges +1
There are two core issues with this graph left to fix from an asymptotics point of view. First, the indegree of each node is (nz/ log n) as n + oo, which is undesirable. Second, the graph does not exhibit self-similarity: it will only work well if the predictions will take place in the final node block, which will be exposed to the "final triangle" of full edges.
end if j x j end while
Different values of p will yield graphs with different lev- els of locality (p = yields a local graph generator). In our experiments. we found that p 0.2 struck the best balance between improving fidelity and penalising mixing time, though the mixing time is still not nearly as control- lable as some of the other graphs the profile of the metrics achieved by Poisson(O.2) 2) is provided in Figure 1.
In order to fix these issues, we first note that each filled chunk of the matrix is essentially corresponding to edges of a bipartite graph. And constructions of bipartite expander graphs (which have excellent neighbourhood coverage) are well understood in mathematics. In Figure 2 (Middle), we provide such construction, built by concatenating random perfect matchings (Lubotzky, 1994; Sarnak, 1990).
6. The FunSearch (FS) Graph Generator
To fix self-similarity, it is evident that all intra-cluster edges (the "blank triangles" in the adjacency matrix) need to be filled equivalently. However, this would result in (n)) asymptotic indegree per node. As such, we opt to fill the intra-cluster edges recursively, by constructing smaller copies of the FS graph, within each triangle. By doing so, we recover the graph from Figure 2 (Right), which is now both suitably sparse and self-similar!
Apparently, even after trying out many hand-crafted sparse graph generators, we have not been able to strike the right balance between mixing time and fidelity. So we turned our attention to evolutionary methods: as there's 's no clear method of constructing graphs which optimise the fidelity while keeping the mixing time within reasonable bounds, we used the FunSearch (Romera-Panee Parerde al., 2023) algorithm to produce graphs with good values for both metries. The most promising result generated by FunSearch may be found in Figure 2 (Left), and it turns out to be impactful motif.
As can be seen in Figure 1, the FS graph generator indeed has a desirable tradeoff between solid normalised minimax fidelity and contained mixing time. Further, the fidelity can be meaningfully controlled by varying the chosen indegree of each expander graph; for example, out of all choices of
The core idea of this graph is to divide the nodes into Ologg n) groups, then applying full bipartite graphs across
7

---

What Makes a Good Feedforward Computational Graph?
Pelasuni and Marrer Df Canakdbez Super
Neltenaee on Sak Canadaaa thuals
reuren Jely Bod Ot Dasp
Racas dligh Lop lndipla (rua Indepres
funeact Rocative dag iddgge
12 Gragh digigee
03
Conprted Capgh
Larght
Yid Langh
Tartango
Figure 3. Performance profiles of GATs trained with various computational graphs, on the max retrieval task (left), second max retrieval task (middle), and parity task (right), when trained up size 256. The x-axis corresponds test accuracy sizes from 16 1, 024.
However, we also need to take care that the recursively introduced edges (which stay in the same block) do not overly impede the random walker's trajectory across blocks. Formally, we prove the following:
for
-.--
Theorem 6.1. Consider FS graph generator with [log n] blocks per level for a graph of n nodes. Further, assume that for every node, the proportion of its outgoing edges going across blocks is lower bounded by a constant a > O. Then the mixing time of graphs produced by this generator is (polylog n).
63
65 75 06
96
95
260
For reasons of brevity, we provide a full proof of this Theo- rem (along with supplementary remarks concerning how to construct the graph to match the assumptions of the Theo- rem) in Appendix C.
Figure 4. Fitted scaling laws of log-minimax fidelity for different indegrees (of the form k logg n for different values of k over n nodes) of sampled expander graphs in the FS graph.
7. Results
To supplement our findings with empirical performance metrics, we evaluate graph attention network (Veličković et al., 20y8)-style model on three representative tasks:
Ollog n) indegree, we find that 4 log n offers a favourable "fidelity scaling law" (see Figure 4).
6.1. Analysing the Mixing Time of the FS Graph
finding the highest valued node in sequence (Veličković et al., 2024);
Having demonstrated that the FS graph generator has high fidelity and low mixing time in an empirical setting, we will now prove one of these mixing time is favourable.
finding the second highest valued node in a sequence (Ong & Veličković, 2022);
that its
computing the parity value of bitstring (Hahn, 2020).
Informally, the idea of the proof is that the partitioning of the nodes into Oloog n) blocks allows for quickly traversing long distances in the graph, via the bipartite edges. Making this construction recursive means that, once we reach the final block of size On// log n), the progression towards the sink will remain fast within that block, avoiding a linear mixing time as n + 00.
using adjacency matrices sampled from our graph genera- tors. The tasks are chosen to represent opposite extremes of sharpness required: for finding the maximum, exactly one node needs to propagate its input features to the sink - for parity, all of them need to. The performances of different computational graphs can be seen in Figure 3.
8

---

What Makes a Good Feedforward Computational Graph?
"(Second) Maximum retrieval' tasks consist in finding the category of the (second) maximum element in the set of items. Categories are provided one-hot encoded, together with the values. For each set the categories are consistent, but are randomised between different sets. Ten categories are used, so chance accuracy is ~ 10%.
well-justified metrics of feedforward information propaga- tion, used them automatically discover an interesting graph generator, and demonstrated its strong performance on several carefully crafted benchmarks.
We are hopeful that our work will inspire targeted follow-up studies in this space, which may usher in a new paradigm of graph rewiring. To this end, we particularly believe would be worthwhile study computational graphs that dynamically change across layers as opposed to single fixed graph studied here as well as attempting to establish more formal framework connecting mixing time, fidelity and similar metrics. The framework of Lim et al. (2024) could be useful for reasoning about feedforward computa- tional graphs spanning multiple layers.
The 'Parity' task consists of computing the parity of the number of Is in bitstring. Since there are only two possible parities, odd and even, random guessing should lead to around 50% accuracy on the task.
For details on the models' architectures and optimisation, please see Appendix E. As one can see in Figure 3, the FS graph leads in general to the best performance in distribution and best out of distribution generalisation when compared to other sparse grachs-matching the intuition found by our metrics. More strongly, in the Parity task the FS graph manages to effectively match the fully connected graph, while having a substantially lower number of edges, and while its performance tends to be similar to the Poisson(O.8) graph inthe Maximum task, in the Second Maximum and Parity tasks there's significant gap in performance between the FunSearch graph and all the other sparse graphs.
Acknowledgements
We would like to extend deep thanks to Steven Kaptur- owski for detailed assistance with the parity experiment, as well as Alexander Novikov for kindly supporting us as we were setting up our FunSearch experiments. We are also grateful to Razvan Pascanu and Simon Osindero for diligently reviewing this paper and providing valuable com- ments. Mare Lackenby was partially supported by the En- gineering and Physical Sciences Research Council (grant number EP/Y004256/1).
Additionally, we may note that the results are aligned with the recommendations given in Figure 4, which concerns the problem sizes up to 1, 024 studied here. Namely, leveraging an in-degree of 4log n for the random expanders used to sparsify the FS graph has a more graceful performance profile with increasing problem size across all three tasks compared to using in-degree of log n.
Impact Statement
This paper presents a novel framework for improving the information propagation quality across data with feed- forward constraint. Such models are highly prevalent, and innovations in this space could eventually lead to improve- ments in model sparsity (allowing for serving more powerful models on edge devices, for example) and model out-of- distribution generalisation (alowing more capable reasoning and scientific advances). Any societal consequences of our work could hence be equated to the societal consequences of accelerating these flavours of research.
On the Importance of Self-Edges and In-Degrees Our theoretical framework always assumes that all self-edges are included, valuable way to preserve each node's information over time. Accordingly, removing it led to significant performance regressions on all tasks - especially on the Parity task where multiple elements need to interact meaningfully for the final answer computation.
We also evaluated our graph generators at different orders-of- magnitude of in-degree- from ((1) Ollog n) to ((vr)) We find that, as the in-degrees are increased, the models get more performant in-distribution, without significant effect on overall out-of-distribution performance.
References
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In In- ternational Conference on Learning Representations, 2021. URL https: /tpp///veeenneeeeeeeeeeee /wt//errurrr forum? id=i800PhOCVE2.
8. Conclusions
In this work, we have embarked on detailed study of feed- forward computational graphs, attempting chart novel path that could enable for principled discovery of useful feedforward blueprints. While it is apparent that analysing these graphs is substantially less straightforward than do- ing so with their undirected counterparts, we believe the outcomes to have been fruitful. Namely, we proposed two
Amaiz-Rodriguez A., Begga, A., Escolano, F., and Oliver, N. Diffwwir: Inductive graph rewiring via the lovász bound. arXiv preprint arXiv:2206.07369, 2022.
Azabou, M., Ganesh, V., Thakoor, S., Lin, C.-H., Sathidevi,
L., Liu, R., Valko, M., Veličkovié, P., and Dyer, E. L.

---

What Makes Good Feedforward Computational Graph?
Half-hop: graph upsampling approach for slowing down message passing. In International Conference Machine Learning, pp. 1341-1360. PMLR, 2023,
Gasteiger, J., Weißenberger, S., and Günnemann, S. Diffu- sion improves graph learning. Advances in neural infor- mation processing systems, 32, 2019.
Barbero, F., Banino, A., Kapturowski, S., Kumaran, D., Araújo, G. M., Vitvitskyi, A., Pascanu, R., and Veličković, P. Transformers need glasses! informa- tion over-squashing in language tasks, 2024. URL https: //axxi///aiiv./// org/ aas//ab///// 2bss/4000 6406. 04267.
Hahn, M. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 156-171, 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leamn ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Barceló, P., Kostylev, V., Monet, M., Pérez, J., Reutter, J., and Silva, The logical expressiveness graph neu- ral networks. International Conference on Learning Representations, 2020. URL https: openreview. net/
Huang, S., Poursafaei, F., Danovitch, J., Fey, M., Hu, W., Rossi, E., Leskovec, J., Bronstein, M., Rabusseau, G., and Rabbany, R. Temporal graph benchmark for ma- chine learning on temporal graphs. Advances in Neural Information Processing Systems, 36, 2024.
Cai, C. and Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
Christie, T. and He, Y. Higher-order expaadde graph propa- gation. arXiv preprint arXiv:2311.07966 2023.
Keriven, N.
Not too little, not too much: theoretical analysis of graph (over) smoothing. Advances Neural Information Processing Systems, 35:2268-2253 2022.
Chung, F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Kim, J. and Suzuki, Transformers provably solve parity efficiently with chain of thought, 2024. URL https: //arxiv.ors wwwpxivvorg/aeo wwwgg/bbs... 2 4 10. 08633.
Csóka, E. and Grabowski, L. On directed analogues of ex- pander and hyperfinite graph sequences. Combinatorics, Probability and Computing, 31(2):184-19)) 2022.
Kowalski, E. An introduction to expander graphs. Société
Deac, A., Lackenby, M., and Veličković, P. Expander graph propagation. In Learning Graphs Conference, pp. 38-1. PMLR, 2022.
mathématique de France Paris, 2019.
Li, Q., Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018.
Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., Markovich, T., and Bronstein, M. M. Understanding convolution graphs via energies. arXiv preprint SXXi:2206.10991 2022.
Liao, and Póczos, B. Graph attention with random rewiring. arXiv preprint 1XXX::407.005499 2024.
Di Giovanni, F,, Rusch, T. K., Bronstein, M., Deac, A., Lackenby, M., Mishra, S., and Veličković, How does over-squashing affect the power of GNNs? Transac- fions Machine Learning Research, 2024. ISSN 2835- 8856. URL https: wttp//peeeeeeweeceeeeee htwpiiewwwee//ttoooeeoeee id-KJRoOvRNNs.
Lim, D.,, Maron. H., Law, M. T., Lorraine, J., and Lucas, J. Graph metanetworks for processing diverse neural architectures. In The Twelfth International Conference on Learning Representations, 2024. URL https:// openreview net forum?idd iiciumiiddiiie 1orumrid-11KShyxx0..
Erdós, P.. Rényi, A., et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1::17-60,, 1960.
Lubotzky, A. Discrete groups, expanding graphs and invari- ant measures, volume 125. Springer Science & Business Media, 1994.
Espuny Díaz, A., Morris, P., Perarnau, G., and Serra, O. Speeding up random walk mixing by starting from a uniform vertex. Electronic Journal of Probability, 29: 1-25, 2024.
Maskey, S., Paolino, R., Bacho, A., and Kutyniok, G. A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 36: 13022-13063, 2023.
Fesser, L. and Weber, M. Mitigating over-smoothing and over-squashing using augmentations forman-ricci cur- vature. In Learning on Graphs Conference, pp. 19-1. PMLR, 2024.
Ong. E. and Veličkovié, P. Learnable commutative monoids for graph neural networks. In Learning on Graphs Con- ference, pp. 43-1. PMLR, 2022.
10

---

Srambical, F. Going beyond the causal mask in language modeling. p(doom) blog, 2024. http://pdoom..orbboog..go What Makes a Good Feedforward Computational Graph?
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. arXiv preprint arXiv: Meeii,900...99 2019.
Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https::/prroceddine neurips. cc cc/sspee_fiieesppprr//////L a 444c5555227772255554ee6666688383 pdf.
Radford, A., Narasimhan, K., Salimans, T., and Sutskever, Improving language understanding by generative pre- training, 2018. URL https: / /www. mi kecaptain. com/resources / pdf/ Sedf/GPTT GPT-1.pdE.
Team, G., Mesnard, T., Hardin, C., Dadashi, R., Bhupatiraju, S., Pathak, S., Sifre, L.,, Rivière, M., Kale, M. S., Love, J., et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.08229 2024a.
Romera-Paredes, B., Barekatain, M., Novikov, A., Ba- log. M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., EI- lenberg, J., Wang. P., Fawzi, O., Kohli, P., and Fawzi, A. Mathematical discoveries from program search with large language models. Nature, 2023. doi: 10.1038/ s41 44156-003-006224-6
Team, G., Riviere M., Pathak, S., Sessa, G., Hardin, C., Bhupatiraju, S., Hussenot, I.., Mesnard, T., Shahriari, B., Ramé, A., Ferret, J., Liu, P., Tafti, P., Friesen, A., Casbon, M., Ramos, S., Kumar, R., Lan, C. L., Jerome, S., Tsit- sulin, A.. Vicillard, N.. Stanczyk, P., Girgin, S., Momchev, N., Hoffman, M., Thakoor, S., Grill, J.-B., Neyshabur, B., Bachem, O., Walton A., Severyn, A., Parrish, A., Ahmad, A., Hutchison, A., Abdagic, A., Carl, A., Shen, A., Brock, A., Coenen, A., Laforge, A., Paterson, A., Bastian, B., Piot, B., Wu, B.. Royal, B., Chen, C., Kumar, C., Perry, C., Welty, C., Choquette- Choo, C. A., Sinopalnikov, D., Weinberger, D., Vijaykumar, D., Rogozińska, D., Her- bison, D., Bandy, E., Wang, E., Noland, E., Moreira, E., Senter, E., Eltyshev, E., Visin, F., Rasskin, G., Wei, G., Cameron, G., Martins, G., Hashemi, H., Klimezak- Plucińska, H., Batra, H., Dhand, H., Nardini, I., Mein, J., Zhou, J., Svensson, J., Stanway, J., Chan, J., Zhou, J. P., Carrasqueira, J., Iljazi, J., Becker, J., Fernandez, J., van Amersfoort, J., Gordon, J., Lipschultz, J., Newlan, J., yeong Ji, J., Mohamed, K., Badola, K., Black, K., Milli- can, K., McDonell, K., Nguyen, K., Sodhia, K., Greene, K., Sjoesund, L. L.., Usui, L., Sifre, L.., Heuermann, L., Lago, L., McNealus, L., Soares, L. B., Kilpatrick, L.. Dixon, I.., Martins, I.., Reid, M., Singh, M., Iverson, M., Görner, M., Velloso, M., Wirth, M., Davidow. M., Miller, M., Rahtz, M., Watson, M., Risdal, M., Kazemi, M., Moynihan, M., Zhang, M., Kahng, M., Park, M., Rahman, M., Khatwani, M., Dao, N., Bardoliwalla, N., Devanathan, N., Dumai, N., Chauhan, N., Wahltinez. O.,, Botarda, P., Barnes, P., Barham, P., Michel, P., Jin, P., Georgiev, P., Culliton, P., Kuppala, P., Comanescu, R., Merhej, R., Jana, R., Rokni, R. A., Agarwal, R., Mullins, R., Saadat, S., Carthy, S. M., Cogan, S., Per- rin, S., Aroll, S. M. R., Krause, S., Dai, S., Garg, S., Sheth, S., Ronstrom, S., Chan, S., Jordan, T., Yu, T. Eccles, T., Hennigan, T., Kocisky, T., Doshi, T., Jain, V. Yadav, V., Meshram, V., Dharmadhikari, V., Barkley, W., Wei, W., Ye, W., Han, W., Kwon, W., Xu, X., Shen, Z., Gong, Z., Wei, Z., Cotruta, V., Kirk, P., Rao, A., Giang, M., Peran, L., Warkentin, T., Collins, E., Bar- ral, J., Ghahramani, Z., Hadsell, R., Sculley, D., Banks, J., Dragan, A., Petrov, S., Vinyals, O., Dean, J., Has- sabis, D., Kavukcuoglu, K., Farabet, C., Buchatskaya, E., Borgeaud, S., Fiedel, N., Joulin, A., Kenealy, K.,
Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006. 10637, 2020.
Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., and Bronstein, M. Graph-coupled oscillator networks. In International Conference Machine Learning, pp. 18888-18909 PMLR, 2022.
Sarnak, P. Some applications of modular forms, volume 99. Cambridge University Press, 1990.
Shazeer, N. and Stern, M. Adafactor: Adaptive learning rates with sublinear memory cost, 2018. URL https: //arxiv. org/ abs /1/./180...00 04235.
Shirzad, H., Velingker, A.. Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transform- ers for graphs. In International Conference on Machine Learning, pp. 1613-316322. PMLR, 2023.
Shirzad, H., Lin, H., Venkatachalam, B., Velingker, A., Woodruff, D., and Sutherland, D. J. Even sparser graph transformers. In The eighth- Annual Con- ference on Neural Information Processing Systems, 2024. URL httph: http::////peeevierrree net/ forum? 4bWuNnk.
Sterner, I,, Su, S., and Veličković, P. Commute-time- optimised graphs for gnns. In scometry-grounder Repre- sentation Learning and Generative Modeling Workshop (GRaM) at ICML 2024, pp. 103-112. PMLR, 2024.
Sutskever, I., Vinyals, O., and Le, Q. V. Sequence to sequence learning with neural networks. In Ghahra- mani, Z., Welling, M., Cortes, C., Lawrence, N., and Weinherger, K. (eds.), Advances in Neural Information

---

What Makes a Good Feedforward Computational Graph?
Dadashi, R., and Andreev, A. Gemma 2: Improving open language models practical size, 2024b. URL https: / /arxiv..vvvv.////// org/ abs/ 2bss2408 2408. 00118.
Thost, V. and Chen, J. Directed acyelic graph neural net- works. In International Conference on Learning Rep- resentations, 2021. URL https:/ https:///peerevit spppreveeeeee... net/Eorum?2 2ic- 2ww.:ndddddddau----- JbuYF437WB6.
Topping, J., Giovanni, F. D., Chamberlain, P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In In- ternational Conference Learning Representations, 2022. URL hww.thttt/////to htttt::://peerrvieee net/ forum? id=7UmjRGZp--A A.
Van Den Oord, A., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A., Kavukcuoglu, K., et al. Wavenet: A generative model for raw audio. arXiv preprint (e0.::3999339999 12, 2016.
Veličković, Badia, Budden, D., Pascanu, R., Ban- ino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. The clrs algorithmic reasoning benchmark. In Inter- national Conference on Machine Learning, pp. 22084- 22102. PMLR, 2022.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018. URL httttss:/openrrevieee http://ee//eoteeeeee forum? id=rJXMpikCZ.
Veličković, P., Perivolaropoulos, C., Barbero, F., and Pas- canu, R. softmax is not enough (for sharp out-of- distribution), 2024. URL https://arxiv.orr 0bo/2440.01100
Wilson, J., Bechler-Speicher, M., and Veličković, P. Cayley graph propagation. In The Third Learning on Graphs Con- ference, 2024. URL https: /tR.tttss//oppeeeeeeeee http:///ppnreeeeeeceeeee n
forum?3d=VaTfEDDS
Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Al- berti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang. L., et al. Big bird: Transformers for longer se- quences. Advances in neural information processing systems, 33:17283-17297, 2020.
Zhou, K., Huang, X., Zha, D., Chen, R., Li, L., Choi, S.-H., and Hu, X. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 14-21834-2184 2021.
Ziyin, L., Wang. Z. T., and Ueda, M. Laprop: Separating momentum and adaptivity in adam, 2021. URL https: //arxivvorde wwwp/viiorrraeoooooooooooooeeee abs 20022 04839.
12

---

What Makes a Good Feedforward Computational Graph?
A. Proof of Proposition 4.2.
Proof. For 0 Si < n let p(i, 8) be the number of paths from vertex to T with length s, Then
p(i,s)
(W") Dre
S 2
This is because (W"),; represents the probability of random walk starting i and reaching by time This is equal to the sum, over all t, of the probability that the random walk first reaches time For any such s, this probability is equal to the sum, over all paths from to with length avoiding the loop based at r. of the probability of taking that path. This latter probability is at most 1/2* because at each step along the path there were at least two options that could have been taken.
Fort equal to the averaged mixing time,
W Tr 2 4"
So,
n-1
s(i,s)
n-1
3 4
2
2
71
2
S
1=0
2
1=0
Therefore, for some S 4
1
p(i, 8)
3
2
41'
1=0
So, the average number of paths from vertex i to with length is at least (3/41)2*.
B. Proof that Minimax Fidelity in Line Graph Decays to Zero with Increasing Size
First let's determine expression for max for fixed
Notice that this is equivalent to finding an expression for maxa and then replacing k: = n 1.
(3) 2"
With a fixed we know that 2 k, otherwise the binomial term would simply be 0. Now let f(a)
and let's compute
f(++1).
f(a)
f(a+1)
2a (a+1)
f(a)
20+T (R)
f(a+1)
(a+1))
kl(a - k)!
f(a)
k k + 1)!
a!
(a (a+1)
2a k+
From that we know that [(a+1) > 1 + (a +
1)
> 2(a k + 1)
+> 2k - 11-1 a. As such f(a) increases for in
f(a)
[k: 2k - 1] and decreases for a > 2k. We can thus say that
2k
max
20
22k
13

---

What Makes a Good Feedforward Computational Graph?
Now let's compute our limit using Stirling's Approximation:
(K)
(2k)!
k
lim
22k
=
10000
lim
k!a
2
(2k) 2k
e2k
1
lim
/ (2k)
k++00
e22
k2
(2*k)
22k
lim k-+00
2²k
1 2-2h
Tk
C. Proof of Theorem 6.1.
Proof. In order to help reason about the mixing time, it will be very useful compute it as function of the starting level and block the random walker is in. That is, we will track T(d, k) as the expected number of steps needed for random walker to reach the sink node, assuming the walker is currently d depth levels away from the deepest recursive level, and k blocks away from reaching the final block in the current depth level.
We already know that k's maximal value will be [lgg]] for each depth level, due to the generator's parameters. For the maximal value of d, i.c. the total number of depth levels, we note that after each level, the number of nodes being considered is further subdivided by [logn]. n]. This means that, after I levels, the block size is [lgn]] No further subdivisions possible once the block size reaches! 1.
Denoting the total number of levels by D, we have that
n/ n/(logn])PPt < 1,
n/ n/(oogn]) nl)
and hence
log (D+1) 1) log log n),
logn 2 D Dlog] logn].
So
log n
D
log log n
With this in mind, we aim to quantify T (1 log
[log 1). To do this, we will establish several upper bounds on
logilog
[dd, k), assuming pessimistic behaviour from the random walker.
Firstly, when the walker is in the final level (d = 0), the number of nodes considered is 1, hence there are are no blocks left to traverse, and therefore 7(0, k)) = 0 for all k.
Then, once the walker hits the final block in its current depth level = 0), automatically transitions into the next level, which is further subdivided into flog n blocks. In the worst-case scenario, the walker will have landed in the very first block of the next depth level, and will need to traverse them all. Hence, ['d, 0) - T'd - 1, [log n]) for all d > 0.
Finally, in all other cases, we leverage the assumption on the outgoing edge ratio to remark that the walker will transition into the next block at its current depth level with probability at least a. We make a pessimistic assumption that, if the walker does not transition into the next block, certainly stays exactly put within its current block. This leads to the upper bound of T(d, k) < + (d 1) + (1 - ad)(d, k))
We now define (dd recursively using the following recurrence relations:
T(d, k) + af 1) (1 (1-a)
(7)
î(d,0) 0) -T(d - 1, [ogg]]
(8)
T(0. k) 0
(9)
A simple induction gives that T'd, k) < [dd, k). So it suffices to find an upper bound for T k).
The key observation is, since a is assumed identical in every depth level, and & is always reset to [log n after each depth level, we can equivalently represent the total walk time as a direct sum of walk times on each depth level.
14

---

What Makes a Good Feedforward Computational Graph?
Then, since each depth level is represented chain of [logr] n| states, [dd, k)) may be observed the expected time of traversing line graph of k (d 1) flog n steps and transition probability a. The total number of such steps is D [log n)] for D being the number of depth levels.
To compute the mixing time of such a Markov chain, we assume that the walker starts in the first node of the first block, and we want to know the smallest value of / such that
Σ () [gggl
<1/4
For ease of notation, set N = Dílog m1]. The left hand side is the cumulative distribution function for the binomial random variable X (t, a). So we must find the smallest value of such that P( a) & N) < 1/4. Now, Hoeffding s inequality gives that
P(X(t,,) S N) < exp -t (a aa=z
N) ))
Hence, when & = 2N
((X S N) < exp (xp)-Na).
When a is fixed and is large, this is certainly less than 1/4. This establishes that the mixing time at most O(N) O(Dlogn). Note that when D [log n). then
Σ
JSDilog m
So the mixing time is certainly at least D [log
Therefore, plugging in the appropriate values of D, we can conclude that the final mixing time will be O is O(polylog n), completing the proof.
which log
log"n
Remark C.I. An important assumption for our mixing time derivation is that the outdegree ratio of each node's cross-blos block outgoing edges can be lower bounded by constant (which we can use as the value of a for our analysis).
Since there will be approximately level, as the ratio is then
log log log
depth levels in total, we cannot maintain a fixed outdegree of 6; at each depth
log log which will decay to zero as -> oo and cannot be lower-bounded by logn
d:- to fag constant. This implics that the relative out-degree of each node each block must decay with increasing depth level.
One simple way to support such a decay is assume geometric decay with ratio 1; that is, if the amount of cross-block edges from given node, depth level would be 8/==1 8,-,
given depth level, d, is o the amount of cross-block edges from that node at the next
This process upper-bounds the total number of outgoing edges of every node in the final graph by a geometric series 5 + 5 r + 5t ,2 + ....
xt T-r As such, the proportion of the edges which are cross-block at the current level would
correspond to = When moving to the next depth level, the number of outgoing edges will be 8,_,,, and since
the previous level has already been fully crossed, there will be no edges from the previous level, and the total outdegree is 1-r also leading to 1 ratio. This trend continues with increasing depth level, and we can hence use 1 as our pessimistic estimate of a.
D. Adjacency Matrix Gallery
In Figures 5-7 we provide visualisations of several adjaceney matrix samples for variety of graph generators we studied in this paper.
15

---

What Makes Good Feedforward Computational Graph?
103
150
200
250
50
100
15C
200
250
100
150
200
250
50
50
150
150
150
250
250
250
Figure 5. Generated samples of adjacency matrices for the graph generators of Oriented Expander (left), Frdös-Rényí with constant indegree (middle) and Poisson(O.2) with constant indegree (right).
100
200
250
50
100
150
200
250
100
150
200
250
0
50
100
100
100
150
150
200
200
200
Figure 6. Generated samples of adjacency matrices for the graph generators of Line Graphs (left), Poisson(O.2) ().2) with /n indegree (middle) and Erdös- Erdös-Rényi with v indegree (right).
100
150
200
250
50
15C
250
100
200
250
100
100
100
150
150
150
200
200
200
750
250
250
Figure 7. Generated samples of adjacency matrices for the graph generators Poisson(O.2)) with log, n indegree (left), Firdös-Rény) with log, n indegree (middle) and the Fully Connected graph (right).
16

---

What Makes a Good Feedforward Computational Graph?
E. Models and Training
We test graphs on two different tasks: bit set parity, which is well known to be hard for transformer architectures without Chain Of Thought (Kim Suzuki, 2024) and finding the category of the maximum or second maximum element in the set, We interested in length generalisation properties of the tasks, So while we train on length up 256 elements, we test sequences of up to 1, 024 elements. We tuned the order-of-magnituce of the learning rate and the weight decay coefficient using the fully-connected graph experiments only, and then reused the tuned parameters everywhere else.
E.1. Maximum Retrieval
For 'maximum' tasks we utilise simple transformer architecture. It consists of one attention block, which is single attention layer followed by two feedforward layers with GELU activations and pre-norm in between. This attention block is repeated (with shared parameters) for log n steps for an input of nodes. We use the cross-entropy loss function and the Adam W optimiser with 10-3 learning rate and 256 batch size. Training is performed over 10, 000 steps. We utilise casual attention mask in conjunction with mask provided by graphs.
E.2. Parity
We use a model similar to Gemma 2 (Team et al., 2024b), but with only only 8 layers and using standard multi-head attention with heads, the vocabulary size was 2, as there are only 2 symbols in a bitstring, and the embedding dimension was 256. The loss is a crossentropy and computed over all positions the sequence, so the model must predict the parity for all prefixes of the input bitstring. To train the model we used the LaProp optimizer (Ziyin al., 2021) with weight decay and RMSClip (Shazeer & Stern, 2018) for 1 million steps, with batch size of 128 sequences. Our hyperparameters were:
Table 1. LaProp Hyperparameters
Hyperparameter
Value
Learning Rate
10-3
S1
0.9
82
0.9
Weight Decay RMSClip's
5 x 10
1
As an indication of the utility of various feedforward graphs in the setting where nodes correspond to natural language tokens, we also fine-tuned Gemma 2B (Team al., 2024a) utilising these graphs as attention masks across all Transformer layers- on the standard Wikipedia dataset* containing texts obtained from Wikipedia database dumps.
After 3, 000 batches of training, we found that the perplexities obtained by the FS graph were comparable with the fully connected graph, while significantly improving on the line graph-a trend which is consistent throughout training.
httpap///ww..eeerrrroooo///aeees log pedia
17


Reviews:
[{"review_id": "lnKO0DuLMf", "reviewer": "Reviewer_GmC2", "summary": "the paper proposed two metrics to measure the quality of computational graph, experiments demonstrate the correlation between those metrics and actual performance.\n\n## update after rebuttal\nthe author's response addresses my question. the paper looks good to me, I will keep my rating", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer GmC2,\n\nWe are very thankful for your kind review and recognising the strengths of our work!\n\nTo address your questions:\n\n> The paper discusses the asymptotic behaviour of various graphs. why certain structures perform better from an ML perspective.\n\nThis is an excellent question. We believe that we can relate at least some of our metrics to established approaches in graph machine learning that study which graphs will have better information propagation from a machine learning perspective.\n\nTo name a few examples:\n* **High mixing time** implies that it takes a long time for information to travel to the final vertex (in the worst case – when there is more than one sink – mixing time is infinite). If there are insufficiently many layers in a model to cover these long paths, this directly relates to the well-known _under-reaching_ phenomenon in graph neural networks (Barceló et al., ICLR’20).\n* **Low fidelity** for a particular node implies that this node’s information is not reaching the final node in a way that is not “drowned out” by others, especially as more model layers are added – this effect is well-studied in the GNN literature as the _over-smoothing_ effect, and was recently also studied in the domain of Transformers as well (Barbero et al., NeurIPS’24).\n* High fidelity in certain nodes, but **low _minimax_ fidelity**, implies that, while some nodes are able to sharply send their information into the final node, this is done at the expense of other nodes, which fail to arrive at the sink quickly enough to avoid being overwhelmed. This kind of biased communication is related to the _over-squashing_ effect, which Barbero et al. (NeurIPS’24) have also studied from the perspective of Transformers.\n\nSince our original submission, we have also managed to make our statement in Section 4.4. (that mixing time is ‘small’ if and only if there are ‘lots’ of paths from ‘most’ vertices to $\\tau$) precise, as follows:\n\n**Proposition:** _Suppose that the outdegree of every vertex other than $\\tau$ is at least $2$. Let $t$ be the average mixing time. Then for some $s \\leq t$, the average number of paths from vertex $i$ to $\\tau$ with length $s$ is at least $(3/4t)2^s$, where the average is taken over all vertices $i$ between $0$ and $n-1$._\n\nThe proof is only a couple of paragraphs long, and it uses the intuition given in Section 4.1. More precisely, $(\\mathbf{W}^t)_{\\tau i}$ represents the probability of a random walk starting at $i$ and reaching $\\tau$ by time $t$. This is equal to the sum, over all $s \\leq t$, of the probability that the random walk first reaches $\\tau$ at time $s$. For any such $s$, this probability is equal to the sum, over all paths from $i$ to $\\tau$ with length $s$ avoiding the loop based at $\\tau$, of the probability of taking that path. This latter probability is at most $1/ 2^{s}$ because at each step along the path there were at least two options that could have been taken. So, for some $s \\leq t$, the average number of paths from vertex $i$ to $\\tau$ with length $s$ is at least $(3/4t)2^s$.\n\nWe intend to include this new result in the appendices.\n\n> The paper presents empirical results on tasks like maximum retrieval and parity. However, the tasks seem relatively simple. Could the authors expand their evaluation to more complex tasks, such as those involving real-world datasets (eg. natural language processing or graph-based tasks)?\n\nThank you for your comment!\n\nWe have designed our tasks to allow us fine-grained control over which (and how many!) nodes are relevant for computing the final answer, as this would allow us to validate our theory’s prescriptions in the most unbiased manner.\n\nThat being said, we fully agree that evaluating our proposal on real world datasets would make the work more valuable. To this end, we have now trained Gemma 2B language models – varying the graph used as the attention mask – on the standard Wiki dataset (https://www.tensorflow.org/datasets/catalog/wikipedia) containing natural language texts scraped from Wikipedia.\n\nAfter 3,000 batches of training, our model achieves the following perplexities:\n\n| **Graph**    | **Perplexity** |\n| :------- | :--------: |\n| Fully connected |  $5.3513$   |\n| Line | $5.7267$ |\n| FS | $\\mathbf{5.2786}$ |\n\nThis trend is consistent throughout training. This demonstrates that the sparse FS graph can remain competitive with the full feedforward graph, even when nodes are natural language tokens.", "claims_and_evidence": "YES", "methods_and_evaluation_criteria": "YES", "theoretical_claims": "YES", "experimental_designs_or_analyses": "YES", "relation_to_broader_scientific_literature": "Related to model optimization, general model training", "essential_references_not_discussed": "NO", "other_strengths_and_weaknesses": "strength:\n1. the paper is well written and easy to follow\n2. the experimental part is good, can support the claim\n\nThe paper address the challenge of what constitute a good feedforward graph sctructure, especially in terms of information propagation quality. two metrics (mixing time and minimax fidelity) provides us a principle for graph design that could inspire further research in this area, crucial for understanding how effectively information flows through the graph. the experiment parts show that the new graph generator outperforms existing models, showcasing the potential for improved model sparsity and out-of-distribution generalization .", "other_comments_or_suggestions": "NO", "questions_for_authors": "1. The paper discusses the asymptotic behaviour of various graphs. why certain structures perform better from an ML perspective.\n2. The paper presents empirical results on tasks like maximum retrieval and parity. However, the tasks seem relatively simple. Could the authors expand their evaluation to more complex tasks, such as those involving real-world datasets (e.g., natural language processing or graph-based tasks)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i30k3bkYec", "reviewer": "Reviewer_y3Tf", "summary": "The paper studies the impact of feedforward graph structures on information flow, introducing two metrics — mixing time and minimax fidelity— to assess speed and accuracy respectively.\n\nThe study reveals a trade-off between fast information propagation and high-fidelity signal propagation among various graph types and proposes the FunSearch (FS) graph generator to design graphs that balance these metrics effectively.\n\nEmpirical evaluations highlight that neural networks using the FS graph architecture outperform or match those with traditional designs in both in-distribution and out-of-distribution tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer y3Tf,\n\nWe are delighted that you have found our foundations to be strong and our results to be interesting. We hope that our responses will strengthen your view of our contributions even further!\n\n> However, Theorem 6.1's proof relies on strong assumptions\n\nThank you for raising this!\n\nWe have now improved the proof of Theorem 6.1 so that all simplifying assumptions have been removed. This turned out to be fairly straightforward, and mostly required the judicious use of ceiling and floor functions; eg. the correct value of the number of levels, $D$, is now:\n\n$$D = \\left \\lfloor \\frac{\\log n}{\\log \\lceil \\log n \\rceil} \\right \\rfloor,$$\n\nbut the key arguments of our random walk analysis are unchanged.\n\nThe proof is unwieldy to paste here but we will of course update it in our revision, and we are happy to discuss further aspects if you would like to know more!\n\n> The experiments use synthetic tasks that lack real-world complexity\n\nWe designed our tasks to allow fine-grained control over which (and how many!) nodes are relevant for computing the answer; this allows us to validate our theory’s prescriptions in the most unbiased manner.\n\nThat said, we agree that evaluating on real world data would make the work more valuable. We have now trained Gemma 2B models – varying the graph used as the attention mask – on the standard Wiki dataset (https://www.tensorflow.org/datasets/catalog/wikipedia) containing natural language texts scraped from Wikipedia.\n\nAfter 3,000 batches of training, our model achieves the following perplexities:\n\n| **Graph**    | **Perplexity** |\n| :------- | :--------: |\n| Fully connected |  $5.3513$   |\n| Line | $5.7267$ |\n| FS | $\\mathbf{5.2786}$ |\n\nThis trend is consistent throughout training. This demonstrates that the sparse FS graph can remain competitive with the full feedforward graph, even when nodes are natural language tokens.\n\n> Providing more detailed information on the experimental settings\n\nThank you; we will include more details. We used default hyperparameters in most places, and tuned the order-of-magnitude of the learning rate and the weight decay coefficient using the fully-connected graph experiments only (then reused the tuned parameters everywhere else).\n\n> The lack of access to the code as part of the supplementary material limits the ability to verify the experimental results.\n\nWe appreciate your remark, and thank you for acknowledging that the paper’s findings should be easier to reproduce since tasks are synthetic. We understand the positive impact of open-sourcing, and would aim to release our code for the synthetic tasks upon acceptance.\n\n> Including discussions of random walks on directed acyclic graphs, or connections to causal inference frameworks, could further highlight the novelty of extending these analyses to feedforward graphs.\n\nWe agree that these points are useful, and will add further discussions! To give a concrete example, since our original submission, we managed to make our statement in Section 4.4. (mixing time is ‘small’ iff there are ‘lots’ of paths from ‘most’ vertices to $\\tau$) precise:\n\n**Proposition:** _Suppose that the outdegree of every vertex other than $\\tau$ is at least $2$. Let $t$ be the average mixing time. Then for some $s \\leq t$, the average number of paths from vertex $i$ to $\\tau$ with length $s$ is at least $(3/4t)2^s$, where the average is taken over all vertices $i$ between $0$ and $n-1$._\n\nWe will include this in the next revision – it provides a relevant connection between our metrics and paths on a DAG and its proof is only a few paragraphs long.\n\n> Related works ([1, 2])\n\nThank you for bringing these to our attention. They are highly relevant to discuss and we will incorporate them. The key difference is that both Big Bird and GRASS optimise for _bidirectional_ graphs, where back edges are allowed.\n\n> Rigorous experiments and ablation studies, e.g., add/remove self-edges, experimenting with various in-degrees\n\nThis is an excellent suggestion! We have now performed both of these ablations, and found that removing self-edges led to significant performance regressions on all tasks – especially on the Parity task where multiple elements need to interact meaningfully for the final answer computation. We also evaluated our graph generators at different levels of in-degree OOM: $O(1)$, $O(\\log n)$ and $O(\\sqrt{n})$. We find that, as the orders are increased, the models get more performant in-distribution, without a significant effect out-of-distribution. We will incorporate both of these analyses in our revision!\n\n> The submission would benefit from a discussion on limitations and future research directions.\n\nWe’ll explicitly include the directions you discussed (integration with Transformer variants, dynamically adapting the computation graph) and we’ll also suggest additional ones (connecting the mixing and fidelity metrics and finding further connections between them and spectrally-motivated analyses!).", "claims_and_evidence": "The paper's claims regarding mixing time and minimax fidelity are well-supported by rigorous theoretical analyses in Lemma 4.1, Proposition 5.1, and evidence obtained from evaluations on canonical graph structures in Figure 3.\n\nThe introduction of the FS graph generator is backed by theoretical guarantees in Theorem 6.1 and evidence from empirical tests in Figure 3, substantiating the claims of achieving a balance between fast mixing and high fidelity.\n\nHowever, idealized assumptions limit the generality of the claims (please see 'Theoretical Claims'), while broader applicability remains uncertain without more evidence on real-world datasets (please refer to 'Experimental Designs Or Analyses').", "methods_and_evaluation_criteria": "The introduction of mixing time and minimax fidelity as complementary metrics measures information propagation efficiency and input detail preservation in graphs.\n\nTheoretical analyses, featuring rigorous derivations and asymptotic studies for various graph constructions, provide a foundation and clarify graph design trade-offs.\n\nThe three synthetic tasks — maximum retrieval, second maximum retrieval, and parity computation — test information propagation efficiency and sharpness, effectively stressing different graph aspects and aligning well with the study's objectives.", "theoretical_claims": "Lemma 4.1 and Proposition 5.1 establish stationary distribution and signal decay in feedforward graphs, with proofs demonstrating valid reasoning under specific assumptions.\n\nHowever, Theorem 6.1's proof relies on strong assumptions, such as integer-valued log n, perfect divisibility, and fixed minimum fraction of outgoing edges crossing blocks.\n\nAlthough the overall strategy is plausible and the recurrence analysis leads to a polylogarithmic upper bound, the proof depends on somewhat idealized conditions, raising questions about how robust the result is when these assumptions are relaxed.", "experimental_designs_or_analyses": "The experiments use synthetic tasks that lack real-world complexity, with graph attention network conditions limited by identity vertex features and synthetic graph structures.\n\nTesting on larger, real datasets with authentic vertex features and real-world graphs would better validate the findings.\n\nAdditionally, providing more detailed information on the experimental settings—such as hyperparameter tuning, hyperparameter details of baselines, and statistical significance tests—would enhance the robustness of the findings.", "relation_to_broader_scientific_literature": "This submission extends the extensive literature on graph rewiring to feedforward (directed acyclic) graphs — a setting where traditional spectral methods fall short due to the lower-triangular structure.\n\nThe introduction of mixing time and minimax fidelity metrics adapts classical Markov chain and expander graph theories to feedforward architectures.\n\nThe FS graph generator, inspired by FunSearch, contributes a practical algorithm for designing graphs that balance rapid information mixing with high signal fidelity.", "essential_references_not_discussed": "Including discussions of random walks on directed acyclic graphs, or connections to causal inference frameworks, could further highlight the novelty of extending these analyses to feedforward graphs.\n\nDiscussing recent work on sparse transformer mechanisms, e.g. [1], would enhance this paper by highlighting parallels in balancing computational efficiency and signal preservation, akin to mixing time and minimax fidelity metrics.\n\nA related work [2] presents a novel method that improves long-range connectivity in directed graphs using stochastic rewiring with graph attention.\n\n[1] Big Bird: Transformers for Longer Sequences, In NeurIPS 2020,\n\n[2] Graph Attention with Random Rewiring, arXiv 2407.05649v1.", "other_strengths_and_weaknesses": "Strengths:\n\n[+] The paper is clearly written and well-organized.\n\n[+] Graph rewiring in the context of feedforward and directed (acyclic) computation graphs is largely unexplored.\n\nWeaknesses:\n\n[-] Experiments are weak; rigorous experiments and ablation studies, e.g., add/remove self-edges, experimenting with various in-degrees, would strengthen the submission.", "other_comments_or_suggestions": "The submission would benefit from a discussion on limitations and future research directions.\n\nFor example, integrating the proposed metrics with modern design paradigms, such as residual connections and transformer variants, could lead to advanced models.\n\nThese models would dynamically adapt their computational graphs based on the specific task.", "questions_for_authors": "1. Was there a consideration for testing the results on real-world datasets with real-world vertex features? This could demonstrate the practical applicability of the metrics beyond synthetic tasks, increasing confidence in their real-world relevance and utility.\n2. Were there considerations for how Theorem 6.1 might adapt to less ideal conditions without strict assumptions like integer-valued log n? This would increase the theorem's applicability to real-world scenarios, enhancing the paper's theoretical impact and generality.\n3. Was there a consideration for conducting comprehensive ablation studies, such as adding/removing self-edges? Such studies can improve understanding of experimental design choices, indicating areas for refinement and strengthening future research outcomes.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4inGYunh0C", "reviewer": "Reviewer_QmmN", "summary": "The authors are motivated by the recent surge of feedforward networks, and analyze the underlying computational graphs. Their core question is: What characterizes a “good” computational graph? To address this, they propose two metrics:\na) Mixing time: Assesses how quickly information from various nodes reaches a designated target node, and\nb) Minimax fidelity: Evaluates whether information vanishes along the paths from input nodes to the target node (i.e., whether bottlenecks exist).\nThey study different random graph models under these metrics, focusing on their asymptotic behavior. They then train a GAT on graphs derived from these models to empirically illustrate some aspects of their theoretical insights.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer QmmN,\n\nThank you for your careful review! We hope to provide useful clarifications, and that you may reconsider the relevance of our work:\n\n### **On feedforward networks**\n\nYour comments focus on our work not easily representing multi-layer feedforward NNs.\n\nFor us, the term **“feedforward graph”** is defined more narrowly (cf. Section 3): we study feedforward computation over a _data axis_ (ie. we assume the _input nodes_ have a sequential ordering to them) rather than the _layer axis_! It is hence a _spatial_ constraint rather than one pertaining to multilayer architectures.\n\nPrior work on analysing data-axis feedforward graphs is **rare**: there was no established theory even for single-layer models over such inputs. The entirety of our paper aims to fill this gap, and study how to integrate information across the data axis with a _single_ graph. This corresponds to studying multi-layer GNNs which use the same feedforward graph in every layer. **It was never our intention to study arbitrary multi-layer signal propagation in this paper**.\n\nThis was sufficient to fill the page limit and pose important directions for future work. Progressing into the general case (where graphs may differ across layers) is a natural next step, but it induces a combinatorial explosion of design choices. We wanted to understand the basics well before inviting such analyses.\n\n> This gap risks misleading readers when considering new architecture development.\n\nWe recognise that, due to the established meaning of “feedforward”, our wording might pose a risk of misleading. We are happy to commit to **changing our title** to be more precise, eg.: “What makes a good _one-step_ feedforward computational graph?”\n\nWe also commit to **detailedly discussing** how our setup differs from general multilayer NNs.\n\n### **On metrics**\n\nOur notion of **mixing time** measures how quickly _salient information_ (ie. input features) can mix within the model. That is, how many feedforward layers (for a given graph) are necessary for a certain level of mixing of salient data to occur.\n\n> ResNets or GPT architectures have ±96 layers to enable the learning of \"strong\" hidden representations without directly propagating information to output neurons.\n\nThis point is _irrelevant_ to our metric, as intermediate neurons in a multi-layer network **do not hold salient information at the beginning**. If every neuron had salient data at the start, then our mixing time would be particularly high; but in the common scenario, our metric’s one-step approach wouldn’t measure mixing in the output neurons only, but at any intermediate point.\n\nOn **minimax fidelity**:\n\n> Modern networks routinely prune away large portions of weights or nodes, indicating that focusing on relatively few “important” nodes/edges is advantageous.\n\nThe problem is that modern NNs over feedforward data (eg. GPT) are topologically biased towards **earlier nodes** (proved in Barbero et al., NeurIPS’24), and hence not equally well-prepared when important data is not at the start of the input. This is **precisely** what we try to quantify with minimax fidelity: _“which node is in the worst possible position by this choice of graph structure”_?\n\nFidelity focuses on averaging (rather than pruning) because the mechanisms current models have for pruning, such as the `softmax` function, will provably fail to prune at OOD problem sizes (proved in Veličković et al., 2024).\n\n> In particular, given that the nodes are an ordered set, are nodes allowed to have the same order?\n\nWhile not explicitly allowed, our framework supports it: simply choose a random order for equal nodes. One component of the FS graph is a block-wise sequence of bipartite communications of this kind.\n\n### **Further points**\n\n> Related work [1, 2]\n\nWe appreciate these relevant papers and will be sure to discuss them in our revision. While [1] generalises oversmoothing to directed graphs, they are not “feedforward”; backwards edges are allowed, making a spectral approach far easier.\n\n> The datasets do not provide meaningful insights into what constitutes a “good” computational graph\n\nWe designed our tasks to allow fine-grained control over which (& how many!) nodes are relevant for computing the answer, allowing us to validate our theory’s prescriptions in an unbiased manner.\n\nThat said, we agree evaluating real-world setups would make the work more valuable. We have now trained Gemma 2B models – varying the graph used as the attention mask – on the standard Wiki dataset (tensorflow.org/datasets/catalog/wikipedia) containing texts from Wikipedia.\n\nAfter 3,000 batches of training, our model achieves the following perplexities:\n\n| **Graph**    | **Perplexity** |\n| :------- | :--------: |\n| Full |  $5.3513$   |\n| Line | $5.7267$ |\n| FS | $\\mathbf{5.2786}$ |\n\nThis trend is consistent throughout training, demonstrating the sparse FS graph is competitive with the full feedforward graph, even when nodes are natural language tokens.", "claims_and_evidence": "- Although the paper is motivated by feedforward networks, after the initial setup, there is little tangible connection between these metrics and actual modern neural network architectures. The authors’ own references to empirical performance remain vague, for instance:\n“As having many paths seems useful for efficient data propagation, mixing time seems a good measure...”\n- Yet such intuition does not necessarily hold for widely used architectures like deep MLPs or Transformers, which can often be represented by combinations of bipartite graphs (leading to high mixing time and low minimax fidelity) yet still excel in performance.\n- Much of the argument feels more opinion-based than backed by empirical evidence. For instance, low mixing time might not be inherently desirable. For example, deep ResNets or GPT architectures have ±96 layers to enable the learning of \"strong\" hidden representations without directly propagating information to output neurons.\n- Similarly, a high minimal fidelity does not obviously correlate with effectiveness. Modern networks routinely prune away large portions of weights or nodes, indicating that focusing on relatively few “important” nodes/edges is advantageous.\n- In contrast to their claims, the authors do not demonstrate any clear empirical link between these proposed metrics and the predictive performance of real-world neural networks.", "methods_and_evaluation_criteria": "The datasets do not provide meaningful insights into what constitutes a “good” computational graph. They consist of synthetic graphs from the different random graph models, on which three different tasks are tested using a GAT. However, there is no clear connection to feedforward networks or their suitability for different tasks, leaving the practical relevance of these experiments unclear.", "theoretical_claims": "- Their motivation comes from feedforward networks, but their graph models can not accommodate them. For example, given a simple MLP, their line graph model can not simulate the forward pass of MLPs. One would need edge weights. The same holds for other architectures like CNNs, RNNs, or attention blocks.\n- There are some unclear parts, e.g., locally connected feedforward graphs with $\\kappa=1$ do not have in- and out-degrees equal to $2$ unless every \"layer\" $n$ (corresponding to order $n$), contains only one node. Please see below for clarifying questions.\n- The other proofs appear correct.", "experimental_designs_or_analyses": "Experimental design and analysis appear sound.", "relation_to_broader_scientific_literature": "The paper is related to the oversquashing literature from GNNs. Some GNN papers are working on spectral properties/oversmoothing on directed graphs that are missing.", "essential_references_not_discussed": "The authors claim that \"many important concepts have not been generalised to the directed case...\" I would suggest [1] where concepts like oversmoothing etc. were generalized to directed graphs.\n\nI would also recommend [2] that discuss how feedforward networks / their parameters can be written as feedforward graphs.\n\n[1] Maskey, S., Paolino, R., Bacho, A., & Kutyniok, G. (2024). A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 36.\n\n[2] Lim, D., Maron, H., Law, M. T., Lorraine, J., & Lucas, J. Graph Metanetworks for Processing Diverse Neural Architectures. In The Twelfth International Conference on Learning Representations.", "other_strengths_and_weaknesses": "### Strengths:\n\n- The presentation is clear and straightforward to follow.\n- Analyzing feedforward networks from a graph perspective is an intriguing approach, particularly if it can spur improvements in sparsity or overall performance.\n- The theoretical analysis is detailed and appears thorough.", "other_comments_or_suggestions": "In conclusion, although the authors appear to address their central question, they do not provide sufficient evidence that these metrics correlate with the performance of modern feedforward networks. The authors’ motivation feels overstated: they neither fully analyze existing feedforward architectures nor demonstrate how to enhance computational graphs beyond the original input design. This gap risks misleading readers when considering new architecture development. For example, while mixing time is presented as a “good measure,” it tends to increase graph density and does not correlate with improved performance, thus casting doubt on its practical value.", "questions_for_authors": "- Given that the author's motivations come from analyzing feedforward networks, what is the relation of their analysis to feedforward networks? In particular, given that the nodes are an ordered set, are nodes allowed to have the same order? This would allow to model feedforward networks as seen in [2]", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates the impact of feedforward graph structures on information flow, introducing two key metrics: mixing time (to measure propagation speed) and minimax fidelity (to assess signal accuracy). The study reveals a fundamental trade-off between speed and fidelity in different graph topologies and proposes FunSearch (FS), a graph generator designed to balance these objectives. FS is supported by theoretical guarantees (notably Theorem 6.1) and validated through empirical evaluation.

The reviewers appreciated the clarity of presentation, the depth and rigour of the theoretical analysis, and the well-motivated formulation of mixing time and minimax fidelity as complementary performance measures. 

The author rebuttal was helpful and thorough, addressing many technical clarifications raised by reviewers. However, concerns remain regarding the experimental validation, which was viewed as less convincing or limited in scope compared to the strength of the theoretical contributions.

Overall, this is a solid theoretical paper with interesting implications, and the introduction of FS with provable properties is a valuable contribution. While the experimental side could be strengthened, the core insights justify inclusion in the program.
Decision: Accept (poster)