Re-Think and Re-Design Graph Neural Networks in Spaces of Continuous Graph Diffusion Functionals
Authors: Tingting Dan
Jiaqi Ding
Ziquan Wei
Shahar Z Kovalsky
Minjeong Kim
Won Hwa Kim
Guorong Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks (GNNs)
total variation (TV)
Euler–Lagrange equation
calculus of variations
over-smoothing
min-max optimization
TL;DR: We introduce a new research framework to develop interpretable deep models, with a great mathematical insight, for learning from graph data.

Abstract: Graphs are ubiquitous in various domains, such as social networks and biological systems. Despite the great successes of graph neural networks (GNNs) in modeling and analyzing complex graph data, the inductive bias of locality assumption, which involves exchanging information only within neighboring connected nodes, restricts GNNs in capturing long-range dependencies and global patterns in graphs. Inspired by the classic Brachistochrone problem, we seek how to devise a new inductive bias for cutting-edge graph application and present a general framework through the lens of variational analysis. The backbone of our framework is a two-way mapping between the discrete GNN model and continuous diffusion functional, which allows us to design application-specific objective function in the continuous domain and engineer discrete deep model with mathematical guarantees. First, we address over-smoothing in current GNNs. Specifically, our inference reveals that the existing layer-by-layer models of graph embedding learning are equivalent to a ${\ell _2}$-norm integral functional of graph gradients, which is the underlying cause of the over-smoothing problem. Similar to edge-preserving filters in image denoising, we introduce the total variation (TV) to promote alignment of the graph diffusion pattern with the global information present in community topologies. On top of this, we devise a new selective mechanism for inductive bias that can be easily integrated into existing GNNs and effectively address the trade-off between model depth and over-smoothing. Second, we devise a novel generative adversarial network (GAN) to predict the spreading flows in the graph through a neural transport equation. To avoid the potential issue of vanishing flows, we tailor the objective function to minimize the transportation within each community while maximizing the inter-community flows. Our new GNN models achieve state-of-the-art (SOTA) performance on graph learning benchmarks such as Cora, Citeseer, and Pubmed.

