Graph Neural Networks as Gradient Flows
Authors: Francesco Di Giovanni
James Rowbottom
Benjamin Paul Chamberlain
Thomas Markovich
Michael M. Bronstein
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Graph Neural Networks
Spectral analysis
Over-smoothing
Energy
Differential equations

Abstract: Dynamical systems minimizing an energy are ubiquitous in geometry and physics. We propose a gradient flow framework for GNNs where the equations follow the direction of steepest descent of a learnable energy. This approach allows to analyse the GNN evolution from a multi-particle perspective as learning attractive and repulsive forces in feature space via the positive and negative eigenvalues of a symmetric `channel-mixing' matrix. We perform spectral analysis of the solutions and conclude that gradient flow graph convolutional models can induce a dynamics dominated by the graph high frequencies which is desirable for heterophilic datasets. We also describe structural constraints on common GNN architectures allowing to interpret them as gradient flows. We perform thorough ablation studies corroborating our theoretical analysis and show competitive performance of simple and lightweight models on real-world homophilic and heterophilic datasets.

We propose Gradient Flow Framework (GRAFF) where the GNN equations follow the direction of steep- 24 est descent a learnable energy. Thanks to this framework we can Graph Neural Networks as Gradient Flows
Anonymous Author(s) Affiliation Address
email
Abstract
1
Dynamical systems minimizing an energy are ubiquitous in geometry and physics. We propose gradient flow framework GNNs where the equations follow the direction steepest descent a learnable energy. This approach allows to analyse the GNN evolution from a palti-particl perspective as learning attractive and repulsive forces in feature space via the positive and negative eigenvalues symmetric 'channel-mixine and conclude that gradient flow graph convolutional models can induce a dynamics dominated by the graph high frequencies, which is desirable for heterophilic datasets. We also describe structural constraints on common GNN architectures allowing to interpret them as gradient flows. We perform thorough ablation studies corroborating our theoretical unalysis and show competitive performance of simple and lightweight models on real-world homophilic and hetcrophilic datasets.
2
3
5
6
matrix. We perform spectral analysis of the solutions
7
8.
1 Introduction and motivations
14 Graph neural networks (GNNs) 38 20 21
7 15 27) and particular their Message Passing 15 formulation (MPNN) 19 have hecome the standard MI. tool for dealing with different types
36
16 relations and interactions, ranging from social networks to partiele physics and drug design. One
17 of the often cited drawbacks of traditional GNN models is their poor 'explainability' making it
18 hard to know why and how they make certain predictions [4 47), and in which situations they may work and when they would fail. Limitations of GNNs that have attracted attention are over-
20
smoothing (29 (3 8 over-squashing and bottlenecks [I] 40 and performance on heterophilic data
21
31
ST 13 4 45
where adjacent nodes usually have different labels.
22
Contributions.
23
25 (i) interpret GNNs as a multi-partich dynamics where the learned
28 parameters determine pairwise attractive and repulsive potentials
27 in the feature space. This sheds light on how GNNs can adapt to
28 heterophily and explains their performance and the smoothness of the prediction. (ii) FF leads to residual convolutional models where the charmel-mixing W is performed by a shared symmet- ric bilincar form inducing attraction and repulsion via its positive and negative eigenvalues, respectively. We theoretically investi- gate the interaction of the graph spectrum with the spectrum of the channel-mise mixing, proving that if there is more mass on the negative eigenvalues of W. then the dynamics is dominated by the graph- high frequencies, which could be desirable on heterophilic graphs. We also extend results of 229 8 by showing that when we drop the residual connection intrinsic the gradient flow framework,
Figure 1: GRAFF dynamics: attractive and repulsive forees lead non-smoothing pro- cess able separate labels.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

graph convolutional models always induce a low-freqeyncy dominated dynamics independent of the sign and magnitude the spectrum of the channel-mixing. We also discuss how simple choices make common architectures fit GRAFF and conduct thorough ablation studies corroborate the the- oretical analysis on role of the spectrum of W. (iii) We crystallize an instance of our framework into linear, residual, convolutional model that achieves competitive performance on homophilic and heterophilic real world graphs whilst being faster than GCN.
Related work. Our analysis is related to studying GNNs as filters on the graph spectrum [ [25] and over-smoothing (29 BC 8 55 and partly adopts techniques similar to 30] The key difference is that we also consider the spectrum of the 'chameel-mixing matrix. The concept of
15
24
gradient flows has been a standard tool in physics and geometry [T6]. from which they were udopted
for image processing [26), and recently used in ML [35] for the analysis of Transformers + see also [T8] for discussion of loss landscupes. Our continuous-time evolution equations follows the spirit
of Neural ODES 22 12 3 and the study of GNNs as continuous dynamical systems 44 TO 17
52 Outline. In Section 2 we review the continuous and discrete Dirichlet energy and the associated gradient flow framework. We formalize the notion of over-smoothing and low(hiig)-frqqunncyy frequency- dominated dynamicy to investigate GNNs and study the dominant components in their evolution. We 55 extend the graph Dirichlet energy to allow for a non non-trive trivirivill norm for the feature edge-gradient This
53
54
55 leads to gradient flow equations that diffuse the features and over-smooth in the limit. Accordingly.
57 in Section we introduce a more general energy with a symmetric channel- mixxing matrix W giving
58 rise to attractive and repulsive pairwise terms via its positive and negative eigenvalues and show dynamics. In Section 4 we first 60 compare with continuous GNN models and then discretize the equations and provide a 'recipe' for
50 that the negative spectrum can induce geth-frequenc--domiiee
61 making standard GNN architectures fit a gradient flow framework. We udapt the spectral analysis to discrete-time showing that gradient flow convolutional models can generate a dynamics dominated by
63 the high frequencies via the negative eigenvalucs of W while this is impossible if we drop the residual connection. In Section S we corroborate our thcoretical analysis on the role of the spectrum of W via ablation studies on graphs with varying homophily. Experiments on real world datasets show competitive performance of our model despite its simplicity and reduced number of parameters.
2 Gradient- flow formalism
Notations adopted throughout the paper. Let EV, he undirected graph with nodes. 69 We denote by F E geod the matrix of d-dimensional node features, by f; E Rd its i-th row
70 (transposed), by I" E I2" its r-th column, and by vec(F) E Rnd the vectorization of F obtained 71 by stacking its columns. Given a symmetric matrix B, we let A__ X denote its most positive and
72 negative eigenvalues, respectively, and PB be its spectral radius. If 2 0, then gBp(B) denotes the positive smallest eigenvalue of B. f(t)) denotes the temporal derivative, and 'a.e.' means almost every w.r.t. Lebesgue measure and usually refers data the complement of some lower dimensional subspace in Rexd, Proofs and additional results appear in the Appendix.
the Kronecker product
78 Starting point: geometric parallelism. To motivate gradient-flow flow approach for GNNs, we start 77 from the continuous case (see Appendix A. for details). Consider a smonth map f RR + (R. h)
with I constant metric represented by H Hz0
0. The Dirichlet energy of / is defined by
h(f.h) = 1
|VS du
Σ q.r=1
O (a)dd
and measures 'smoothness" of f. natural approach find minimizers of E called harmonic 80 maps was introduced (16] and consists in studying the gradient flow of ε, wherein a given map
81 f(0) = fo is evolved according to f(t = (()(f(t)) These type of evolution equations have historically been the core of variational and PDE-based image processing; in particular, gradicnt
63 flows of the Dirichlet energy were shown (26) to recnver the Perona-Mas Malik nonlinear diffusion 33]
84 Motivation: GNNs for node-clasiffcation. We wish to extend the gradient flow formalism to node classification on graphs Assume we have graph G. node-fcatures Fo and lahels (ur) Viratn C V, 86 and that we want predict the labels on Vieaa C V. A GNN typically evolves the features via some
2

---

parametric rule, (GN Fo). and uses decoding mup for the prediction y/ VDE (G, Fn))- In graph convolutional models 27] GNN, consists two operations: applying shared linear 09 transformation to the features ('channel mixing') and propagating them along edges of the graph ("diffusion"). Our goal consists studying when GNN, is the gradient flow some parametric class 91 of energies Eg Ruxdd - R. which generalize the Dirichlet energy. This means that the parameters 92 can be interpreted as 'finding the right notion smoothness' for our task. We evolve the features by F()) = - (F()) with prediction y (TD=(((T)) for some optimal time T.
the energy dissipates along the gradient flow. Accordingly, this framework allows to explain the GNN dynamics as flowing the node features in the direction of steepest descent of Eg. Indeed. we find that parametrizing an energy leads to equations governed by attractive and repulsive forces that can be controlled via the spectrum of symmetric 'channcl-mixing" matrices. This shows that by learning to distribute more mass over the negative (positive) eigenvalues of the channel-mixing, gradient flow models can generate dynamies dominated by the higher (respectively, lower) graph frequencics and hence tackle different homophily scenarios. The gradient flow framework also leads sharing of the weights across layers (since parametrize the energy rather than the evolution equations, as usually done GNNs), allowing us to reduce the number of parameters without compromising performance (see Table []]
Why gradient flow? Since Eg (F(()) =
100
101
102
103
104
Analysis on graphs: preliminaries. Given a connected graph G with self- self-loops, adjacency matrix A is defined as d; if (i. e E and zero otherwise. We Det = diag the degree matrix and write A == D AD 1/2 Let F e Raxd be the matrix representation of signal. Its f
105
105
107
graph gradient is (VF),,
f./Vd. We detine the Laplacian A := - (the
108
divergence div is the adjoint of V), represented by A = Á 2 O. We refer to the eigenvalues of A as frequencies: the lowest frequency is always 0 while the highest frequency is Pa < [4] As
109
110
for the continuum casc, the gradient allows to define a (graph) Dirichlet energy as 49
Dir (F) == Σ Σ |(
f
trace F AT),),
(2)
Vd.
V
(J)EE
111 where the extra 1 is for convenience. As for manifolds, goD measures smoothness. If we stack the
112 columns of F into (F)(F)= E Rnd, gradient flow of Dir yields the heat equation on each channel:
vec ((()) - -V F
E (vec(F(t)) (Ia @ A)vec(F(t))
= (t) Af (t), (3)
113 for 1 <r I d. Similarly to (.) we rely on Dir to assess whether given dynamics + F(t) is
114 smoothing process. A different choice of Laplacian L = D A with non-normalized adjacency
3 1trace(FT LF). Throughout this paper, we rely 116 on the following definitions (see Appendix[As [A.3 for fürther equivalent formulations and justifications):
115 induces the analogous Dirichlet energy (Pa =
Definition 2.1. F()) CNN, (F()),)) t) initialized at (() is smoothing if gDi ((())) S C + ((t).
117
with C constant only depending on gDi (F(O)) and (p(t) Over-smoothing occurs if either
118
DDr (f)) or eL (t)) 0 for co.
119
120
Our notion of "over-smotthing" is a relaxed version of the definition in 2 although in the lincar case one always finds an exponential decay of Dir We note that g (F (i) + O iff (!)( + 0 for each column f", As in [30]. this corresponds to a loss of separation power along the solution where nodes with equal degree become indistinguishable since we converge to ker A (if we replaced A
121
122
123
124
with L then we would not even be able to separate nodes with different degrees in the limit).
125
To motivate the next definition, consider F(1) = AF((). Despite [[[]]] being unbounded for a.e. OO). the low- owwfrrque components are growing the fastest and indeed F() F[ -> F oz s.t.
125
127
A = 0 for 1 E r I d. We formalize this scenario - including the opposite case of high-frequency
components being dominant - by studying eD (F (t)/[[F (t)]l), i.c. the Rayleigh quotient of I & A.
128
129
Definition 2.2. F()) = GNNo(F(t), t) initialized F(O) is Low/ftigh-Freguency Saagguennc--Diinnne (L/HFF) if gir (F()) ((OIl) 0 (respectively, gir (F(()()))))))))))))))))) ((LI)) Pa/2) for L cc.
130
131
We report a consequence of Definition 2.2 and refer to Appendix A.3 for additional details and motivations for characterizations of LFD and HFD.
192
133
Lemma 2.3. GNN, is LFD (HFD) iff for each ty + there exist ty. oo and F st
134
F(4,)/1[[(()) F and A f O Ap% pa Pa respectively).
3

---

135
If a graph is homophilic, adjacent nodes likely to share the same label and expect smoothing LFD dynamics enhancing the frequency components
136
successful node classification tasks [43 43]. In the opposite case of heterophily, the high frequency components might contain more prototypical exampic being the cigenvector of A associated with largest frequency pa separating regular bipartite graph. other words, the class of heterophilic graphs contain instances where signals should be sharpened by increasing Dir rather
137
138
relevant information for separating classes [
139
140
141
than smoothed out. Accordingly, an ideal framework for learning on graphs must accommodate both of these opposite scenarios by being able to induce either an LFD or a HFD dynamics.
142
145
Parametric Dirichlet energy: channel-mixing as metric in feature space. In oq. ①1 constant nontrivial metric l in @dd leads to the mixing of the feature channels. We adapt this idea by considering symmetric positive semi-definite H W W with W c Rdxd and using it to generalize g as
144
145
W
Σ
Σ
Σ
(V = Σ ( (1,))E
(4)
145 note the analogy with eq. ( where the sum over nodes replaces the integration over the domain and j-th derivative some point i is replaced by the gradient along the edge (1.)) E. 148 We generally treat as learnable weights and study the gradient flow of &w
147
(t) V (F())
AF( W.
149 We see that eq. 5 generalizes eq. Below 'smoothing" is intended as in Definition 2T
150 Proposition 2.4. Let Pkat he the projection onto ker(W" W). Equation (5) smoothng since
(D (F(t)) I 20gap(W (Pea(A))[[(O))) E ((Pler 60 [.)oo)(F(())). 120. In fact F(1)
151
s.1. 2 Rd: for each
have (fxx); = vo P())
152
Proposition 2.4 implies that weight matrix W in eq. can separate the limit embeddings F(o) of nodes with some degree and input features. If W has trivial kemnel, then nodes with same degrees converge to the same representation and mver-smoothig occurs per Definition [. Differently
153
155
from [29 [0 over-smoothing occurs independently of the spectral radius of the bhannel-mixing positive even for equations which lead residual GNNs when discretized I2 According Proposition[2.4 we do not expect eq. (5) to succeed heterophilic graphs where
198
if its eigenvalues
157
smoothing processes are generally harmful this is contirmed in Figure 2 (see prod-curve). To
198
159
remedy this problem, we generalize eq.
55 to gradient flow that be HF- ID per Definition 2.2
160
3
A general parametric energy for pairwise interactions
161
We first rewrite the energy E in eq.
Dir (F)
Σ
1 Cantfe WT WT,). W WE)
(6)
162 We then define a new more general energy by replacing the occurrences of W W with new
185 symmetric matrices Ω E gdxaal since we also want to generate repulsive forces:
go (F. nt)
Σ 1J
(f Wf,) CF) + E (F),
(7)
184
with associated gradient flow of the form (see Appendix B
F(t) -p (F(()) F(t) AF(:)W
165
Note that eq. 8 is gradient flow of some energy F r- grot (F) iff both f and W are symmetric.
165 A multi-particle system point of view: attraction vs repulsion. Consider the d-dimensional features as particles in Rd with energy goee_ While the term E is independent of the graph topology and represents an external field the feature space, second term epair constitutes potential energy, with W bilinear form determining the pairwise interactions adjacent node
167
188
169
4

---

representations. Given symmetric W, we write W 0 -e_e., _,... by decomposing the spectrum of W in positive und negative values. We can rewrite gool = Et w + Eo, EDis i.c.
170
171
200 FF) De. W)f) +
> o (VF), 1J
(9)
172
The gradient flow of goot minimizes E and maximizes 6 The matrix W encodes repulsive pairwise interactions via its negative-definite component @ which lead to terms (-(V)),) increasing along the solution. The latter affords a 'sharpening' effect desirable on heterophilic graphs where we need to disentangle adjacent node representations and hence 'magnify' the adge-gradient
173
174
175
176 Spectral analysis of the channel-mixing. We will now show that eq. K can lead to HFD
that eq. becomes F(() (.) According 178 to eq. (9) negative cigenvalues of W lead repulsion. We show that the latter can induce HFD
177 dynamics. this end, we assume that Q
179 dynamics as per Definition 2.2 We Pw be the orthogonal projection into the eigenspace of
180 W & A associated with the eigenvalue == |
Ip
We define EHED explicitly in eq. (24
181
Proposition 3.1. p- A. then F(t) (F W is HFD for a.e. F(D): there exists EIFD
& (F)((F()) = 250- (PS PW F(O) + =((e-Beur)))
120,
and F(1/ [(O] converges to Fx Raxd such AC Par., f
182
183 Proposition 3.1 shows that if enough mass of the spectrum of the 'channel-mixing is distributed over
184 the negative eigenvalues, then the evolation is dominated by the graph high frequencies. This analysis
185 is made possible in our gradient flow framework where W must he symmetric. The HFD dynamics induced by negative cigenvalues of W is confirmed in Figure 2 (neg--rod-ad prod-curve in the bottom chart).
106
A general energy. Equations with source term may have better expressive power 24 39
our framework this means adding an extra energy term the form Esaurco(F) := 3(E, F(O)W)
188
W
180
to eq. with some learnable and W. This leads to the following gradient flow:
F(t) (C) AF(()W 3F(D)W.
(10)
190
We also observe that could replace the fixed matrix Á with more general symmetric graph vector field satisfying A. if (i.j) & E, although in this work we focus the case A == A.
191
192
We also note that when f = W, then
becomes F(t)= -F) We perform a spectral
193
analysis of this case in Appendix B
Non-linear activations. In Appendix B.3
we discuss non-linear gradient flow equations. Here R. We longer gradient flow, the learnable multi-purticle energy grot is still
195
study what happens if the gradient flow in eq. (10) is activated pointwise by show that although decreasing along the solution, meaning that the interpretation of the channel-mixing W inducing attraction and repulsion via its positive negative eigenvalues respectively preserved.
198
197
198
Proposition 3.2. Consider non linear map R + R such that the function xa(x)) 0.
+ (t) solves the equation
F(t)= =0 ( (-F(1) AF(:) MOWWW3F10 -FF(O)))
201
where a acts elementwise, then
det (F())(F(L)) S.
dt
A proof of this result and more details and discussion are reported in Appendix We emphasize here that differently from previous results about behaviour of ReLU wit Ebr (30 much more general energy that can also induce repulsion and more general family of activation functions (that include ReLU, tanh, arctan and many others).
203
deal with
204
205
4
Comparison with GNNs
206
207
In this Soction, we study standard GNN models from the perspective of our gradient flow framework.
5

---

208 4.1
Continuous case
209
Continuous GNN models replace layers with continuous time. In contrast with Proposition 3.1
210
show that three main linearized continuous GNN models are either smoothing LFD as
per Definition
2 The linearized PDE- G model [17] corresponds to choosing 3 = 0 and
212
W
K K(t) in eq. (10), for some time-dependent family L +> K(() Rdxa;
F GOND (t) = (FF(() (()).
213
The CGNN model
44) can be derived from cq. 10 by setting 32 = - 2 W = W = -18
FC) = (z))) + F() + F(0).
Finally, in lincarized GRAND I0 row-stochastic matrix ((F())) learned from the encoding via attention mechanism and have
215
F (C)AND(L) - F() = -I (()))))
216
We note that if A is not symmetric, then GRAND is not gradient flow.
217
Proposition 4.1. PDE GCND, CGNN and GRAND satisfy the following:
218
(i) PDE GCN is smoothing model: & (F F (t)) _ O.
219
(ii) For a.e. F(O) it holds: CGNN is never HFD and we remove the source term, then CGNN (FContttt////ccaot]]ll) $ (--aa((A).
220
(ii) If connected, FCRAND(F) paast
with n² mean(f 15rsd
222
(ii) the source-free free CGNN-evolution is LFD independent of f. Moreover. by (iii), over-smoothing
223
occurs for GRAND per Definition[2.1 On the other hund, Proposition [.]]soowss shows that the negative eigenvalues of W can make the source-free gradient flow in oq. (8) HFD. Experiments in Scction confirm that the grudient flow model outperforms CGNN and GRAND heterophilic graphs.
224
225
228
4.2
Discrete case
227
We now describe discrete version our gradient flow model and compare it to 'discrete' GNNs where discrete time steps correspond to different layers. In the spirit [[2], we use explicit Euler scheme with step size < to solve eq. 110p and set W = I. In the gradient flow framework we parametrize the energy rather than the actual equations, which leads to symmetric channel-mixing matrices Q W dgdd that shared across the layers. Since the matrices are square, an encoding block t'EN 1g*xr + R is used process input features Fo R"xp and generally reduce the hidden dimension from p d. Moreover, the iterations inherently lead to residual architecture because of the explicit Euler discretization:
226
229
234
F(t + r) = F(f) + ( (-F()) + AF(:) + BF(0)), F(O) = (Fo).
(11)
235
with prediction y = 1iDe:(((TT produced by a decoder thE Rxdd + Bgnk,, where & is the number of label classes and T integration time of the form = mrr, so that m E N represents the number of layers. Although eq. {Iip is linear, we can include non-linear activations in eiNN thm making the entire model generally non-linear. We emphasize two important points:
236
237
238
239
Since framework residual, even the message- paassgggg is linear, this not equivalent to collapsing the dynamics into a single layer with diffusion matrix A,, m the number of layers, see eq. (27) the appendix where we derive the expansion of the solution.
240
241
242
We could also activate the equations pointwise
maintain the physics interpretation thanks following though. we mainly
245
to Proposition 3.2 to gain greater expressive power. stick to the lincar discrete gradient flow unless otherwise stated.
244
245
Are discrete GNNs gradient flows? Given (learned) symmetric graph vector field A é Rox satisfying A.j = if (i & E, consider a family of lincar GNNs with shared weights of the form
246
1) = F() + AF()) + (F(0) W, 0 S.
(12)
247 Symmetry is key requirement interpret GNNs in eq. 12 gradient flow framework.
6

---

Lemma 4.2. Equation 12 is the unit step size discrete gradient flow of - - + Epelr Euouroe with Evair defined by replacing with A in eq. 7 :lf and W are symmetric.
248
"W
249
250
Lemma 4.2 a recipe for making standard architectures into gradient flow, with symmetry being the key requirement. When eq. (12) is gradient flow, the underlying GNN dynamics is
251
252
equivalent to minimizing a mulli-
energy by learning attractive and repulsive directions in
253
feature space as discussed in Section [] In Appendix C.2 we show how Lemma (4.2 4.2 covers linear
254
versions of GCN 43) GAT [42). GraphSAGE [23 and GCNI (11 to name a few.
255
Omortsmog analysis in discrete setting. By Proposition 3.1 we know that the continuous
295
version of eq. (I) can be HFD thanks to the negative eigenvalues of W. The next result represents a
257
discrete counterpart of Proposition ann shows that residual, symmetrized graph convolational
258
models can be HFD. Below Fo is the projection into the eigenspace associated with the eigenvalue
(pa 1) and we report the explicit value of dHND in eq. (88 in Appendix C333 Wc let:
P
XM 1)) < 1 2(7(2 pa))
(13)
260
Theorem 4.3, Given F(1 T) = F(() + 7 with W symmetric, ifq.
13
holds then
(F(()))) (1 Tp_)2m
11 F( +
((
(1+ (rgeee
(I+T
2m)
ÓHED p-:
hence the dynamics is HFD for a.e. (() and fact F(mT)//lF(mm) Conversely, if G is not bipartite, then for F(O) the system +((++)) AF(OW, with W symmetric,, LFD independent of the spectrum of W.
F AC PA
262
253
Theorem 4.3 shows that lincar discrete gradient flows can be HFD due to the negative eigenvalues of W. This differs from statements that standard GCNs act as low-pass filters and thus over-smonth in the limit. Indeed, in these cases the spectrum of W is generally ignored [3] [ required to be sufficiently small in terms of singular value decomposition (29 30, B when no residual connection
285
267
208
is present. On the other hand, Theorem 4.3 emphasizes that the spectrum of W plays key role to enhance the high frequencies when enough mass is distributed the negative eigenvalues provided that residual connection exists this confirmed by the neg-prod-curve Figure 2
269
270
271
The residual connection from spectral perspective. Given sufficiently small step-size that the right hand side of incquality is satisficd, F(t 7) = F(r) - F W is HFD for F(D) if [A_ (pa 1) > XW i.e. 'there is mass' in the negative spectrum of W than in the positive onc. This means that differently from 29 30 R. there is requirement
273
the minimal magnitude of the spectral radius of W coming from the graph topology long XW is small enough, Conversely, without residual term, the dynamics is LFD for a.e. F(O) independently of the sign and magnitude of the eigenvalues of W. This is also confirmed by the GCN-curve in Figure
275
278
277
278
Smooting LFD. We highlight how in general a lincar GCN equation F(1 - 7) AF may avoid smoothig in the sense of Definition 2.11 meaning that DDr (F()) - as soon there exist X E (0, 1) and the spectral radius of W large enough. However, this will not lead sver-sepanation since the dominating term is the lowest frequency in other words, once re-set the scale right per the normalization in Theorem [ encounter loss of separability
282
293
with large (and possibly negative) spectrum of W.
204
5
Experiments
285
In this section we evaluate the gradient flow framework (GRAFF). We corroboratc the spectral analysis using synthetic data with controllable homophily. We confirm that having negative (positive) eigenvalues of the channel-mixing W are essential heterophilic (homophilic) scenarios where the gradient flow should align with HFD (LFD) respectively. We show that the gradient flow in eq. [ lincar, residual, symmetric graph convolutional model achieves competitive performance heterophilic datasets.
285
287
208
289
290
7

---

291
Methodology. We crystallize GRAFF in the model presented in eq. 11 with VEN. VDD im- plemented as single lincar layers MLPs, and we set Q to be diagonal. For the real-world experiments we consider diagenallyddominnl (DD), diagonal (D) and time-dependent choices for the structure of W that offer explicit control over its spectrum. In the (DD)-case, we consider a W E Rddd synumetric with zero diagonal and w E Ied defined by w.. q. Ea W aall + Ta-
282
293
284
295
295
and set W diag(w) + Wo Due to the Gershgorin Theorem the eigenvalues of W belong to [W.. Eg(Wa.l ael: Wa + +Egl aall. so the model 'can' easily re-distribute mass in the spectrum of
297
298
W via Ja: aa. This generalizes the decomposition of W in [IT]] providing a justification in terms of its spectrum and turns out to be more efficient w.r.t the hidden dimension d as shown in Figure the Appendix. For (D) we take W to be diagonal, with entries sampled 44 1] and fixed - i.e. we do not train over W- and only leam V'N, VID.. We also include time- demedednddent model where W, varies across layers. To investigate the role of the spectrum of W on synthetic graphs, construct
289
200
201
202
three additional variants: W W + W W = + W W' named sum, prod and neg-prod respectively where prod (rod) variants have only non-negate non-negative (non-pon positive) eigenvalues.
303
204
205
Complexity and number of parameters. If we treat the number of layers constant, the discrete gradient flow scales O( [[[Vpd + |E d²). where p and d are input feature and hidden dimension respectively, with p d usually. Note that GCN has complexity (dd) and in fact our model is faster than GCN confirmed in Figure in Appendix D Since E'N, VDE are single linear layers (MIPs), we can bound the number of parameters by pd de 3d + dk, with ls the number of lahel have pd + 3d + dk. Further ablation studies appear in Figure 4 in the Appendix showing that (DD) outperforms sum and GCN- especially in the lower hidden dimension regime- on real- world benchmarks with varying homophily.
205
207
808
309
310
classes, in the (DD)-varian) while in the (D)-variani
311
312
313
Synthetic experiments and ablation studies. To investigate our claims in controlled environ- ment we use the symthetic Cora dataset of [51] Ap- pendix GJ. Graphs are generated for target levels
314
piod
215
318
317
of homophily via preferential attachment see Appendix D33 for details. Figure 2 confirms the spectral analysis and offers better understanding in terms of performance and smoothness of the predictions. Each curve except GCN repre- sents version of W in 'methodology' and implement eq. [T]) with 8 = 0. S O. Fig- ure (top) reports the test accuracy
318
319
320
221
222
223
824
label homophily. Neg-prod is better than prod on low- homophily and viceversa on highhhlyp This confirms Proposition 3.1 where we have shown that the gradient flow can lead to HFD dy- namics that are generally desirable with low- homophily through the negative eigenvalues of W. Conversely, the prod configuration (where we have an attraction-only dynamics) struggles in low- homophily scenarios even though a residual connection is present. Both prod and neg-prod are "extreme' choices and serve the purpose of highlighting that by turming off one side of the spectrum this could he the more damaging depending on the undcrlying homophily. In general though 'ncutral" variants like sum and (DD) are indeed more ficxible and better performing,
325
328
327
328
329
330
Figure 2: Experiments synthetic datasets with controlled homophily.
231
832
833
334
335
338
fact, (DD) outperforms GCN especially in low- homoholphily secnarios, confirming Theorem [4.3 where we have shown that
337
238
without residual connection convolutional models are LFD and hence more sensitive to underlying homophily irrespectively of the spectrum of W. This is further confirmed in Figure 3
339
840
In Figure 2 (bottom) we compute the homophily of the prediction (cross) for given method and
361
compare with the homophily (circle) the prediction read from the encoding (i.c. graph-agnostic). The homophily here proxy assess whether the evolution smoothing. the goal being explaining
842
343
the smoothness the prediction via the spectrum of W as per our theoretical analysis. For peg-prod
364
the homophily after the evolution is lower than that of the encoding, supporting the analysis that
345
negative cigenvalues of W enhance nigh-freeqencice The opposite hchaviour occurs in the of
365
prod and explains that the low low- homophlyy regime prod is under performant due to the prediction
8

---

Treas
Cameill
Filn
Sparrel
Chomeden
Cheeerr
Putteed
Care
1051
201
7.60
5
33527
1,205
2M5
495
280
26,253
1M0
11:431
4,00
46.327
5,274
5
FAIKNN
55
105
17.54-
1.35
55.17
5.55
71.31
4: 1.54
77:31
58-15
0137
N7
1.45
GIRRGINN
-336
0.51
19117 11
31.03
1:133
J1.63
3:31
11.56
6 1.71
1.67
67.50
00:00100 0330
077
1.36
60.00 66
7:35
87
03
00.70
35.20-4
8:145
00.11
3:15
77:11
1.57
58
11:38
87
87
1:80
00:51
3.09
00.51
35.35
0:93
00.20:
3.61
7h.060
1:15
00:05
0.17
05.25
1.55
Parfomm
00:57
0.31
08
03 6:31
56.1 4:31
07:00-4 1:31
30:11
3.01
02:71 à 2,53
73-34
1:47
67.50
0.00
15 71
1.01
03 0111
81
3.50
75.00
5:01
31:41 0:99
11:61
6:671
14.73
6: 1.06
76.04
1:30
68.08
1150
16
1.0
GART
50 16 61603
19
0101
(11
00 5.05
07.01
03:22
4: 3.55
00.36
2:30
71.55
1.55
67:30 1:10
95.33
MLP
04.81 6:75
86.29
9.31
81.00
2.000
05.03 0.00
22.77
4: 1.35
2::1::2::0
74.00 1:50
2:10
85 57.10 0.00
11.50=00
10.01
1:20
2:00
5.0.5
20:21 1.00
51
GRAND
1:35
Sheaal (san)
56.00
0.04
00.41 2.44
81.88.44.7 4.71
07.81
1.15
06.34
4 1.33
68.04 6 1.88
76.70
1.57
10.09:0..
=0.90-1.1
CERAFE (D0)
08.20
87 85 7:1
J5.05 0:641
58.52
1:17
71.08
1:25
76.00
58.16 0.51
00:00 1100
GRAFF sinnakge (DD)
50.00
2:00
22.18:77777
$5.03 2 1.23
53,37
1.45
60.38
à 1,30
76.50
2 1.5
58.2
67.38 1.06
Table 1: Results on heterophilic and homophilic datasets
847
being smoother than the true homophily. (DD) and sum variants adapt better to the true homophily. We note how the enending compensates when the dynamics can only either attract repulse (i.c. the spectrum of W has a sign) by decreasing inereasing the initial homophily respectively.
348
349
350
Real world experiments. We test GRAFF against range of datascts with varying homophily
251
R7 [3]] [I (see Appendix[D.4]] [Dr4]or additional details). We use results provided in [5 Table 1],
252
which includes standard baselines as GCN (27). GraphSAGE [23]. GAT [42). PairNorm [48 and
253
recent models tailored towards the heterophilic setting (GGCN [SS]. Geom GCN [31. H2GCN
254
(1I) and GPRGNN (T3.. For Sheaf [5]. a recent top-performer on heterophilic datasets, we took
355
the best performing variant (out of six provided) for cach dataset. We also include continuous
258 baselines CGNN [+4]]] and GRAND [0] to provide empirical evidence for Proposition I.] Splits taken from [31 are used in all the comparisons. The GRAFF FF model discussed in 'methodology is a very simple architecture with shared parameters across layers and run uuntimme-n smaller than GCN and more recent models like GGCN designed for hetcrophilic graphs (sec Figure in the Appendix). Nevertheless. it achieves competitive results on all datasets, performing on par or better than more complex recent models. Moreover, comparison with the 'imme-dependent (DD) variant confirms that by sharing weights across layers we do not lose performance. We note that on heterophilic graphs short integration time is usually needed due to the topology being harmful and the negative cigenvalues of W leading exponential hehaviour (sec Appendix D).
357
355
359
360
362
363
365
6 Conclusions
388
In this work, we developed framework for GNNs where the evolution can he interpreted as minimizing multi- panlti- learnable energy. This translates into studying the interaction between the spectrum of the graph and the spectrum of the 'channel-mixing" leading to better understanding of when and why the induced dynamics is low (high) frequency dominated. From theoretical perspective, we refined existing asymptotic analysis of GNNs account for the role of the spectrum of the channel-mixing well. From practical perspective, our framework allows for "educated' choices resulting in simple convolutional model that achieves competitive performance on homophilic and heterophilic benchmarks while being faster than GCN. Our results refute the folklore of graph convolutional models being too simple for heterophilic henchmarks.
368
370
871
872
878
374
375
Limitations and future works. We limited our attention to a constant bilincar form W. which might be excessively rigid. It is possible to derive non non-constant alternatives that are aware of the features or the position in the graph. The main challenge amounts to matching the requirement for local "heterogeneity' with efficiency: we reserve this question for future work. Our analysis is also a first step into studying the interaction of the graph and 'channel-mixing spectra; we did not explore other dynamics that are neither LFD nor HFD as per our definitions. The energy formulation points to new models more 'physics' inspired; this will he explored in future work.
376
277
078
279
380
361
382
Societal impact. Our work sheds light on the actual dynamics of GNNs and could hence improve their understanding, which is erucial for assessing their impact on large-scale applications. We also show that instances of our framework achieve competitive performance on heterophilic data despitc being faster than GCN, providing evidence for efficient methods with reduced footprint.
383
384
305
9

---

References
388
297
[1] U. Alon and E. Yahav, On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
888
380
[2] M. Bulcilar, G. Renton, P. Héroux, B. Gaüzère, S. Adam, and P. Honeine. Analyzing the
390
expressive power of graph neural networks a spectral perspective. In International Conference on Learning Representations, 2020.
391
382
[3] M. Biloš, J. Sommer, S. S. Rangapuram, T. Januschowski, and S. Günnemann. Neural flows: Efficient alternative to neural odes. In Advances in Neural Information Processing Systems, volume 34, 2021.
293
304
895
[4] D. Bo, X. Wang. C. Shi, and H. Shen. Beyond low-frequency information in graph convolutional networks. In AAAL AAAI Press, 2021.
396
297
[5] C. Bodnar, F. Di Giovanni, B. P. Chamberlain, P.
Lid, and M. M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. arXiv preprint arXiv:2202.04572 2022.
380
299
400
[6] S. Brody, U. Alon, and F. Yahav. How attentive graph attention networks? arXiv preprint 2rXi:2200..4442 2021.
402
[71 Bruna, W. Zaremba, Szlam, and LeCun. Spectral networks and locally connected networks on graphs. In 2nd International Conference on Learning Representations, ICLR 2014. 2014.
403
404
405
[8] C. Cai and Y. Wang. A note on over-smoothing for graph neural networks. arXiv preprint 2006, 13318, 2020.
406
[9] B. Chamberlain, J. Rowhottom, D. Eynard, F. Di Giovanni, X. Dong, and M. Bronstein. Beltrami flow and neural diffusion on graphs. Advances in Neural Information Processing Systems, 34, 2021.
409
410
[10] B. Chamberlain. Rowbottom, Gorinova, Bronstein, S. Webb, and E. Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pages 1407-1418. PMIR, 2021.
411
412
413
[1]] M. Chen, 7. Wei, 7. Huang, B. Ding, and L. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735 PMLR, 2020.
414
415
[12] R. T. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018
415
417
[13] E. Chien, J. Peng, P. li, and O. Milenkovic. Adaptive universal generalized pagerank graph
418
neural network. 9th International Conference on Learning Representations, ICLR 2021. 2021.
419
420
[14] F. R. Chung and F. C. Graham. Spectrul graph theory. Number 92. American Mathematical Soc., 1997.
422
[15] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs
423
with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
424
425
[16] J. Eells and J. H. Sampson. Harmonic mappings of riemannian manifolds. American journal of mathematics, 86(1):109-166 1964.
<25
427
[17] M. Eliasof, E. Haber. and E. Treister. Pde-gen; Novel architectures for graph neural networks
425
motivated by partial differential equations. Advances in Neural Information Processing Systems. 34, 2021.
430
[18] Geiger, I.. Petrini, and Wyart. Landscape and training regimes in deep lcarning. Physics Reports, 924:1 2021.
431
10

---

432
[19] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272 PMLR, 2017.
433
434
435
[20] C. Goller and A. Kuchler. Learning task-dependent distributed representations by backprop- agation through structure. In Proceedings of International Conference on Neural Networks (ICNN'96), volume 1. pages 347-352. IEEE, 1996.
435
437
435
[21] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2. pages 729-734. IEEE, 2005.
439
461
[22] E. Haber and I., Ruthotto. Stable architectures for deep neural networks, Inverse Problems, 2018.
442
443
[23] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs.
464
Advances in neural information processing systems, 30, 2017.
445
[24] D. K. Hammond, P. Vandergheynst, and R. Gribonval. The spectral graph wavelet transform: Fundamental theory and fast computation. In Vertex-Frequency Analysis of Graph Signals. pages 141-175. Springer, 2019.
446
447
448
[25] He, Z. Wei, Xu, Bernet: Learning arbitrary graph spectral filters via hemstecn approximation. Advances Neural Information Processing Systems, 34, 2021.
469
450
[26] R. Kimmel, N. Sochen, and R. Malladi. From high energy physics to low level vision. In
451
International Conference on Scale-Space Theories in Computer Vision, pages pages236-2222 236-247. Springer. 1997.
452
453
[27]
T.N. Kipf and M. Welling. Semi-Super Clussification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR '17 2017.
456
1281 Kliepera, Weißenberger, and S. Günnemann. Diffusion improves graph learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. 2019.
457
455
459
[29] H. Nt and T. Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv
460
preprint arXiv: 195.00000 2019.
[30] K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
463
[31] H. Pei, Wei, C. Chang, Y. Lei, and Yang. Geom-gen: Geometric graph convolutional
464
networks. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
465
[32] P. Perona and J. Malik. Scale-space and edge detection using anisotropic difffusion. PAMI, 12(7)x629-639 1990.
486
467
[33] B. Rozemberezki, C. Allen, and R. Surkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2)xenab014, 2021.
465
469
[34] T. K. Rusch, Chamherlain, J. Rowhottom, S. Mishra, and M. M. Bronstcin. Graph-coupled
470
oscillator networks. In International Conference on Machine Learning, 2022.
471
[35] M. E. Sander, P. Ablin, M. Blondel, and G. Peyré, Sinkformers: Transformers with doubly
472
stochastic attention. In International Conference on Artificial Intelligence and Statistics, pages 3515-3530. PMLR, 2022.
473
474
[36] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEFE transactions neural networks, 20(1): 2008.
475
478
[37] P. Sen, G. Namata, M. Bilgic, Getoor, Galligher, and -liassi-Rad. Collective classifica- tion in network data, Al magazine, 29(3):33-95 2008
477
11

---

478
[38] A. Sperduti. Encoding labeled graphs by labeling raam. Advances in Neural Information Processing Systems, 6, 1993.
479
480
[39] M. Thorpe, T. M. Nguyen, H. Xia, T. Strohmer, A. Bertozzi, S. Osher, and B. Wang. Grand++: Graph neural diffusion with a source term. In International Conference on Learning Represen- tations, 2021.
481
402
463
[40] J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein, Understanding over- squashin and bottlenecks on graphs via curvature. International Conference on Learning Representations, 2022.
484
405
[41] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need, Advances neural information processing systems. 30, 2017.
497
488
489
[42] P. Veličković, G. Cucurull, A. Casanova, A. Romero, Liò, and Bengio. Graph attention networks. In International Conference on Learning Representatioss, 2018.
490
491
[45] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
432
493
[44] L.P. Xhonneux, M. Qu. and J. Tang. Continuous graph neural networks. In International Conference on Machine Learning, pages 10432-10441, PMLR, 2020.
495
[45] Y. Yan, M. Hashemi, K. Swersky. Y. Yang. and D. Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06662, 2021.
498
497
495
[46] Z. Ying, D. Bourgoois, J. You, M. Zitmik, and J. Leskovee, Ganexplainer: Generating expla- nations for graph neural networks. Advances neural information proessing systems, 32, 2019.
400
500
501
[47] H. Yuan, H. Yu, S. Gui, and S. Ji. Explainability in graph neural networks: A taxonomic survey. Xrxiv preprint 2012 2020.
502
503
[48] L.. 7hao and I.. Akoglu. arXiv: 1909. 12223, 2019.
Pairoor: Tackling oversmoothing in gnns. arXiv preprint
504
505
[49] Zhou and Schölkopf. Regularization on discrete spaces. In Joint Pattern Recognition Synposium, pages 361-368 Springer, 2005.
695
507
[50] K. Zhou, X. Huang, D. Zha, R. Chen, L. Li, S.IIL Choi, and X. Hu. Dirichlet energy constrained
508
learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34:21834-21846, 2021.
E09
E10
[51] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems. 33:7793-7804, 2020.
612
513
[52] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. In NIPS workshop, 2018
514
515
[53] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, Yang, Z. De M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, I.. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high- performance deep learning library. In NewrIPS. 2019.
516
517
518
519
[54] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorc Geometric. In ICLR Workshop on Representation Learning on Graphs and Monifolds, 2019.
520
521
155] I. Biewald. Experiment tracking with weights and biases, 2020. Software available from wandb.com.
522
12

---

Checklist
623
E24
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For cach question, change the default [TODO] to [Yss], [No]. , or
525
526
| You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing hrief inline description. For example:
527
526
Did you include the license to the code and datascts? [Yes] See Section ??.
529
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
530
Did you include the lieense to the code and datascts? [N/A]
632
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section docs not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
533
634
635
1. For all authors...
536
(a) Do the main claims made in the abstract and introduction accurately reffect the paper's contributions and scope? [Yes]
537
838
(b) Did you describe the limitations of your work? [Yes], in Section g
539
(c) Did you discuss any potential negative socictal impacts of your work? [Yes] the Societal impact paragraph in Section(6
640
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Ys]]
643
If you are including theoretical results...
544
(a) Did you state the full set ussumptions of all theoretical results? [Yes]
565
(b) Did you include complete proof' of all theoretical results? [Yes] in Appendix A
648
Appendix B and Appendix C
647
If you ran experiments..
548
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] Code and README in SM, dataloaders in code
649
850
551
Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] Splits and hyperparameters provided in code zip
692
553
(c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [Yes] Standard deviations
stated in results table
E55
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] in appendix( [D]
855
857
4. If are using existing assets (e.g.. code, data, models) curating/releasing new assets...
658
(a) If your work uses existing assets, did you cite the creators? [Yes] datasets and standard libraries cited in appendix[D
559
560
(b) Did you mention the license of the assets? |Yss] industry standard librarics and benchmark datasets were used in accordance with licences
582
(c) Did you include any new assets either the supplemental material or as URL? [Yes] code provided in SM zip
588
664
(d) Did you discuss whether and how consent obtained from people whose data you's 're
565
using/curating? [N/A]
588
(c) Did you discuss whether the data you are using/curating contains personally identifialle
information or offensive content? Yes]] no personal data is contained within bench- marking datasets
587
368
569
5. If you used crowdsoureing conducted research with human subjects...
570
(a) Did you include the full text of instructions given participants and sereenshots, if applicable? [N/A]
871
13

---

672
Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
573
Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zkVQHhU_NoS", "reviewer": "Reviewer_4YFR", "summary": "In this work, authors present GRAFF, a gradient flow based graph neural network in which the evolution of GNN is represented as minimizing the combination of attractive and repulsive interactions of a multi-particle system. Detailed theoretical characterization in terms of a parametric Dirichlet energy, a general parametric energy and spectral analysis is performed. ", "questions": "It has been shown by earlier works that energy formulation results in a loss landscape that has a large number of local minima and hence gradient based minimization results in a poor solution. In contrast, deep neural networks with large number of parameters have flat minima and the loss landscape is connected by level set. Reading these together, it is unclear whether the energy-based formulation with simpler formulation loses the advantages of the landscape that a deep-learning architecture has. Could this also be the reason why the performance of the GRAFF is not superior in comparison to other SOTA models? Authors should investigate this.", "limitations": "The experiments has primarily focussed on one aspect while studying on several datasets with varying hetero/homophily. To evaluate the true performance of the approach, several other experiments on varying downstream tasks are required. in addition, a closer analysis on the loss landscape is required to understand the nature of the minima and saddle points. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is well-written and clearly presented. It builds on similar ideas as outlined in several previous works such as, for instance, [27]. While the presentation in the work is good, the idea in itself is fairly intuitive and simple and has been discussed in contexts of neural networks and physics (related works, see: Landscape and training regimes in deep learning, M. Geiger; L. Petrini; M. Wyart, Physics Reports. 2021-04-16. Vol. 924, p. 1-18. DOI : 10.1016/j.physrep.2021.04.001.). Further, the empirical experiments reveal that the results are comparable with the existing approaches, but not necessarily better. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jxDn0fiTC3U", "reviewer": "Reviewer_13DY", "summary": "The paper suggests a new graph neural network architecture that can be seen as a gradient descent minimization of a learnable energy function. The authors use channel-mixing matrices with mixed eigenvalues to infuse high frequencies into the architecture dynamics. Many existing architectures fall into this framework. Three variants of the new architecture are presented. ", "questions": "- The gradient of Eq (4) looks like Grad^TW^TWGrad(F). Why is Eq (5) the way it is? Please clarify in the text. \n\n- I am confused by the derivation from (6) to (7). First, if the rest of the paper uses the energies in (7), why introduce the energies in (4)-(6)? How do (6) and (7) relate? This is not clear. More importantly, is it the same W in both equations? It does not seem so. This is very confusing. Please consider revising. \n\n- Line 202-203: Are the authors saying that there is no role for the non-linearities in graph neural networks? But that is the most important aspect of a neural network’s definition (otherwise, the whole network collapses to a single linear operator). It does not make sense. Maybe try other experiments? CNNs, for example, sure require non-linearities for image classification. Maybe test this hypothesis on graph classification? Maybe shape classification (ModelNet40)?  \n\n- Line 209: by linearized GNNs, do the authors mean with identity activation? Because there are no activations in the following equations. But - this is not the traditional use of the word \"linearized\", which is traditionally used for a Taylor approximation. Please revise. \n\n- Line 228 – why do the authors introduce tilde{W}, and then set it as identity? Can’t tilde{W} be chosen better? And if so - why introduce this matrix? \n\n- Line 230 – Why are Omega and W shared across the layers? Traditionally, at least in CNNs, one learns a variety of channel-mixing convolution operators. What is different here? This negates the common practice of neural networks and requires explanation and evaluation.\n\nLine 235 – the authors have T, tau, and the number of layers. How do we choose T or tau? Is it a hyperparameter? Do the authors choose tau to be small enough to ensure the stability of the Euler scheme? \n\nLine 236 – The authors state that they can include the non-linearities in the encoder and decoder layers only. Will that be the equivalent to having a non-linearity in Eq. (12)? I do not understand why. Again, that is against the fundamental aspect of neural networks – the use of non-linear activations to express complex functions.\n\nLines 244-245: Symmetry being a key requirement. When other works learn the channel-mixing operators, they do not enforce symmetry. So – this is important only for looking at architectures as a gradient flow. Further, in lines 247-248: indeed (13) can be seen as a generalization of the mentioned methods (with identity activation), but none of these learn symmetric matrices. Also, as the authors note, GAT does not have a symmetric attention matrix. So, is symmetry really important? Will we get better networks if we enforce symmetry in the learning?  \n\nIn continuation to the previous point: the symmetrization in lines 304. In my opinion, this whole concept of symmetry or not should be evaluated in extensive experiments, but I do not see such experiments in the paper.  \n\nLines 282-284: Essentially, when choosing negative eigenvalues for W, you indeed reverse the time integration. But then, the Euler method that is used is known to become unstable. Isn’t that a problem with the whole approach?\n\nLines 290: The authors state that linear GNNs achieve competitive performance on real-world data sets. Again, having linear layers negates the whole concept of NNs. This cannot be a conclusion that holds for all data sets and tasks. Given the rather limited scope of experiments, I would say that this is a too strong statement here. \n\nLines 301-302: The authors choose W to be diagonal and random and do not train over it. Why is that? Won’t we get better results if we train over W? This means that there are no non-linearities in the network, and there are no learnable channel-mixing parameters. So, except the encoding and decoding layers, it’s essentially a classical algorithm. How do the authors explain that?\n\nLines 301: the random W. How does the choice of a random W influence the results? Are the achieved accuracies stable? Or do the authors see large deviations between different runs?\n\nLine 375: This is yet another strong sentence, given the rather limited experimental study in the paper. \n", "limitations": "yes. ", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1) The paper is rich in theoretical insights. \n2) Unlike previous works, this is the first work that analyzes the channel mixing matrix. \n\nWeaknesses: \n1) The experiments are rather limited. The authors show only node classification, where it is customary to show more experiments. The work of GCNII, for example, shows PPI, and two cases of node classification (semi and fully supervised).  Also, an example on a large dataset (e.g., OGBN-Arxiv) is also important. Most importantly, it is not clear how well the method works on graph classification tasks (e.g., the TUD data sets), without the non-linearities in the layers. Given the strong claims made by the authors regarding those non-linearities (see below), showing these experiments is essential in my opinion.\n\n2) I find only a single data set where GRAFF yields the best performance. Overall, this method does not improve the SOTA. \n\n3) There is very little discussion about over-smoothing in this work (only in the paragraph in line 249). At the end, the authors do not show if their method is over-smoothing or not. Ideally, the authors would provide accuracies for a variety of number of layers and show that the accuracy does not degrade (e.g., see GCNII). \n\n4) There are questionable choices for the architecture (e.g., no non-linearities) that are accompanied by too strong statements without backing them up. See details in the questions section. In particular, the authors do not show that indeed adding and removing the non-linearity has no influence on the accuracy. \n\n5) The writing of the paper is hard to follow. I would say that the presentation (i.e., notation and language) can be simplified to make this paper more reader-friendly. \n\n6) I could not find how many layers were used in Table 1.\n\n7) Missing citation from the previous Neurips: \nZhou, 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, 34, 2021.\nThis paper also discusses the Dirichlet energy throughout the layers.\n\n8) Missing citation from ICLR 2022:\nHow attentive are graph attention networks? (GATv2)\nThe conclusion of this paper is that having a more non-linear (in some sense) attention matrix improves the accuracy and training stability over GAT. How does the conclusion in this work align with the findings in GATv2? Note that there are additional data sets in GATv2, which may be more challenging and require non-linearities in the layers.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R2n3t2ffnkS", "reviewer": "Reviewer_c28L", "summary": "In this paper, the evolution of the GNN is explained as learning attractive and repulsive forces in feature space by the positive and negative eigenvalues of a symmetric 'channel-mixing' matrix. According to the spectral analysis of the solutions, gradient flow graph convolutional models result in a dynamic dominated by graph high frequencies, which is desirable for heterophilic datasets. Moreover, the authors present structural constraints on common GNN architectures, allowing them to be interpreted as gradient flows. We perform extensive ablation studies to verify our theoretical analysis and demonstrate the comparative performance of simple and lightweight models on real-world homophilic and heterophilic datasets. ", "questions": "If two particle (two nodes) is repulsive to each other, will both feature blow up (going to infinity) as the time of the dynamic system increases? How can you ensure all the feature on every node is bounded with the system is evolving?\n\n\n", "limitations": "The authors discussed the limitation of their works and their social impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nIn this paper, the author gives a new perspective on GNN in terms of the particle system, which explain why the original GNN does not work well on heterophilic datasets and also analysis Dirichlet energy change in the dynamic system.\n\nThe whole paper's structure is clear and easy to follow. Several adequate experiments are used to verify the author's statement.\n\nWeaknesses:\n\nWhen the graph size is increasing, is this GNN also computation feasibly? As this model needs to compute the eigendecomposition of the graph Laplacian, when the graph size is increasing, it should be hard to compute.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "F-Oh_ruEYzA", "reviewer": "Reviewer_PPbd", "summary": "This paper introduces a new family of models, GRAFF, on graphs wherein graph features are transformed according to a dynamical system given by the negative gradient of an *energy functional*, which is parameterized and learned.  This amounts to a re-parameterization to focus on an energy function describing a discretized iterative update, instead of parameterizing the iterative update itself, as the most widely used GNN architectures do. This relation is properly studied in Section 4, where they show that GRAFF still includes many prior GNN model (up to the perhaps critically important matter of the non-linearity). However, this re-parameterization appears to offer more than just a reinterpretation of existing models. The primary value added explored in this work is to the analysis (and empirics) of the ability to handle heterophilious graphs. ", "questions": "- What component(s) of GRAFF explain the inference speedup vis-à-vis GCN? Is it due to parameter sharing? Also, no details are given as to how this comparison was decided. Right now I cannot be sure that the comparison is apples to apples; maybe the GCN is a really massive model and the GRAFF is much smaller. More details on this would be great.\n- Why just compare inference time? What about comparison of training time? It seems remiss not to include this, especially since the main paper simply mentions “run-time smaller than GCN” (line 359).\n- The connection to spectral GNNs is interesting. Perhaps this suggests a path to developing expressive power results. ", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First, a congratulations to the authors on a nice piece of work that offers some new perspectives, and promising new directions. I enjoyed reading your work and certainly felt that I learned something in the process. \n\nBelow I discuss some of the things I especially liked in this work, as well as some of the concerns I have about certain aspects. Overall, I think this work contains some great conceptual components, but leaves open so quite important questions, particularly revolving around expressive power. The empirical evaluation is also relatively weak, and leaves me uncertain whether gradient flow models would enjoy widespread adoption. I will explain why I came to each of these beliefs in more detail below.\n\n---\n\n**Strong aspects:**\n\nThe community is moving towards a number of candidate approaches for circumnavigating the weaknesses of message passing networks. Although many ideas have already been given, the debate remains open. The idea of models following gradient flows is creative, and immediately prompted an “aha!” feeling. The community is in need of creative ideas like this, as you never know which will end up having a decisive impact.\n\nOn a technical level, it was pleasing to see the amenability of gradient flows to analysis of smoothing properties. The result in Section 3 on the Dirichlet energy functional were particularly interesting. It is quite unfortunate, however unfortunately typical, that the analysis doesn’t extent to non-linear activations (line 201). \n\n--- \n\n**Weak aspects:**\n\nA major missing piece of the picture is an understanding of the expressive power of the proposed gradient flow models. I found it particularly perplexing that line 202 mentions that no non-linearity is used in experiments. This raises a number of questions: are these models then of comparable expressive power to linear GNNs? Given that having no non-linearity doesn’t hurt performance does this just suggest that the empirical benchmarks considered just aren’t that challenging? \n\nThe paper claims several times that GRAFF models are “explainable”. The basis for this is that the model predictions can be understood by probing property of the energy functional. While this may turn out to be a useful point, the paper does not properly substantiate the claim. Indeed, there are no examples of any such “explanation” in practice. I would ask the author to either drop the “explainable” claim entirely (which isn’t critical in any-case, despite it’s prominent position in the explanation of ”why a gradient flow?”) or to clearly substantiate it, probably via an example. \n\nExperimental evaluation is fairly limited. Table 1 is the main seat of comparisons to other models on node level classification tasks for varying levels of homophily. As billed, the strengths of GRAFF seem to emerge primarily in low homophily (high heterphily) graphs. However, the heterophilic graphs are very small: half only have a few hundred nodes, and the biggest graph considered—“Films”- has 7,600 nodes, and an MLP is a fairly competitive baseline on Films. All this means that the possible benefits to empirical methodology in the immediate future from seem unclear. \n\n---\n\nTo conclude, although the empirics leave a number of question marks over the immediate empirical viability, the idea of graph models via gradient flows along an energy functional is elegant and thought provoking for me. The idea itself, plus the good exploration of the connection to smoothing, is enough to put me on the side of acceptance, but the limitations mentioned keep it only marginally so.\n\n\n---\n\n**Miscellaneous:**\n\n- Clarity in certain places could be improved. For instance, Propositions 2.4 and 3.1 give explicit rates for the energy functional. Since (unless I am missing something!) the key point in both cases is that the models are high-frequency dominant, the rate itself seems to be more of an intermediate step towards this final HFD conclusion. Maybe it is a matter of personal taste but I would have hidden the gory details I the appendix. \n- More generally, the paper is pretty notation heavy\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject