ACMP: Allen-Cahn Message Passing with Attractive and Repulsive Forces for Graph Neural Networks
Authors: Yuelin Wang
Kai Yi
Xinliang Liu
Yu Guang Wang
Shi Jin
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Neural message passing is a basic feature extraction unit for graph-structured data considering neighboring node features in network propagation from one layer to the next. We model such process by an interacting particle system with attractive and repulsive forces and the Allen-Cahn force arising in the modeling of phase transition. The dynamics of the system is a reaction-diffusion process which can separate particles without blowing up. This induces an Allen-Cahn message passing (ACMP) for graph neural networks where the numerical iteration for the particle system solution constitutes the message passing propagation. ACMP which has a simple implementation with a neural ODE solver can propel the network depth up to one hundred of layers with theoretically proven strictly positive lower bound of the Dirichlet energy. It thus provides a deep model of GNNs circumventing the common GNN problem of oversmoothing. GNNs with ACMP achieve state of the art performance for real-world node classification tasks on both homophilic and heterophilic datasets. Codes are available at https://github.com/ykiiiiii/ACMP

Published as a conference paper at ICLR 2023
ACMP: ALLEN-CAHN MESSAGE PASSING WITH AT- TRACTIVE AND REPULSIVE FORCES FOR GRAPH NEU- RAL NETWORKS
Yuelin Wang*
Kai Yi*
Shanghai Jiao Tong University sjtu wyl8 jtu edw.e.du.com en
University of New South Wales kai, yi@unsw. edu, au
Xinliang Liu"
Yu Guang Wang
King Abdullah University of Science and Technology xinliang. wew.linnngiuukkuae edu. sa
Shanghai Jiao Tong University Shanghai Artificial Intelligence Laboratory yuguang. wangês jtu. edu. en
Shi Jin
Shanghai Jiao Tong University Shanghai Artificial Intelligence Laboratory shijin-mes jtu. edu.en
ABSTRACT
Neural message passing a basic feature extraction unit for graph-structured data considering neighboring node features in network propagation from one layer to the next. We model such process by an interacting particle system with at- tractive and repulsive forces and the Allen- Allen-Cahn force arising in the modeling of phase transition. The dynamics of the system is a reaction-diffusion process which separate particles without blowing up. This induces Allen-Cahn message passing (ACMP) for graph neural networks where the numerical iter- ation for the particle system solution constitutes the message passing propaga- tion. ACMP which has a simple implementation with a neural ODE solver can propel the network depth up to one hundred of layers with theoretically proven strictly positive lower bound of the Dirichlet energy. It thus provides deep model of GNNs circumventing the common GNN problem of oversmoothing. GNNs with ACMP achieve state of the art performance for real-world node classifica- tion tasks on both homophilic and heterophilic datasets. Codes are available at https://gites com/ http//yk1111//AMMMMM
INTRODUCTION
Graph neural networks (GNNs) have received a great attention in the past five years due to its power- ful expressiveness for learning graph structured data, with broad applications from recommendation
systems to drug and protein designs (Atz et al. 2021 Back et al. [202]] Bronstein et al. 2021 2017;; Gainza al. 2020 Wu et al. 2020). Neural message passing (Gilmer al. (017)) serves fun- damental feature extraction unit for graph-structured data that aggregates the features of neighbors network propagation. We develop GNN message passing, called the Allen-Cahn message pass- ing (ACMP), using interacting particle dynamics, where nodes are particles and edges representing the interactions of particles. The system is driven by both attractive and repulsive forces, plus the Allen-Cahn double-well potential from phase transition modeling. This model is motivated by the behavior of the particle system of collective behaviors common in nature and human society, for ex- ample, insects forming swarms to work; birds forming flocks to immigrate; humans forming parties
equal contribution corresponndng author

---

Published as a conference paper at ICLR 2023
One-step ACMP
xi 2)) x(0
(G,, x())
Xitaaxx(t + A0)
Repulsive
Attractive
Double well potential
C
An illustration for one-step ACMP. Graph 9, with features x(t) in the purple and green blocks have different treatment of attraction or repulsion. The same color indicates similar node features. The node (() is updated by one step to x(1 + At) via ODE solver. Nodes in the green block tend to attract each other and in the other block, nodes in different colors repel each other, and thus both colors are strengthened during propagation. gives rise to forming bi-cluster flocking. The double well potential turns features darker under gradient flow to circumvent blowup of energy.
Figure 1:
to express public opinions. Various mathematical models have been proposed to model these be- haviors (Albi et al. 2019: Motsch & Tadmor, 2011: Castellano et al. 2009 Proskurnikov & Tempo 2017 Degond & Motsch 2008). There are two major components in this model. First, while the attractive force forces all particles into one cluster, the repulsive forces allow particles separate into two different clusters, which is essential to avoid oversmoothing. However, repulsive forces could make the Dirichlet energy diverge. We augment the model with the Allen-Cahn (Allen & Cahn 1979) term (or Rayleigh friction (Rayleigh 1894)), which is crucial in preventing the Dirich- let energy in the evolution from becoming unbounded, allowing us to prove mathematically that the lower bound of the Dirichlet energy is strictly bigger than zero, hence avoiding oversmoothing. Specifically, we will prove that under suitable conditions on the parameters, the dynamics of the ACMP particle system will time-asymptotically form 2d different clusters and the Dirichlet energy has a strictly positive lower bound.
The structure of ACMP can handle two problems in GNNs: oversmoothing and heterophily, Over- smoothing (Nt & Maeharal 2019; Oono & Suzuki, 2019 Konstantin Rusch et al. 2022) means that all node features become undistinguishable, and equivalently, in the formulation of particle systems, features form only one consensus. Heterophily problems means GNNs perform worse in heterophilic graphs (Lim al. 2021 Yan al., 202T). It is due to the neighboring nodes of differ- ent classes are mistaken for the same class in GNNs like GCN and GAT. However, the presence of repulsion in ACMP makes particles separate into two different clusters, hence provides a simple and neat solution for prediction tasks on both two problems.
Overall, the benefit of the Allen-Cahn message passing with repulsion manifold. 1) It circumvents oversmoothing issue, namely the Dirichlet energy is bounded from below. 2) The network is stable in the sense that features and Dirichlet energy are bounded from above. 3) Feature smoothness (energy decreasing) and the balance between nodes features and edge features can be adjusted by network parameters that control the attraction, repulsion and phase transition. The model can then reach an acceptable trade-off on self-features and neighbor effect, as shown in Figure [] Our model can thus handle node classification tasks for both homophilic and heterophilic datasets by using only one-hop neighbour information. 4) The proposed model can be implemented by neural ODE solvers for the system with attractive and repulsive forces.
In theory, we prove that Dirichlet energy of GNNs with ACMP has lower bound above zero (lim- iting oversmoothing), as well as an upper bound (circumventing blow-up) under specific conditions. This agrees with the experimental results (Section 6). We also prove that ACMP is process for the features to generate clusters thanks to the double-well potential, which provides an interpretable theory for node classification.
BACKGROUND
Message Passing in GNNs Graph neural networks are kind of deep neural networks which take graph data as input. Neural Message Passing (MP) (Gilmer et al. (007 Battaglia et al., 20188) is a most widely used propagator for node feature update in GNNs, which takes the following form: for
2

---

Published as a conference paper at ICLR 2023
the undirected graph 9 (V) is with sets of nodes V and edges E, with (k-1) 1) x; E Id denoting features of node in layer (k: 1) and aje E TRD edge features from node j to node i,
(k) (x] [k- DENN ((())
xx] (k-1) (k-1)
xj .a,s))
where [ denotes differentiable, (node) permutation invariant function, e.g., sum, mean max, and ? and Φ denote differentiable functions such as MLPs (Multilayer Perceptrons), and Nr is the set of one-hop neighbors of node i. The message passing updates the feature of each node by aggregating the self-feature with neighbors' features. Many GNN feature extraction modules such GCN (Kipi & Welling, 2017), GAT (Veličković et al., 2018) and GIN (Xu et al., 2018) can be written as message passing. For example, the MP of GCNs reads, with learnable parameter matrix 0i.1 θ x θ ΣjEMUGI) Våzd; Xj, where d; = 1 + ΣjeN(o) Oj,a and i = (dl..(d......... ) is the degree matrix for A+I. T. Graph attention network (GAT) uses attention coefficients aij similarity information between nodes in the MP update x 0x + 2jEN; Oii Ox2, with
exp (LeakyReLU (a [0x; ( ai ExEN(UD) exp (LeakyReLU (a [Ox, (xx)))
The MP framework was also developed PDE solvers Brandstetter al. (2022b) by embedding differential equations as a parameter into message passing like Brandstetter et al. (2022a). This paper regards particle system evolution (ODE) as message passing propagation, and the appropriate design of the particle system offers desired properties for the resulting GNN.
Graph neural diffusion Neural diffusion equations graphs (GRAND) proposed by Cham- berlain et al. (2021), which provides a unified mathematical framework for some message passings:
i
at x() = dix)
(2)
where (tag(a( where a is function reflecting similarity between nodes and j, and x; is the scale-valued feature for node and x ex,,
MOTIVATIONS
3.1 ATTRACTIVE AND REPULSIVE FORCES
The equation (2) itself can be interpreted in formulation different from diffusion. this paper, we study the neural equations of interacting particle system, which has similar structure to (2). We rewrite (2) into component-wise version and obtain a particle system
i at z:( = Σ a(z,, zz). JEN,
(3)
In the formulation of particle systems, one can easily discover the evolution trend of the features. If a(x,, O, the direction of 24 velocity towards Ty, which means that x; is attracted by zy. In the contrast, if a(x;, 22) < O, has trend to move away from Zy. Hence, a(x; 22,) serves as the attractiveness or repulsiveness of the force between 2; and zy. the diffusion model above, all a(x; Y are positive, therefore all the node features in one connected component attract each other. If the weight matrix (a(x;, x,,) )) X is right-stochastic, one can prove that the convex hull of the features will not dilate in time (see Motsch & Tadmor (2014); Chamberlain al. (2021)). Such feature aggregation means that message propagates along the edges of the graph and some potential consensus forms in the process.
However, the message propagation does not limit to consensus (corresponding to diffusion). In- formation interaction can derive polarization of final judgement when negative message matters in some problems rather than positive message. For instance, in a node classification task on a bipar- tite, the neighbour message is negative since connected nodes belong different classes. In the
3

---

Published as a conference paper at ICLR 2023
formulation of particle systems, the mechanism of positive and negative messages be modelled by adding bias Bag into (3)
aL 2i(1) ()( (1z) --;));;)) Ti).
(4)
JEN,
The coefficient term a(z;, [z) Bi, corresponds to the interactive force. By adjusting Bij both > 0, I; is attracted by ry. While if azz;, - B., < 0, 2, is repelled by z.y. If the coefficient equates zero, there is no interaction between 24 and zy. Then, the dynamics is enabled to adapt both positive and neg- ative message passing. In this way, the neural message passing handle either homophilic or heterophilic datasets (see Section 6 detailed discussion).
the system attractive and repulsive forces co-exist. If
3.2 PSEUDO-GINVBURG-LANDDI ENERGY
However, adding the repulsion term may cause the particles being separated away infinitely, thus the Dirichlet energy becomes unbounded. To avoid this problem, we add a damping term dz;(1 =f), which we call Allen-Cahn lerm. The coefficient convenience.
0 is multiplied just for technical
(1) = a Σ (a( - Bey)(rr xx) 5o, - -xf)-
(5)
at
JEN.
Gradient Flow The variational principle governing many PDE models states that the equilibrium state is actually the minimizer of one specific energy. We first introduce the Dirichlet energy and show that (3) can be characterized by looking into the corresponding Euler-Lagrange equation of the Dirichlet energy. Let adjacent matrix A represent the undirected connectivity between nodes I; and xj, with aij = for (i,j) E & and 0z,j = 0 for (i, g &. The Dirichlet energy in terms of g = (V,E) and node features X E Nxxd takes the form
E(x)
Σ
ax]l|x; - -x,1?
(6)
N
iEV
JEN,
By calculus of variation, we can formulate the corresponding particle equation Ox;
Ox = VxE,
aE
= Oz,
Ci x..)
Öt
Ot
N
JEN.
On the RHS of (7), the summation takes over the one-hop neighbors N₁ of node i, which aggregates the impact from the neighboring nodes. Equation (7) is (5) when one takes adjacent matrix A as the weight matrix (a(x,, N)))
Particle equation with the double-well potential To avoid blowing-up of the solution, one can design an external potential to control the solutions so they are bounded. Here, we define the pseudo- Sintburg-Landla energy on graph G denoted by Φ I.²(V) + R, as combination of the interact- ing energy and double-well potential W : R4,, with
(xx) = (5/4)(1 - 1|=
((x)
2 a Σ
Σ
(ai, - Br,) -,,1| Σ W(x.), (8) iEV
iEV JeN.
where parameters a, > O are used to balance the two types of energy. From now on, we denote a(z;, I2) by di.j for simplicity. The neculo-GizburrgLLnndee the matrix (a:,j- Nx. N can be non-positive definite. 3; 's all equate zero, it then becomes the
energy is not a true energy because
Ginzburg-Lae Lanzurgg-Landuu energy defined in Bertozzi & Flenner (2012) Luo & Bertozzi (017). Using this
Ox combined energy, we can obtain the Allen-Cahie equation with repulsion on graph as a: Vx which is equivalent to (5).
4 ALLEN-CAHI MESSAGE PASSING
We propose the Allen-Cale Message Passing (ACMP) neural network based on equation (5). where the message is updated by the evolution of the equation via neural ODE solver. To our best knowledge, this is the first time to introduce a type of message passing to amplify the difference between connected nodes by repulsive force.
4

---

Published as a conference paper at ICLR 2023
Figure 2: We compare the evolution of node features in GCN and ACMP. The initial position is represented by the 2-dimensional position of the nodes, which is shown in the first column. The GCN aggregates all node features by taking the weighted average of its neighbors' features. With the propagated steps increasing, all the nodes' features shrink to a point, which gives rise to over- smoothing. When it comes to ACMP, nodes' features are grouped by four attractors, which helps to circumvent oversmoothing. More details can be seen in Section
Network Architecture Suppose d-dimensional node-wise features represented by a matrix x where row i represents feature of node i. Our scheme first embeds the node feature x(0) MLP(xx") by a simple multi-layer perceptron (MLP), which is treated as an input for ACMP prop- agation A Rd - Rd, by x0) + x(T), where x(T) = x(0) - fo" @x(t)
x(0) = MLP (xm)),
where ax(1) is estimated by ACMP defined on G based on (). The node features x(T) at the ending
Φt time are fed into an MLP based classifier. Then, we define the Allen-Cahn message passing by
0 Ot
(t)
O Σ - x (t)) JEN,
xxx (t( xt))). (9)
Here a, 0 Rd are learnable vectors of the same length as the node feature x,, While we can use more general case when each edge (i, uses different trainable 3t,j. we have simplied to single hyper-parameter E g U {0}. which makes the network and optimization easier. The in our model is a crucial parameter, which can be adjusted such that the attractive and repulsive forces both present to enrich the message passing effect. If one chooses ō 0, B our model is reduced to the graph neural diffusion network (GRAND) in Chamberlain al. (022I). In experiments, we would make significant use of nontrivial 8 and B3.
The operations of all terms are chan involving d channels, except a(x;(1), x;))), and @ represents channel- wise multiplication for d feature channels. Figure [ illlustrates the one-step ACMP mechanism (9): Nodes with close colors attracts each other otherwise repel. Nodes in the same block tend to attract each other and both colors are strengthened during message passing propagation. The double-well potential prevents the features and Dirichlet energy from blowup. In this process, node feature x(t) is updated to x(t + At) for a time increment At. Ultimately, a bi-cluster flock is formed for node classification.
In the propagation of ACMP in 9.. we need to specify how the neighbors are interacted, that is how the (I), x, (t)) is evolved with time. There many kinds of methods to update the edge weights. The two typical types are GCN (Kipf & Welling) 2017) and GAT (Veličković et al. 2018)).
ACMP-GCN: this model uses deterministic (t), x, (t)), which is given by the adacency matrix A (at.s) of the original input graph G and does not change with time. That is, the coefficients in
GON == at.5/ / d.dg. The message passing of (9 is reduced
GCNs o
(t) Σ
GON ()) x1))) (1)
xi(1) o x;))) o()))) (10)
0t
JEN.
5

---

