# Expander Graph Propagation

Andreea Deac
Mila, Université de Montréal
<EMAIL_ADDRESS>Lackenby
University of Oxford
<EMAIL_ADDRESS>Veličković
DeepMind
<EMAIL_ADDRESS>
###### Abstract

Deploying graph neural networks (GNNs) on whole-graph classification or
regression tasks is known to be challenging: it often requires computing node
features that are mindful of both local interactions in their neighbourhood
and the global context of the graph structure. GNN architectures that navigate
this space need to avoid pathological behaviours, such as bottlenecks and
oversquashing, while ideally having linear time and space complexity
requirements. In this work, we propose an elegant approach based on
propagating information over _expander graphs_. We leverage an efficient
method for constructing expander graphs of a given size, and use this insight
to propose the EGP model. We show that EGP is able to address all of the above
concerns, while requiring minimal effort to set up, and provide evidence of
its empirical utility on relevant graph classification datasets and baselines
in the Open Graph Benchmark. Importantly, using expander graphs as a template
for message passing necessarily gives rise to negative curvature. While this
appears to be counterintuitive in light of recent related work on
oversquashing, we theoretically demonstrate that negatively curved edges are
likely to be required to obtain scalable message passing without bottlenecks.
To the best of our knowledge, this is a previously unstudied result in the
context of graph representation learning, and we believe our analysis paves
the way to a novel class of scalable methods to counter oversquashing in GNNs.

##  1 Introduction

Graph neural networks (GNNs) are a flexible class of models for learning
representations over graph-structured data [1]. Their versatility [2, 3, 4]
and generality [5, 6] has made them a very attractive approach, leading to
considerable application in areas as diverse as virtual drug screening [7],
traffic prediction [8], combinatorial chip design [9] and pure mathematics
[10, 11].

Most GNNs rely on repeatedly propagating information between neighbouring
nodes in the graph. This is commonly expressed in the _message passing_ [4]
paradigm: nodes send vector-based _messages_ to each other along the edges of
the graph, and nodes update their representations by _aggregating_ all the
messages sent to them, in a permutation-invariant manner. Under many
industrially-relevant tasks, this paradigm is very potent, often allowing for
highly scalable model variants [12, 13, 14].

However, in many areas of scientific interest, purely local interactions are
likely insufficient. Among the principal graph tasks, _graph classification_
is perhaps most ripe with such situations: to meaningfully attach a label to a
graph, in many cases it is insufficient to treat graphs as “bags of nodes”.
For example, when classifying a molecule for its potency as a candidate drug
[7], the label is driven by complex substructure interactions in the molecule
[15], rather than a naïve sum of atom-level effects.

Accordingly, GNNs deployed in this regime need to update node features in a
manner that is mindful of the _global_ properties of the graph. It quickly
became apparent that it is often inadequate to merely stack more message
passing layers over the input graph. In fact, for many graph classification
tasks, such approaches may be weaker than discarding the graph structure
altogether [16, 17]. Now, it is well-understood that stacking many local
layers leaves GNNs vulnerable to pathological behaviours such as oversquashing
[18]. Intuitively, oversquashing occurs when nodes need to store quantities of
information that are _exponentially_ increasing with model depth [18, Section
5]. Such nodes often arise in the vicinity of _bottlenecks_ in a graph—small
collections of edges which are responsible for carrying representations
between large groups of nodes. One typical example of such a bottleneck can be
found in a _barbell graph_ , where the red edge is under significant
representational pressure to transport information between the two
communities.

Within this space, we are interested in proposing a method that satisfies
_four_ desirable criteria: (C1) it is capable of propagating information
_globally_ in the graph; (C2) it is _resistant_ to the oversquashing effect
and does not introduce bottlenecks; (C3) its time and space complexity remain
_subquadratic_ (tighter than $O(|V|^{2})$ for sparse graphs); and (C4) it
requires _no dedicated preprocessing_ of the input. Satisfying all four of
these criteria simultaneously is challenging, and we will survey many of the
popular approaches in the next section—demonstrating ways in which they fail
to meet some of them.

In this paper, we identify _expander graphs_ as very attractive objects in
this regard. Specifically, they offer a family of graph structures that are
fundamentally _sparse_ ($|E|=O(|V|)$), while having _low diameter_ : thus, any
two nodes in an expander graph may reach each other in a short number of hops,
eliminating bottlenecks and oversquashing (see Figure 1). Further, we will
demonstrate an efficient way to construct a family of expander graphs
(leveraging known theoretical results on the _special linear group_ ,
$\mathrm{SL}(2,\mathbb{Z}_{n})$). Once an expander graph of appropriate size
is constructed, we can perform a certain number of GNN _propagation_ steps
over its structure to globally distribute the nodes’ features. Accordingly, we
name our method _expander graph propagation_ (EGP).

A key contribution of our work extends the implications of prior art on
oversquashing via curvature analysis [19]. According to [19], negatively
curved edges are causing the oversquashing effect—yet, counterintuitively, the
edges of the expander graphs we construct will _always be negatively curved_!
We prove, however, that our expanders can never be sufficiently negatively
curved to trigger the conditions necessary for the results in [19] to be
applicable, and show that the existence of negatively curved edges might in
fact be required in order to have sparse communication without bottlenecks.

Figure 1: Left: The Cayley graph of $\mathrm{SL}(2,\mathbb{Z}_{3})$,
constructed using our method. It has $|V|=24$ nodes and it is $4$-regular
(implying $|E|=2|V|$), hence it is sparse. Despite its sparsity, it is highly
interconnected: any node is reachable from any other node by no more than $4$
hops. Hence, it can serve as a strong “template” for globally propagating node
features with a GNN. Right: The Cayley graph of
$\mathrm{SL}(2,\mathbb{Z}_{5})$, constructed in an analogous way (with
$|V|=120$ nodes). A $2$-hop neighbourhood of one node (in red) is highlighted,
demonstrating its tree-like local structure.

##  2 Related work

We begin with a survey of the many prior approaches to handling global context
in graph representation learning, evaluating them carefully against our four
desirable criteria (C1–C4; cf. Table 1). This list is by no means exhaustive,
but should be indicative of the most important directions.

Table 1: A summary of principal approaches to handling global context in graph representation learning (Section 2). “(✓)” indicates that a criterion _may_ be satisfied, depending on the method’s tradeoffs. Our proposal, the expander graph propagation (EGP) method, satisfies all four criteria. Approach | (C1) | (C2) | (C3) | (C4)
---|---|---|---|---
| (global prop.) | (no bottlenecks) | (subquadratic) | (no dedicated preproc.)
GNNs | ✗ | ✗ | ✓ | ✓
Sufficiently deep GNNs | ✓ | ✗ | ✗ | ✓
Master node [20, 4] | ✓ | ✗ | ✓ | ✓
Fully connected [18, 21, 22, 23, 24, 25] | ✓ | ✓ | ✗ | ✓
Feature aug. [26, 27, 28, 29, 30, 31] | ✓ | (✓) | (✓) | ✗
Graph rewiring [32, 19, 33] | ✓ | ✓ | ✓ | ✗
Hierarchical MP [34, 35, 36, 37, 38, 39] | ✓ | ✓ | (✓) | ✗
EGP (ours) | ✓ | ✓ | ✓ | ✓

Stacking more layers. As already highlighted, one way to achieve global
information propagation is to have a deeper GNN. In this case, we are capable
of satisfying (C1) and (C4)—no dedicated preprocessing is needed. However,
depending on the graph’s diameter, we may need up to $O(|V|)$ layers to cover
the graph, leading to quadratic complexity (violating (C3)) and introducing a
vulnerability to bottlenecks (C2), as theoretically and empirically
demonstrated in [18].

Master nodes. An attractive approach to introducing global context is to
introduce a _master node_ to the graph, and connect it to all of the graph’s
nodes. This can be done either explicitly [4] or implicitly, by storing a
“global” vector [20]. It trivially reduces the graph’s diameter to $2$,
introduces $O(1)$ new nodes and $O(|V|)$ new edges, and requires no dedicated
preprocessing, hence it satisfies (C1, C3, C4). However, these benefits come
at the expense of introducing a bottleneck in the master node: it has a very
challenging task (especially when graphs get larger) to continually
incorporate information over a very large neighbourhood in a useful way. Hence
it fails to satisfy (C2).

Fully connected graphs. The converse approach is to make _every_ node a master
node: in this case, we make all pairs of nodes connected by an edge—this was
initially proposed as a powerful method to alleviate oversquashing by [18].
This strategy proved highly popular in the recent surge of Graph Transformers
[22, 23, 25], and is common for GNNs used in physical simulation [21] or
reasoning [24] tasks. The graph’s diameter is reduced to 1, no bottlenecks
remain, and the approach does not require any dedicated preprocessing. Hence
(C1, C2, C4) are trivially satisfied. The main downside of this approach is
the introduction of $O(|V|^{2})$ edges, which means (C3) can never be
satisfied—and this approach will hence be prohibitive even for modestly-sized
graphs.

Feature augmentation. An alternative approach is to provide additional
features to the GNN which directly identify the structural role each node
plays in the graph [26]. If done properly (i.e., if the computed features are
relevant to the target), this can drastically improve expressive power. Hence,
in theory, it is possible to satisfy (C1) while not violating (C2, C3).
However, computing appropriate features requires either specific domain
knowledge, or appropriate pre-training [27, 28, 29, 30, 31], in order to
obtain such embeddings. Hence all of these gains come at the expense of
failing to satisfy (C4).

Graph rewiring. Another promising line of research involves modifying the
edges of the original graph to alleviate bottlenecks. Popular examples of this
approach involve using diffusion [32]—which diffuse additional edges through
the application of kernels such as the personalised PageRank, and stochastic
discrete Ricci flows [19]—which surgically modify a small quantity of edges to
alleviate the oversquashing effect on the nodes with negative Ricci curvature.
Recent concurrent work [33] also uses constructions inspired by expander
graphs to randomly locally rewire a given input graph. If realised carefully,
such approaches will not deviate too far from the original graph, while
provably alleviating oversquashing; hence it is possible to satisfy (C1, C2,
C3). However, this comes at a cost of having to examine the input graph
structure, with methods that do not necessarily scale easily with the number
of nodes. As such, dedicated preprocessing is needed, failing to satisfy (C4).

Hierarchical message passing. Lastly, going beyond modifying the edges, it is
also possible to introduce additional _nodes_ in the graph—each of them
responsible for a particular _substructure_ in the graph111Master nodes are a
special case: a single node is responsible for a “substructure” spanning the
entire graph.. If done carefully, it has the potential to drastically reduce
the graph’s diameter while not introducing bottlenecked nodes (hence, allowing
us to satisfy (C1, C2)). However, in prior work, a cost has to be paid for
this, usually in the need for dedicated preprocessing. Prior proposals for
hierarchical GNNs that remain scalable require a dedicated pre-processing step
[34, 35, 36], sometimes coupled with domain knowledge [36]—thus failing to
satisfy (C4). In addition, such methods may require adding prohibitively large
numbers of substructures [37, 38] or expensive pre-computation, e.g. computing
the graph Laplacian eigenvectors [39]. This might make even (C3) hard to
satisfy.

We remark that our work is not the first to study expander graph-related
topics in the context of GNNs. Specifically, the ExpanderGNN [40] leverages
expander graphs over neural network weights to sparsify the update step in
GNNs. This is a direct application of Deep Expander Networks [41], which
studied such constructs over CNNs. With respect to our contributions, neither
of these cases discuss expanders in the context of the computational graph for
a GNN, nor attempt to propagate messages over such a structure. Further,
neither satisfy all four of our desired criteria (C1–C4).

##  3 Theoretical background

We now dedicate our attention to the key theoretical results over expander
graphs, which will allow EGP to have favourable properties and be efficiently
precomputable.

######  Definition 1.

For a finite connected graph $G=(V(G),E(G))$, we consider functions $f\colon
V(G)\rightarrow\mathbb{R}$. The _Laplacian_ $Lf\colon
V(G)\rightarrow\mathbb{R}$ of such a function is defined to be

$Lf(v)=\mathrm{deg}(v)f(v)-\sum_{vw\in E(G)}f(w),$

where $\mathrm{deg}(v)$ is the degree of the vertex $v$.

The mapping $L\colon\mathbb{R}^{V(G)}\rightarrow\mathbb{R}^{V(G)}$ sending a
function $f$ to its Laplacian $Lf$ is a linear transformation. It is not hard
to show [42] that $L$ is symmetric with respect to the standard basis for
$\mathbb{R}^{V(G)}$ and positive semi-definite and hence has non-negative real
eigenvalues

$0=\lambda_{0}(G)<\lambda_{1}(G)\leq\lambda_{2}(G)\leq\dots.$

The smallest eigenvalue is $0$ and its associated eigenspace consists of the
constant functions (assuming $G$ is connected). The smallest positive
eigenvalue, $\lambda_{1}(G)$, is central to the definition of expander graphs,
as the next definition shows.

######  Definition 2.

An infinite collection $\\{G_{i}\\}$ of finite connected graphs is an
_expander family_ if there is a constant $c>0$ such that for all $G_{i}$ in
the collection, $\lambda_{1}(G_{i})\geq c$.

Expander families [43, 44, 45] have many remarkable and useful properties,
particularly when there is a uniform upper bound on the degree of the vertices
of $G_{i}$.

######  Definition 3.

Let $G$ be a finite graph. For $A\subset V(G)$, its _boundary_ $\partial A$ is
the collection of edges with one endpoint in $A$ and one endpoint not in $A$.
The _Cheeger constant_ $h(G)$ is defined to be

$h(G)=\min\left\\{\frac{|\partial A|}{|A|}:A\subset
V(G),0<|A|\leq|V(G)|/2\right\\}.$

Thus, having a small Cheeger constant is equivalent to the graph having a
‘bottleneck’, in the sense that there is a collection of edges $\partial A$
that, when removed, disconnects the vertices into two sets ($A$ and its
complement, $V(G)\setminus A$), with the property that the sizes of $A$ and
its complement are significantly larger than the size of $\partial A$.

Expander families can be reinterpreted using Cheeger constants, as follows
(see, e.g., [46, 47, 48, 49]):

######  Theorem 4.

Let $\\{G_{i}\\}$ be an infinite collection of finite connected graphs with a
uniform upper bound on their vertex degrees. Then the following are
equivalent:

  1. 1.

$\\{G_{i}\\}$ is an expander family;

  2. 2.

there is a constant $\epsilon>0$ such that for all graphs in the collection,
$h(G_{i})\geq\epsilon$.

Hence, expander graphs have higher Cheeger constants and will hence experience
less severe problems arising due to bottleneck edges. The following result is
one of the many useful properties of expander families, and it concerns their
_diameter_. It was proved by Mohar [50, Theorem 2.3]. See also [47].

######  Theorem 5.

The diameter $\mathrm{diam}(G)$ of a graph $G$ satisfies

$\mathrm{diam}(G)\leq
2\left\lceil\frac{\Delta(G)+\lambda_{1}(G)}{4\lambda_{1}(G)}\log(|V(G)|-1)\right\rceil,$

where $\Delta(G)$ is the maximal degree of any vertex of $G$. Hence, if
$\\{G_{i}\\}$ is an expander family of finite graphs with a uniform upper
bound on their vertex degrees, then there is a constant $k>0$ such that for
all graphs in the family,

$\mathrm{diam}(G_{i})\leq k\log V(G_{i}).$

Therefore, if we want to globally propagate information over an expander graph
which has $|V|$ nodes, we only need $O(\log|V|)$ propagation steps to do
so—yielding subquadratic complexity.

We showed that expanders will experience less severe problems arising due to
bottleneck edges, with favourable propagation qualities. What is missing is an
efficient method of constructing an expander of (roughly) $|V|$ nodes. To
demonstrate such a method, we leverage known results from group theory.

######  Definition 6.

A group $(\Gamma,\circ)$ is a set $\Gamma$ equipped with a _composition_
operation $\circ:\Gamma\times\Gamma\rightarrow\Gamma$ (written concisely by
omitting $\circ$, i.e. $g\circ h=gh$, for $g,h\in\Gamma$), satisfying the
following axioms:

  * •

_(Associativity)_ $(gh)l=g(hl)$, for $g,h,l\in\Gamma$.

  * •

_(Identity)_ There exists a unique $e\in\Gamma$ satisfying $eg=ge=g$ for all
$g\in\Gamma$.

  * •

_(Inverse)_ For every $g\in\Gamma$ there exists a unique $g^{-1}\in\Gamma$
such that $gg^{-1}=g^{-1}g=e$.

A group is hence a natural construct for reasoning about transformations that
leave an object invariant (unchanged). Further, we define a relevant notion of
a group’s generating set:

######  Definition 7.

Let $\Gamma$ be a group. A subset $S\subseteq\Gamma$ is a _generating set_ for
$\Gamma$ if it can be used to “generate” all of $\Gamma$ via composition.
Concretely, any element $g\in\Gamma$ can be expressed by composing elements in
the generating set, or their inverses; that is, we can express $g=s_{1}^{\pm
1}s_{2}^{\pm 1}s_{3}^{\pm 1}\cdots s_{n-1}^{\pm 1}s_{n}^{\pm 1}$ for $s_{i}\in
S$.

Now we are ready to define a Cayley graph of a group w.r.t. its generating
set.

######  Definition 8.

Let $\Gamma$ be a group with a finite generating set $S$. Then the associated
_Cayley graph_ $\mathrm{Cay}(\Gamma;S)$ has vertex set $\Gamma$ and it has an
edge $g\rightarrow gs$ for each $g\in\Gamma$ and each $s\in S$. We say that
$s$ is the _label_ on this edge. This is a potentially non-simple graph, as it
may have edges with both endpoints on the same vertex and it may have multiple
edges between a pair of vertices. In particular, when $s$ has order $2$, then
we view the edge $g\rightarrow gs$ and the edge $gs\rightarrow gs^{2}=g$ as
distinct edges.

Note that the degree of each vertex of a Cayley graph $\mathrm{Cay}(\Gamma;S)$
is $2|S|$. This is because each vertex $g$ is joined by edges to $gs$ and
$gs^{-1}$ for each $s\in S$. Thus, we shall be particularly interested in the
case where there is a uniform upper bound on $|S|$. The specific group we use
for EGP is as follows.

For each positive integer $n$, the _special linear group_
$\mathrm{SL}(2,\mathbb{Z}_{n})$ denotes the group of $2\times 2$ matrices with
entries that are integers modulo $n$ and with determinant $1$. One of its
generating sets is:

$S_{n}=\left\\{\left(\begin{matrix}1&1\\\
0&1\end{matrix}\right),\left(\begin{matrix}1&0\\\
1&1\end{matrix}\right)\right\\}.$

Central to our constructions is the following important result.

######  Theorem 9.

The family of Cayley graph $\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$
forms an expander family.

The proof uses a result of Selberg [51] who showed that the smallest positive
eigenvalue of the Laplacian of certain hyperbolic surfaces is at least $3/16$.
One can use this to a produce a lower bound on the first eigenvalue of the
Laplacian on $\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$. Full proofs
are given in [45, 44].

Lastly, it is useful to state a known result: the number of nodes of
$\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$ is:

$\left|V(\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n}))\right|=n^{3}\prod_{\text{prime
}p|n}\left(1-\frac{1}{p^{2}}\right),$ (10)

hence, it is of the order of $O(n^{3})$. We now study the local properties of
Cayley graphs in detail.

##  4 Local structure of the Cayley graphs, and the utility of negative
curvature

Recent work [19] has suggested that the local structure of the graph $G$
underlying a GNN may play an important role in the way that information
propagates around $G$. In particular, various notions of ‘Ricci curvature’
such as Forman curvature [52], Ollivier curvature [53, 54] and balanced Forman
curvature [19] have been examined. These are all local quantities, in the
sense that they depend on the structure of the graph within a small
neighbourhood of each edge. In this section, we will therefore examine the
local structure of the Cayley graphs
$G_{n}=\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$.

The various notions of curvature given above are defined for each $e$ of the
graph $G$. Since, as defined by [19], the balanced Forman curvature of an edge
depends only on local structures (i.e. triangles and squares) around that
edge, they can be determined by only observing the immediate 2-hop surrounding
of that edge. Formally, for an edge $e$ of a graph $G$, let $N_{2}(e)$ be the
induced subgraph with vertices that are at most two hops away from at least
one endpoint of $e$. Then the curvature of $e$ only depends on the isomorphism
type of $N_{2}(e)$. More specifically, if $e$ and $e^{\prime}$ are edges in
possibly distinct graphs, and there is a graph isomorphism between $N_{2}(e)$
and $N_{2}(e^{\prime})$ that sends $e$ to $e^{\prime}$, then this guarantees
that the curvatures of $e$ and $e^{\prime}$ are equal.

This situation arises prominently in the Cayley graphs that we are
considering, as follows.

######  Proposition 11.

Let $s$ be one of

$\left(\begin{matrix}1&1\\\
0&1\end{matrix}\right),\qquad\left(\begin{matrix}1&0\\\
1&1\end{matrix}\right).$

Let $n,n^{\prime}>18$ and let $e$ and $e^{\prime}$ be $s$-labelled edges in
$G_{n}$ and $G_{n^{\prime}}$. Then there is a graph isomorphism between
$N_{2}(e)$ and $N_{2}(e^{\prime})$ taking $e$ to $e^{\prime}$.

We prove Proposition 11 in Appendix A. This immediately allows us to
characterise the balanced Forman curvature and Ollivier curvature for all of
the Cayley graphs we generate:

######  Proposition 12.

The balanced Forman curvatures $\mathrm{Ric}(n)$, and the Ollivier curvatures
$\kappa(n)$ of all edges of Cayley graphs $G_{n}$ are given by:

$\mathrm{Ric}(n)=\begin{cases}0&\text{if }n=2\\\ -1/4&\text{if }n=3\\\
-1/2&\text{if }n=4\\\ -1&\text{if }n\geq
5,\end{cases}\qquad\qquad\kappa(n)=\begin{cases}0&\text{if }n=2\\\
-1/8&\text{if }n=3\\\ -1/4&\text{if }n=4\\\ -3/8&\text{if }n=5\\\
-1/2&\text{if }n\geq 6.\\\ \end{cases}$

###### Proof.

Proposition 11 implies that the balanced Forman and Ollivier curvatures are
all equal for $n>18$. Their values for $2\leq n\leq 19$ can all be empirically
computed, and are given as above. ∎

Prior work [19] suggests it is preferable for GNNs to operate on graphs with
positive Ricci curvature, whereas our graphs $G_{n}$ $(n>2)$ all have negative
Ricci curvature. However, we contend that negative Ricci curvature is not in
itself an impediment to efficient propagation around a GNN. Indeed, it was
shown in [19, Theorem 4] that poor propagation arises when the balanced Forman
curvature is close to $-2$, specifically if it is at most $-2+\delta$ for some
$\delta>0$. Here, $\delta$ is required to satisfy certain inequalities. But,
with certainty, $\delta=1$ can _never_ be satisfied in the hypotheses of [19,
Theorem 4].

Furthermore, positive Ricci curvature may have _downsides_ when used for GNNs.
One significant downside can be derived using the main result of [55], which
says that the three properties of expansion, sparsity and non-negative
Ollivier curvature are incompatible, in the following sense.

######  Theorem 13.

For any $\delta>0$ and $\Delta>0$, there are only finitely many graphs with
maximum vertex degree $\Delta$, Cheeger constant at least $\delta$ and non-
negative Ollivier curvature.

We prove Theorem 13 in Appendix B. Furthermore, quoting directly from [55]:

_“The high-level message is that on large sparse graphs, non-negative
curvature (in an even weak sense) induces extremely poor spectral expansion.
This stands in stark contrast with the traditional idea – quantified by a
broad variety of functional inequalities over the past decade – that non-
negative curvature is associated with good mixing behavior.”_

In our view, it is highly desirable that the graphs used for GNNs have high
Cheeger constants, in the sense of globally lacking bottlenecks. Having
bounded vertex degree is certainly useful too, since it implies that the
graphs will be sparse, and the nodes will not have to handle ever-increasing
neighbourhoods for message passing as graphs grow larger in size.

However, by proving Theorem 13, we showed non-negative Ollivier curvature is
_incompatible_ with these properties for sufficiently large graphs.
Specifically, given the _finite_ supply of non-negatively curved sparse
graphs, we can define $N^{\prime}$ as the largest number of nodes of such
graphs. Then, for all graphs $G$ where $|V(G)|>N^{\prime}$, we will be
_unable_ to produce a computational graph for a GNN which is non-negatively
curved everywhere. It remains an interesting challenge to provide an bound on
$N^{\prime}$ (as a function of $\delta$ and $\Delta$). It is possible that a
careful analysis of [55] may provide this.

Further, while the expander graphs we generate are negatively-curved at $-1$
everywhere, and we will empirically show this helps alleviate oversquashing,
we also believe that it is worthy of further investigation to theoretically
examine whether performance of GNNs decreases significantly when the curvature
is less than $-1$.

The negative curvature of each edge in $G_{n}$ implies that they are locally
‘tree-like’. In Appendix C, we make this statement precise by showing that
$G_{n}$ is ‘tree-like’ up to scale $c\log(n)$ about each node, for
$c\simeq(1/2)(\log((1+\sqrt{5})/2))^{-1}$ (see Figure 1 (Right) for a
schematic view).

This tree-like structure might seem, at first, to be counter-productive for
good propagation across the graphs $G_{n}$. Indeed, GNNs based on trees have
been shown to have provably poor performance [18]. The reason for this seems
to be two-fold. On the one hand, trees have small Cheeger constant. Indeed,
any tree $G$ on $n$ vertices has a Cheeger constant $1/\lfloor n/2\rfloor$,
since we may find an edge that, when removed, decomposes the graph into
subgraphs with $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ vertices. As
discussed in Section 3 and in [19], when a graph has small Cheeger constant,
its performance when used as a template for a GNN is likely to become poor.
Secondly, GNNs based on trees are susceptible to oversquashing. For a
$k$-regular infinite tree, there are $k(k-1)^{r-1}$ vertices at distance $r$
from a given vertex. Hence, if information is to be propagated at least
distance $r$ from a given vertex, then seemingly an exponential amount of
information is required to be stored.

However, neither of these issues are problematic for a GNN based on the Cayley
graph $G_{n}$. By Theorem 9, their Cheeger constants are bounded away from
$0$. Secondly, although they are tree-like locally, this is only true up to
scale $O(\log n)$. In fact, the $r$-neighbourhood of any vertex is the whole
graph $G_{n}$ as soon as $r>C\log n$, for some constant $C$, by Theorem 5.
Being tree-like up to distance $O(\log n)$ does not lead to a requirement to
store too much information as the message propagates. This is because
$k(k-1)^{r-1}$ is polynomial in $n$ when $r\leq O(\log n)$. Beyond this scale,
there exist many additional connections, which lead to many possible paths
joining any pair of vertices. The perspective of information transfer also
gives rise to another perspective in which expanders fare very favourably: the
_mixing time_ of their corresponding Markov chain (see Appendix D for
details).

##  5 Expander graph propagation

Let an input to a graph neural network be a node feature matrix ${\bf
X}\in\mathbb{R}^{|V|\times d}$, and an adjacency matrix ${\bf
A}\in\mathbb{R}^{|V|\times|V|}$. This setup is such that the feature vector of
node $u$, $\mathbf{x}_{u}\in\mathbb{R}^{d}$, can be recovered by taking an
appropriate row from ${\bf X}$. Note that the adjacency information can also
be fed in an edge-list manner, which is desirable from a scalability
perspective. Further, each edge in the graph may be endowed with additional
features rather than a single real scalar. None of the above modifications
would change the essence of our findings; we use a matrix formalism here
purely for simplicity.

There exist many ways in which the computed Cayley graph
$\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$ can be leveraged for
message propagation, and exploring these variations could be very useful for
future work. Here, we opt for a simple construction: interleave running a
standard GNN over the given input structure, followed by running another GNN
layer over the relevant Cayley graph. If we let ${\bf A}^{\text{Cay}(n)}$ be
an adjacency matrix derived from
$\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$, this implies:

${\bf H}=\mathrm{GNN}(\mathrm{GNN}({\bf X},{\bf A}),{\bf
A}^{\mathrm{Cay}(n)})$ (14)

Here, $\mathrm{GNN}$ refers to any preferred GNN layer, such as the graph
isomorphism network [56, GIN]:

$\mathbf{h}_{u}=\phi\left(\left(1+\epsilon\right)\mathbf{x}_{u}+\sum_{v\in\mathcal{N}_{u}}\mathbf{x}_{v}\right)$
(15)

where $\mathcal{N}_{u}$ is the neighbourhood of node $u$, i.e. in our setup,
the set of all nodes $v$ such that $a_{vu}\neq 0$. $\epsilon\in\mathbb{R}$ is
a learnable scalar, and
$\phi\colon\mathbb{R}^{d}\rightarrow\mathbb{R}^{d^{\prime}}$ is a two-layer
MLP.

This procedure is iterated for a certain number of steps, after which the
computed node embeddings in ${\bf H}$ can be used for any downstream task of
interest—such as node classification, link prediction or graph classification.
Note that, unlike [18], who apply their custom layer only at the _tail_ of the
architecture, we apply the expander graph immediately after each layer over
the input graph. We find that if the input graph given by ${\bf A}$ contains
bottlenecks, applying the GNN over ${\bf A}^{\text{Cay}(n)}$ only at the end
may result in oversquashing occurring before any expander graph propagation
can take place.

The setup so far assumed the number of nodes in our input graph to line up
with the Cayley graph, that is, ${\bf
A}^{\text{Cay}(n)}\in\mathbb{R}^{|V|\times|V|}$. However, there is no
guarantee that we can find an appropriate $n$ such that
$\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$ would have $|V|$ nodes.
What we can do in practice, as an approximation, is choose the smallest $n$
such that the number of nodes of
$\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$ is $\geq|V|$, then
consider ${\bf A}^{\text{Cay}(n)}_{1:|V|,1:|V|}$—i.e. only the subgraph
containing the first $|V|$ nodes in the Cayley graph.

There is a slight misalignment to our theory in this slicing choice—if the
$|V|$ vertices in this subgraph are chosen completely arbitrarily, we risk
disconnecting the graph. However, in all our experiments we construct the
Cayley graph in a breadth-first manner, starting from the identity element as
“node zero”. Hence, the node at index $i$ is always guaranteed to be reachable
from the nodes at lower indices ($j<i$), and the graph cannot be disconnected
under this construction. More interesting strategies for this step can also be
considered in the future. Note that, much like the fully connected graph used
by [18], we interpret the Cayley graph mainly as a _template_ for global
information propagation, in order to relieve bottlenecks in a scalable way.
Our interpretation, hence, assumes that the efficient diffusion of information
over the whole graph is of benefit to the learning task we perform. When this
is not the case, it might be worthwhile to construct expanders that somehow
align with the input graph, but no such expander constructions are currently
known, to the best of our knowledge. There is also a possible effect of
_stochasticity_ due to arbitrarily having to align the Cayley graph’s nodes to
the input graph—which would not appear when using master nodes or fully-
connected graphs—though our preliminary experiments did not observe any such
negative effects.

Algorithm 1 summarises the steps of our proposed EGP model. As direct
corollaries of results we proved or demonstrated, we note that EGP satisfies
all four of our desirable criteria: (C1) by Theorem 5 (so long as
logarithmically many layers are applied), (C2) by Theorem 4 (high Cheeger
constant implies no bottlenecks), (C3) by the fact our Cayley graphs are
4-regular and hence sparse, and (C4) by the fact we can generate a Cayley
graph of appropriate size without detailed analysis of the input—we may
precompute a “bank” of Cayley graphs of various sizes to use in an ad-hoc
manner.

Inputs : Node features ${\bf X}\in\mathbb{R}^{|V|\times d}$, Adjacency matrix
${\bf A}\in\mathbb{R}^{|V|\times|V|}$

Output : Node embeddings ${\bf H}$

// Choose the smallest Cayley graph from our family that has number of nodes
equal to, or greater than, $|V|$

$n\leftarrow\mathrm{argmin}_{m\in\mathbb{N}}|V(\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{m});S_{m}))|\geq|V|$;

// We can use Equation 10 to determine $n$

$G^{\mathrm{Cay}(n)}\leftarrow\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$
${\bf A}^{\mathrm{Cay}(n)}_{uv}\leftarrow\begin{cases}1&{(u,v)\in
E(G^{\mathrm{Cay}(n)})}\\\ 0&\mathrm{otherwise}\end{cases}$;

// Populate adjacency matrix of the Cayley graph

${\bf H}^{(0)}\leftarrow{\bf X}$;

// Initialise GNN inputs

for  _$t\in\\{1,\dots,T\\}$_ do

if  _$t\mod 2=0$_ then

${\bf H}^{(t)}\leftarrow\mathrm{GNN}^{(t)}({\bf H}^{(t-1)},{\bf A})$ ;

// GNN layer over input graph; e.g. Equation 15

end if

else

${\bf H}^{(t)}\leftarrow\mathrm{GNN}^{\mathrm{Cay}(t)}\left({\bf
H}^{(t-1)},{\bf A}^{\mathrm{Cay}(n)}_{1:|V|,1:|V|}\right)$;

// GNN layer over Cayley graph; e.g. Eq. 15

end if

end for

return _${\bf H}^{(T)}$_ ;

// Return final embeddings for downstream use

Algorithm 1 Expander graph propagation (EGP) forward pass

##  6 Empirical evaluation

Our work provides mainly a theoretical contribution: demonstrating a simple,
theoretically-grounded approach to relieving bottlenecks and oversquashing in
GNNs without requiring quadratic complexity or dedicated preprocessing.
Further, we prove several additional results which deepen our understanding of
curvature-based analysis of GNNs, showing how our expanders can be favourable
in spite of their negatively-curved edges. We now provide results that
empirically supplement our claim.

Tree-NeighborsMatch  We start by comparing our models on the Tree-
NeighborsMatch task (for more details, see Alon and Yahav [18, Section 4.1]).
Tree-NeighborsMatch is a synthetic benchmark explicitly designed to test a
GNN’s ability to counter oversquashing, and therefore it allows us to
empirically verify that EGP is capable of alleviating oversquashing. We
augment the original GIN implementation from the authors [18] with EGP layers,
and find that it is capable of solving the task at depth=5 at $\mathbf{100\%}$
accuracy, demonstrating alleviated oversquashing. In comparison, baseline GIN
can only achieve $29\%$ on this same task, and the best-performing GNN without
EGP—i.e. propagating over the input tree only—cannot exceed $60\%$ accuracy.

OGB Datasets  For real-world evaluation, we leverage the established Open
Graph Benchmark collection of tasks [57, OGB]. Specifically, we provide
results on all of its graph classification datasets: ogbg-molhiv, ogbg-
molpcba, ogbg-ppa and ogbg-code2. The first two are among the largest molecule
property prediction datasets in the MoleculeNet benchmark [58]. The third
dataset is concerned with classifying species into their taxa, from their
protein-protein association networks [59, 60] given as input. The fourth
dataset is a _code summarisation_ task: it requires predicting the tokens in
the name of a Python method, given the abstract syntax tree (AST) of its
implementation.

We provide a summary of important dataset statistics in Appendix E; please see
[57] for detailed information. These datasets are designed to span a wide
variety of domains (virtual drug screening, molecular activity prediction,
protein-protein interactions, code summarisation) and sizes (from small
molecules to very large syntax trees—the largest graph in ogbg-code2 has
$36,123$ nodes).

Models  In all four datasets, we want to _directly_ evaluate the empirical
gain of introducing an EGP layer and completely rule out any effects from
parameter count, or similar architectural decisions.

To enable this, we take inspiration from the experimental setup of [18]. Our
baseline model is the GIN [56], with hyperparameters as given by [57]. We use
the _official_ publicly available model implementation from the OGB authors
[57], and modify all _even_ layers of the architecture to operate over the
appropriately-sampled Cayley graph.

Note that our construction leaves both the parameter count and latent
dimension of the model _unchanged_ , hence any benefits coming from optimising
those have been diminished.

Results  The results of our evaluation are presented in Table 2. It can be
observed that, in all four cases, propagating information over the Cayley
graph yields improvements in mean performance—these improvements are most
apparent on ogbg-molhiv, but also present in ogbg-molpcba and ogbg-ppa. We
believe that these results provide encouraging empirical evidence that
propagating information over Cayley graphs is an elegant idea for alleviating
bottlenecks. We provide additional results on OGB, comparing EGP to various
other oversquashing-countering methods, in Appendix E.

Table 2: Comparative evaluation performance on the four datasets studied. Our baseline model is a GIN [56], using exactly the same implementation as in [57]. See Appendix E for ablations. Model | ogbg-molhiv | ogbg-molpcba | ogbg-ppa | ogbg-code2
---|---|---|---|---
GIN | $0.7558\pm 0.0140$ | $0.2266\pm 0.0028$ | $0.6892\pm 0.0100$ | $0.1495\pm 0.0023$
GIN + EGP | ${\bf 0.7934}\pm 0.0035$ | ${\bf 0.2329}\pm 0.0019$ | ${\bf 0.7027}\pm 0.0159$ | ${\bf 0.1497}\pm 0.0015$

##  7 Conclusion

In this paper, we have presented expander graph propagation (EGP), a novel and
elegant approach to alleviating bottlenecks in graph representation learning,
which provably supports global communication while not requiring quadratic
complexity or dedicated preprocessing of the input.

To this end, we offered a detailed theoretical overview of Cayley graphs of
special linear groups, $\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z}_{n});S_{n})$. We
cite proofs that these graphs have highly favourable properties for
information propagation in graph neural networks: they are sparse and
$4$-regular, they have logarithmic diameter, and they can be efficiently
precomputed by a simple procedure that does not rely on the input structure.
We show that, in spite of having negatively curved edges, our findings do not
violate any prior results on understanding oversquashing via curvature. Even
under a simple intervention—interleaving EGP layers inbetween standard GNN
layers—we have been able to recover significant performance returns without
changing the parameter count or latent space dimensionality.

We hope that our work serves as a foundation for further work on deploying
Cayley graphs—or other expander families—within the context of GNNs.

## Acknowledgements

We would like to thank the developers of the Open Graph Benchmark [57], whose
open-source implementations made our experiments much easier to prepare. In
addition, we are very grateful to Francesco Di Giovanni for his very
thoughtful discussions about our work and its broader implications, and
especially for bringing to our attention the important work from Salez [55].
We also thank Alex Davies, Bogdan Georgiev and Charles Blundell for reviewing
the paper prior to submission, and all of our anonymous reviewers for their
diligent feedback.

This research was conceived while all authors were visiting the Institute for
Advanced Study (IAS) in Princeton. The surreal atmosphere at the IAS strongly
stimulated the creative development of research ideas at the intersection of
machine learning and pure mathematics. We would like to thank the IAS for
kindly inviting us to visit, and hope to come again soon!

## References

  * Hamilton [2020] William L Hamilton.  Graph representation learning.  _Synthesis Lectures on Artifical Intelligence and Machine Learning_ , 14(3):1–159, 2020.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Gilmer et al. [2017] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , pages 1263–1272. PMLR, 2017.
  * Bronstein et al. [2021] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković.  Geometric deep learning: Grids, groups, graphs, geodesics, and gauges.  _arXiv preprint arXiv:2104.13478_ , 2021.
  * Veličković [2022] Petar Veličković.  Message passing all the way up.  _arXiv preprint arXiv:2202.11097_ , 2022.
  * Stokes et al. [2020] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al.  A deep learning approach to antibiotic discovery.  _Cell_ , 180(4):688–702, 2020.
  * Derrow-Pinion et al. [2021] Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, et al.  Eta prediction with graph neural networks in google maps.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 3767–3776, 2021.
  * Mirhoseini et al. [2021] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al.  A graph placement methodology for fast chip design.  _Nature_ , 594(7862):207–212, 2021.
  * Blundell et al. [2021] Charles Blundell, Lars Buesing, Alex Davies, Petar Veličković, and Geordie Williamson.  Towards combinatorial invariance for kazhdan-lusztig polynomials.  _arXiv preprint arXiv:2111.15161_ , 2021.
  * Davies et al. [2021] Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel Zheng, Nenad Tomašev, Richard Tanburn, Peter Battaglia, Charles Blundell, András Juhász, et al.  Advancing mathematics by guiding human intuition with ai.  _Nature_ , 600(7887):70–74, 2021.
  * Huang et al. [2020] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson.  Combining label propagation and simple models out-performs graph neural networks.  _arXiv preprint arXiv:2010.13993_ , 2020.
  * Tailor et al. [2021] Shyam A Tailor, Felix Opolka, Pietro Lio, and Nicholas Donald Lane.  Do we need anisotropic graph neural networks?  In _International Conference on Learning Representations_ , 2021.
  * Wu et al. [2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In _International conference on machine learning_ , pages 6861–6871. PMLR, 2019.
  * Duvenaud et al. [2015] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  _Advances in neural information processing systems_ , 28, 2015.
  * Errica et al. [2019] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli.  A fair comparison of graph neural networks for graph classification.  _arXiv preprint arXiv:1912.09893_ , 2019.
  * Luzhnica et al. [2019] Enxhell Luzhnica, Ben Day, and Pietro Liò.  On graph classification networks, datasets and baselines.  _arXiv preprint arXiv:1905.04682_ , 2019.
  * Alon and Yahav [2020] Uri Alon and Eran Yahav.  On the bottleneck of graph neural networks and its practical implications.  _arXiv preprint arXiv:2006.05205_ , 2020.
  * Topping et al. [2021] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein.  Understanding over-squashing and bottlenecks on graphs via curvature.  _arXiv preprint arXiv:2111.14522_ , 2021.
  * Battaglia et al. [2018] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al.  Relational inductive biases, deep learning, and graph networks.  _arXiv preprint arXiv:1806.01261_ , 2018.
  * Battaglia et al. [2016] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al.  Interaction networks for learning about objects, relations and physics.  _Advances in neural information processing systems_ , 29, 2016.
  * Kreuzer et al. [2021] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou.  Rethinking graph transformers with spectral attention.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Mialon et al. [2021] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal.  Graphit: Encoding graph structure in transformers.  _arXiv preprint arXiv:2106.05667_ , 2021.
  * Santoro et al. [2017] Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap.  A simple neural network module for relational reasoning.  _Advances in neural information processing systems_ , 30, 2017.
  * Ying et al. [2021] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform badly for graph representation?  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Bouritsas et al. [2022] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864, 2016.
  * Perozzi et al. [2014] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 701–710, 2014.
  * Tang et al. [2015] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  Line: Large-scale information network embedding.  In _Proceedings of the 24th international conference on world wide web_ , pages 1067–1077, 2015.
  * Thakoor et al. [2021] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko.  Large-scale representation learning on graphs via bootstrapping.  In _International Conference on Learning Representations_ , 2021.
  * Veličković et al. [2018] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  _arXiv preprint arXiv:1809.10341_ , 2018.
  * Gasteiger et al. [2019] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann.  Diffusion improves graph learning.  _arXiv preprint arXiv:1911.05485_ , 2019.
  * Banerjee et al. [2022] Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar.  Oversquashing in gnns through the lens of information contraction and graph expansion.  _arXiv preprint arXiv:2208.03471_ , 2022.
  * Bodnar et al. [2021a] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein.  Weisfeiler and lehman go cellular: Cw networks.  _Advances in Neural Information Processing Systems_ , 34:2625–2640, 2021a.
  * Bodnar et al. [2021b] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein.  Weisfeiler and lehman go topological: Message passing simplicial networks.  In _International Conference on Machine Learning_ , pages 1026–1037. PMLR, 2021b.
  * Fey et al. [2020] Matthias Fey, Jan-Gin Yuen, and Frank Weichert.  Hierarchical inter-message passing for learning on molecular graphs.  _arXiv preprint arXiv:2006.12179_ , 2020.
  * Morris et al. [2020] Christopher Morris, Gaurav Rattan, and Petra Mutzel.  Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.  _Advances in Neural Information Processing Systems_ , 33:21824–21840, 2020.
  * Morris et al. [2019] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 4602–4609, 2019.
  * Stachenfeld et al. [2020] Kimberly Stachenfeld, Jonathan Godwin, and Peter Battaglia.  Graph networks with spectral message passing.  _arXiv preprint arXiv:2101.00079_ , 2020.
  * Lutzeyer et al. [2021] Johannes F Lutzeyer, Changmin Wu, and Michalis Vazirgiannis.  Sparsifying the update step in graph neural networks.  _arXiv preprint arXiv:2109.00909_ , 2021.
  * Prabhu et al. [2018] Ameya Prabhu, Girish Varma, and Anoop Namboodiri.  Deep expander networks: Efficient deep networks from graph theory.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 20–35, 2018.
  * Chung [1997] Fan R. K. Chung.  _Spectral graph theory_ , volume 92 of _CBMS Regional Conference Series in Mathematics_.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.  ISBN 0-8218-0315-8.
  * Lubotzky [1994] Alexander Lubotzky.  _Discrete groups, expanding graphs and invariant measures_ , volume 125 of _Progress in Mathematics_.  Birkhäuser Verlag, Basel, 1994.  ISBN 3-7643-5075-X.  doi: 10.1007/978-3-0346-0332-4.  URL https://doi.org/10.1007/978-3-0346-0332-4.  With an appendix by Jonathan D. Rogawski.
  * Davidoff et al. [2003] Giuliana Davidoff, Peter Sarnak, and Alain Valette.  _Elementary number theory, group theory, and Ramanujan graphs_ , volume 55 of _London Mathematical Society Student Texts_.  Cambridge University Press, Cambridge, 2003.  ISBN 0-521-82426-5; 0-521-53143-8.  doi: 10.1017/CBO9780511615825.  URL https://doi.org/10.1017/CBO9780511615825.
  * Kowalski [2019] Emmanuel Kowalski.  _An introduction to expander graphs_ , volume 26 of _Cours Spécialisés [Specialized Courses]_.  Société Mathématique de France, Paris, 2019.  ISBN 978-2-85629-898-5.
  * Alon [1986] N. Alon.  Eigenvalues and expanders.  volume 6, pages 83–96. 1986.  doi: 10.1007/BF02579166.  URL https://doi.org/10.1007/BF02579166.  Theory of computing (Singer Island, Fla., 1984).
  * Alon and Milman [1985] N. Alon and V. D. Milman.  $\lambda_{1},$ isoperimetric inequalities for graphs, and superconcentrators.  _J. Combin. Theory Ser. B_ , 38(1):73–88, 1985\.  ISSN 0095-8956.  doi: 10.1016/0095-8956(85)90092-9.  URL https://doi.org/10.1016/0095-8956(85)90092-9.
  * Dodziuk [1984] Jozef Dodziuk.  Difference equations, isoperimetric inequality and transience of certain random walks.  _Trans. Amer. Math. Soc._ , 284(2):787–794, 1984\.  ISSN 0002-9947.  doi: 10.2307/1999107.  URL https://doi.org/10.2307/1999107.
  * Tanner [1984] R. Michael Tanner.  Explicit concentrators from generalized $N$-gons.  _SIAM J. Algebraic Discrete Methods_ , 5(3):287–293, 1984.  ISSN 0196-5212.  doi: 10.1137/0605030.  URL https://doi.org/10.1137/0605030.
  * Mohar [1991] Bojan Mohar.  Eigenvalues, diameter, and mean distance in graphs.  _Graphs Combin._ , 7(1):53–64, 1991.  ISSN 0911-0119.  doi: 10.1007/BF01789463.  URL https://doi.org/10.1007/BF01789463.
  * Selberg [1965] Atle Selberg.  On the estimation of Fourier coefficients of modular forms.  In _Proc. Sympos. Pure Math., Vol. VIII_ , pages 1–15. Amer. Math. Soc., Providence, R.I., 1965.
  * Forman [2003] R Forman.  Discrete and computational geometry.  2003\.
  * Ollivier [2007] Yann Ollivier.  Ricci curvature of metric spaces.  _Comptes Rendus Mathematique_ , 345(11):643–646, 2007.
  * Ollivier [2009] Yann Ollivier.  Ricci curvature of markov chains on metric spaces.  _Journal of Functional Analysis_ , 256(3):810–864, 2009.
  * Salez [2021] Justin Salez.  Sparse expanders have negative curvature.  _arXiv preprint arXiv:2101.08242_ , 2021.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Hu et al. [2020] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ , 33:22118–22133, 2020.
  * Wu et al. [2018] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande.  Moleculenet: a benchmark for molecular machine learning.  _Chemical science_ , 9(2):513–530, 2018.
  * Szklarczyk et al. [2019] Damian Szklarczyk, Annika L Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta-Cepas, Milan Simonovic, Nadezhda T Doncheva, John H Morris, Peer Bork, et al.  String v11: protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets.  _Nucleic acids research_ , 47(D1):D607–D613, 2019\.
  * Zitnik et al. [2019] Marinka Zitnik, Rok Sosič, Marcus W Feldman, and Jure Leskovec.  Evolution of resilience in protein interactomes across the tree of life.  _Proceedings of the National Academy of Sciences_ , 116(10):4426–4433, 2019.
  * Margulis [1982] Grigorii A Margulis.  Explicit constructions of graphs without short cycles and low density codes.  _Combinatorica_ , 2(1):71–78, 1982.
  * Serre [2002] Jean-Pierre Serre.  _Trees_.  Springer Science & Business Media, 2002.

##  Appendix A Proof of Proposition 11

_Let $s$ be one of_

$\left(\begin{matrix}1&1\\\
0&1\end{matrix}\right),\qquad\left(\begin{matrix}1&0\\\
1&1\end{matrix}\right).$

_Let $n,n^{\prime}>18$ and let $e$ and $e^{\prime}$ be $s$-labelled edges in
$G_{n}$ and $G_{n^{\prime}}$. Then there is a graph isomorphism between
$N_{2}(e)$ and $N_{2}(e^{\prime})$ taking $e$ to $e^{\prime}$._

###### Proof.

Note first that, by the homogeneity of the Cayley graphs $G_{n}$ and
$G_{n^{\prime}}$, we may assume that $e$ and $e^{\prime}$ emanate from the
identity vertex of each graph.

Let $G_{\infty}$ be the Cayley graph of $\mathrm{SL}(2,\mathbb{Z})$ with
respect to the generators

$S_{\infty}=\left\\{\left(\begin{matrix}1&1\\\
0&1\end{matrix}\right),\left(\begin{matrix}1&0\\\
1&1\end{matrix}\right)\right\\}.$

Let $e_{\infty}$ be the $s$-labelled edge emanating from the identity vertex
of $G_{\infty}$. The quotient homomorphism

$\mathrm{SL}(2,\mathbb{Z})\rightarrow\mathrm{SL}(2,\mathbb{Z}_{n})$

induces a graph homomorphism $G_{\infty}\rightarrow G_{n}$ sending
$e_{\infty}$ to $e$. We will show that it restricts to a graph isomorphism

$N_{2}(e_{\infty})\rightarrow N_{2}(e).$

As there is a similar graph isomorphism $N_{2}(e_{\infty})\rightarrow
N_{2}(e^{\prime})$, the proposition will follow.

Note that two elements of $\mathrm{SL}(2,\mathbb{Z})$ map to the same element
of $\mathrm{SL}(2,\mathbb{Z}_{n})$ if and only if they differ by
multiplication by an element of the kernel $K_{n}$. This is

$K_{n}=\left\\{\left(\begin{matrix}a&b\\\
c&d\end{matrix}\right)\in\mathrm{SL}(2,\mathbb{Z}):a\equiv d\equiv 1\text{ mod
}n\text{ and }b\equiv c\equiv 0\text{ mod }n\right\\}.$

The graph homomorphism sends edges to edges, and so it is distance non-
increasing. Hence it certainly sends $N_{2}(e_{\infty})$ to $N_{2}(e)$. It is
also clearly surjective, because any element of $N_{2}(e)$ is reached from an
endpoint of $e$ by a path of length at most $2$, and there is a corresponding
path in $N_{2}(e_{\infty})$.

We just need to show that this is an injection. If not, then two distinct
vertices $g_{1}$ and $g_{2}$ in $N_{2}(e_{\infty})$ map to the same vertex in
$N_{2}(e)$. Note then that as elements of $\mathrm{SL}(2,\mathbb{Z})$,
$g_{2}=g_{1}k$ for some $k\in K_{n}$. There are paths with length at most $3$
joining the identity $1$ to $g_{1}$ and $g_{2}$ respectively. Hence, the
distance in $G_{\infty}$ between $g_{1}$ and $g_{2}$ is at most $6$.
Therefore, the distance between $1$ and $g_{1}^{-1}g_{2}$ is at most $6$. This
element $g_{1}^{-1}g_{2}$ lies in $K_{n}$. We will show that when $n>18$, the
only element of $K_{n}$ that has distance at most $6$ from the identity is the
identity itself. This will imply that $g_{1}^{-1}g_{2}=1$ and hence
$g_{1}=g_{2}$. But this contradicts the assumption that $g_{1}$ and $g_{2}$
are distinct vertices. Our argument follows that of [61].

The operator norm $||A||$ of a matrix $A\in\mathrm{SL}(2,\mathbb{Z})$ is

$||A||=\sup\\{|A(v)|:v\in\mathbb{R}^{2},\,|v|=1\\}.$

This is submultiplicative: $||AB||\leq||A||\,||B||$ for matrices $A$ and $B$.
It can be calculated as the square root of the largest eigenvalue of $A^{t}A$.
In our case, the operator norms satisfy

$\left\|\left(\begin{matrix}1&1\\\
0&1\end{matrix}\right)\right\|=\left\|\left(\begin{matrix}1&0\\\
1&1\end{matrix}\right)\right\|=\frac{1+\sqrt{5}}{2}.$

Consider an element

$K=\left(\begin{matrix}a&b\\\ c&d\end{matrix}\right)$

of $K_{n}$ that is not the identity. Since $a\equiv d\equiv 1$ modulo $n$ and
$b\equiv c\equiv 0$ modulo $n$, we deduce that at least one $|a|$, $|b|$,
$|c|$ and $|d|$ is at least $n-1$. Therefore, this matrix acts on one of the
vectors $(1,0)^{t}$ or $(0,1)^{t}$ by scaling its length by at least $n-1$.
Therefore, $||K||\geq n-1$. Suppose now that $K$ has distance at most $6$ from
the identity. Then $K$ can be written as a word in the generators of
$\mathrm{SL}(2,\mathbb{Z})$ with length at most $6$. Therefore, we obtain the
inequality

$||K||\leq\left(\frac{1+\sqrt{5}}{2}\right)^{6}<17.95.$

Hence, $n<18.95$ and therefore, as $n$ is integral, $n\leq 18$. ∎

##  Appendix B Proof of Theorem 13

_For any $\delta>0$ and $\Delta>0$, there are only finitely many graphs with
maximum vertex degree $\Delta$, Cheeger constant at least $\delta$ and non-
negative Ollivier curvature._

###### Proof.

This is a consequence of the main result of Salez [55, Theorem 3]. This states
if $G_{n}=(V_{n},E_{n})$ is a sequence of graphs with the following
properties:

$\sup_{n\geq 1}\left\\{\frac{1}{|V_{n}|}\sum_{v\in
V_{n}}\mathrm{deg}(v)\log\mathrm{deg}(v)\right\\}<\infty$ (16)
$\forall\epsilon>0,\quad\frac{1}{|E_{n}|}|\\{e\in
E_{n}:\kappa(e)<-\epsilon\\}|\rightarrow 0\text{ as }n\rightarrow\infty,$ (17)

then

$\forall\rho<1,\quad\liminf_{n\rightarrow\infty}\left\\{\frac{1}{|V_{n}|}|\\{i:\mu_{i}(G_{n})\geq\rho\\}|\right\\}>0.$

Here, $\kappa(e)$ is the Ollivier curvature of an edge $e$ and

$1=\mu_{0}(G)\geq\mu_{1}(G)\geq\dots\geq 0$

are the eigenvalues of the lazy random walk operator. To prove the theorem, we
suppose that on the contrary, there are infinitely many distinct graphs
$G_{n}=(V_{n},E_{n})$ with maximum vertex degree $\Delta$, Cheeger constant at
least $\delta$ and non-negative Olliver curvature. Then

$\sum_{v\in
V_{n}}\mathrm{deg}(v)\log\mathrm{deg}(v)\leq|V_{n}|\Delta\log\Delta$

and so condition 16 is satsfied. Condition 17 is trivially satisfied because
the Ollivier curvature of each graph is non-negative. Thus, we deduce that the
conclusion of Salez’ theorem holds. Setting $\rho=1-(\delta^{2}/4\Delta^{2})$,
we deduce that a definite proportion of the eigenvalues of the lazy random
walk operator are at least $1-(\delta^{2}/4\Delta^{2})$. In particular,
$\mu_{1}(G_{n})\geq 1-(\delta^{2}/4\Delta^{2})$. Denote the eigenvalues of the
normalised Laplacian by

$0=\lambda^{\prime}_{0}(G_{n})\leq\lambda^{\prime}_{1}(G_{n})\leq\dots$

These are related to the eigenvalues of the lazy random walk operator by
$\lambda^{\prime}_{i}(G_{n})=2-2\mu_{i}(G_{n})$. Hence,
$\lambda^{\prime}_{1}(G_{n})\leq\delta^{2}/(2\Delta^{2})$. There is a
variation of Cheeger’s inequality that relates $\lambda^{\prime}_{1}$ to the
_conductance_ of the graph. To define this, one considers subsets $A$ of the
vertex set, and defines their _volume_ to be $\mathrm{vol}(A)=\sum_{v\in
A}\mathrm{deg}(v)$. The conductance $\phi(G)$ of a graph $G$ is

$\phi(G)=\min\left\\{\frac{|\partial A|}{\mathrm{vol}(A)}:A\subset
V(G),\,0<\mathrm{vol}(A)\leq\mathrm{vol}(V(G))/2\right\\}.$

Then, by Chung [42, Theorem 2.2],

$\phi(G)\leq\sqrt{2\lambda^{\prime}_{1}(G)}$

Hence, in our case,

$\phi(G_{n})\leq\delta/\Delta.$

Consider any subset $A_{n}$ of the vertex set that realises $\phi(G_{n})$.
Thus $0<\mathrm{vol}(A_{n})\leq\mathrm{vol}(V_{n})/2$ and $|\partial
A_{n}|/\mathrm{vol}(A_{n})=\phi(G_{n})\leq\delta/\Delta$. If $A_{n}$ is at
most half the vertices of $G_{n}$, then this implies that the Cheeger constant
$h(G_{n})\leq\delta$. On the other hand, if $A_{n}$ is more than half the
vertices of $G_{n}$, we consider its complement $A_{n}^{c}$. Its cardinality
$|A_{n}^{c}|$ satisfies

$|A_{n}^{c}|\geq\mathrm{vol}(A_{n}^{c})/\Delta.$

Hence,

$h(G_{n})\leq\frac{|\partial A^{c}_{n}|}{|A^{c}_{n}|}\leq\frac{|\partial
A_{n}|\Delta}{\mathrm{vol}(A^{c}_{n})}\leq\frac{|\partial
A_{n}|\Delta}{\mathrm{vol}(A_{n})}=\phi(G_{n})\Delta\leq\delta.$

In either case, we deduce that the Cheeger constant of $G_{n}$ is at most
$\delta$, contradicting one of our hypotheses. Hence, there must have been
only finitely many graphs satisfying the conditions of the theorem. ∎

##  Appendix C Cayley graph at infinity is quasi-isometric to a tree

As all vertices of $G_{n}$ look the same, we focus attention on $N_{r}(1)$,
the $r$-neighbourhood of the identity vertex. The proof of Proposition 11
immediately gives the following.

######  Proposition 18.

Let $r$ be a positive integer satisfying

$r<\frac{1}{2}\left(\log\left(\frac{1+\sqrt{5}}{2}\right)\right)^{-1}\log(n-1).$

Then there is a graph isomorphism between the $r$-neighbourhood of the
identity vertex in $G_{n}$ and the $r$-neighbourhood of the identity vertex in
$G_{\infty}$. This isomorphism takes the identity vertex to the identity
vertex.

###### Proof.

As shown in the proof of Proposition 11, there is a graph homomorphsm from
$N_{r}(1)$ in $G_{\infty}$ to $N_{r}(1)$ in $G_{n}$ that is a surjection. If
it fails to be an injection, then there is a non-trivial element $K$ in the
kernel $K_{n}$ of
$\mathrm{SL}(2,\mathbb{Z})\rightarrow\mathrm{SL}(2,\mathbb{Z}_{n})$ satisfying

$||K||\leq\left(\frac{1+\sqrt{5}}{2}\right)^{2r}.$

But any non-trivial element $K$ in $K_{n}$ satisfies

$||K||\geq n-1.$

Rearranging gives the required inequality. ∎

This raises the question of the local structure of $G_{\infty}$. The answer is
well-known: it is ‘tree-like’. Specifically, it is quasi-isometric to a tree.
The formal definition of quasi-isometry is as follows.

######  Definition 19.

A _quasi-isometry_ between two metric spaces $(X_{1},d_{1})$ and
$(X_{2},d_{2})$ is a function $f\colon X_{1}\rightarrow X_{2}$ that satisfies
the following two conditions:

  1. 1.

there are constants $c,C>0$ such that, for every $x,x^{\prime}\in X_{1}$

$c\,d_{1}(x,x^{\prime})-c\leq d_{2}(f(x),f(x^{\prime}))\leq
C\,d_{1}(x,x^{\prime})+C,$

  2. 2.

there is a constant $K\geq 0$ such that for every $y\in X_{2}$, there is an
$x\in X_{1}$ with $d_{2}(f(x),y)\leq K$.

If there is such a quasi-isometry, we say that $(X_{1},d_{1})$ and
$(X_{2},d_{2})$ are _quasi-isometric_.

This forms an equivalence relation on metric spaces. When two metric spaces
are quasi-isometric, they are viewed as being ‘essentially the same’ at large
scales.

When $S$ and $S^{\prime}$ are finite generating sets for a group $\Gamma$, the
graphs $\mathrm{Cay}(\Gamma;S)$ and $\mathrm{Cay}(\Gamma;S^{\prime})$ are
quasi-isometric. Hence, the quasi-isometry type of a finitely generated group
is well-defined, and this is the central object of study in geometric group
theory.

The group $\mathrm{SL}(2,\mathbb{Z})$ has a finite-index subgroup that is a
free group $F$ [62]. If $S^{\prime}$ denotes a free generating set for $F$,
then $\mathrm{Cay}(F;S^{\prime})$ is a tree. As passing to a finite-index
subgroup preserves its quasi-isometry class, we deduce that the Cayley graph
$G_{\infty}=\mathrm{Cay}(\mathrm{SL}(2,\mathbb{Z});S_{\infty}))$ is indeed
quasi-isometric to a tree, as claimed above.