Re- Rhink and Re-Design Graph Neural Networks in Spaces of Continuous Graph Diffusion Functionals
Tingting Dan
Jiaqi Ding
University of North Carolina at Chapel Hill tdan@email edu
University of North Carolina at Chapel Hill j jiaqidecs edu
Ziquan Wei
Shahar Z Kovalsky
University of North Carolina at Chapel Hill zi ziquanweemail. unc.
University of North Carolina at Chapel Hill shaharko@unc, edu
Minjeong Kim
Won Hwa Kim
University of North Carolina at Greensboro mkim@uncg.ee edu edu
Pohang University of Science and Technology wonhva@postech.aa .cc........ .rr
Guorong Wu
University of North Carolina Chapel Hill grwuumed. unc. edu
Abstract
Graphs are ubiquitous in various domains, such as social networks and biological systems. Despite the great successes of graph neural networks (GNNs) in modeling and analyzing complex graph data, the inductive bias of locality assumption, which involves exchanging information only within neighboring connected nodes, restricts GNNs in capturing long-range dependencies and global patterns in graphs. Inspired by the classic Brachistochrone problem, we seek how to devise a new inductive bias for cutting-edge graph application and present general framework through the lens of variational analysis. The backbone of our framework is a two-way mapping between the discrete GNN model and continuous diffusion functional, which allows us to design application-speciff objective function in the continuous domain and engineer discrete deep model with mathematical guarantees. First, we address over-smoothing in current GNNs. Specifically, our inference reveals that the existing fayer-by-layer models of graph embedding learning equivalent 2 2n-norm integral functional of graph gradients, which is the underlying cause the over-smoothing problem. Similar to edge-preserving filters image denoising, we introduce the total variation (TV) to promote alignment of the graph diffusion pattern with the global information present community topologies. On top of this, we devise new selective mechanism for inductive bias that can be easily integrated into existing GNNs and effectively address the trade-off' between model depth and over-smoothing Second, we devise a novel generative ad vvvesariial network (GAN) to predict the spreading flows in the graph through neural transport equation. To avoid the potential issue of vanishing flows, we tailor the objective function to minimize the transportation within each community while maximizing the inter-community flows. Our new GNN models achieve -fate-of-the-an art (SOTA) performance on graph learning benchmarks such as Cora, Citeseer, and Pubmed.
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Introduction
Graph is a fundamental data structure that arises in various domains, including social network analysis [42], natural language processing [36], computer vision [30,, recommender systems [37]. and knowledge graphs [2T] among others. Tremendous efforts have been made to operate machine learning on graph data (called graph neural networks, or GNNs) at the node [23]. link AT, and graph level (27]. The common inductive bias used in GNNs is the homophily assumption that nodes that are connected in graph are more likely to have similar features or labels. In this context, most GNN models deploy collection of fully-connectoe layers to progressively learn graph embeddings by aggregating the nodal feature representations from its ropologicall--conneteed connected neighbors throughout the graph
Demonstration of the root cause of over-smoothing in GNNs. Nodes #1 and #2 are located along the boundary of two com- munities. The locality assumption in GNNs steers the learning of the graph representations by constraining the information exchange via node-to- do-deto-ode connections. However, such link wise inductive bias opts to neutralize the contrast of node embeddings between nodes #1 and #2, which might undermine the node classification accuracy. Our research framework yields the solution for the over-smoothing issue by enabling heat kettee diffusioo within each community while penal- izing the excessive community-to to-community information exchanges (highlighted in red).
Figure 1:
hode #t
goode
group 16 group 3 O group O unlabeled
Under the hood of GNNs, the graph representation learning process is achieved by various learnable operations, such as message passing [5] or graph convolution [23]. Due to the nature of exchanging information in local graph neighborhood, however, it is challenging to capture global graph representations, which go beyond node-to-node relationship, by leveraging the deep architecture in GNNs while being free of overly smoothing the feature representations for the closely-connected nodes. Fig. demonstrates the root cause of over-smoothing issue in current GNNs, where node color denotes the group label (no color means unlabeled) and edge thickness indicates connection strength. It is clear that nodes #1 and #2 are located at the boundary of two communities. The inductive bias of GNNs (i.e., locality assumption) enforces the node embedding vectors on node #1 and #2 becoming similar due to being strongly connected (highlighted in red), even though the insight of global topology suggests that their node embeddings should be distinct. As additional layers are added to GNNs, the node embeddings become capable of capturing global feature representations that underlie the entire graph topology. However, this comes at the cost of over-smoothing node embeddings across graph nodes due to (1) an increased number of node-to-node information exchanges, and (2) greater degree of common topology within larger graph neighborhoods. this regard, current GNNs only deploy a few layers (typically two or three) (26]. which might be insufficient to characterize the complex feature representations on the graph.
It is evident that mitigating the over-smoothing problem in GNNs will enable training deeper models. From a network architecture perspective, skip connections [16] 39 residual connections [25] [8) and graph attention mechanisms [34] [3] have been proposed to alleviate the information loss in GNNs, by either preserving the local feature representation or making information exchange adaptive to the importance of nodes in the graph. Although these techniques are effective to patch the over-smoothing issue in some applications, the lack of an in-depth understanding of the root cause of the problem poses the challenge of finding generalized solution that can be scaled up to current graph learning applications.
Inspired by the success of neural ordinary differential equations in computer vision 10 research focus has recently shifted to link the discrete model in GNNs with partial differential equation (PDE) based numerical recipes [38] 29 6 [4]. For example, graph neural diffusion (GRAND) formulates GNNs as a continuous diffusion process [6]. In their framework, the layer structure of GNNs corresponds to specific discretization choice of temporal operators. Since PDE- model does not revolutionize the underlying inductive bias in current GNNs, it is still unable prevent the excessive information change between adjacent nodes as in nodes #1 and #2 in Fig. [] In this regard, using more advanced PDE solvers only can provide marginal improvements in terms of numerical stability over the corresponding discrete GNN models, while the additional computational cost, even in the feed-forward scenario, could limit the practical applicability of PDE-based methods for large-scale graph learning tasks.
2

---

Numerical solutions
System Characteristics
Brachistochoone problem
Topr Z006
stor
Classic Mechanles
ploge if!
Ealer-Lagrange equation
wlaye
What SLOPE optimized for speed or
alope A4
aod
stope
lope 83
Mathh
Learning
Which of DIFFUSION
X
X
beat to preserve community orgaiiattion?
Your 2022
Leaming
Machine
xx
ligoo eitr fanege
Rethink, Recksign GNNN
Dokk vidre nypology
Figure 2: Top: The Brachistochrone problem played a pivotal role in the development of classical mechanics and the powerful mathematical tool known the calculus of variations. Bottom: We introduce a general framework to answer "Brachistochrone" problems regarding diffusion patterns on graphs that allow us to re-think and re-design application-specilis deep model of GNNs with enhanced mathematical interpretability.
In this regard, pioncering work on continuous approaches has prompted to re-think GNN as graph diffusion process governed by the Buler-Lagrange (E-L) equation of the heat kernel. This formulation is reminiscent of the Bruchistochrone problem which emerged over 400 years ago and established the mathematical framework of classical mechanies. The powerful calculus of variations allows us to generate solutions for various mechanics questions (e.g., the slope that yields the fastest ball sliding down the curve is given by cycloid) through the lens of E-L equation, as shown in Fig. (top).
In a similar vein, the question that arises in the context of community detection is: What graph diffusion pattern is best suited for preserving community organizations? The question for graph classification would be: What graph diffusion pattern works best for capturing the system-level characteristics of graph topology? Following the spirit of Brachistochrone problem, we present general research framework to customize application-specific GNNs in a continuous space of graph diffusion functionals. As shown in Fig. _ (bottom), we have established fundamental structure for our framework that involves a two-way mapping between a discrete GNN model and continuous graph diffusion functional. This allows us to develop pepiication-spccinf objective functions (with an explainable regularization term) in the continuous domain and construct discrete deep model with mathematical guarantee. We demonstrate two novel GNN models, one for addressing weerssoothing and one for predicting the flows from longitudinal nodal features, both achieving state-of -oee----theerrrr performance (Cora: 85.6%, Citeseer: 73.9%, Pubmed: 80.10%, even in 128 network layers).
We have made four major contributions. (1) We establish a connection between the discrete model of GNNs and the continuous functional of inductive bias in graph learning by using the E-L equation as a stepping stone to bridge the discrete and continuous domains. (2) We introduce a general framework to re-think and re-design new GNNs that is less "black-box", (3) We devise novel selective mechanism upon inductive bias to address the over-smoothing issue in current GNNs and achieve state-of- state-of-the-ar the-art performance on graph learning benchmarks. (4) We construct a novel GNN in the form of generative adversarial network (GAN) to predict the flow dynamics in the graph by neural transport equation.
2 Methods
In the following, we first elucidate the relationship between GNN, PDE, and calculus of variations (COV), which sets the stage for the GNN-PDE-COT framework for new GNN models in Section 2.2
2.1 Re-think GNNs: Connecting dots across graph neural networks, graph diffusion process, Euler-Lagrange equation, and Lagrangian mechanics
Graph diffusion process. Given graph data g = (V, W) with N nodes V = (o.li adjacency matrix W = [wulit E N describes connectivity strength between any two nodes. For each node us. we have a graph embedding vector x; E RT. In the context of graph topology, the graph gradient (Vgz).g = way (x; 2zy) indicates the feature difference between e; and vy weighted
NY. the
'The Brachistochrone problem is a classic physics problem that involves finding the curve down which a bead sliding under the influence of gravity will travel in the least amount of time between two points.
3

---

is the by the connectivity strength wij. where Vg is R + R N operator. Thus, the graph diffusion Be(t) process can be formulated as Bt = div (Ver(t)), where the evolution of embedding vectors = [a:]]== 1 is steered by the graph divergence operator.
Connecting GNN to graph diffluiion In the regime of GNN, the regularization in the loss function often measures the smoothness of embeddings I over the graph by x" Az, where A =
graph Laplacian operator [23] To that end, the graph smoothness penalty encourages two connected nodes to have similar embeddings by information exchange in each GNN layer. Specifically, the new graph embedding x' in the 1th layer is essentially a linear combination of the graph embedding x'-1 in the previous layer, i.c., x' = Aw,ez wwwez'-1 where the matrix A depends on graph adjacency matrix W and trainable GNN parameter +. After rewriting x' = Ax'-1 into x' - x' = (A - f)x'-1 updating graph embeddings x in GNN falls into discrete graph diffusion process, where the time parameter i acts as continuous analog of the layers in the spirit of Neural ODEs [[O]. It has been shown in 6 that running the graph diffusion process for multiple iterations is equivalent to applying GNN layer multiple times.
GNN is a discrete model of Lagrangian mechanics via E-L equation. The diffusion process Bmit) div (V))(t)) has been heavily studied in image processing for decades ago, which is the 0t
E-L equation of the functional min Sq / By replacing the ID gradient operator defined x in the Euclidean space Q with the graph gradient (Vgz)yj. it is straightforward to find that the equation governing the graph diffusion process Su(t) die (V)=(()) is the E-L equation of the functional min fg / over the graph topology. Since the heat kernel diffusion is essentially the mathematical description of the inductive bias in current GNNs 14], we have established a mapping between the mechanics of GNN models and the functional of graph diffusion patterns in a continuous domain.
Tracing the smoking gun of over-smoothing in GNNs. In Fig. we observed that the inductive bias of link-wise propagation is the major reason for excessive information exchange, which is attributed to the over-smoothing problem in GNNs. An intuitive approach is align the diffusion process with high-level properties associated with graph topology, such as network communities. After connecting the GNN inductive bias to the functional of graph diffusion process, we postulate that the root cause of over-smoothin is the isotropic regularization mechanism encoded by the fg-norm. More importantly, connecting GNN to the calculus of variations offers a more principled way to design new deep models with mathematics guarantees and model mechanistic explainability.
2.2 Re-design GNNs: Revolutionize inductive bias, derive new E-L equation, and construct deeper GNN
The general roadmap for re-designing GNNs typically involves three major steps: (1) formulating inductive bias into the functional of graph diffusion patterns; (2) deriving the corresponding E-L equation; and then (3) developing new deep model of GNN based on the finite difference solution of E-L equation. Since the graph diffusion functional is application-specinee construction of new GNN models in the following two graph learning applications.
we demonstrate the
2.2.1 Develop VERY deep GNNs with selective mechanism for link-adaptive inductive bias
Problem formulation. Taking the feature learning component (learnable parameters Q) out of GNNs, the graph embeddings xz (output of an L-layer GNN) can be regarded as the output of an iterative smoothing process (L times) underlying the graph topology G. constrained by the data fidelity | -
-==""" 1| (w.r.t the initial graph embeddings z²) and graph smoothness term SG Vg 2dx. Inspired by the great success of total variation (TV) for preserving edges in image denoising BI], reconstruction (35) and restoration (8) proposed to address the over-smoothing issue in current
GNN by replacing the quadratic Laplacian regularizer with TVV on graph gradients, i.e., Jrv (x)
/Vgaddd. Thus, the TV-based objective function for graph diffusion becomes: min([I= x 1 (x).
However, the noorm function, denoted by |. in the definition of the total variation functional JrV. is not differentiable at zero. Following the dual-optimization schema 4 7). we introduce the latent

---

FC layer
layer
Flyyer
FC Calayr layer
FC layer DG layor
2.
Wij
Ws1
Inputs
Outputs
Figure 3: Our deep model integrates novel diffusion- cnffusiiongaathrring (DG) layer (for selective graph diffusion)
after the conventional fully-connected (PC) layer (for graph representation learning).
auxiliary matrix RNNN and reformulate the TV-based functional as min max JTV (2,
max (2 & Vgæ)dx, subject to |a| < NNNN where & Hadamard operation between two
matrices. Furthermore, we use an engineering trick of element-wise operation žgy| [Vgz); to keep the degree always non-negative (same as we take the absolute value), which makes the problem solvable. In the end, we reformulate the minimization of Jrv (a) into a dual min-max functional as Jrv (z, z). where we maximize (z + 1 NxxN such that JTV (ar, 2) is close enough to (T). Therefore, the new objective function reformulated as:
I [ar, 2) max min - + (zVaz)dz,
where À is sealar balancing the data fidelity term and regularization term. Essentially, Eq. D the dual formulation with min-mux property for the TV distillation problem 44
Constructing E-L equations. To solve Eq. I we present the following two-step alternating
optimization schema. First, the inner minimization problem (solving for x;)) in Eq. can be solved
by letting dx; J (xx, 2,) ==
82, J 24) =((, x2) + dz gzz 0
V
Replacing (Vg*),; with wey (z; - xz)), the intuition of Eq. is that each element d; essen- tially the combination between the corresponding initial value in x! and the overall graph gradients 2, VVgz, = EjeN, Wiy(2z (2; >;)=; within its graph neighhorhood Ng. this regard, Eq. 2 character- izes the dynamic information exchange the graph, which is not only steered by graph topology but also moderated by the attenuation factor 2; at each node.
Second, by substituting Eq.
2 back into Eq. [ the objective function of 2; becomes J(z:) max 2 V \= ( Σे V gw:). With simplification (in Eq. S1 to Eq. S3 of Supple-
|
mentary), the optimization of each z; is achieved by arg min V Vg Vgz; 1 Vga.
|4|s1
Specifically, we employ the majorization invorizationmmimmmzzttii (MM) method 115] to optimize 2; by solving this constrained minimization problem (the detailed derivation process is given in Eq. S4 $12 of Section S1.1 of Supplementary), where 2; can be iteratively refined by:
b
b <
2 BN
of = g(2
Voz,,
1
b>1
(3)
-1 b<-1
is a hyper-parameter that is required to be no less than the largest eigenvalue of (Vax))
Develop new GNN network architecture with a selective inductive bias. The building block in vanilla GNN 2 is FC (fully-connected) layer where the input is the embedding vectors after isotropic graph diffusion (in (2-norm). Since the estimation of graph embeddings x in Eq. depends on the latest estimation 2(), such recursive min-max solution for Eq. allows us to devise network architecture that disentangles the building block in vanilla GNN into the feature representation learning and graph diffusion underlying TV. As shown in Fig. 3 we first deploy a FC layer to update the graph embeddings z²(), After that, we concatenate a diffusion- -aatheing (DG) layer for selective graph diffusion, which sequentially applies (1) node-adaptive graph diffusion (blue
5

---

1.0
3.0
fi
Mer1
1.5
[Φ()
fij
1
f12
0.5
0.5
GCN
Fax
1..
G
3 s+1
f3
MSE
0.5
(a)
2.0
flow dynamics
2.5
(b)
Ars1
Figure 4: (a) The illustration of the computational challenge for estimating the spreading flow. (b) The GAN architecture for min-max optimization in the network.
arrow in Fig. 3 on x (1) by Eq. and (2) gathering operation g(-) (purple arrow in Fig. to each (1)
I by Eq.
Remarks. Eq. 3jidiictess that larger connective degree results in larger value of 2. Thus, the DG layer shifts the diffusion patterns by penalizing the inter-community information exchange (due to strong connections) while remaining the heat-kernel diffusion within the community. The preference of such link-adaptive diffusion can be adjusted by the hyper-paranee parameter > i in Eq. [ Recall our intuitive solution for over-smoothing problem in Fig. [ the DG layer offers the exact global insight of graph topology to keep the node embeddings distinct between nodes #1 and #2. We demonstrate the effect of DG layer on the real-world graph data in Fig. S3 of Supplementary document.
2.2.2 Predict flow dynamics through graph neural transport equation
Problem formulation. We live in world of complex systems, where everything is intricately connected in multiple ways. holistic insight of how the system's components interact with each other and how changes in one part of the system can affect the behavior of the whole sheds new light on the dynamic behaviors of these complex systems over time. However, oftentimes is an ill-posed problem. Taking the toy system in Fig, 4 a as example, while it is simple to calculate the future focal patterns based on the focal patterns at the current time point and the node-to-node flow information, determining flow dynamics based on longitudinal nodal observations is computationally hard since the solution is not unique.
The naïve solution to predict the spreading flow is to (1) train GNN to learn the intrinsic node embeddings and (2) predict the flow based on the difference of learned embeddings. However, this two-step approach might suffer from vanishing flow due to over-smoothing in GNNs. Following the spirit Bruchistochrone problem, we ask the question "What flow field [(t) (D) underlines the system mechanics to the extent that it is able to predict the behaviors in the future?"
In this paper, we focus on the conservative system of energy transportation 2 is formulated as:
The system mechanies
dæ + div(g)= =
dt
where = Jaylğ=1 is the flux field which propagates the potential energy u(t) = [t), (conserved quantity) over time. Similar to a gravity field driving water flow, the intuition of Eq. is that the change of energy density (we assume there is non-linear mapping ø from external force x to u, i.e., u, = o(x:)) leads to energy transport throughout the entire graph. As flux is closely related to the difference of energy Veu underlying the graph topology, we assume the energy flux q is regulated by the potential energy field Vgu, i.e., g = a @ Vgu, where a [o,,]]]== is learnable matrix characterizing the link-wise contribution of each energy potential Vgug to the potential energy flux Gij-
By plugging q = a & V Vgu into Eq. 4 the energy transport process can be reformulated as:
Du - & div( (gu)) - & Au), Øt
(5)
where A = div(Ve (Vg) is the graph Laplacian operator. Since the PDE in Eq. 5 is equivalent
to the E-L equation of the quadratic functional J(u) min Sg a & VVu du (after taking
Since the optimization schema has been switched to the layer- manner, the initialization zn becomes (1- ) from the previous layer.
'A can be either pre-defined or learned from the data.

---

away), a major issue is the over-smoothhess in that might result in vanishing flows. In this context, we propose replace the norm integral functional J(u) with TV-based counterpart (T) min Jg 6 [Vguldu.
Renovate new E-I equation - graph neural transport equations. Following the min-max optimization schema in Eq. +3 we introduce an auxiliary matrix f to lift the undifferential- able barrier. After that, the minimization of (rv(u) boils down into a dual min-max functional (u, f) min max Ig @ f(Vgu)du. Since u(t) is time series, it is difficult to derive the
deterministic solutions (as Eq. 3 by letting JTV 0 and of Jrv 0. Instead, we Gâteauz variations to optimize Jrv (u, f) via the following two coupled time-dependent PDEs (please see Section S1.2, Eq. S14 to Eq. S19, in Supplementary for details);
max of
Vgu
(6)
min
du di
= a @ dio(f)
Remarks. The solution to Eq. 6 is known as continuous max-flow and constitutes a continuous version of graph-cut [1] Since is latent variable and potential energy u is given, the maximization of f opts towards maximizing the spreading flow through the lens of a. In this regard, the mechanistic role of auxiliary matrix f is essentially the latent (maximized) spreading flows that satisfy u(t+ 1),
u(t); + (z,(() The potential energy â can be solved via a wave equation (Uez = div(f.)
a² ② Au). where the system dynamics is predominated by the adjusted Lagrangian mechanics 2 X Au. By determining a at granularity of graph links, we devise a novel GAN model predict the spreading flows f which not only offers explainability underlying the min-max optimization mechanism in Eq. but also sets the stage to understand system dynamics through machine learning. Develop GAN model of flow prediction with TV-based Lagrangian Mechanics. The overall network architecture is shown in Fig. 4 (b), which consists of a generator (red solid box) and discriminator module (blue solid box). Specifically, the generator (G) consists of (1) GCN component [14] to optimize through the wave equation Ugt = a² @ Au and (2) a FC layer to characterize the non-linear mapping function 2(t + 1) o (u(t)). In contrast, the discriminator (D) is designed to (I) synthesize a and (2) construct the future ū++1 based on the current ue and current estimation of spreading flow
Vgu (orange dash box). To make the network architecture consistent between generator and discriminator modules, we include another GCN to map the synthesized ū(t + 1) the external force ä(t + 1). Note, since the working mechanism of this adversarial model underlines the min-max optimization in the energy transport equation, the nature of predicted spreading flows is carved by the characteristies of max-flow.
The driving force of our network is to minimize (1) the MSE (mean square error) between the output of the generator 4.+1 and the observed regional features, (2) the distance between the synthesized regional features ēt+1 (from the discriminator) and the output of generator 2:41 (from the generator). In the spirit of probabilistic GAN (4), we use one loss function Lp to train the discriminator (D) and another one LG to train the generator (G):
{
LD D (1++1) + --DD-((()))
= D
where & denotes the positive margin and the operator |+] max(0. -). Minimizing Le is similar to maximizing the second term of LD except for the non-zero gradient when D(G(zz)) 2 g.
3 Experiments
In this section, we evaluate the performance of the proposed GNN-PDE-COV framework with comparison six graph learning benchmark methods on a wide variety of open graph datasets [32] as well as a proof-of-concey application of uncovering the propagation pathway of pathological events in Alzheimer's s disease (AD) from the longitudinal neuroimages.
3.1 Datasets and experimental setup
Dataset and benchmark methods. We evaluate the new GNN models derived from our proposed GNN framework in two different applications. First, use three standard citation networks, namely
7

---

Cora, Citeseer, and Pubmed [32 for node classification (the detailed data statistic is shown in Table S2 of Supplementary). We adopt the public fixed split [0] to separate these datasets into training. validation, and test sets. We follow the experimental setup of [9] for a fair comparison with six benchmark GNN models (vanilla GCN 23 GAT (44 GCNII [9], ResGCN [25), DenseGCN (25],
GRAND ()). Since our DG-layer can be seamlessly integrated into existing GNNs as a plug-in. The
corresponding new GNN models (with DG-layer) are denoted GCN+, GAT+, GCNII+, ResGCN+
DenseGCN+, and GRAND+, respectively.
Second, we apply the GAN model in Section 2.2.2 to predict the concentration level of AD-related pathological burdens and their spreading pathways from longitudinal neuroimages. Currently, there is no invo imaging technique that can directly measure the flow of information across brain regions. Here, our computational approach holds great clinical value in understanding the pathophysiological
mechanism involved in disease progression [22 Specifically, we parcellate each brain into 148
cortical surface regions and 12 sub-cortical regions using Destrieux atlas [12]. The wiring topology of these 160 brain regions is measured by diffusion-
imaging [] and tractography techniques
17 The regional concentration levels AD pathology including amyloid, tau, and fluorodeoyyglucose
(FDG) and cortical thickness (CoTh) are measured from PET (positron emission tomography) and
MRI (magnetic resonance imaging) scans [20]. We use total of M = 1, 291 subjects from ADNI
28 each having longitudinal imaging data (2-5 time points). The details of image statistics and
pre pre-processing are shown in Sec. 1.2..2. Since we apply the flow prediction model to each modality separately, we differentiate them with X- FllowNer (X stands for amyloid, tau, FGD, and CoTh)
Experimental setup. In the node classification task, we verify the effectiveness and generality of DG-layer in various number of layers (I. = 2, 4, 8, 16, 32, 64, 128). All baselines use their default parameter settings. Evaluation metrics include accuracy, precision and F1-score. To validate the performance of X-FlowNet, we examine (1) prediction accuracy (MAE) of follow-up concentration level, (2) prediction of the risk of developing AD using the baseline scan, and (3) understand the propagation mechanism in AD by revealing the node-to-node spreading flows of neuropathologies.
The main results of graph node classification and flow prediction are demonstrated in Section 3.2 and 3.3 respectively. Other supporting results such as ablation study and hyper-paramene setting are shown in Section S2 of the Supplementary document.
3.2 Experimental results on graph node classification
We postulate that by mitigating the over-smoothing issue, we can leverage the depth of GNN models to effectively capture complex feature representations in graph data. As shown in Table [I] we investigate the graph node classification accuracy as we increase the number of GNN layers by six benchmark GNN models and their corresponding plug-in models (indicated by '+' at the end of each GNN model name) with the DG-layer. The results demonstrate that: (1) the new GNN models generated from the LNN-PDE-COV framework have achieved SOTA in Cora (86.30% by GCNII+), Citeseer (75.65% by GRAND+). and Pubmed (80.10 % by GCNII+); (2) all of new GNN models outperforms their original counterparts with significant improvement in accuracy; (3) the new GNN models exhibit less sensitivity to the increase of model depth compared to current GNN models; (4) the new GNN models are also effective in resolving the gradient explosion problem (26) (e.g, the gradient explosion occurs when training GAT on all involved datasets with deeper than 16 layers, while our GAT+ can maintain reasonable learning performance even reaching 128 layers.)
It is important to note that due to the nature of the graph diffusion process, graph embeddings from all GNN models (including ours) will eventually become identical after a sufficiently large number of layers [I]. However, the selective diffusion mechanism (i.e., penalizing excessive diffusion across communities) provided by our and optimize them for specific graph learning applications.
framework allows us to control the diffusion patterns
3.3 Application for uncovering the propagation mechanism of pathological events in AD
First, we evaluate the prediction accuracy between the ground truth and the estimated concentration values by our X-FlowNei and six benchmark GNN methods. The statisties of MAE (mean absolute error) by X-FlowNel, GCN, GAT, GRAND, ResGCN, DenseGCN and GCNII, at different noise levels on the observed concentration levels, are shown in Fig. (a). It is clear that our X-FlowNet consistently outperforms the other GCN-based models in all imaging modalities.
8

---

Table 1: Test accuracies (%) on citation networks. We show the mean value, the quota of increase (M)decrease()) after adding DG layer. Statistical significance is determined from 50 resampling tests. '*' means statistically significance with p S 0.05, '**" denotes p S 0.01. The missing results are due to the huge consumption of GPU memory for large graphs (DenseGCN) or gradient explosions (GAT) or non-convergence (GRAND). The best performance of baselines is denoted in blue, while the best performance after adding the DG layer is denoted in red.
Dataset Model
L=2
==4
==8
L 16
== 32
L == 64
128
GCN
81.30
79.90
75.70
25.20
20.00
31,80
20,80
GCN+
82.70
82.70
201
82.30
6.601
25.60
67.80
17.8
66.60
59.9030.11
GAT
82.40
80.30
57.90
31.90
Cora
GAT+
82.60
80.50
69.70
66.00
14.17
63.60
54.60
45.70
GRAND
80.00
82.64
82.74
83.45
8183
80.81
79.19
GRAND+
81.93
931
83.45
82.95
201
84.27
1.321
83.15
81.52b.711 711
90.10
ResGCN
76.30
77.30
76.20
77.60
73.30
31.90
31.90
ResGCN+
77.80
78.70
1.07 1utt
78.80
2.0r
78.60
Lour
76.90%
s.car
76.80
44 .t
33.601.707
DCnseGCN
76.60
78.50
76.00
DenseGCN
78.00
78.70
76.90 101
.00
201
GCNII
76.40
81.90
81.50
84,80
84.60
85.50
85.30
GCNII+
84.70
84.80
2007
301
84.70
2.20
85.20
85.40
86.30%
85.60
GCN
70.20
62.50
62.90
21.00
17.90
22.90
19.80
GCN+
72.902.70:
67.30%
s01
72.00 1.0
54.70 71
50.30
32.41 41
48.40 21
46.60% 26.81
GAT
71.70
58.60
26.60
18.10
Citeseer
GAT+
73.001
.3p
69.50
47.60
31.80
13.71
31.30
30.60
29.30
GRAND
71.94
72.58
73.87
75.00
76.16
72.90
69.
GRAND+
72.26
73.55
75.161
291
75.65
651
75.52
0.35
74.52 122
72.262.711
ResGCN
67.10
66.00
63.60
65.50
62.3
18.80
18.10
ResGCN+
68.00%
0.00:
67.60
66.00
2.40
66.00
65.80
3.500
24.00 201
24.30%.207
DenseGCN
67.40 WenseGCN+67.80000
64.00
62.20
66.60
64.70
GCNII
66.50
67.80
69.30
71.60
73.10
71.40
70.20
GCNII+
72.40 our
73.30 at
73.80
4.50r
73.40
sot
73.80
0.70r
74.60 201
73.903.707
GCN
78.50
76.50
77.30
40.90
38.20
38.10
38.70
GCN+
79.80
.00
79.10
200
78.20
0.sot
77.40%..
36.51
76.20%3.0
38.01
75.10
73.00
GAT
77.40-
72.20
77.80
40,70
GAT+
77.906.ca7
77.30;
78.50
tm 73.50
68.20
66.80
63.50%3.6
Pubmed
1ot
GRAND
77.07
77.94
78.29
79.93
79.12
GRAND+
78.03
78.34
(5.34..007
0.10
80.21
1
80.08
15t
79.32
0.201
ResGCN
76.30
77.
26.20
77.6 20
73.30
31.90
31.90
ResGCN+
77.80
.oy
78.70
1ot
78.802.cr
78.601.07
oor
76.90%
3.e
76.80
sot 32.00..10r
DenseGCN DenseGCN+
75.80
76. 16.10
75.80
MinnseCN++6.10.....
76.10p.30
76.70%
aot
77.50
GCNII
77.30
78.80
79.50
79.70
79 90
0,7980
79.70
GCNII+
78.40
or 80.10;
301
80.00
80.10
g.007 80.00 $0.00
80.10,.407
Second, we have evaluated the potential of disease risk prediction, which can be regarded as graph classification problem. We assume that we have baseline amyloid, tau, FDG, and CoTh scans, and evaluate the prediction accuracy, precision and F1-score of various models in forecasting the risk of developing AD. We consider two dichotomous cases: one included only AD vs. CN groups and the other involved AD/LMCI vs. CN/EMCI. The results of the mean of 5-fold cross-validation are Our GNN-PDE-CON -CV model not only achieved the highest diagnostic accuracy but also demonstrated a significant improvement (paired 1-test p < 0.001) in disease risk prediction compared to other methods. These results suggest that our approach holds great clinical value for disease early diagnosis.
shown in Table 2
Third, we examine the spreading flows of tau aggregates in CN (cognitively normal) and AD groups. As the inward and outward flows shown in Fig. 5(b), it is evident that there are significantly larger amount of tau spreading between sub-cortical regions and entorhinal cortex in CN (early sign of AD onset) while the volume of subcortical -entrriiii tau spreading is greatly reduced in the late stage of AD. This is consistent with current clinical findings that tau pathology starts from sub-cortical regions and then switches to cortical-cortical propagation as disease progresses [24]. However, our Tau-FlowNer offers a fineggraullrrity brain mapping of region-to-region spreading flows over time, which provides new window understand the tau propagation mechanism in AD etiology [13).
9

---

Tan-PET
GAT
Amyloid-PET
(b)
CNAD
E
Awyyloa Plooa-FFFoe-eee
MAE
ResGeN
GCNI
GCX
GRAND
ReGGC
DemeGON
GUNI
Pipporampus
I.S.
Candate
GCN
GAT
2999 B.878R
FDG FloowNer
GRAND
GCNT
RexGON
DenneCer
MAE 1
GON
Grand
BLASS
Co
RoEGEN
GCNI
degree
7,2/1.96
total flow volume
FDG-PET
CoTh-PET
Figure 5: (a) Prediction accuracy by X-FlowNer and six benchmark GNN models w.r.f. various noise levels. (b) The subcortical-ccooe tau flows are profound in CN. But in AD, there is a diminished extent of such flows.
Table 2: The performance of disease risk prediction. Note: RGCN denotes ResGCN, DGCN denotes
DenseGCN. *** denotes the significant improvement (paired 1-test: p < 0.001). Blue: Tau, red:
amyloid, orange: FDG, green: CoTh.
Tau
Unit (56) GCN GCN+ GAT GAT+ GCNII GCNIG RGCN RGCN+ DGCN DGCN+ GRAND GRAND+
ADILMC
Precision 80.15 90.03(") 69.91 86.18(*) 83.93 90.03(*)
84.64 89.46(*)
84.03 91.58(*)
87.95
88,22(*)
Vs.
Accuracy 82.30 88.74()) 81.05 87,50(*)
83.79 88.75(*)
86.03 90.00(*)
85.54 91.25(*)
88.75
90.12(*)
CN/EMCI
Fl-spore 75.55 (4)49(*) 72.87 84.72(*)
78.82
84,45(*)
83.15 88,54(*)
82.45 (1.39(*)
88.14
89,44(*)
AD
Precision 89.29 91.92(") 87.26 90,13(*)
83.65
88.52())
92.61
95.72(*) 92.61 95.91())
91.77
95,76(")
vs.
Accuracy 86.64 90.91(*) 84.86 88.41(*)
76.84 86.36(*)
91.07
95.45(*)
91.07 95.65(*)
90.91
95.45(%)
CN
Fl-score 85.64 90.26(") 83.99 87.16(*)
71.51 84.68(*)
90.45
95.32(*)
90.45 95.55(*)
88.86
95,38(
Amyloid
Unit (%) GCN GCN+ GAT GAT+ GCNIT GCNI++
RGCN RGCN+ DGCN DGCN+ GRAND GRAND+
AD/LMCI
Precision 76.36 83,78(") 67.73 71.79(*) 60.87 60.010
72.53
83.21(*)
74.92 60.17(*)
79.00
79.93(")
vs.
Accuracy 76.40 79.44(*) 75.43 77.57(*) 74.31 76.64(*)
75.99 78.50(*)
76.92 77.57(*)
80.37
81.31(
CN/EMC
F1-score 70.33 72.58( 67.66 69.39(*) 63.57 (7.31(*)
70,66 70.67(*)
72.68 67.77(*)
79.25
79.63(*)
AD
Precision 81,58 (8.37( 81.54 87,98(*) 70.59 79,98(
85.75 93.09(
83.87
90.56(*)
65.53
89.62(*)
vs.
Accuracy 80.77 88.10(") 80.78 88.10()) 75.02 )
85.56 92.86(*)
85.29 90.48(*)
80.95
87,80())
CN
F1-score 78.14 87.68(*) ") 78.07 87.98(*) 65.87 77.42(*)
85.34 92.92(*)
82.30 90.27(*)
72.43
88,22(")
FDG
Unit GCN GCN+ GAT GAT+ GCNII GONIL+ RGCN RGCN+ DGCN DGCN+ GRAND GRAND+
AD/MMI
Precision 68.43 69.29( 55.86 59.29(*) 60.08 70,94(3)
50.45 55.14(²)
50.45 55.14(*)
$1.38
56,25(*)
vs.
Accuracy 73.17 76.00(*) 72.17 77.00(*) 71.78 (
70.98 74.26(*) 70.98 74.26(*)
71.10
75.00(
CN/EMCI
F1-score 63.94 68.15(") 62.15 66.99(*)
61.02 69.07(*)
58.96
63.29(*)
58.96 63.29(*)
59.42
64.29(*)
AD
Precision 81.11 87.25(") 61,90 62.33(*) 74.31 81.06(*)
59.77 80.57())
66.84 81.77())
70.91
72.24())
vs.
Accuracy 82.17 84.62(") 72.82 78.95(") 79.55 82.05(*)
73.35 79.58(*)
73.87 80.11(*)
84.21
86.32(
CN
Fi-score 79.40 82.04(")
69.66(*)
73.88 80.99(*)
62.77 75.98(*)
63.92 76.58(*)
76.99
78.06(
CoTh
(%) GCN GCN+ GAT GAT+ GCNII GONI++ RGCN RGCN+ DGCN DICN+ GRAND GRAND+
AD/LMC
Precision 74,85 76.23(") 62.63 67.15(*) 62.63 74.71(*)
62.63 68.77(") 62.63 64.59(*)
63.81
68.77())
vs.
Accuracy 80.68 82.32(") 79.10 79.34(*)
79.10 80.37(*)
79.10 82.93(*) 79.10 80.37(*)
79.88
82.93(")
CN/EMCI
Fi-score 73.55 75.93(")
70.44(*)
69.89 72.72(*)
69.89 75.19(*)
71.62(*)
70.94
75.19(")
AD
Precision 83.45 85,77(*) 71.24 72.80(*)
76.14 79.84(*)
65.04
80.62( 63.04
81.52(
71.24
74.37(*)
vs.
Accuracy 84,79 87.16(*) 81.50 85.32(*)
81,50 (3.49(*)
80.59
83.52(*)
80.59
82.42(*)
84.40
86.24(
CN
Fl-score 82.02 83.69(") 75.06 78.56(*)
74.17
81.07(*)
71.95
78.48(*)
71.95
76.13(*)
77.27
(9)
4 Conclusion
In this work, we present the GNN-PDE-CON framework to re-think and re-design GNN models with great mathematical insight. On top of this, we devise the selective inductive bias to address the over-smoothing problem in GNN and develop new GNN model to predict the pathology flows in-vivo via longitudinal neuroimages. Future work may involve exploring innovative graph regularization techniques and conducting further validation on broader range of graph-based learning tasks.
Acknowledgement
This work was supported by the National Institutes of Health AG070701, AG073927, AG068399, and Foundation of Hope. Data collection and sharing for this project was funded by the Alzheimer's Disease Neuroimaging Initiative (ADNI) (National Institutes of Health Grant UOI AG024904) and DOD ADNI (Department of Defense award number W8IXXH--1222-0022)
10

---

References
[1] Appleton, B., Talbot, H.: Globally minimal surfaces by continuous maximal flows. IEEE
Transactions on Pattern Analysis and Machine intelligence 28(1), 106-118 (2005)
[2] Aroo'', V.:: Mathematical methods of classical mechanics, vol. 60. Springer Science & Business Media (2013)
[3] Bammer, R.: Basic principles of diffusion weiggte imaging. European Journal of Radiology 45(3), 169-184 (2003)
[4] Beck, A., Teboulle, M.: fast iterative problems. SIAM Journal on Imaging Sciences 2(1), 183-202 (2009)
algorithm for linear inverse
[5] Bronstein, M.: Beyond message passing: physics-inspired paradigm for graph neural networks. The Gradient (2022)
[6] Chamberlain, B., Rowbottom, J., Gorinova, M.I., Bronstein, M., Webb, S., Rossi, E.: Grand: Graph neural diffusion. In: International Conference on Machine Learning. pp- 1407-1418. PMLR (2021)
[7] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applica- tions to imaging. Journal of Mathematical Imaging and Vision 40(1), 120-145 (2011)
[8] Chan, T., Esedoglu, S., Park, F., Yip, A.: Total variation image restoration: Overview and recent developments. Handbook of Mathematical Models in Computer Vision pp. 17-31 (2006)
[9] Chen, M., Wei, Z., Huang, Z., Ding, B.. Li, Y.: Simple and deep graph convolutional networks. In: International Conference Machine Learning. pp. 1725- 1735. PMLR (2020)
[10] Chen, R.T., Rubanova, Y., Bettencourt, J., Duvenaud, D.K.: Neural ordinary differential equations. Advances in Neural Information Processing Systems 31 (2018)
[11] Coifman, R.R., Lafon, S.: Diffusion maps. Applied and Computational Harmonic Analysis 21(1), 5-30 (2006)
[12] Destrieux, C., Fischl, B., Dale, A., Halgren, E.: Automatic parcellation of human cortical gyri and sulci using standard anatomical nomenclature. Neuroimage 53(1), 1-15 (2010)
[13] Dujardin, S., Fermandes, A., Bannon, R., Commins, C., De Los Santos, M., Kamath, T.V., Hayashi, M., Hyman, B.T.: Tau propagation is dependent the genetic background of mouse strains. Brain Communications 4(2), feac048 (2022)
[14] Eliasof, M., Haber, E., Treister, E.: Pde-gen: novel architectures for graph neural networks motivated by partial differential equations. Advances in Neural Information Processing Systems 34, 1836-3849 (2021)
[15] Figueiredo, M.A., Bioucas-Dise J.M., Nowak, R.D.: cnneiiaationmminnnzaatiiio algorithms for wavelet-based image restoration. IEEE Transactions Image processing 16(12), 2980-2991 (2007)
[16] Gao, H., Ji, S.: Graph u-nets. In: International Conference Machine Learning, pp. 2083-2092 PMLR (2019)
[17] Glasser, M.F., Rilling, J.K.: Dti tractography of the human brain's language pathways. Cerebral Cortex 18(11), 2471-2482 (2008)
[18] Guo, 7., Zhang, Y., Teng, Z., Lu, W.: Densely connected graph convolutional networks for traph-to-sequenee learning. Transactions of the Association for Computational Linguistics 297-312 (2019)
[19] Hamilton, W., Ying, 7.,, Leskovee, J.: Inductive representation learning on large graphs. Ad- vances in Neural Information Processing Systems 30 (2017)

---

[20] Jack Jr, C.R., Bennett, D.A., Blennow, K., Carrillo, M.C., Dunn, B., Haeberlein, S.B., Holtzman, D.M., Jagust, W., Jessen, F., Karlawish, J., et al.: Nia-aa research researhs framework: toward biological definition of alzheimer's disease. Alzheimer's & Dementia 14(4), 535-562 (2018)
[21] Ji, S., Pan, S., Cambria, E., Marttinen, P., Philip. S.Y.: A survey on knowledge graphs: Repre- sentation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems 33(2), 494-514 (2021)
[22] Jones, D.T., Graff-Radford J., Lowe, VJ.., Wiste, H.J., Gunter, J.L., Senjem, M.L., Botha, H., Kantarci, K., Boeve, B.F., Knopman, D.S., et al.: Tau, amyloid, and cascading network failure across the alzheimer's disease spectrum. Cortex 97, 143-159 (2017)
[23] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (2017)
[24] Lee, W.J., Brown, J.A., Kim, H.R., La Joie, R., Cho, H., Lyoo, C.H., Rabinovici, G.D., Seong, J.K., Seeley, W.W.: Regional a,8-tau interactions promote onset and acceleration of alzheimer's disease tau spreading. Neuron 110(12). 1932- 1943 (2022)
[25] Li, G., Muller, M., Thabet, A., Ghanem, B.: Deepgens: Can gens go deep cnns? In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 9267-9276 (2019)
[26] Li, Q.. Han, Z., Wu, X.M.: Deeper insights into graph convolutional networks for semi- supervised learning. In: Proceedings of the AAAI Conference Artificial Intelligence. vol. 32 (2018)
[27] Morris, C.: Graph neural networks: Graph classification. In: Wu, L., Cui, P., Pei, J., Zhao, L. (eds.) Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 179-193. Springer Singapore, Singapore (2022)
[28] Petersen, R.C., Aisen, P.S., Beckett, L.A., Donohue, M.C., Gamst, A.C., Harvey, D.J., Jack, C.R., Jagust, W.J,, Shaw, L.M., Toga, A.W., Trojanowski, J.Q., Weiner, M.W.: Alzheimer's disease neuroimaging initiative (adni). Neurology 74(3), 201-209 (2010)
[29] Poli, M., Massaroli, S., Park, J., Yamashita, A., Asama, H., Park, J.: Graph neural ordinary differential equations. arXiv preprint arXiv:1911.07533 (2019)
[30] Pradhyumna, P., Shreya, G., et al.: Graph neural network (gnn) in image and video understanding using deep learning for computer vision applications. In: 2021 Second International Conference on Electronics and Sustainable Communication Systems (ICESC), pp. 1183-1 119. IEEE (2021)
[31] Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena 60(1-4), 259-268 (1992)
[32] Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., Eliassi-Rad, T.: Collective classifica- tion network data, AI Magazine (3)3), 93-93 (2008)
[33] Thekumparampil, K.K., Wang, C., Oh, S., Li, L.J.: iitention-based graph neural network for semi-supervised learning. arXiv preprint arXiv:1803.0377 (2018)
[34] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. International Conference on Learning Representations (2018)
[35] Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM Journal on Imaging Sciences 1(3), 248-272 (2008)
[36] Wu, L., Chen, Y., Shen, K., Guo, X.. Gao, H., Li. S., Pei, J., Long, B., al.: Graph neural networks for natural language processing: A survey. Foundations and Trends@) in Machine Learning 16(2). 119-328 (2023)
[37] Wu, S., Sun, F,, Zhang, W., Xie, X., Cui, B.: Graph neural networks in recommender systems: a survey, ACM Computing Surveys 55(5), 1-37 (2022)
12

---

[38] Xhonneux, L.P., Qu, M., Tang, J:: Continuous graph neural networks, In: International Confer- ence on Machine Learning, pp. 10432-10441. PMLR (2020)
[39] Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.i., Jegelka, S.: Representation learning on graphs with jumping knowledge networks. In: International Conference on Machine Learning. pp. 5453-5462. PMLR (2018)
[40] Yang. Z., Cohen, W., Salakhudinov, R.: Revisiting semi-supervised learning with graph embed-
dings. In: International Conference on Machine Learning. pp. 40 48. PMLR (2016)
[41] Zhang, M., Chen, Y.: Link prediction based on graph neural networks. Advances in Neural Information Processing Systems 31 (2018)
[42] Zhang, Y., Gao. S., Pei, J., Huang, H.: Improving social network embedding via new second- order continuous graph neural networks. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp- 2515-2555 (2022)
[43] Zhao, J., Mathieu, M., LeCun, Y:: Energy- based generative adversarial network. International Conference on Learning Representations (2017)
[44] Zhu, M., Wright, S.J., Chan, T.F., et al.: Duality-baat based algorithms for Notal-variation reguulrrie- image restoration. Computational Optimization and Applications 47(3), 377 (2010)
13


Reviews:
[{"review_id": "5PkalXhQuJ", "reviewer": "Reviewer_VF1D", "summary": "The authors develop a framework for linking discrete (message passing) GNNs to continuous graph diffusion functional networks using Euler-Lagrange equations of heat kernels.  Via this framework, they analyze the causes of oversmoothing in current GNNs. By noting that the main cause of oversmoothing is the minimization of the quadratic graph smoothness term in the diffusion equation, their main contribution is to replace this by a Total Variation (TV) term (as used in image reconstruction, restoration etc.), yielding a new objective function. Further since the $l_1$ norm term of TV is non-differentiable at 0, they develop a dual min-max approach for solving this objective function iteratively by first minimizing for X and then maximizing for Z. This solution technique then results in a new GNN architecture with a separate feature learning layer (Fully Connected layer) for $l^{th}$ layer embeddings $X^l$ followed by a diffusion clip layer for generating the Z terms. They then apply their method for a specific application of predicting spreading flow dynamics. Experimental results are presented on 3 benchmark citation datasets and 6 GNN models including Vanilla GCN and  one other diffusion GCN (GRAND).\n\nTL;DR takeaway of the problem setup/motivation is how to preserve community/contextual embeddings of adjacent (dissimilar) boundary nodes in different labeled communities by preventing oversmoothing through localized message passing. The proposed solution is via the Total Variation parameter Z that should penalize inter community information diffusion.\n", "questions": "Please consider different graph setups to validate your oversmoothing diffusion models such as heterophilic graphs in which dissimilar nodes are close by and similar nodes can be far away.\n\nMore extensive evaluation of tradeoffs between convergence time and accuracy would be helpful, especially to improve accuracy on the 4 datasets as compared to the newer baselines suggested above.\n\nConsider a more realistic diffusion flow application to validate your diffusion model such as a traffic flow problem.", "limitations": "The authors have addressed the limitations of this work in the appendix, primarily the lack of diversity in evaluation datasets. In general, as pointed earlier, paper could be improved with more extensive comparisons on diverse datasets and models.\n\nThe authors have stated that the proposed topic doesn't have any negative societal impacts. To the contrary they state that \"From the application perspective, the new deep model for uncovering the in-vivo propagation flows has great potential to establish new underpinning of disease progression and disentangle the heterogeneity of diverse neurodegeneration trajectories.\" While technical correct, this comment in general applies to any work on sensitive datasets in the medical field.\n\n\n", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tAvoiding local oversmoothing by replacing the quadratic graph smoothness term in the diffusion equation by an $l_1$ norm regularize which is the TV term. This seems to be a novel application of TV to diffusion GNNs.\n\n2.\tFormal derivation of an iterative dual min-max method for solving the non-differentiable objective function with the TV term. While this type of iterative technique has gained increasing popularity starting with ADMM, the detailed derivation is a good contribution. \n\n3.\tFor small layers (2 layers), their method shows performance improvement over the other baselines. This might be due to ameliorating the oversmoothing process due to the TV Z parameter.\n", "weaknesses": "1.\tI am surprised the authors do not have references to classic papers that analyze the root causes of oversmoothing in GNNs, for example, the DropEdge paper [1] “Tackling Over-Smoothing for General Graph Convolutional Networks”, W Huang∗ , Yu Rong∗  et al.. IEEE TPAMI Aug. 2015. This paper analyzes oversmoothing by looking at a spectral analysis of the underlying adjacency matrix. It would be interesting to see if there is a connection between the $beta$ parameter and degree connectivity of equation (3) and results from [1].\n\n2.\tThe baseline model comparisons are too limited - vanilla GCN, GAT, one diffusion GNN (GRAND).\n\ta. There have been several papers that either explicitly focus on deep sampling while mitigating oversmoothing e.g., [2] “Decoupling the Depth and Scope of Graph Neural Networks”, H. Zeng, M. Zhang et al. Neurips 21. \n\tb. They test their model on citation networks which are considered highly homophilic. However, dissimilar nodes (as they illustrate in fig. 1) that would ideally prove their oversmoothing claims are adjacent to each other primarily in heterophilic networks. It would be useful if they can show their results on heterophilic graphs.\nThere needs to be an extended comparison with GNN  models  such as [2] as well as others that look at heterophilic graphs e.g., $H_2GCN$ [3] “Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs,” J. Zhu, Y. Yan et al, Arxiv. As they claim their method prevents over-smoothing, it would be very valuable to see comparative results  on heterophilic graphs and if they can show improvements over other models.\n\n3.\tExperimental Results:  [3] $H_2GCN$, [4] GeomGCN [5] GPRGNN   seem to show better results. For instance, accuracy of this paper on Pubmed is 80% while H2GCN, GeomGCN, GPRGNN show 90% accuracy. Similar results for Cora and Citeseer . \n[4] Geom-GCN: “Geometric Graph Convolutional Networks. In International Conference on Learning Representations”, Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. ICLR 2020.\n[5] GPRGNN: “Adaptive Universal Generalized PageRank Graph Neural Network”, ICLR2021.\n\n4. There may be some typos in experimental results -  published results are not consistent with published tabular data in the previous works.  E.g. GCNII results for Pubmed are 90% in Table 1 in the following nips 22 paper: https://papers.nips.cc/paper_files/paper/2022/file/75c45fca2aa416ada062b26cc4fb7641-Paper-Conference.pdf but Table 1 in this paper only shows around 79% for GCNII on Pubmed. Similarly please check Table 5 in the following nips 20 paper: https://arxiv.org/pdf/2006.11468.pdf for other discrepancies. I suggest rerunning experiments and checking for typos or otherwise undertanding why numbers are different. In general, the margin of improvement is around 2-4 points over vanilla GCNs for $H_2GCN$ and GPRGNN while the margin is also in that range for this paper, even though they show lower scores for vanilla GNN and GAT. It would definitely improve this paper if you added these papers as baselines for direct comparison.\n\n5. The diffusion flow application that is used in the paper to validate the diffusion model seems to a very niche application. It would greatly add value to the paper if you validated the model over a realistic flow model such as a traffic flow problem.\n\n6. The authors note that their iterative solution technique is not computationally intensive (appendix). However, the method was tried only on 4 limited datasets that are all citation networks. In general, for any iterative solution process the tradeoff between convergence time and accuracy requires more sophisticated and detailed evaluation. Can you improve accuracy on Pubmed (see above) at the cost of increased computation time?\n\n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely thankful for all constructive comments provided by this reviewer. We are pleased that the reviewer recognizes the merits of our new GNN technique, as the major concerns are centered on more extensive comparisons on diverse datasets and models. We have prepared all necessary results in the attached pdf file, which includes comparisons with more GNN models (such as ShaDowGNN [2], $H_2$GCN[3], and GPRGNN [5]) on six new datasets and two new benchmark experiments on traffic flow data. These results are ready to be included in the final version. \n\n$\\textbf {(1)}$ Regarding the relatively low accuracy on Cora, Citeseer, and PubMed shown in our paper compared to other published works (weakness #3,4), we would like to emphasize that such discrepancy is due to the use of different data splitting strategies. As shown in Table 1 of the 1-page PDF, we show the classification accuracies by ShaDowGNN, $H_2$GCN, and GPRGNN, utilizing a 3:1:1 (i.e., randomly split nodes of each class into 60%, 20%, and 20% for training, validation and testing, and measure the performance of the models on the test sets over 10 random splits) data split (often used for full-supervised learning) [4] (you mentioned) and a 1:25:50 (with 20 nodes per class for training, 500 nodes for validation and 1000 nodes for testing) split (often used for semi-supervised learning) [11] (as shown in Supplementary file). The relatively higher accuracy referenced by the reviewer pertains to the models trained and tested on the 3:1:1 split, where training data significantly outnumbers the validation and testing sets. In contrast, the results presented in the manuscript are based on the more challenging 1:25:50 split of the dataset. \n\n[11] Revisiting semi-supervised learning with graph embeddings, ICML, 2016\n\n$\\textbf {(2)}$ Regarding the additional evaluations on heterophilic graphs and more baseline models (weakness #2,6), we have included Texas, Wisconsin, Actor, Squirrel, Chameleon, and Cornell datasets, where the homophily ratios are less than 0.3. In Table 2 of the 1-page PDF, we have shown the node classification results as the number of GNN layers increases from 16 to 128 (we will add all the experimental results of all the layers (2 to128) on all methods in the final version). It is clear that our TV-based GNN model (GCNII+ by adding DC-layer on top of GCNII backbone) outperforms $H_2$GCN, GPRGNN, ShaDowGNN in all testing scenarios. Note, we observed a consistent 1-3% enhancement over GCNII, which is consistent with the benchmark results we have presented in Table 1 of the manuscript. Also, we are unable to make Geom-GCN running in our GPU environment (with a newer version of deep graph library) since Geom-GCN reportedly requires CUDA 9.2. Given the short turnaround time, we didn’t include Geom-GCN in Table 2 of the attached 1-page PDF. We have released all the codes and data on GitHub (please use the same anonymous link shown in the manuscript if can access).\n\n$\\textbf {(3)}$ Regarding the validation of flow experiment on traffic data (weakness #5), we have evaluated our FlowNet on two benchmarks of traffic flow datasets: METR-LA (arXiv:1707.01926) and PEMS-BAY (arXiv:2108.09091). The MAE by our FlowNet is 3.411 in METR-LA (3.229 by the best model) and 1.814 in PEMS-BAY (1.790 by the best model), respectively. Compared with the results published on website paperswithcode (please refer to Fig.1 in the 1-page PDF), our proposed method can achieve competitive promising results, compared to the current state-of-the-art models. Thank you for this constructive suggestion, we will add these experiment results to the Supplementary in the final version.\n\n$\\textbf {(4)}$ Regarding the methodology comparison with DropEdge [1] (weakness #1), we appreciate this valuable information. We will include this work in the final version, as part of the related work. Since the journal paper this reviewer is referring to has not yet been published in TPAMI, we will cite their conference paper (DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. ICLR 2020). Although both works aim to address the over-smoothing issue in GNN, the two approaches are completely different. “DropEdge” focused on preventing over-smoothing by reducing the number of network edges which might undermine the graph topology. Our work provided a top-down mathematical framework to regulate the message exchange through a min-max optimization schema. In the perspective of methodology, we would like to argue that there is NO DIRECT connection between the beta parameter in Eq. 3 and the “DropEdge” operation in their work. \n\n$\\textbf {(5)}$ Regarding the computational cost (weakness #6), we have summarized the running time for various GNN models in Table 3 of 1-page PDF.\n\n$\\textbf {(6)}$ Regarding the concern on societal impact, we mainly use neuroimaging data and clinical outcomes from public databases. Note there are no biological/chemical resources included in this paper. The human subject information of all imaging and demographic data has been completely removed from the public databases.\n"}, {"review_id": "3aTbfyrBsW", "reviewer": "Reviewer_paGB", "summary": "The authors propose a framework based on the Euler-Lagrange equation to derive specialized GNNs by discretizing continuous diffusion functionals. By deriving a new GNN layer from the Total Variation functional, they manage to control the oversmoothing problem in existing GNN architectures and improve node classification performance of six existing architectures with up to 128 layers. Additionally, the authors introduce a new GAN to learn flow problems on graphs and evaluate it on longitudinal data from Alzheimer's disease.", "questions": "1. In how far does GNN-PDE-COV rely on the homophily assumption? Part of the problem illustrated in Figure 1 is that the strong connection between nodes of separate classes breaks the homophily assumption of many GNN models.\n1. How does the runtime of your model scale in the number of nodes $N$ and number of edges $E$?", "limitations": "The appendix mentions briefly limitations of the mode of evaluation. I would be interested in a point on how feasible it is to derive specialized architectures based on the GNN-PDE-COV framework given that the optimization problem in the proposed GAN is completely different from the optimization problem in Section 2.2.1.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The prominent strengths of this paper are the thorough evaluation and the great results on node classification showing that the proposed DC layer can improve different architectures and enable deeper graph neural networks. The proposed GAN also performs very well on flow prediction in an Alzheimer's disease dataset though I cannot judge the subject-specific interpretation of those results. In the derivation of their method, the authors combine many techniques though it is in parts difficult to follow (see Weaknesses).", "weaknesses": "The one major weakness of this paper is its (lack of) clarity in writing. Many ideas are insufficiently explained and notation is often inconsistent and confusing. In particular, I refer to the following:\n\n1. Line 90: The numbers for Cora and Citeseer are not in Table 1.\n1. Line 110: Graph divergence operator is never defined and no reference is given.\n1. Line 111-121: Unclear writing that mixes two different ideas. The first two sentences talk about an often-used (citations missing) regularization term and its effect, but the remainder of the paragraph is about interpreting GNN structures as neural ODEs on graphs.\n1. Line 127-130: Drawing the conclusion that you have established this mapping requires either further explanation or at least a citation.\n1. Line 136: Which L2 norm does this refer to? The one in the functional in line 127?\n1. Line 158-159: The definition of $J_{\\mathrm{TV}}$ is completely unclear. $x$ is triple bound (parameter of $J_{\\mathrm{TV}}$, parameter of $\\min$ operator and integrated over) and $z$ is double bound.\n1. Line 160-161: What exactly does this \"trick\" consist of and in which sense is \"degree\" used in this sentence?\n1. Equation (1): Same issue as line 158-159.\n1. Equation (3): Is the clipping elementwise?\n1. Line 190: Why are the $x_i$ being clipped when Equation (3) referes to the $z_i$?\n1. Line 191: How does large degree increase $z_i$? An arbitrary number of edges of identical nodes would leave $z_i$ still unchanged, wouldn't it?\n1. Line 192-193: What does it mean to \"shift the diffusion pattern\"? Which cases of the case distinction in Equation (3) correspond to \"heat-diffusion within community\" and \"penalizing inter-community exchange\"?\n1. Line 211: How is future predictability related to the Brachistochrone problem that asks about the shortest path?\n1. Section 2.2.2: The whole section is difficult to follow because it introduces yet another problem and solution in little space. While I understand the importance of this section as an example for an alternative GNN architecture derived from the proposed method, for the overall clarity of the paper the space might be better used to clarify the main method.\n1. Overall, the importance of the Brachistochrone problem is overemphasized and diverts attention from the main contribution of the paper. It is a nice example application of the E-L equation but even in Figure 1 the analogy between the mechanics and ML case is weak.\n\nThis paper leaves the impression of solid work, though the opaque presentation prevents me from saying so with any certainty. A thorough rewrite of Section 2 with a focus on the reader could make this a great paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive comments from this reviewer. We answer the general question first and then clarify each specific comment. \n\nGeneral questions: \n\nWe appreciate the insightful question regarding the homophily assumption. In our GNN-PDE-COV framework, similar to current GNN models, we do adopt the homophily assumption, which implies that graph embeddings between two nodes that are topologically connected are expected to be similar. As we explained in lines 191-196, we introduce the total variation (TV) on graph gradients to incorporate a high-level heuristic of community structure into the information exchange on the graph. Thus, the homophily assumption remains a fundamental driving factor in our GNN models. The inclusion of the TV term in the DC layer (Eq. 3) provides a flexible mechanism to adaptively control the information exchange based on the global topology of the network community. In the 1-page PDF attached with this rebuttal, we have shown the new benchmark results on five heterophilic graph datasets (Texas, Wisconsin, Actor, Squirrel, Cornell, and Chameleon) in Table 2. The results indicate that our TV-based GNN model also performs well on heterographic data. \n\nRegarding the running time (summarized in Table 3 of the attached 1-page PDF), the driving factor is the number of nodes $N$. This is because the majority of operations in our GNN model, as well as in other GNN methods, are primarily applied to nodes rather than edges.\n\nSpecific comments in “Weaknesses” session:\n\n1. The accuracy numbers for Cora and Citeseer are in Table 1 (128 layers, last column and last row of each dataset). Since the numbers in Table 1 are densely packed, this reviewer might have missed the %. We will highlight them in the final version. \n\n2. We will explain the graph divergence operator in the final version. \n\n3. We will smooth out the write-ups to transit from GNN regularizer to PDE. Thanks for this constructive comment. \n\n4. We will add a reference since it is not our major contribution. Thanks. \n\n5. Correct. We will make it clear in the final version. \n\n6. We apologize for this notation issue. We will fix this in the final version by replacing “$J_{TV}(x,z)$” with \"$\\mathop {\\min }\\limits_{x} \\mathop {\\max}\\limits_{z}J_{TV}(x,z)$\", where $J_{TV}$=...”.  \n\n7. We will include a reference to explain the approximation used to handle the absolute value operator on $z$ during optimization. Due to the page limit, this information will be provided in the Supplementary material.\n\n8. We have explained in #6.\n\n9. Correct, the clip operation is element-wise. \n\n10. We apologize for the confusion. Actually, $z$ is the intermediate result of $x$. Precisely speaking, we update $z$ based on $x$ and then apply clip operation on $z$. After that, we replace $x$ with the updated $z$ for graph diffusion. We will make it clear in the final version. \n\n11. Following the homogeneity assumption that nodes within the same community share the group-specific characteristics of graph embeddings, inter-community links are supposed to have large gradient gradients, which leads to the large value of $z$. \n\n12. We have specifically discussed the TV-based diffusion patterns in Supplement S2.2. Please also refer to Fig. S3. Specifically, we find that (1) more than 70% nodes are actually associated with inter-class links which confirm the hypothesis of over-smoothing in Fig. 1 of our manuscript; (2) Our novel GNN models have the ability to learn feature representations that better preserve the discriminative power for node classification (as indicated by the distribution of node-to-node similarity shifting towards the sign of anti-correlation).\n\n13. We used the shortest path in the Brachistochrone problem as an example motivating work. For each learning problem, the underlying questions may vary. For example, the FlowNet (in 2.2.2) is seeking for a set of max-flows that underline the network community structure. \n\n14. Due to the page limit, we moved the background of neuroimaging application to the Supplement. We will make it clear in the final version (by adding more detail of background in the Supplementary). \n\n15. We would like to emphasize that the Brachistochrone problem in Fig. 1 is only used to help readers understand the motivation of linking GNN to a calculus of variation problem. Our major contribution is to address the over-smoothing issue in GNN from the perspective of designing application-specific graph diffusion patterns.\n\nThank you for your valuable comments, we will incorporate all the comments and suggestions in the final version.\n"}, {"review_id": "bHrhL9BRm1", "reviewer": "Reviewer_CRUA", "summary": "The authors connects graph neural networks with discretizations of PDEs and connects their limiting behavior with E-L equations. By changing regularization / smoothing term from second order to first order, the authors designed a new E-L equation and its corresponding GNN. The author then present numerical experiments to show their improvement in performance. ", "questions": "- Equation 3 sounds similar to the MBO scheme, which is basically diffusion + clip. Are there any connections in between?\n- Does your model transfer to other types of neural networks like convolutional neural networks?\n- Does your model requires more computation time? How much more compared to the origional run time of GCN, GAT, and GRAND?", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The authors tackles the problem of oversmoothing in GNN, which is an essential problem GNN cannot get as deep as other neural networks.\n- The authors provided solid mathematical support on their method and great experimental performance.\n- It is an original work connecting TV-minimization from the old school machine learning, with the SOTA design of GNNs.", "weaknesses": "- The authors should do an table outlining the steps of their algorithm. It will make it easier for audience who prefer testing model before going through the math.\n- The infomation in figure 5 is too dense. It would be better if the authors could split it into two figures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the reviewer is enthusiastic about this work. We will outline the steps of our algorithm in a table (likely in the Supplementary material). Also, we appreciate the comment regarding the layout of Fig. 5. We will split it into two figures in the final version. \n\nWe agree with this reviewer that our min-max optimization is very close to the classic Merriman-Bence-Osher (MBO) scheme for TV-based image filtering. Actually, our work is greatly inspired by these pioneering works. \n\nOur current work only applies to graph data. Recall the connection between ResNet and NeuroODE, it is possible to devise a new CNN-based backbone using the similar framework, that is, designing new functionals in a continuous domain and developing the equivalent discrete deep models. \n\nCompared to GCN and GAT, there is no significant increase of running time by our method since the operations in the DC-layer are element-wise multiplication and clip. However, our method is almost 5 times faster than GRAND which relies on a PDE solver. We have summarized the comparison of running time (by text) in the Supplementary (lines 161-165). We will show the detailed computation time in a table (as shown in Table 3 of the 1-page pdf file in the rebuttal) in the final version. \n"}, {"review_id": "h4bzqrDhwD", "reviewer": "Reviewer_sJUp", "summary": "This work studies a novel design of GNN leveraging the connection with graph diffusion. Specifically, this work considers the discrete GNN model in view of continuous graph diffusion functional formulated as the Euler-Lagrange equation. This work proposes a new design of GNN with selective inductive bias which alleviates the over-smoothing in GNNs. Further, this work proposes a new approach for predicting the flow dynamics in the graph via a neural transport equation using the GAN model to predict the spreading flow.", "questions": "- What is the purpose of using total variation? Is it simply from the inspiration explained in line 151?\n\n- Although the extra training time is described in section S2.4, comparing it with the training time without DC layer would show that the computational burden is not significant.", "limitations": "The limitations are discussed in the supplementary file section S2.4.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper is well-written with clear motivation and justification. The writing is easy to follow with summarized questions and the paper's approach (re-think and re-design) helps to understand this work.\n\n- The proposed architecture is novel yet simple based on theoretical justifications leveraging the connection with the graph diffusion (although this was studied widely in other papers). Further, the GAN model for flow prediction is also new, using neural transport equations.\n\n- The experimental results show superior performance compared to the baselines in node classification, and the results in node classification demonstrate that the proposed architecture mitigates the over-smoothing issue.", "weaknesses": "- Related work section could greatly help the readers for understanding this work as it deals with new GNN as well as flow prediction in graphs. I assume that the related work section was omitted due to the page limit, and recommend adding it if possible.\n\n- The reason for the superior performance of the GAN model is not clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the valuable comments from this reviewer. We will incorporate all suggestions into the final version. \n\nWe will add a “Related Work” section in the Supplementary which includes the relevant GNN work in solving over-smoothing issues (suggested by Reviewer HWVs) and neuroimaging background on predicting pathology spreading flows.  \n\nIn general, the performance gain of GAN is largely from the min-max optimization schema. Specifically, mounting neuroscience evidence shows that the propagation of disease-specific pathologies underlines the community structure of the brain’s wiring diagrams [1, 2]. Following this assumption, we formulate the flow estimation problem into a TV-constrained objective function, where we minimize the graph smoothness constraint (using the graph heat kernels) while maximizing the inter-community flux ($\\alpha$ in Eq. 6). After that, we devise the equivalent discrete deep model using GAN. At a higher level, the promising result of flow estimation showcases the effectiveness of our GNN-PDE-COV framework in designing a less “black-box” GNN model for real-world machine learning problem. \n\n[1] Deborah N Schoonhoven and others, Tau protein spreads through functionally connected neurons in Alzheimer’s disease: a combined MEG/PET study, Brain, 2023.\n\n[2] Steward, A., Biel, D., Luan, Y., Brendel, M., Dewenter, A., Roemer, S.N., Rubinski, A., Dichgans, M., Ewers, M. and Franzmeier, N. (2022), Brain network segregation attenuates tau spreading in Alzheimer’s disease. Alzheimer's Dement., 18: e061626.\n\nRegarding the purpose of using total variation, TV has demonstrated its effectiveness in mitigating the problem of excessive smoothing in image denoising and reconstruction. In this work, we tackle a similar challenge related to over-smoothing in graph data. Upon identifying that the root cause of over-smoothing in existing GNN models is linked to the $l_2$-norm graph smoothness term, we conjecture that, similarly to image processing, TV might be an effective solution for over-smoothing in GNN.\n\nRegarding the extra computational cost due to the min-max schema, we have summarized the comparison of running time with other GNN models (such as GCN, GAT, and GRAND) in Table 3 of the attached 1-page pdf file. "}, {"review_id": "r19sCXXMHw", "reviewer": "Reviewer_HWVs", "summary": "This paper focuses on devising a new inductive bias for cutting-edge graph application and present a general framework through the lens of variational analysis. To this end, the authors first introduce a new selective mechanism that can be easily integrated into existing GNNs and effectively address the trade-off between model depth and over-smoothing, and then devise a novel generative adversarial network to predict the spreading flows in the graph through a neural transport equation. Extensive experiments show that the proposed GNN models can achieve state-of-the-art performance on graph learning benchmarks such as Cora, Citeseer, and Pubmed.", "questions": "Please see the weak points.", "limitations": "Please see the weak points.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The perspective of the article is innovative, as it creatively utilizes heuristic problems from traditional physics to inspire the design of GNN structures. \n2. The description of the proposed GNN architecture is clear, and the experimental setup is well-defined. \n3. The experimental results validate the superiority of the method proposed by the author and demonstrate the rationality of the proposed theory.\n", "weaknesses": "1. The majority of the content in the article is based on the Euler-Lagrange (E-L) equation of the heat kernel. However, I don't believe that the detailed knowledge of the EL equation is familiar to every graph neural network researcher. Therefore, I think it is important to briefly introduce it when it first appears (Line 74) or mention it in the appendix. This is crucial for maintaining the readability and coherence of the article. In fact, it took me a lot of time to consult relevant materials for the subsequent introduction of the Euler-Lagrange (E-L) equation to LaGrangian Mechanics.\n2. The issue of over-smoothing in GNNs has been extensively studied since 2020, but the theoretical reasons behind this problem have not been conclusively determined [1, 2, 3]. In line 135-136, the authors claim that after connecting the GNN inductive bias to the function of the graph diffusion process, we can postulate that the root cause of over-smoothing is the isotropic regularization mechanism encoded by the ℓ2-norm. Treating this theory as a conclusion is certainly not a problem. However, due to the fact that many subsequent formula derivations are based on this theory, I have to consider whether this theory has been somewhat hasty and overclaimed. I think the authors should provide some deductions before presenting this theory to maintain logical rigor.\n3. In line 166, the authors claim that Eq. 1 is the dual formulation with min-max property for the TV distillation problem. It is well known that the dual problem is strictly mathematically defined. I do not fully understand how the duality problem here is derived. Please provide further explanation.\n4. In line 185-186, I am confused about how the recursive min-max solution for Eq. 1 is obtained by disentangling the building block in vanilla GNN into the feature representation learning and graph diffusion underling TV. I do not intuitively perceive the connection between the two. Please explain. \n\nreference:\n1. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. ICLR 2020\n2. Towards Deeper Graph Neural Networks. KDD 2020\n3. Beyond Low-frequency Information in Graph Convolutional Networks. AAAI 2021\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate this reviewer’s insightful comments. We provide answers to the four major questions below. \n\n1. $\\bf Q$: Lack of detailed knowledge of the EL equation for GNN researchers. \n\n    $\\bf A$: We apologize for this oversight. We will add more details and relevant work in the Supplementary. Specifically, we plan to open the background introduction by discussing the NeuroODE work [1], which offers a PDE-based implementation for ResNet. Additionally, we will provide a brief summary of the pioneering contributions [2-4] that establish connections between GNN and heat equations on graph data. Our work draws significant inspiration from these early studies.\n\n[1] Neural ordinary differential equations. NeurIPS 2018.\n\n[2] Grand: Graph neural diffusion. ICML 2021.\n\n[3] GRAND++: Graph neural diffusion with a source term. ICLR 2021.\n\n[4] PDE-GCN: Novel architectures for graph neural networks motivated by partial differential equations. NeurIPS 2021.\n\n2. $\\bf Q$: Should provide some deduction regarding the cause of over-smoothing to maintain logical rigor. \n\n    $\\bf A$: We appreciate this constructive comment. We will make it clear in the final version by the following means. \n\n$\\bf First$, we will introduce the GNN models in [1-3] (shown below) in the final version (placed in the last paragraph of section 2.1), as part of relevant works. Specifically, [1] showed an interesting engineering solution to alleviate the over-smoothing issue by trimming graph nodes/edges. [2] proposed to disentangle feature learning and propagation steps which is similar to our idea of adding the FC layer and DC layer (in Fig. 3 of the main manuscript). The approach in [3] presented an adaptive information aggregation approach by treating low and high-frequency information differently.  \n\n$\\bf Second$, we will follow the approach in [2] to explain the intuition of why deeper GNN fails using $l_2$-norm regularization term from the perspective of (1) t-SNE visualization of node feature representations as the number of GNN layers increases, (2) the evolution curve of $l_2$-norm, and (3) the evolution curve of the TV term, as the number of layers increases. Preliminary results on the Cora dataset are shown in Fig. 2-3 of the 1-page PDF. We will show the same results for other datasets (such as PubMed and Citeseer) in the Supplementary of the final version. It is clear that (1) the topological community structure by isotropic diffusion is much less consistent with the label distributions than TV-based adaptive diffusion (in Fig. 2), and (2) the trajectory of $l_2$-norm drops much faster than the counterpart curve by TV term (in Fig. 3), indicating that the effectiveness of TV-based GNN in alleviating the vanishing of graph gradients (effect of the over-smoothing issue).  \n\n$\\bf Third$, we will strengthen the rigor by linking the classic TV-based work (such as Merriman-Bence-Osher (MBO) scheme [4]) in image processing with our TV-based GNN solution for graph data learning. Despite the distinct mathematical frameworks used to define diffusion processes on grid coordinates and graph structures, they both exhibit a common cause for the over-smoothing issue, which can be attributed to the isotropic regularization mechanism encoded by the $l_2$-norm.\n\n[1] DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. ICLR 2020.\n\n[2] Towards Deeper Graph Neural Networks. KDD 2020.\n\n[3] Beyond Low-frequency Information in Graph Convolutional Networks. AAAI 2021.\n\n[4] An MBO scheme on graphs for classification and image processing. SIAM Journal on Imaging Sciences. 2013;6(4):1903-30.\n\n3. $\\bf Q$: How is the duality problem in Eq. 1 (line 166) derived?\n\n    $\\bf A$: We apologize for the confusion. Since the TV term is not differentiable at 0, there are two common approaches to circumvent this issue: (1) replace |.| by a function which behaves almost like the magnitude function while is differentiable, e.g., $|x|=(x^2)/\\sqrt{(x^2+\\epsilon^2)}$ where $\\epsilon$ is a small perturbation; (2) introduce a dual variable and rewrite the minimization problem into the min-max scheme (line 158-159) by introducing the dual variable $z$. We choose to employ the dual formulation (specifically the Lagrange dual form), as commonly used in TV-based image processing [1]. We will make it clear in the final version. \n\n[1] A simple primal–dual method for total variation image restoration. Journal of Visual Communication and Image Representation, 2016, 38, 814-823.\n\n4. $\\bf Q$: How the recursive min-max solution for Eq. 1 is obtained by disentangling the building block in vanilla GNN into the feature \n         representation learning and graph diffusion underlying TV?\n\n    \n $\\bf A$: In general, the min-max optimization consists of two alternating steps: (1) solving for $x$ (while $z$ is fixed) by minimizing the $l_2$-norm graph smoothness term (Eq. 2 in line 172) and (2) solving for $z$ (while $x$ is fixed) where we employ the majorization-minimization (MM) method (line 178-181). To solve for $x$, Following early work (such as GRAND) on linking PDE and GNN, Eq. 2 essentially describes a heat kernel diffusion process. Thus, the solution for $x$ can be achieved by the discrete GNN model. Meanwhile, the solution for $z$ boils down to a node-wise clip operation (Eq. 3 in line 180). Since the optimization of $x$ and $z$ have been decoupled into two alternating steps, we encapsulate them into a building block consisting of FC-layer (for solving $x$) and DC-layer (for solving $z$), and then cascade a collection of building blocks into a deep GNN model. We will make it clear in the final version. \n"}]

Author rebuttal:
We thank all reviewers for their thoughtful feedback. 

We are thrilled by the reviewers’ comments which they consider our paper as being original (Reviewer CRUA), creative (Reviewer HWVs), novel yet simple (Reviewer VF1D, sJUp, HWVs), clear (Reviewer sJUp, HWVs), great (Reviewer CRUA), very well  (Reviewer paGB) and well written (Reviewer VF1D). 

We are glad they found our study provided solid mathematical support  (Reviewer CRUA) and the rationality of the proposed theory (Reviewer HWVs), as well as our analyses are thorough (Reviewer paGB), well-defined (Reviewer HWVs) and the great and superior experimental results (Reviewers paGB, CRUA, sJUp) strongly support the claims. 

We agree with the Reviewer HWVs who recognizes the detailed knowledge of the EL equation is not familiar to every graph neural network researcher. We were constrained by space. Therefore, we will add more details and relevant work in the Supplementary of the final version.

One primary concern is limited evaluations of the experiments on comparison methods and datasets (Reviewer VF1D). We have added three comparison methods (Reviewer VF1D mentioned), six benchmark datasets of heterophilic graphs and two benchmark data of traffic flow. All the results are provided in the 1-page PDF.

$ \bf Table 1$ (for Reviewer VF1D): The performance of different data splitting schemas.

$ \bf Table 2$ (for Reviewer VF1D): Node classification results on heterophilic graphs (including six datasets) for four methods. 

$ \bf Table 3$ (for Reviewers VF1D, CRUA, paGB, sJUp): The running time on different methods.

$ \bf Fig 1$ (for Reviewers VF1D): Traffic flow prediction accuracy in terms of mean absolute error (MAE) in PEMS-BAY and METR-LA benchmark datasets. 

$ \bf Fig 2$ (for Reviewers HWVs): The t-SNE visualization of node feature representations.

$ \bf Fig 3$ (for Reviewers HWVs): The evolution of $l_2$-norm graph smoothness term and $l_1$-norm TV term as the number of GNN layers increases. 

We have answered all the specific questions for every reviewer as below and will incorporate all feedback in the final version.


Meta-review: Most reviewers support the paper. So I recommend acceptance as a poster.
Decision: Accept (poster)