Published as a conference paper at ICLR 2023
we can replace 2 in (10) by the attention coefficients 1 of GAT, which with extra trainable parameters measures the similarity between two nodes by taking account of both node and structure features. The system then drives edges to update in each iteration of message passing.
ACMP-GAT:
Neural ODE Solver Our method uses ODE solver to numerically solving the equation (9)) and (IO). To obtain the node features x(T), we need a stable numerical integrator for solving the ODE efficiently and backpropagation of gradients. Since our model is stable in terms of evolution time, most explicit and implicit numerical methods such as explicit Fuler, Runge- Kutta 4th-order, midpoint, Gormand-Princee (Chen al. 2018 Lu et al. 2018 Norcliffe et al. 2020) Chamberlain et al. 2021) work well as long as the step size is small enough. In experiments, we implement ACMP using Dormand- Prince- method which provides a fast and stable numerical solver. The network depth of ACMP-GNN is equal to the numerical iteration number n, set in the solver.
Computational Complexity The computational complexity of the ACMP is O Ednz), ((NEEnn), where D4, N, E and are number of time steps in time interval [0, T). number of nodes, number of edges and number of feature dimension, respectively. Since our model only considers nearest (one-hop) neighbors, is significantly smaller than that of graph rewiring (Gasteiger et al.] 2019 Alon & Yahav 202l and multi-hop (Zhu et al. 2020 methods.
Channel Mixer Channel mixing can be spontaneously introduced from the perspective of diffu- sion coefficients though our model is previously written in the channel-wise form. Whether channel mixing happens depends on the specific GNN driver we choose for ACMP. When the coefficients (tx, x,) (t)) in (9) that do not update with time are a scalar or vector, like in ACMP-GCN the operations of the message passing propagator are channel-win and channel mixing is not incorpo- rated. On the other hand, the ACMP-GAT with graph attention driver incorporates a learnable chan- nel mixing when the coefficients tensors. The channel mixer can be introduced by generalizing the Dirichlet energy to high dimension, for example, E(x) := N
Σ Σ (x; x,)" a (x; - x,), JEVJEN,
when any E R are connectivity tensors.
5 DIRICHLET ENERGY
The dynamics 55) can circumvent the oversmoothing issue of GNNs (Nt & Maehara, 2019 Oono Suzuki| 2019] Konstantin Rusch et al. 2022). Oversmoothnng phenomenon means that node features converge to the same constant consensus forms - as the network deepens, and equivalently, the Dirichlet energy will decay to zero exponentially. This idea was first introduced in Cai & Wang 2020 Konstantin Rusch et al. (2022) gives an explicit form for oversmoothing.
In our model, as we will show below, the node features in each channel tend to evolve into two clusters departing from each other under certain conditions. This implies strictly positive lower bound of the Dirichlet energy. In addition, the system will not blow up thanks to the Allen-Cahn term. We put all the proofs and some related supplementary results in the appendix.
Proposition 1. 8 > 0. the node features x; in (5) is bounded in terms of || Il and energy for all t >> 0, Le., E(x(()) < C, and ||x|| S C, where the constant C only depends on N and Amax-
In the following propositions, we imitate the emergent behavior analysis in Fang et al. 2019 (see Appendix for details). For graph G with N nodes, its vertices said to form bi-cluster flocking there exist two disjoint sets of vertex subsets {x]
(1) (1),N, Je and {x," (2)
3 satisfying
(2 2f)) < 0C,
sup max 10 (2(( 2 (2) (t) oo; Ostcoo 15t,jEN2
max 0steco ISIJEN
sup
(1I)
(11) C T 0 such that
min I.
{10
(t) (1)
(2) (0)) 2 vt > T
where 2.!1
x denote any component of xf! xx(
We now show the long-time behaviour of model (5) following the analysis of Fang et al. (2019) for
strength coupling (o: 8) that satisfies the following condition: there exists (Br,) such that 7

---

Published as a conference paper at ICLR 2023
{1....,N) N can be divided into two disjoint groups I1, I2 with N1 and N2 particles respectively: for i, E Zi, for i,j I2, otherwise,
0 < S S D.jj with J. =- Di.j - -Bis
< S S D. with a. == di - -B,s
(12)
0 0 R. S D with T. = (at.) Bag))
where S, D are independent of time I. The S and D in (12) are the repulsive and attractive forces. We prove that if the repulsive force between the particles is stronger than the attractive force, that is, > D, the system is guaranteed to have bi-cluster flocking, as shown in Proposition 2 below. For time t 2 O, suppose x. (t) and x.
(2) (t) are the feature centers of the two groups of the particles {x} ( (x()(()) (t)) and (x) (2) (t) which are partitioned as above from the whole vertex set V/ given by M
1 N2
(1)
1 NI Σ (O) X (1)
(2)
(t).
22
1=1
Suppose x. (1) has the d-dimensional feature, and let x x h I.... d, be the thth (dimension)
component of the feature x! (t), 1,2.
Proposition 2. The system (5) has a bi-cluster flocking for each k 1, ...., d, the initial [x! (1 (0)
(2)) c.k (0) >> 1, and if there exists positive constant 1j such that
aSS - D) min( NNi N2) 2 +1,
(13)
where the is the weight factor for the double-wel potential the equation (5) Proposition 3. For system T such that VI T
( with bi-cluster flocking, there exists a constant C > 0 and some time
(t) (xx))xx()(()) (t) C>0, Vi,j. Thus, if the non-zero aij are all positive, the Dirichlet energy for ACMP is lower bounded by posilive constant.
6 EXPERIMENTS
Dirichlet Energy We first illustrate the evolution of the Dirichlet energy of ACMP by an undi- rected synthetic random graph. The synthetic graph has 100 nodes with two classes and 2D feature which is sampled from the normal distribution with the same standard deviation a = 2 and two means fl1 0.5, P22 = 0.5. The nodes are connected randomly with probability p = 0.9 if they are in the same class, otherwise nodes in different classes are connected with probability = 0.1. We compare the performance of GNN models with four message passing propagators: GCNs (Kipf & Welling 2017), GAT (Veličković et al.) 2018), GRAND (Chamberlain et al., 202 and ACMP- GCN. Figure 2, we visualize how the node features evolve from their initial state to their final steady state when 50 layers of GNN are applied. Additionally, in Figure 3 show the Dirichlet energy of each layer's 's output in logarithm scales. Traditional GNNs such as GCNs and GAT suffer oversmoothing as the Dirichlet energy exponentially decays to zero in the first layers. GRAND relieves this problem by multiplying a small constant which can delay all nodes' features to collapse to the same value. For ACMP, the energy stabilizes at the level that relies upon the roots of the double-well potential in after slightly decaying in the first two layers.
Node Classification We compare the performance of ACMP with several popular GNN model chitectures on various node classification benchmarks, containing both homophilic and heterophilic datasets. Graph data is considered as homophilic (Pei al., 2020) if similar nodes the graph tend to connect together. Conversely, the graph data is said heterophilic if it has a small homophily level, when most neighbors do not have the same label with source nodes. We aim demonstrate that ACMP is a flexible GNN model which can learn well both kinds of datasets by balancing the attractive and repulsive forces. The GCN for examples cannot perform well for heterophilic dataset as its message passing aggregates only the neighbor (1-hop) nodes. The neural ODE is solved by Forchdi f feq package with Dormand- Prince adaptive step size scheme. Only few hyperparam- eters needed to be tuned in our model. For all the experiments, weight decay, dropout, hidden dimensional of the 3 which controls the repulsive force between nodes. We outline the details of hyperparameter search space in Appendix D.
fine tune the learning rate,
7

---

Published as a conference paper at ICLR 2023
185
GEN
28'
C2k
Taxas
2015
0.0
0.1
0.2
0.3
0.4
0.5
Jagan
0
Figure 3: Evolution of Dirichlet energy E(x") of layer-wise node features X" propagated by GCN, GAT, GRAND, ACMP-GCN.
Figure 4: Significance plot for B in terms of test accuracy on Cora (orange) and Texas (blue) with 10 fixed random splits.
Homophitic datasets Our results are presented for the most widely used citation networks: Cora (McCallum et al., 2000), Citeseer (Sen et al. 2008) and Pubmed (Namata et al. 2012). Moreover, we evaluate our model on the Amazon co-purchasing graphs Computer and Photo (Namata al.)
2012), and CoauthorCS (Shchur et al. 2018). We compare our model with traditional GNN models: Graph Convolutional Network (GCN) (Kipf & Welling 2017). Graph Attention Network (GAT) Veličkovié al.) 2018), Mixture Model Networks (Monti et al., 2017) and GraphSage (Hamilton
ct al. 2017). We also compare our results with recent ODE-based GNNs, Continuous Graph Neural Networks (CGNN) (Xhonneux al. 2020), Graph Neural Ordinary Differential Equations (GDE)
(Poli et al. 2020) and Graph Neural Diffusion (GRAND) (Chamberlain et al. (021). To address the limitations of this evaluation methodology proposed by Shehur et al. (2018), report results for
all datasets using 100 random splits with 10 random initialization's is and show the results in Table
Table 1: Test accuracy and std for 10 initialization and 100 random classification benchmarks. Red (First), blue (Second), and violet (Third) the best three methods.
splits on six node
Random Split
Cora 0.83
CiteSeer 0.71
PubMed 0.79
Coauthor CS
Computer 0.77
Photo
Homophily level
0.80
0.83
GCN Kipf & Welling
2017
81.5 1.3
71.9 1 1.9
77.8 1 2.9
91.1 0.55
82.6 226622 2.4
91.2 1.2
GAT Velicovii
81.8
71.4
78.7
90.5
78.0
85.7
GAT-ppr Velickovic ot al
2018
81.6 0.3
68.5
76.7 0.3
0..
8.1
90.9 0.3
MoNet Mont ot ai 2017
81,3= 1.3
712+20
28.
9.8
83.5=22
91.2
Graph (Hamiion al. 2017
7.72
716120
77.4
91.31228
82.4 1.8
91.41.33
GraphSage-max ('Tamilion el 2017
76.6 1.9
67.5
76.1
85.0
N/A
90.4 1.3
CGNN (Xhonneux
2020
81.4
1.8
66.6
9.2
80.29 + 2.0
91.39 + 1.5
GDE (Poli et alg 2040
78.7
718
3.79
91.6
81.9
92.4 2.0
GRAND- liambrrion Caanneeiann
7.8117
0.4
1.2
92.3
ACMP-GCN (ours)
8.9
75.0=1.0
78.9110
0.5
83.5 1.4 14.41.6
91.8 =
ACMP-GAT (ours)
82.3 0.5
75.5 1.0
7.44
91.8
91.1 0.7
Heterophilic datasets We evaluate ACMP-GCI on the heterophilic graphs; Cornell, Texas and Wisconsin from the WebKB " In this case, the assumption of common neighbors does not hold. The poor performance of GCN and GAT models shown in Table indicates that many GNN models struggle in this setting. Introducing repulsion can improve the performance of GNNs on heteroplilic datasets significantly. ACMP-GCI scores 30% higher than the original GCN for the Texas dataset which has the smallest homophily level among the datasets in the table.
Attractive and Repulsive interpretation As shown in Table 2 and Table D ACMP-GCN and ACMP-GAT achieve better performance than GCN and GAT both homophilic and heterophilic datasets. The majority of as,j 3 in the homophilic are positive, which means most nodes are attracted to each other. Conversely, most a, for the heterophilic negative, which means that most nodes are repelled by their neighbors. Several GNNs exploiting multi-hop information can
http:/ /ww.. cmu amu.edd//aees cmu. http:////../ooooooo....e///////e 11 wwww/////aa/ wwkb/
8

---

Published as a conference paper at ICLR 2023
Table 2: Node classification results heterophilic datasets. We the 10 fixed splits for training. validation and test from Pei et al. (2020) and show the mean and std of test accuracy. Red (First), blue (Second), and violet (Third) are the best three methods.
Texas 0.11
Wisconsin 0.21
Cornell
Homophily level
0.30
GPRGNN (Chien et al. 2021
78.4 + 4.4
82.9
4.2
80.3 +
H2GCN Zhu
84.9
87.7
5.0
82.7 5.3
GCNI Chen el al.
20.0
77.6 3.8
80.4
$0.4
3.8
Geom-GCN (Fer a..
2020
66.8 + 2.7
64.5 3.7
60.5 +:37
PairNorm Zhao Akogiu
2020
60.3
68.4
5.2
GraphSAGE (Hamitin et 2017
6.1
5.6
76,0
MI.P
+0.8+4.8
85.3
+-3
81.9 6.4
GAT (Veličković 2018
6.62
4.14
61.9
GCN Kipl Welling 2017
5.,1
51.
3.1
60.5
GraphCON (Konstami Kusch et al. 2022
85.4 4.2
87.8
3.3
84.3
4.8
ACMP-GCN (ours)
86.2
3.0
86.1
4.0
85.4 7.0
achieve high performance in node classification (Zhu et al. 2020 Luan et al. 2021). However, high- order neighbor information will make the adjacency matrix dense and therefore can not be extended to large graphs, due to heavier computational cost. In our model, we take only one-hop information into account and add repulsive force (3 2 0) message passing, which has achieved the same or higher level of accuracy as multi-hop models in heterophilic datasets.
Performance of ACMP to 3 Hyperparameter / is a signal of the repulsive force, meaning that when oiy - is negative, the two nodes repel one another. To illustrate f3's impact, diffusion term as dij do not change during the ODE process and all the changes are related to B. As shown by Figure 4 ACMP performs best in Cora (orange curve) when all nodes are attracted to one another i.e., all dzj 3 is positive. As the beta increases, the performance of the model degrades. In contrast, for the Texas dataset, when all force is attractive, ACMP achieves only 70% accuracy (blue curve). As 3 increases, most ai ,8 is negative, and the model's 's performance gets better.
GCN as
7 RELATED WORK
Neural differential equations The topic of neural ODEs becomes an emerging field since E (017 and Chen et al. (2018), with many follow-up works in the GNN field (Avelar et al. 2019 Poli
ct al. 2020 Sanchez- Sanzaez-Gonzalez et al. 2019). GRAND (Chamberlain et al. 2021) propagated GNNs by the graph diffusion equation and Wu et al.] (2023) developed an mvegy-ccosstrinee diffusion transformer. GraphCON (Konstantin Rusch et al. (002)) employed second-order system quer oversmoothing of deep graph neural networks. By exploiting the fixed point of the dynamical system, Gallicchio Micheli (2020) proposed FDGNN an approach graph classification.
Allen-Cahi based variational graph models In Bertozzi & Flenner 2012); y; Luo & Bertozzi (0177) ; Merkurjev et al. (2013) and references therein, authors extended Allen-Cahn related poten- tial to graphical framework and developed class of variational algorithms to solve the clustering, semisupervised learning and graph cutting problems. The new ingredient of graph neural network which enables us combine learnable attraction and repulsion separates our method from the clas- sical variational graph models.
8 CONCLUSION
We develop new message passing method with simple implementation. The method is based on the Allen-Cahn particle system with repulsive force. The proposed ACMP inherits the characteristic dynamics of the particle system and thus shows adaption for node classification tasks with high homophily difficulty. Also, propels networks to dozens of layers without getting oversmoothing. A strictly positive lower bound of the Dirichlet energy is shown by theoretical and experimental results which guarantees oonoomersmootiing of ACMP. Experiments show excellent performance of the model for various real datasets.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work was supported by the Shanghai Municipal Science and Technology Major Project, and Science and Technology Commission of Shanghai Municipality grant No. 20JC1414100, (221IHZDDZX0102) and Shanghai Artificial Intelligence Laboratory (P22KN00524). S. Jin was partially supported by the NSFC grant No. 12031013.
REFERENCES
Giacomo Albi, Nicola Bellomo, Luisa Fermo, S-Y Ha, J Kim. Lorenzo Pareschi, David Poyato, and Juan Soler. Vehicular traffic, crowds, and swarms: From kinetic theory and multiscale methods to applications and research perspectives. Mathematical Models and Methods Applied Sciences,
19110);191122005 2019.
Samuel Allen and John Cahn. microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening. Acta Metallurgica, 27(6):1085-1099 1979.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Kenneth Atz, Francesca Grisoni, and Gisbert Schneider. Geometric deep learning molecular representations. Nature Machine Intelligence, pp. 1-10, 2021.
Pedro HC Avelar, Anderson R Tavares, Marco Gori, and Luis C Lamb. Discrete and continuous deep residual learning over graphs. arXiv preprint arXiv: 1et.19991..0554.. 2019.
Minkyung Baek, Frank DiMaio, Ivan Anishchenko, Justas Dauparas, Sergey Ovchinnikov, Gyu Rie Lee, Jue Wang, Qian Cong, Lisa N Kinch, R Dustin Schaeffer, et al. Accurate prediction of protein structures and interactions using a 3-track network. Science, 373:871-876, 2021.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst. Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/ 806.01261, 2018.
Andrea L Bertozzi and Arjuna Flenner. Diffuse interface models graphs for classification of high dimensional data. Multiscale Modeling Simulation, 10(3):1090-11 2012.
Johannes Brandstetter, Rob Hesselink, Elise van der Pol, Erik Bekkers, and Max Welling. Geometric and physical quantities improve E(3) equivariant message passing. In ICLR, 2022a.
Johannes Brandstetter, Daniel E. Worrall, and Max Welling. Message passing neural PDE solvers. In ICLR, 2022b.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18 (144):1-42) 42, 2017.
Michael Bronstein, Joan Bruna, Taco Cohen, and Petar Veličkovié. Geometric deep learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv preprint arXiv:2104.13478 2021.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In ICML Workshop Graph Representation Learning, 2020.
Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics of social dynamics.
Reviews of Modern Physics, 81(2):591, 2009.
Benjamin Paul Chamberlain, James Rowbottom, Maria I. Gorinova, Stefan D Webb, Emanuele Rossi, and Michael M. Bronstein. GRAND: Graph neural diffusion. In JCML, 2021. URL
httpss://ppenree net net/Forum?id= ffu_cjsaRE
10

---

Published as a conference paper at ICLR 2023
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In JCML, pp. 1725-1735. PMLR, 2020.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In NeurIPS, volume 31, 2018.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pager- ank graph neural network. In ICLR, 2021. URL
formm?
n6j17fLxrP
Felipe Cucker and Steve Smale. Emergent behavior in flocks. IEEE Transactions Automatic Control, 52(5):852-862, 2007.
Pierre Degond and Sébastien Motsch. Large scale dynamics of the persistent turning walker model of fish behavior. Journal of Statistical Physics, 131(6):989-122) 2008.
Weinan E. proposal on machine learning via dynamical systems. Communications in Mathematics and Statistics, 1(5):1-11, 2017.
Di Fang, Scung- Yeal Ha, and Shi Jin. Emergent behaviors of the Cucker-Smale ensemble under attractie-reeuulsive couplings and rayleigh frictions. Mathematical Models and Methods Ap- plied Sciences, (3(07):1349-1388 2019.
Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, D Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geo- metric deep learning. Nature Methods, 17(2):84-199, 2020.
Claudio Gallicchio and Alessio Micheli. Fast and deep graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 1898-3905, 2020.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In NeurlPS, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML., 2017.
Seung-Year Yeal Ha and Eitan Tadmor. From particle to kinetic and hydrodynamic descriptions of flock- ing. Kinetic & Related Models, 1(3):115, 2008
Seung- Sealg-Yeal Ha, Taeyoung Ha, and Jong-Ho Kim. Asymptotic dynamics for the Cucker-Smale-type model with the Rayleigh friction. Journal of Physics A: Mathematical and Theoretical, 43(31); 315201, 2010.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Konstantin Rusch, Benjamin Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M. Bronstein. Graph-coupled oscillator networks. In ICML,, 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Yiping Lu, Aoxiao Zhong, Quanzheng Li, and Bin Dong. Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations. In ICML, pp. 3276-3285, 2018.
Sitao Luan, Chenqing Hua. Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Wen Chang, and Doina Precup. Is heterophily real nightmare for graph neural networks to do node classification? arXiv preprint 10ii:2/09.05660 109.05641, 2021.
Xiyang Luo and Andrea L Bertozzi. Convergence of the graph Allen-Cahn scheme. Journal of Statistical Physics, 167(3):934-955) 2017.
11

---

Published as a conference paper at ICLR 2023
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Ekaterina Merkurjev, Tijana Kostic, and Andrea L Bertozzi. An MBO scheme on graphs for classi- fication and image processing. SIAM Journal Imaging Sciences, 6(4):1903-1930, 2013.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In CVPR, pp. 5115-5124, 2017.
Sebastien Motsch and Eitan Tadmor. A new model for self-organized dynamics and its flocking behavior. Journal of Statistical Physics, 144(5):223-947, 2011.
Sebastien Motsch and Eitan Tadmor. Heterophilious dynamics enhances consensus. SIAM Review, 56(4):577-621, 2014.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp. 1, 2012.
Alexander Norcliffe, Cristian Bodnar, Ben Day, Nikola Simidjievski, and Pietro Liò. On second order behaviour in augmented neural ODEs. In NewrIPS, volume 33, pp. 5911-5921, 2020.
Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 1905.0950, 2019.
Reza Olfati-Saber, J Alex Fax, and Richard M Murray. Consensus and cooperation networked multi-agent systems. Proceedings of the IEEE, 95():225--333, 2007.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN; geo- metric graph convolutional networks. In ICLR, 2020. URL
forum?id-SSe2ayee
Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations. In AAAI Workshop on Deep Learning on Graphs: Methodologies and Applications, 2020.
Anton V Proskurnikov and Roberto Tempo. tutorial on modeling and analysis of dynamic social networks. Part I. Annual Reviews in Control, 43:65-79, 2017.
Loan Rayleigh. JWS, The Theory of Sound, vol. 1. Macmillan, London (reprinted Dover, New York, 1945), 1894.
Alvaro
Victor Bapst, Kyle Cranmer, and Peter Battaglia. Hamiltonian graph networks with ODE integrators. In NeurIPS Workshop on Machine Learning and the Physical Sciences, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Fliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-93, 2008.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1.05668 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. Dif- former: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.09447 2023.
12

---

Published as a conference paper at ICLR 2023
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 24, 2020.
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In ICML, pp. 10432-10441, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2018.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
Lingxiao Zhao and Leman Akoglu. PainNorm: Tackling oversmoothing in GNNs. In ICLR, 2020. URL / net/ wwt.teeuummiiie worrmmidddreellrttt....
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NeurlPS, volume 33, pp. 7793-7804, 2020.
13

---

Published as a conference paper at ICLR 2023
The Appendix is stuructured follows:
In Appendix
A we state more related works on flocking or consensus model.
In Appendix we introduce several model variants with different damping term with D
In Appendix
we give more analysis on the GRAND model and the attraction only case of equation addition, we prove the statements in Section S i.e. Proposition [ Proposition
and Proposition 3
In Appendix D we show additional experimental details and an ablation study for ACMP.
A FLOCKING AND CONSENSUS
The microscopic (agent-based particle systems) modeling of flocking and consensus has been tensively studied. Motsch & Tadmor (2014) reviews general class models for self-organized dynamics and shows the relationship between heterophily and conseus. Castellano et al. (2009)
presents a series of social and dynamics under the formulation statistical physics. The flocking
problem is to some degree similar the general consensus problem (Olfati-Sabed et al. 2007) which
studies the emergent behaviours for multi-agent systems. The Cucker-Smale (in short C-S) model
Cuccker & Smale 2007) famous model in this field considering second-order system adopting to classical dynamics, Ha & Tadmor (2008) and Ha et al. (2010) discuss asymptotic flocking for the C-S model with the Rayleigh friction. Fang al. (2019) furthermore studies frameworks leading to bi-cluster flocking for the C-S model with the Raleigh friction and attractiverrepllsive coupling.
B MODEL VARIANTS
More clusters We simply replace the double well potential W by multi-well potential to generate more equilibria. We provide two alternatives here. One can use a higher-order polynomial construct additional wells. In general, (2k + 1)th order polynomial can produce k + stable equilibria in a proper form, which gives rise to more stable clusters. One can also use sin( + 1)TZ + 3). 0, k,, defined on the interval [-1, 1] as the multi-well potential, which has / stable equilibria.
Stronger trapping force As the consensus state (i.e., 2, = xj for all i.j) might not a global equilibrium of (TO), particles could escape from well of the potential of W to another well. We can circumvent this instability by enhancing the attraction of the wells, which can be achieved by reducing the diffusion power around wells:
à Øt (t) a Σ (a GNN JEN
(t)) (1)(()))) 02 (t) (
(14)
where 'GNN' in a GNN can be GCN or attn, and 2 is 3 z. With this modification in 14p. in any channel k, if any particle x! (k) gets caught in one potential well, then is not likely to escape:
Proposition 4. For 14), there exists proper 8' such that x 1-1,-1+00 u1)
then particle x; (k) cannot transition into another well.
Proof. For the case, assume I; + for c S 8' 1 at a certain time to, that is.
1=to I; [-1,-1 d'). We want show da: < 0, which means
a Σ aaslo, xx)(1 - x2)² x1)==))--20 JEN.
- =x7)-
By Σ 0i from (26), the above inequality is equivalent to JEN:
81 81 -
8
Σ ai
+ 1
+ 2ac
(15)
cc
2x
JEN,
14

---

Published as a conference paper at ICLR 2023
Since {2,} are bounded (See Proposition (15) is satisfied for sufficiently small 8. The other case H2 = 1 - e can be similarly proved.
For the * case, we also assume z; -1 for S 8' at certain time to. Similarly with 15
we have
1 el
Σ (a.s B)a jEN;
+ +1 (3)(E - 2cE
+ d, - 1 e(1 -d3).
0 2 EE
By the boundedness of (1;))==: properly small 8' can be found.
C SUPPLEMENTARY RESULTS AND PROOFS OF PROPOSITIONS IN SECTION 5
We assume that di is symmetric, and ai 0 if as, á 0. This condition means that graph is undirected. Since we deal with each channel independently, we abuse the notation to let x; denote one feature component of node x; simplifying the notation in proofs.
C.1 THE GRAND MODEL
First, we consider the oversmoothing phenomenon if there is only the diffusion process with diffu- sion coefficients independent of F;, which is a specific model of graph diffusion network (GRAND) (Chamberlain et al. 202T).
=
Σ 0t.5(1z =22)
(16)
5-6-5)EE
Proposition 5. Let denote the degree matrix, i.e., D == diag(d1, dx). where d; = E, atd
Then D A is symmetric positive semi-definite with the eigenvalues O = 2o S A1 S ... S A < 00. Let Amin
be the smallest positive eigenvalue, then for all 2 0, there exists constant C> 0 such that E(x(t)) S C' C'exp(-Xannn t).
Proof. Let C D A, we have,
x(t) = x2
Using eigenvalue decomposition, the solution xxft) writes
x(I) UTe A Ux(()
(17)
Since the Dirichlet energy can also be written as
E(x(t) x(t) Lx(t),
(18)
Taking
17 to 18
gives
E(x(t)) = x0) U - M
(19)
Therefore, E(x(()) S C exxp(-X2 (i for some constant C > 0.
Proposition We also consider more general case,
d
dt (t) = Σ
alx,, 2z) vz):
(20)
with a(x,, a(I),II)) xxi) 2 amin for any 24, Ij.
Let the mass center I, N Eiey Zi. From the symmetry of a axx; II2) and 20) we obtain dx,/dtt O for any >> Without loss of generality, we may assume
(0) = O,
(21)
and graph G is connected, Le., v(i.j) E V x V, contains a path from j. Then have, | < [|x(()) (2mmmllaa
200ia 20min Amin' and E(x(t)) & >mmal|lx(0)] 22 Amint. Note that the above estimates hold true for any initial condition (0) = since & satisfies the ODE system (20) up to a constant. If x0( = c, I; will converge to in time. G is not connected, then we just need to consider each connected sub-graph separately with the assumption z (0) = / Eiey I; è' for each sub-graph G' (V", E²) x in each sub-grapi will converge constant d' independently.
15

---

Published as a conference paper at ICLR 2023
Proof. We multiply 2, on both sides of the equation
20 and over x; obtain
34 dxi
Σ
a (z)) (rz x2) xi
(22)
dt
JEN()
||| = -2 Σ
(Zi, (z)) (zg - Iz¹) -x;)²
(23)
dl
(Kr))E
d
|=>1| < -20mia
Σ
(x) x2,)
(24)
(1))EE
The RHS 24 can be written in matrix form with L == D A,
Σ (a,- - xx:)
Σ
oi (2g - x.) TT Lx.
(i,))8
(iJ)EVXV
Since G is a connected graph, is the only eigenvector consisting of the kernel space of L, therefore,
x La \ for any x satisfying Σiev 22 = 0. Then, (24 leads to
d |0 & -22min | dt
(25)
This yields the decay estimates for ||= and E(z(t)):
||x(t)]1 = [1x(0)]| -2 Amiat
E(x(t)) S Amax [nxx|[= 20mindmiat
C.2 THE MODEL WITH ALLEN-CAME TERM
Next, we consider the case B = 0 but with Allen-Cahn term:
di ai((1 Σ a(zi, xz) + dzz (1 (1-xi) --x;),
d
(26)
a(I,; = az 20, 0, Vi,jEV V Ea(as, = 1, Vj E V.
Proposition Suppose x (fi xby) global equilibrium (or steady state solution) of 26 on R and x, then x. E 1-1
Proof.
Suppose x² achieves the equilibrium of 26). and xt 2 ot Vi. a(xt, - =xt) I 0 and xi (1 - x < O, which contradicts with Bt T = 0.
x > 1, then
Σ
j((KE)EEE
The emergence of clusters depends on the distribution of initial features. If all the initial features are in only one potential well, then intuitively it is impossible to produce more than one cluster in the dynamics (26). As a simple transference of Lemma 3.2 Ha et al. (2010), we can prove this. Set
x (1) max (I). x (I) min (t;());
(27)
where x; is still some component of node feature x,. Assume x. N are both Lipschitz continuous and therefore they are almost differentiable everywhere in time t.
Proposition 8. Let {#r} be the solutions of (26). then the following holds. (i) If Th (0) > 0, then xt (t) 2 frror all > 0.
(ii) Mf (0) O, then M (t) < for all 0.
Proof. The proof was essentially given by Ha et al. (0100). For the sake of completeness. we give a proof here. (i) If mh (0) O, we assert there exists time sequence { satisfying tu
t <... <t ...,, xd (t) is differentiable in each time interval (fz-1.tz) ty) and x."" when / E [0, 4). By induction, firstly we set
(1) 2 0, 1. [0,
16

---

Published as a conference paper at ICLR 2023
If 2 becomes negative in the time interval (ti, t(+1) there exists t" E (t,, f++1) such that x (t*) 0 by the continuity of (t). One can assume (t) = 2x(() for some node 2; in some time interval subset to (t,, 12+1). At that moment,
dx di (t))
-x:0(((()))((())))))))))))))))() Σ (1)(()))) xx(())) + (1-)((12=)11))
(28)
20
Hence, the trajectory " becomes non-decreasing at t². By induction, we derive (i).
(ii) can be proved by the same argument as those for (i).
Now we consider the second kinetic model [1... We can prove that if any particle x; gets caught in one potential well, then it will not escape from that well.
C.3 THE ATTRACTIVE-REPULSII MODEL
We first show that the solution features of graph in Allen-Cahn model below is bounded. For sim- plicity of the proof, we rewrite 10 in component form where we let a(z;, == azj Big
d
(1) =a
Σ (1),, - xz) + dz; (1 x??)
(29)
dt
Model (29 allows negative a(z,, my) which is different from the condition in 26
Proof of Proposition
We multiply both sides of the following equation and sum over to obtain
dr,
Σ a(I;, I;) (I, xz) - -x² + 2z
dt
JEN,
1 ?
a(x;, m3) (Ir xx) xi - x; + ot
dt
(30)
JEM;
dx
Σ
a(z;, (xz - xz) 21 + x
2 1EV
dt
NEV
JEN
By grouping a(x; R.)) (xz - 2z4) Tig then
|
1
Σ
Σ iEV JEN;
a(z,, (.) (I, (I,- x1)² 2-)2-A - x7 + ||
(31)
dt
2
iev
Note that a(z,, my) are bounded for any (I;, Let the |a(zi, 21)) pending on hyper-parameters Rt By the Cauchy-Schwan inequality,
Dj for constant D, de-
Ja(2;,2;)(a, - 2D x3))
Hence,
ΣΣ JEN;
a(z,, 23)² < ca ||,1|/
Also, Σ xt 2 ca||=]| for constant es depending only N. Taking the above estimates to 31
gives
d
dt |||| < 22c3|lol11 + (ca + 2]
17

---

Published as a conference paper at ICLR 2023
If |a||| blows up for 0, the ||>||| - time t increases, and d |z||| >> for all t before the de blowing-up up time Tend. However, one can find a t* < Teud such that (xx(t) [| is large enough and
-2cg||=((")) I| + (c4 + 2) 0,
which produces a contradiction. Thus, |||||| I c3 for constant cs only depending on N and D₁ and
E(x) I Xmaxx| |==l| Amax
where Amax is the largest eigenvalue of : D D-A A. Thus, we proved the assertion Proposition
Recall
( under 12
and rewrite as
d (1)
(1) x2())
k (x) (2) - x2(1) 5z. (1- (== (2) i= ==:..... I,.....NI N1
dt 1
km
dt 5j
d (2) (xr
(2) (2)
T (
(1) ( + 80
(2) (1 (,r]))))),
N2.
(32)
For the attractivereepulsive model (32). we can refer to the the proof of its Theorem 5.1. in Fang et al. (2019).
We define the following notations for further proof:
= [nodes indexed by In};
W = {nodes indexed by I2),
N1 [V,
N₂ = W/
x(1) =
x.
(1)
(1)
x
I;
(2)
I
(2)
N1
N2
x
1
(1)
x
1
T
(2)
N1
N₂
N
N
Mc(V) = N1
M2(W) =
9)2
N₂
M₂ = M2(V) + MzW),
M2 M2(V) M2(W).
Remark 1. (3) indicates that the repulsive force between the particles should be weaker than the altractive force(S D).
To prove Proposition 2 we need the following two lemmas, which we would postpone to prove.
Lemma 1. Let {x:} be solution
332 Then M2 satisfies
M2 d1
d a
N
TR
(1)
2a No
N di
(2
(2)
x (1)
(1)
N
1,k=1
k=1
i=1
N
25
(of (1-))(11-())) (2)
+
-
N
(33)
2a N:
Tke (1 (2) - 2 12)gz
(1 =x )1))
(1)
(2)
N₂
N₂
j.k=1
28
N2
(2)
2₂
Suppose that the system parameters satisfy
S 0,
D >>0 0, 8 8>0,
18

---

Published as a conference paper at ICLR 2023
then there exists positive constant Ma such that
sup M2(t) - M < 00.
(34)
0st<00
Proof of Lemma
1
d
2
N₁
(1) (1)
M2(V)
3/
dt
N1
i=1
N1
N₂ N₁
a
Tk (
- 53
(2)/33
20
T
(
22 )a
(35)
N1
N1 k
i,k
N1
26
( (2)
+
N
Similarly,
d
2
N₂
(2) (2)
M2(W)
2
dt
N2
i=1
N₂
N₂ N₂
a
akj
(
(2)
23
12)
20
(,
(1) (2) (2)
2j )
(36)
N2
N2 Jmm
J,k=1
28
N2
(2)
(1 (1)
N₂
j=1
Sum the M2(V) and M2 Note that T.j- Tjj. Then
N₂
N₁
Ni
N₂
M2 S
Da
ΣΣ
(a
+ (a())²) +
x
+
Da
(m - x +
+ (z, (2)
dt
Ni
N2
26
26
N₂
+ N
0) (z! ()
(a
(2(2))2( (z. (2(
N2
(37)
By the Cauchy-Schward incquality,
N₁ Eia0iie
N N2
Σ [a( N Σ (
(a
22)
(x. (1) 2. p2 < ((( + (4,
These relations and 37) yield Riccati-type differential inequality:
di M2 (W) + (VV + M2(V) - 3DDNNM2(W)
+ 25M, 5(M2)
(38)
<(aCm + 25) 5M22)²
Let be solution of the following ODE:
y = aCmy - 6y6-
(39)
Then, the solution y(t) to (3 satisfies
am
Mt(t) s vtt S max
+ 2, 22 -M
(40)
5
19

---

Published as a conference paper at ICLR 2023
Lemma 2. Let {2t) be solution
32 with 8 0. Then My satisfies
d
M2 I 2n + 2aD(1a x. 1 M2.
(41)
dt
where Ç = max (N1, N2) and r is the positive constant in Proposition
Proof of Lemma 2.
By computation,
N2
(1)
1
N1
i=1
8 N1
(1)
(1)
(2)
(1)
Σ 24 (1 (z) (2)
Cg. (
N1
N1
N1
i,k=1
i=1
N₂
N1
(2)
(1)
N1 (1 (z
5
(1)
+
k=
1=1
(1) Take the inner product 2x; (1)
Note that 22
xe
with the above equation and sum it over
all i = 1 ,,..., Ni, combining with Σ tt = 0. Then,
(1)
d dt
M2(V)
(2,(
(1)
[.12)/22 - 2a
(1 xz )0
(2)
(1)
26
(1)
(1- (a.
(1
-
N1
k==1
k= i=1
1=1
N₂
N1 N₂
(
- x 1112 - 2a Σ>
a (x (2) - xx
+ F
(1)
)z
N1
1=1 k=
1
2 2 (1 (1-(x; (2)
(1) (1)
26
N1
1=1
Similarly,
d dt
M2(W)
1
T
(
(2)
x
12)
2a
(x!!)
x2(2)
2
(1) (2) (2)
N2
k=1
1
28
I
(2)
x
(2)
(z (2)))))).
N2
Combine the two equations,
4 M2
Σ
1, where
==1
h
ūg ( (1 - 1z 22
S M2
N
i,k=1
=
1
0 (2) 12)
220
< MW,
(42)
N₂
I + 12 < -a5 min N1N
20

---

Published as a conference paper at ICLR 2023
22 M
N1 N2
13 ;= -2a
2
20
(2
23
123 3
Ni
N2
k=1
k=1
M
2₂
12
< max
2a
T.d (4)
N
2
i= j=1
N1
max
1
20l)
(1)
12
Ni
N₂
j=
(43)
1
2a max
N1N2M
N2 122
22,DMM,
N₂ N₁
N1 N₂
1 = 2a Σ
kk (x) x j0
(2) 11)
20
(x( (1)
)a²
(2)
N1
N₂
km 1=1
km
j=1
$ $2aDcl=!" - x!!2) IV M2,
N1
I5: 26
Σ
3 22
(1)
(1 (1- (2,
N₂
(44)
N2
1. 26
x 1 (1 - (o.
(2) (2)
N₂
1=1
Using m;
(1) (1)
Fi
+ Fo
(1)
and Σ r,
(1)
0, we obtain
28 N1
N
I5 N1 1=1
(1
(x.
2)00
(2)))22)
28
(1)
N1
i=1
25 N1
28 N1
vV)
(1) 1
(1)
2
(1) (
N1 i=1
N1 1=
4
(45)
28 Ni
-V)
3
(1)
N1
$ (V)
The last inequality is based on
N₁
N; (1)
Σ
- (1)
1=1
1
(a())(((a())) (222))2 + (1r - 13)
2
1 N
(2(
(2()))(((()))) (2)
2
N
Ni
Σ
1
M
(a
(1) (1:
2 1=1
2
t=1
N
Ni
(1(1)
1
(a(1)
20.
2
2N1
1=1
21

---

Published as a conference paper at ICLR 2023
Similarly on Ja: one has Is s 26), Thus, Is + Is I 20M2. Note that
+ + 18 16 S -2a5 min N2 N22 + 2aDçMM2 + +28M2
v -2 D) Ni, 6) M2
(46)
22
Proof of Proposition] 2 (a) (Uniform upper bound of |
Ze
By Cauchy's 's inequality and Lemma
x
(2)
(1)
1
(2)
N
N2
1=1
i=1
N2
(1)
1
|
(2)
N1
22
(47)
N
N2
$ 2
11)
(ar
22
N1
N₂
i=1
2V Ma(l) S 2 M
(b) (Uniform boundedness of M2) By Lemma and 47
d V M2 = -ny M2 + aDC - xx!2)
di
(48)
S - Mr + 2Do VM
Use Gronwall's lemma to obtain
V Ma(1) & M2(0)e ot 2Da M en)
1
(49)
2Da5 M V MM(0),
< max
= C3.
1)
(c) (Separation of the particle centers)
By
32 we have
d
[1)
-
x22)
a
(1
(1)
x
(1)
N₂ N
Øk (2 -z, (02))
(2)
dt
N1
N₂
k=1
N;
N₂
N₂ N
(2) - -0x()) (11)
0k i (1
(1) (0))
(50)
N
2₂
k=1
k=
N
N
8
Σ
(xt
(1) (1 ((a(())p))
28
x (1 - ((x) (2) (2)
N1
N₂
22

---

Published as a conference paper at ICLR 2023
Ng N
By the symmetry of (Ts.)),
ag (1k
)11 = 0 for p 1, Thus,
k=
N1
N2
d
(2)
(2)
11)
x
1
N₂
N
(Th
x
(1)
3/
(2)
x (2))
(51)
+
N1
+
+x(1)
28
N₂
4
(2)
+ x (2)
N
N2
:=1
25
N1
(a)
1))
+
25
2₂
N1
N2
1=1
By similar estimate with Lemma 2 we have
d [1(1] - -0(0))1 x22212=--0 2(x!0))
x(22)
(2)
a
N
N₂
(
+ (2)
32 x
(1)
dt
N1
1=
+ +2(x(0)
(2)
a
C (1rk
+ I 1, x
(1) (2) (2)
N2
M
N2
28
28
+
(x!1)) - 212)
N
2₂
28
28
N2
(1)
(2)
(o
(1) x!
ftc
N1
N₂
28
11) ( - -x(!)) 2.(2)
20
N₂
(2) ((c - x!?2)
+
N
N₂ i=1
M N₂
N2 N1
20
(x! (2) (2)) +
20
C d (3(
(2) x011)3
N1
k=
N1 N2
N2 N1
(2)
(1)
(xx (2)
x (1)
+
20
(1 - xz )xx - x(())
N
N1
j=1 k=
+ +2(x!²) =())
N1
(1)
8
(2)
2
N
N2
i=1
3=1
N1
N₂
8
+ 22(x(2) - x(2)
2
(1)
x
(2)
N1
N₂
i=1
3=1
(52)
d (1) (2)
1
N
N₂
1e x
22
a
+
Oi + 25
(xr - 2.222)3 + Ic1 + Izz.
(53)
dt
N₂
N₂
[=1 1=1
where
Iel = 2a
(
1
Ni
N₂
(1)
(2)
1
(1) )= (2) x ()))
(54)
N₂
N₂
i=1
j=1
23

---

Published as a conference paper at ICLR 2023
28 N NI
28 N2
Iep ==
11)
x
+
a (x (1) - x!
(55)
N2
By the Cauchy-Schwarc inequality,
N1.No
Ial S 2a
+
1
DV
NiNNN xx.-
Σ
( 26
(2) (1)
N1
N₂
(56)
1
DNIN - x!?² M2.
S
20
+
N1
N2
For Tez, note that
N1
20
1)3
N1
28 N
(a. (2))))
< 0
M2(V) S SONN)M
2₂
Then, one gets
8 N1
5
N₂
Is2 2 -2 x(
(1) xx(2)
11)33
x
N1 i=1
N₂
1=1
(57)
2 2 x
(1)
x!22
8
m No. MM
Hence,
N: N2
1
xc 121122
200
+
Oi
+ +5
(oo2) - xx6 12
dt
N₂
N₂
i=
j=1
2N:(NN + N2)
(1(1) - x!!²1
MM 25 /m3x( N1, N2)
x
(1) (22)
M
(58)
Combining with Lemma and (49). one obtains the estimate
dt 1
d
=!?212 2
Σ
N;
Σ
N₂
ais + 28 lo!") x!?2!
N₂
(59)
j=1
DDD(Ni N2) /v // N2,
By Gronwall's Jemma, if the initial data satisfy:
(o) - =0) 2 aD(N1 + N2)Cs + 8 max N1, N2
Ca
(60)
28
8
then,
(t) (t) 2 C. + (z) 8
C4 e 2
C2
(
(2)) (0)
(61)
8
8
(d)(Spatial separation of the two sub sub-ensembles) For any i = 1,... N1, j =
N2.
|
x (t) (()) [2(1) (t) x(2) (t)l
2 (1) (t) V max (Ni, No) M2
C1
+ |oo - = Co 7
2 8
V (2)( " + M
1/2max
(1 (1-61- )
24

---

Published as a conference paper at ICLR 2023
Then, there exists some time 7 such that Vt 2 T
[ (t) - (2) (t)l - Vi,j-
(62)
Combing with Proposition [ we finish the proof.
Remark 2. The proof of Proposition included in part (d) of proof of Proposition 2
Now denote 1/2
Σ
di.j
0 in some channel, then the Dirichlet energy in this channel has
sE sEIi
lower bound:
1 ((x) = N
Dijj (2 - xz2²
Σ
and -2,
Σ
- 22
Σ
cid(o!")
iEZ
Σ
(1) 2 /
N
VELLETTA
C
12
N
(63)
D EXPERIMENTS
The code for the experiments is available
https http://gtthhb.ccoo http:/hwww.coo/kkiii/////eaeee
We will replace this anonymous link with a non-anonymous GitHub link after the acceptance. We implement all experiments in Python 3.8.13 with PyTorch Geometric on one NVIDIA @ Tesla A100 GPU with 6,912 CUDA cores and 80GB HBM2 mounted on an HPC cluster.
In addition, we take the official implementation of the Graph Neural Diffusion (GRAND) as diffu- sion term in (9) from the repository:
https://gtthiii htt.://www...oott....oo.ooo///aa
D.1 DETAILS FOR EXPERIMENTS
Datasets We consider two types of datasets: Homophilic and Heterophilic. They are differentiated by the homophity level of graph (Pei et al. 2020):
Number of v's neighbors who have the same label as v Number of v's neighbors
H
PEV
In the experiments, we have used six homophilic datasets, including Cora (McCallum et al. 2000), Citeseer (Sen et al. 2008) and Pubmed (Namata al. 2012). Computer and Photo (Namata al. 2012). and CoauthorCS (Shchur et al. 2018). and three heterophilic datasets: Cornell, Texas and Wisconsin from the WebKB dataset" For completeness, we list the numbers of classes, features, nodes and edges each dataset, and their homophily level in Table 3 The low homophily level means that the dataset is more heterophilic when
of neighbours are not in the same class, and the high homophily level indicates that the dataset close to homophilic when similar nodes tent to be connected. The datasets we used Table 3 covers various homophily levels.
Experiment setup For homophilic datasets, we use 10 random weight initializations and 100 random splits, which contains 1,000 tests. Each combination randomly select 20 numbers for each class. For heterophilic data, we use the original fixed 10 split datasets. We fine-tune our model
11 /twp///wwbbb/////////////tww/./w
25

---

Published as a conference paper at ICLR 2023
Table 3: Information for Graph Datasets Used in Experiments
Dataset
Classes
Features
#Nodes
Edges
Homophily level
Cora
1433
2485
5069
0.83
CiteSeer
3703
2120
3679
0.71
PubMed
500
19717
44324
0.79
CoauthorCSS
15
6805
18333
81894
0.80
Computer
10
767
13381
245778
0.77
Photo
745
7487
119043
0.83
Texas
1703
183
309
0.11
Wisconsin
1703
183
499
0.21
Cornell
1703
183
499
0.30
within hyper-paramett search space, as detailed in Table We use the Dormand-Prince adaptive step size scheme (DOPRI5) as the neural ODE solver for all datasets. Hyperparameter search used Ray Tune with hundred trials using asynchronous hyperband scheduler with a grace period of 50 epochs. All the details to reproduce our results have been included in the submission and will be publicly available after publication.
Table Hyperparameter Search Space
Hyperparameters
Search Space
Distribution
learning rate
[10-6, 10 '1
log-uniform
weight decay
11-3,10-1
log-uniform
dropout rate
[.81
uniform
hidden dim
{64, 128, 256}
categorical
time (T)
[2,25]
uniform
e
[0, 1]
uniform
6.20
6.00
4.10
1.50
Figure 5: Example of how adding Allen-Cahn terms can prevent the nodes feature from becoming infinite. We choose the first channel in the node's feature of dimension 150. In the first row, the repulsive force is added to message passing without Allen-Cahn term, and the second row, Allen- Cahn term is added to message passing. The first, second and third columns show the neural ODE's initial state, and the states when T 10 and 30.
D.2 ABLATION STUDY FOR ACMP
Message Passing Performance ys Depths We compare ACMP with various GNN models such GRAND, GCN, GAT, and GraphSage with different depths on the planetoid datasets. Table
26

---

Published as a conference paper at ICLR 2023
lists the nodes classification accuracy Cora, Citeseer and Pubmed. We observe that ACMP can maintain its model performance as the network deepens and achieve top test accuracy among all listed models using the same depth. ACMP can thus overcome the oversmoothing.
Table 5: Test Accuracy of Models with Different Depth
Model
depth
Cora
CiteSeer
PubMed
4
82.80 + 1.62
73.87 + 2.12
78.71 + 1.19
GRAND-1
16
82.75 1.17
72.61 + 2.42
78.79 + 0.93
32
82.19 1.78
72.65 3.15
78.70 = 1.08
64
80.87 = 2.28
69.84 2.66 NA
NA
128
77.22 1 2.88
NA
4
81.35 + 1.27
70.54 + 6.61
77.15 + 3.00
GCN
16
19.70 10.70+1 7.06
24.78 + 1.45
41.36 = 1.77
32
21.86 6.09
24.23 + 1.65
40.66 = 1.86
4
80.95 + 2.28
72.31 + 2.82
77.37 + 1.32
GAT
16
29.14 + 1.02
24.84 + 1.45
39.21 + 0.43
32
1.57 29.75
24.83 + 1.45
39.02 + 0.12
4
79.83 2.43
50.00 1. 14.27
76.01 1 2.35
GraphSage
16
25.52 6.45
24.84 1 1.45
37.55 1 3.92
32
1.02 29.14
28.38 1 2.54
39.21 1 4.39
4
83.87 + 0.52
74.61 = 1.04
79.74 0.24
ACMP (ours)
16
83.19 0.67
73.13
79.16 0.36
32
83.11
0.81
72.76 1.05
79.81 1.61
64
80.48
1.21
68.92 1.37
78.01 +.01
128
80.30 + 1.18
67.83 0.02
0.02
77.98
0.01
Table 6: The number of parameters for different models
GCN
GAT
GraphSage
CGNN
GRAND-I
ACMP GCN
JCMP.GAT
Cora
144k
230k
200k
26k
17k
17k
19k
Model parameter comparison We compare the number of parameters of model with different benchmark model on Cora dataset in T The depth of all model is chosen as the number which achieves the best performance on Cora dataset. We show that ACMP is light-weight neural network architecture which can achieve good classification performance with fewer parameters.
We now show in Figure 5 Show Allen-Cahn term can stabilize training and pre- vent node features from blowing up. The first row is the evolution of the diffusion equation without Allen-Cahn term while the second row has Allen-Cahn term added. can observe that introducing the repulsive term is essential for bounding GNN outputs, particularly when learning heterophilic datasets. However, naively adding to message passing will result in all node's 's features becoming infinite. In the first have increased to 3 x 10 when T T==00 10, from 0.1 when T = 1. By the time equals 30, the node's largest feature becomes handle numerically corrected, When we introduce Allen-Cahn term, the system contains two strong attractors of +1, and the nodes are attracted to the two ends of and -1 by their own features.
Allen-Cahh term
of Figure 5 when Allen-Cahn term is not incorporated, the node's features
1020, which the neural ODE solver and message passing can hardly
27


Reviews:
[{"review_id": "ylHRHFIqriV", "reviewer": "Reviewer_A1JY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper proposes a novel message passing algorithm for graph neural networks. It explores both the attractive and repulsive forces simultaneously. Intuitively, it is introducing a measure to tell when to gather/diverge the neighborhood nodes.\n", "summary_of_the_review": "I think this paper is technically interesting, and I can understand the core ideas of the authors. I have two major concerns:\n1. The presentation is not clear, especially Sec 1.\n2. The experiments are a little weak. Such particle system can be better verified on some quantum datasets. If the results still hold, then I think this would be a very solid paper.", "strength_and_weaknesses": "## Strengths \n- This paper introduces using an interacting particle system with attractive and repulsive forces and the Allen-Cahn force for message passing.\n- The Sec 3 & 4 are technically sound and clearly explained.\n## Weakness\n- The motivation is missing, and why we want to study Allen-Cahn message passing (ACMP) is not explained.\n  - In Sec 1, the authors mention the that particle system is common in nature and human society, but the difference between ACMP and traditional GNN is not clearly explained.\n  - Namely, a smoother logic is that, what is missing in the current GNN message passing, and how this can motivate ACMP.\n  - The oversmoothing should be briefly introduced in Sec 1. Now it just shows up directly in paragraph 1 and 2, making it hard to follow, e.g., how the repulsive orces can avoid oversmoothing is not clear.\n\nI need to confirm some points in Sec 1 with the authors:\n- For sentence “Most existing message passing neural networks are driven by attractive forces associated with the Dirichlet energy …” Can authors give more detailed explanations?\n- What is the difference between Allen-Cahn energy and Dirichlet energy? So that AC energy can avoid the exploding issue when the GNN gets deeper?\n\nSome questions on Sec 2.\n  - There exist several deep GNN works [1, 2], but not discussed in the paper. They are also related to the oversmoothing. Besides, I’m wondering which category would they fall into the framework introduced by the authors.\n  - Before Eq(2), the authors say ‘’ (GRANND) … for some message passings:’’, can authors add citations for these message passing works?\n\n\n\n\n- I have two concerns on the experiments.\n  - The performance on existing datasets are far behind the SOTA, e.g., https://paperswithcode.com/sota/node-classification-on-cora. Can authors also switch to some of the SOTA GNNs in the board?\n  - A minor gap between method and experiments. Since ACMP can mimic the particle dynamics, the authors should conduct experiments on more related datasets, like quantum chemistry dataset. The current experiments are on the datasets like Cora, where the notions like forces and potential are hard to verify.\n\n\n[1] Gallicchio, Claudio, and Alessio Micheli. \"Fast and deep graph neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.\n\n[2] Yan, Yujun, et al. \"Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks.\" arXiv preprint arXiv:2102.06462 (2021).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nar7h7VcRI", "reviewer": "Reviewer_W9W7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper falls in the area of deep learning for graphs. It is presented a new methodology for message passing, inspired from the study of interacting particles, in which the distinctive characteristic is that it has (in addition to conventional attracting forces) a repulsive force term in the message passing equation. This has the effect of improving the neural representations developed for heterophilic datasets and alleviate oversmoothing. Moreover, the proposed method includes an additional term called Allen-Cahn potential, to trying constraining the neural representations. The network architecture is run by a neural ODE solver, and it is demonstrated on several benchmarks.\n\nUpdate after rebuttal:\nI thank the authors for clarifying my doubts regarding the paper, and I am happy to confirm my score.", "summary_of_the_review": "The paper presents an interesting methodology. In my view, downsides in the current version of the manuscript are mostly related to the experimental settings, where details about the model selection performed on the proposed model and on the competitors from the literature, do not completely eliminate doubts about the fairness of the reported experimental comparison.", "strength_and_weaknesses": "Strengths:\n* The paper addresses an interesting problem in the area of deep learning for graphs, with an elegant approach\n* The mathematical analysis seems sound and interesting\n\nWeaknesses:\n* Experimental settings are not fully convincing. In particular, from the manuscript it is not clear if hyperparameter tuning with model selection has been performed or not, and how this phase is conceived in order to ensure fairness in the performance assessment wrt literature methods. I could find some details in the supplementary material concerning the hyperparameters values explored for the proposed method (which sounds reasonable): I invite the authors to include this kind of information in the main text of the paper. Moreover, I suggest to clearly comment on the number of trainable parameters when comparing with the literature methods from the literature, in order to ensure that the performance advancements are not simply determined by a higher complexity of the resulting neural network (i.e., please report the number of trainable parameters in the proposed method vs those used in the experiments from the literature methods).\n* Some aspects of the analysis are not fully clear. For instance, in the abstract it is claimed that \"ACMP which has a simple implementation with a neural ODE solver can propel the network depth up to one hundred of layers\", while I could not see any analysis in this sense in the paper. Moreover, while figure 2 is sufficiently explanatory and insightful, I could not find specific details on the network used to generate the plots. This, after all hampers the significance of the example, for which I suggest to include full details (at least in the caption).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LAke4Tsgyo", "reviewer": "Reviewer_boSt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Firstly, in this paper, the authors purpose that ACMP can help solve the over-smoothing problem in the GNN network by keeping the Dirichlet energy of GNN. Then, this paper shows that adding the term repulsive force may cause the particles to be pushed away to infinite, the Dirichlet energy becomes unbounded, and how the purposed method helps solve the problem. Finally, the author uses the experimental results to show that ACMP can keep Dirichlet energy in GNN and help improve the performance of GNN methods.\n\n### Update after reading rebuttal\nThe authors address my concerns and I raised my score.", "summary_of_the_review": "The purposed method can help solve the GNN oversmoothing phenomenon by keeping the Dirichlet energy. The experiment result shows this. However, this paper lacks the experiment to compare the performance of the purposed method and the former method that overcomes GNN oversmoothing. This paper uses the properties of Allen-Cahn. Therefore, the novelty of this paper is not very significant.  ", "strength_and_weaknesses": "Strength\n1.\tUsing the property of ACMP to help keep the Dirichlet energy and help solve the oversmoothing of GNN is a good attempt.\n2.\tThe experimental results show that ACMP can improve the performance of existing GNN models in the node classification task.\n3.\tIn this paper, the mathematical arguments are detailed without obvious errors.\n\nWeakness\n1.\tAs this ACMP is focused on the oversmoothing problem of GNN. It should work for more tasks. The author only tests it at the node classification task. This cannot show that the purposed method can help solve the oversmoothing of all kinds of GNN task.\n2.\tThe purposed method is not the first method to try to solve this problem. So, there should be experiments to show this method is better than the former methods.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%