##  Appendix D Mixing time properties of expander graphs

Expanders are well known to have small mixing time, in the following sense.

Let $G$ be a graph. We will consider probability distributions $\pi$ on
$V(G)$. The lazy random walk operator $M$ acts on probability distributions as
follows. We think of $\pi(v)$ as being the probability of the random walk
being at vertex $v$. If the current location of the walk is at $v$, then at
the next step of the walk, either we stay put with probability $1/2$ or we
move to one of its neighbours with equal probability. Then $M\pi$ is the new
probability distribution.

In the case when $G$ is $k$-regular, this takes a particular simple form. The
operator $M$ is represented by the matrix $(1/2)I+(1/2k)A$, where $A$ is the
adjacency matrix. In that case, any initial distribution $\pi$ converges under
powers of $M$ to the uniform distribution.

This is true for any reasonable notion of convergence, but we will use the
$\|\cdot\|_{1}$ norm, where for two probability distributions $\pi$ and
$\pi^{\prime}$,

$\big{\|}\pi-\pi^{\prime}\big{\|}_{1}=\sum_{v\in
V(G)}|\pi(v)-\pi^{\prime}(v)|.$

######  Definition 20.

The _mixing time_ for a regular graph $G$ is the minimum value of $\ell$ such
that for any starting probability distribution $\pi$ on the vertex set of $G$,

$\big{\|}M^{\ell}\pi-u\big{\|}_{1}\leq\frac{1}{4}.$

Here, $u$ is the uniform probability distribution on the vertex set, and $M$
is the lazy random walk operator.

Expanders have small mixing times in the following very strong sense.

######  Theorem 21.

For any $k>0$ and $\delta>0$, there is a constant $c>0$ with the following
property. If $G$ is a connected $k$-regular graph on $n$ vertices with Cheeger
constant at least $\delta>0$, then the mixing time for $G$ is at most
$c\log(n)$.

##  Appendix E Additional experimental details and ablations

### OGB dataset statistics

We provide additional details on the dataset statistics for the OGB tasks we
used in Table 3. More substantial details can be found in the OGB paper [57].

Table 3: Statistics of the three graph classification datasets studied in our evaluation. Name | Number of graphs | Avg. nodes/graph | Avg. edges/graph | Metric
---|---|---|---|---
ogbg-molhiv | $41,127$ | $25.5$ | $27.5$ | ROC-AUC
ogbg-molpcba | $437,929$ | $26.0$ | $28.1$ | Avg. precision
ogbg-ppa | $158,100$ | $243.4$ | $2,266.1$ | Accuracy
ogbg-code2 | $452,741$ | $125.2$ | $124.2$ | F1 score

### Ablations on propagation graph.

Our work concerns sparse expander graphs, determined using the Cayley graphs
of the special linear group. We acknowledge that this approach, while
theoretically beneficial, is not the only possible way to aid global
information propagation in a GNN. Therefore, in this subsection we compare
against other classes of approaches.

Our additional baseline methods include: GINs with a _master node_ , GINs with
a _fully connected_ layer (FA), as done in Alon and Yahav [18], and GINs with
applying a recently proposed rewiring method, G-RLEF [33].

Note that both the FA method and G-RLEF have motivations related to expanders:
the fully-connected graph in the FA method is a trivial _dense_ expander,
whereas G-RLEF’s rewiring iterations can converge to an expander for certain
input graph distributions. Therefore, comparing against these methods allows
us to also evaluate the impacts of expander density, as well as proximity to
the input graph (since G-RLEF iteratively modifies the input graph). We run
G-RLEF for $O(V)$ steps.

The results of our ablative analysis are summarised in Table 4. We find that,
as expected, all of our added methods outperform the baseline GIN,
demonstrating that oversquashing had been alleviated. When comparing them
against each other, however, we find that EGP tends to be highly competitive
on two out of the three datasets considered (having the largest average
overall). The fully-adjacent dense expander method remains strong on both
ogbg-molhiv and ogbg-molpcba, but runs out of memory as graphs increase in
size (as is the case with ogbg-ppa).

We find that this collection of ablation studies further supplements the
analysis of EGP we have conducted, and serves as a good starting point for
further investigations of expander propagation templates with various
properties.

Table 4: Comparative ablation performance of various propagation templates on ogbg-molhiv, ogbg-molpcba and ogbg-ppa. Our baseline model is a GIN [56], using exactly the same implementation as in [57]. All models have _exactly_ the same number of parameters—we only modify the connectivity in certain layers depending on the scheme. N.B. The fully-connected graph, used in the FA approach [18] can be seen as a dense expander graph, i.e. a special case of EGP. ’OOT’ indicates that the method failed to approach baseline performance within five days of training time (while not converging within this time), and ’OOM’ indicates out-of-memory (on a V100 GPU). Model | ogbg-molhiv | ogbg-molpcba | ogbg-ppa
---|---|---|---
GIN | $0.7558\pm 0.0140$ | $0.2266\pm 0.0028$ | $0.6892\pm 0.0100$
GIN + master node | $0.7668\pm 0.0096$ | $0.2527\pm 0.0064$ | $0.6916\pm 0.0154$
GIN + FA [18] | $0.7850\pm 0.0090$ | ${\bf 0.2595}\pm 0.0049$ | OOM
GIN + G-RLEF [33] | $0.7802\pm 0.0024$ | OOT | OOM
GIN + EGP (ours) | ${\bf 0.7934}\pm 0.0035$ | $0.2329\pm 0.0019$ | ${\bf 0.7027}\pm 0.0159$