$\omega$GNNs: Deep Graph Neural Networks Enhanced by Multiple Propagation Operators
Authors: Moshe Eliasof
Lars Ruthotto
Eran Treister
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Deep Learning
Graph Propagation Operators
Over-Smoothing

Abstract: Graph Neural Networks (GNNs) are limited in their propagation operators. These operators often contain non-negative elements only and are shared across channels and layers, limiting the expressiveness of GNNs. Moreover, some GNNs suffer from over-smoothing, limiting their depth. On the other hand, Convolutional Neural Networks (CNNs) can learn diverse propagation filters, and phenomena like over-smoothing are typically not apparent in CNNs.
In this paper, we bridge this gap by incorporating trainable channel-wise weighting factors $\omega$ to learn and mix multiple smoothing and sharpening propagation operators at each layer. Our generic method is called $\omega$GNN, and we study two variants: $\omega$GCN and $\omega$GAT.
For $\omega$GCN, we theoretically analyse its behaviour and the impact of $\omega$ on the obtained node features. Our experiments confirm these findings, demonstrating and explaining how both variants do not over-smooth.
Additionally, we experiment with 15 real-world datasets on node- and graph-classification tasks, where our $\omega$GCN and $\omega$GAT perform better or on par with state-of-the-art methods. 

Under review as a conference paper at ICLR 2023
wGNNs: DEEP GRAPH NEURAL NETWORKS EN- HANCED BY MULTIPLE PROPAGATION OPERATORS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) are limited in their propagation operators. These operators often contain non-negative elements only and are shared across channels and layers, limiting the expressiveness of GNNs. Morcover, some GNNs suffer from over-smoothing, limiting their depth. On the other hand, Convolutional Neural Networks (CNNs) can learn diverse propagation filters, and phenomena like over-smoothing are typically not apparent in CNNs. In this paper, we bridge this gap by incorporating trainable channel-wise weighting factors to learn and mix multiple smoothing and sharpening propagation operators at each layer. Our generic method is called wGNN, and we study two variants: wGCN and wGAT. For wGCN, we theoretically analyse its behaviour and the impact of w on the obtained node features. Our experiments confirm these findings, demonstrating and explaining how both variants do not over-smooth. Additionally, we experiment with 15 real-world datasets on node- and graph-classificttion tasks, where our wGCN and wGAT perform better or par with state-of-the-at methods.
INTRODUCTION
Graph Neural Networks (GNNs) are useful for wide array of fields, from computer vision and graphics (Monti et al. 2017: Wang et al. 2018 Eliasof & Treister 2020) and social network analysis (Kipf & Welling, 2016 Defferrard et al. 2016) to bio-informaties (Hamilton al. 2017|/umpe al.] 1021). Most GNNs are defined by applications of propagation and point-wise operators, where
the former is often fixed and based on the graph Laplacian (e.g., GCN (Kipf & Welling 2016)), or is
defined by attention mechanism (Veličković et al. 2018 Kim & Oh 2021 Brody al. 2022).
Most recent GNNs follow a general structure that involves two main ingredients - the propagation operator, denoted by S(D), and convolution denoted by K(), as follows
f(++1) (SS(ppp K
(1)
where f()) denotes the feature tensor at the I-th layer. The main limitation of the above formulation
that the propagation operators in most common architectures constrained be non-negative
This leads to two drawbacks. First, this limits the expressiveness of GNNs. For example, the gradient of given graph node features can not be expressed by non-negative operator, while a mixed-sign operator as in our proposed method can (see demonstrations in Fig. [ and Fig. 2 Moreover, the utilization of strictly non-negative propagation operators yields smoothing process, that may lead GNNs to suffer from wer-smoothing. That is, the phenomenon where node features become indistinguishable from one and other as more GNN layers are stacked causing severe performance
degradation in deep GNNs (Li et al. 2018 Wu et al. 2019 Wang et al. 2019).
Both of the drawbacks mentioned above are not evident in Convolutional Neural Networks (CNNs), which can be interpreted as structured versions of GNNs (i.e., GNNs operating on a regular grid). The structured convolutions in CNNs allow to learn diverse propagation operators, and in particular it is known that mixed-sign kernels like sharpening filters are useful feature extractors in CNNs (Krizhevsky et al. 2012), and such operators cannot be obtained by non-negative (smoothing) kernels only. In the context of GNNs, Eliasof al. (2022) have shown the significance and benefit of employing mixed-sign propagation operators in GNNs as well. In addition, the over- over-smoothing phenomenon is typically not evident in standard CNNs where the propagation (spatial) filters

---

Under review as a conference paper at ICLR 2023
0.5.5 6m110
wm1.5
(a) Input graph.
(b) Node
(c) GCN (d) WGCN
gradient. estimation, estimation.
Figure 1: The impulse response of wGCN's propaga- tion operator for different w values. For 0.5, 1.0 non-negann non-negative values are obtained, while for 1.5 we see mixed-sign values. The dashed node starts from a feature of and the rest with O.
Figure The expressiveness of wGNNs. Our wGCN can express the gradient of the node features while GCN cannot.
learnt, and usually adding more layers improves accuracy (He et al. 2016). The discussion above demonstrates two gaps between CNNs and GNNs that we seek to bridge in this work.
third gap between GNNs and CNNs the ability of the latter to learn and mix multiple propagation operators. In the scope of separable convolutions, CNNs typically learn a distinct kernel per channel. known as depth-wise convolution (Sandler et al. 2018) key element modern CNNs TTan &
Le 2019: Liu al., 2022). On the contrary. the propagation operator ((!) from equation acts on all channels (Chen et al., 2020b Veličković et al., 2018), and in some cases on all layers (Kipf & Welling 2016 Wu et al. 2019). We note that one exception the multi-head GAT (Veličković et al., 2018) where several attention heads are learnt per layer. However, this approach typically employs only a few heads due to the high computational cost and still limited by learning non-negative propagation operators only.
In this paper we propose an effective modification to GNNs to directly address the three shortcomings of GNNs discussed above, by introducing parameter control the contribution and type of the propagation operator. We call our general approach WGNN, and utilize GCN (Kipf & Welling 2016) and GAT (Veličković et al., 2018) to construct two variants, wGCN and wAAT We theoretically prove and empirically demonstrate that our WGNN can prevent over-smoothing. Secondly, we show yield propagation operators with mixed signs, ranging from
that by learning w, wGNNS smoothing to sharpening operators which do not exist in current GNNs (see Fig. [ for an illustration). This approach enhances the expressiveness of the network, as demonstrated in Fig. 2 and to the best of our knowledge, was not considered in the GNNs mentioned above that employ non-negative propagation operators only. Lastly, we propose and demonstrate that by learning different w per layer and channel, similarly to a depth-wise convolution in CNNs, our wGNNs obtains state-of state-of-the-an -hetttrrrt accuracy.
Our contributions are summarized as follows:
We propose GNN, effective and computationally light modification GNNs of a common and generic structure, that directly avoids over-smoothing and enhances the expressiveness of GNNs. Our method is demonstrated by wGCN and wGAT.
A theoretical analysis and experimental validation of the behaviour of wGNN are provided to expose its improved expressiveness compared to standard propagation operators in GNNs.
We propose to learn multiple propagation operators by learning w per layer and per channel and mixing them using a x 1 convolution to enhance the performance GNNs.
Our experiments with 15 real-world datasets on numerous applications and settings, from semi- and fully-supervised node classification graph classification show that our wGCN and wGAT read on par or better performance than current state-of- of-the-art methods.
2
METHOD
We start by providing the notations that will be used throughout this paper, and displaying our general GGNN in Sec. 2.1] Then we consider two popular GNNs that adhere to the structure presented in equation [ namely GCN and GAT. We formulate and analyse the behaviour their two counterparts wGCN and GAT in Sec. 2.2 and 2.3 respectively.
2

---

Under review as a conference paper at ICLR 2023
Notations. Assume we are given an undirected graph defined by the set 9 = (V, E) where V is set of n vertices and is a set of m edges. Let us denote by f. E R' the feature vector of the i-th node of 9 with channels. Also, denote the adjacency matrix A, where Aij (i,j) E & and O otherwise. We also define the diagonal degree matrix D where D is the degree of the i-th node. The graph Laplacian is given by L D A. Let us also denote the adjacency and degree matrices with added self-loops by A and D respectively. Lastly, we denote the symmetrically normalized graph Laplacian by L sym D : LD where L = D A.
if there exists an edge
2.1 wGNNs
The goal of wGNNs is to utilize learnable mixed-sign propagation operators that control smoothing and sharpening to enrich GNNs expressiveness. Below, we describe how the learnt w influences the obtained operator and how to learn and mix multiple operators for enhanced expressiveness.
Learning propagation weight w. To address the expressiveness and over-smoothing issues, we suggest general form given an arbitrary non-negative and normalized (e.g., such that its row sums equal to 1) propagation operator (()), Our general wGNN is then given by
p(++1) ((I- (I (-5")) FOK())
where (1) is a scalar that is learnt per layer, and in the next paragraph we offer a more elaborated version with a parameter w per layer and channel. The introduction of ( allows our GGNN layer to behave in three-fold manner. When w(()) < 1, a smoothing process is obtained Note, that 2 reduces the standard GNN dynamics from equation In case w()) 2 reduces to a x 1 convolution followed by non-linear activation function, and does not propagate neighbouring node features. On the other hand, (())) > 1, we obtain an operator with negative signs the diagonal but positive on the off-diagonal entries, inducing sharpening operator. An example of various (1()) values and their impulse response is given in Fig. Thus, a learnable (()) allows to learn new family of operators, namely sharpening operators, that are not achieved by methods like GCN and GAT. To demonstrate the importance of sharpening operators, we consider a synthetic task of node gradient feature regression, given graph and input node features(sec Appendix for more details). As depicted in Fig. using non-negative operator as in GCN cannot accurately express the gradient operator output, while our wGCN estimates the gradient output with a machine precision accuracy. Also, the benefit of employing both smoothing and sharpening operators is reflected in the obtained accuracy of our method on real- real-world datasets in Sec.
for () 1, equation
equation
Multiple propagation operators. To learn multiple propagation operators, we extend equation 2 from a channels-shane weight to channel wise weights by learning a vector (3() e as follows
(1+1)) ((I Pige I (I- (()
where Dgze is an operator that scales each channel j with a different 3 As discussed in Sec. this procedure vields propagation operator per-channel, which is similar depth-wise convolutions in CNNs (Howard al. 2017; Sandler et al. 20188). Thus, the extension vector (((4) helps to further bridge the gap between GNNs and CNNs.
We note that using this approach, our GNNN is suitable many existing GNNs, and in particular to those which act as separable convolution, as described in equation [ In what follows, we present and analyse two variants based on GCN and GAT, called GCCN and rGAT, respectively.
2.2 wGCN
GCNs are a class of GNNs that employ a pre-determined propagation operator P = D- that stems from the graph Laplacian. For instance, GCN GCN/ & Welling (2016) is given by:
p((+)) (Pp(((())
'The of the value 1 in this discussion corresponds its diagonal, normalized have row sums of 1. Other normalizations may yield other constants. Also, flips the sign of the i-th diagonal entry.
non-negative operator (1)) with zeros on
0 < s 1, then setting with) 1-8!!
3

---

Under review as a conference paper at ICLR 2023
w
0.001 w 0.0001
Wearnt
E(TO)) /E(ro)
0.5
0.5
148
16
32
64
14
16
32
64
Layer
Layer
(a) wGCN.
(b) wGAT.
Figure Node features energy at I-th layer relative the initial node embedding energy on Cora. Both WGCN and wGAT control the respective energies from equation O and equation to avoid over-smoothing while the baselines with w = 1 reduce the energies to 0 and svooth.
that is, by setting (()) P in equation 1 Other methods like SGC (Wu et al. 2019). GCNII (Chn et al. 2020b) and EGNN /houu et al. 2021) also rely on P as propagation operator.
The operator a fixed non-negative smoothing operator, hence, repeated applications of equation lead to the over-smoothing phenomenon, where the feature maps converge single eigenvector as shown by Wu et al. (2019); Wang et al. (201). Moreover, P is pre-determined, and solely depends on the graph connectivity, disregarding the node features, which may harm performance.
By baking our proposed wGNN with a learnable weight, denoted by w()) E R into GCN we obtain the following propagation scheme, named WGCN:
p(++1) =o ((I-w() (I-P)) ( pO)
(5)
We now present theoretical analyses of our wGCN and reason about its non over-smoothing property. We first define the node features Dirichlet energy the 1-th layer, as in Zhou et al. (2021):
) iEV
(6)
V(++))
V1+d,
Fig. 3a demonstrates how the Dirichlet energy F(((W) decays when w is constant, and to fixed positive value when learnt. Next, we provide a theorem that characterizes the behaviour of and how prevents over-smoothing. To this end we denote the propagation operator of WGCN
from equation by
P.. -.-I-w = I- w (I- (I-D-AAD -
-
where the latter equality is shown in Appendix A In essence, show that repeatedly applying the operator P is equivalent applying gradient descent steps for minimizing equation 6 with learning rate w. We build on the observation that smoothing is beneficial (Gasteiger et al. 2019
Chamberlain al. (221)) and assume that there exists an optimal energy at the last layer that satisfies >> 0. shared across all layers, then taking L to infinity will lead w to zero. Thus, our WGCN will not over-smooth, as
0 Eopt (f E(F()). ). Then, we show that if we learn single (1)
the energy at the last layer E(((4) can reach to Eopr Later, in Corollary
we generalize
this result for per-layer (!),, and empirically validate both results in Sec. 4.5 The proofs for the Theorem and Corollary below are given in Appendix A.
Theorem 1. Consider L applications of equation
7 i.e., p(L) = (P with a shared parameter
( = w that is used in all the layers. Also assume that there is some optimal Dirichlet energy of the final feature map that satisfies 0 (f()((( < E))())). Then, at the limit, more layers are added, w converges to a up to first order accuracy, where L is the number of layers and i is a value that is independent of T. and leads Foopt-
4

---

Under review as a conference paper at ICLR 2023
Corollary 1.1. Allowing variable w 0 each layer in Theorem 1 yields Σ to first order accuracy.
1-1 1== w
8 up
Next, we dwell on the second mechanism in which wGCN prevents over-smoothing We analyse the cigenvectors of Paw showing that different choices of yield different leading cigenvectors that alter the behaviour of the propagation operator (i.e. smoothing and sharpening processes). This result is useful because changing the leading cigenvector prevents the gravitation towards a specific eigenvector, which causes the over-smoothing to occur (Wu et al., 2019; Oono & Suzuki 2020).
Theorem 2. Assume that the graph is connected. Then, there exists some wp 2 where for all 0 Wo. the operator P., in equation is smoothing and the leading eigenvector is D For > wo or w < O, the leading eigenvector changes.
The proof for the theorem is given in Appendix A
GCNN with multiple propagation operators. To further increase the expressiveness of our wGCN we extend (1()) E R ,ه E R and learn propagation operator per channel, at each layer. To this end, we modify equation to the following formulation
p(++1)
(( Lgz (I-P))
K
(8)
As show in Sec. 4.5 learning propagation operator per channel is beneficial to improve accuracy.
2.3 wGAT
The seminal GAT (Veličković et al. 2018) learns a non-negative edge-weight as follows
exp (LeakyReLU (0T ||
0 EpEN, exp (TeakyRe..U(a"" (wor.") | (w
where a 2c and W Rexe are trainable parameters and || denotes channel concatena-
tion. Here, GAT is obtained by defining the propagation operator (() in equation as (!!) kj
= Oij-
To avoid repeated equations, we skip the per-layer w formulation (as in equation 2 and directly define the per-channel wGAT as follows
((++) =0 ( (I- p()) (()))
(10)
The introduction of Qgw yields a learnable propagation operator per layer and channel. We note that it is also possible to obtain multiple propagation operators from GAT by using a multi-head attention. However, we distinguish our proposition from GAT in a 2-fold fashion. First, our propagation operators belong to a broader family that includes smoothing and sharpening operators as opposed to smoothing-only due to the SoftMax normalization in GAT. Secondly, our method requires less computational overhead when adding more propagation operators, as our wGAT requires a scalar per operator, while GAT doubles the number of channels to obtain more attention-heads Also, utilizing multi-head GAT can still lead to wwoossmot as all the heads induce a non-negative operator.
To study the behaviour of our WAT, we inspect its node features energy compared to GAT. To this end, we define the GAT energy as
EGAT (P())
Σ - TEV JEN;
1
(11)
This modification of the Dirichlet energy from equation 6 is required because in GAT (Veličkovic
et al.
2018) the leading eigenvector of the propagation operator (()) is the constant vector 1 as shown by Chen al. 2020a). unlike the vector D 1 in the symmetric normalized P from GCN (Kipf &
Welling 2016 where the Dirichlet energy natural to consider (Pei et al. 2020
We present the energy of 64 layer GAT trained on the Cora dataset in Fig. 3b is evident that the accuracy degradation of a deep GAT reported by Zhao Akoglu (020 is in congruence with the decaying energy in equation [I]] while our wGAT does not experience decaying energy accuray degradation as more layers are added, as can be seen in Tab. [ To further validate our findings, we repeat this experiment in Appendix D on additional datasets and reach to the same conclusion.
5

---

Under review as a conference paper at ICLR 2023
2.4 COMPUTATIONAL COSTS
Our GGNN approach is general and can be applied to any GNN that conforms to the structure of equation I and can be modified into equation 3 The additional parameters compared to the bascline GNN are the added 92z0) IR parameters each layer, yielding a relatively low computational overhead. For example, in GCN (Kipf & Welling (016) there are e x c trainable parameters requiring c x c n multiplications due to the 1 x 1 convolution K(", In our wGCN, we will have e x c + c parameters and (c + 1) X n multiplications. That is in addition to applying the propagation operators S which are identical for both methods. A similar analysis holds for GAT. To validate the actual complexity of our method, we present the training and inference times for wGCN and wGAT in Appendix [ We see negligible addition to the runtimes compared to the baselines, the return of better performance.
3 OTHER RELATED WORK
Over-smoothing in GNNs. The over-smoothing phenomenon was identified by Li et al. (2018). and was profoundly studied in recent years. Various methods stemming from different approaches were proposed. For example, methods like DropEdge (Rong et al.] (020)) PairNorm (Zhao & Akoglu 2020), and EGNN (Zhou et al. 2021) propose augmentation, normalization and energy-based penalty methods alleviate over-smoothing, respectively. Other methods like Min al. (2020) propose to augment GCN with geometric scattering transforms and residual convolutions, and GCNII (Chen al. 2020b) present a spectral analysis of the smoothing property of GCN (Kipf & Welling 2016) and propose adding an initial identity residual connection and decay of the weights of deeper layers, which are also used in EGNN (Zhou et al. 2021).
Graph Neural Diffusion. The view of GNNs as diffusion process has gained popularity in recent years. Methods like APPNP (Kliepera al., 2019) propose to use a personalized PageRank (Page)
et al., 1999) algorithm to determine the diffusion of features, and GDC (Gasteiger et al. 2019)
imposes constraints on the ChebNet (Deferrard et al. 2016) architecture to obtain diffusion kernels,
showing accuracy improvement. Other works like GRAND Chamberlain et al. (021).
FCG
(Belbute-Peres et al. 2020), PDE-GCN (Eliasof ct al. 2021 and GRAND++ (Thorpe et al. 2022) propose view GNN layers as time steps the integration process of ODEs and PDES that arise from a non-linear heat equation, allowing to control the diffusion (smoothing) in the network to prevent over-smoothing. In addition, some GNNs (Eliasof et al. 2021 Rusch al. 2022) propose a mixture between diffusion and oscillatory processes to avoid over-smoothing by frequency preservation of the features.
Mixed-sign operators in GNNs, The importance of mixed-sign operators in GNNs was discussed Eliasof et al. (2022). where k-hop filters and stochastic path sampling mechanisms are utilized. However, such a method requires significantly more computational resources than a standard GNN like Kipf Welling (2066): Veličković al. (2018) due to the path sampling strategy and larger filters of 5-hop required for optimal accuracy. However, our GNNNs perform 1-hop convolutions and as we show Appendix obtain state-of-the-an results without significant added computational
costs.
4 EXPERIMENTS
We demonstrate our wGCN and wGAT on node classification, inductive learning and graph classifica- tion tasks. Additionally, we conduct an ablation study of the different configurations of our method and experimentally verify the theorems from Sec. 2 A description of the network architectures is given in Appendix E We use the Adam (Kingma & Ba 2014) optimizer in all experiments, and perform grid search to determine the hyper-parameters reported in Appendix [F The objective function in all experiments is the cross-entropy loss, besides inductive learning on PPT (Hamilton al. 2017) where we use the binary cross-entropy loss. Our code is implemented with Py Torch (Paszke et al. 2019) and Py ffrch-Geommtric (Fey & Lenssen 2019) and trained on Nvidia Titan RTX GPU.
We show that for all the considered tasks and datasets, whose statistics are provided Appendix our GGNN and GAT are either better or on par with other sfateoof-the-ar models.

---

Under review as a conference paper at ICLR 2023
Table Summary of semi-supervised node classification accuracy (%)
Method
GCN
GAT
APPNP
GCNII
GRAND
superGAT
EGNN
wGCN (Ours)
wGAT (Ours)
Cora
81.1
83.1
83.3
85.5
84.7
84.3
85.7
85.9
84.8
Citeseer
70.8
70.8
71.8
73.4
73.6
72.6
73.3
74.0
Pubmed
79.0
78.5
80.1
80.3
71.0
81.7
80.1
81.1
81.8
Table Semi-supervised node classification accuracy (%).
indicates not available results.
Dataset
Cora
Citeseer
Pubmed
Layers
16
16
32
GCN
81.1
80.4
69.5
64.9
60.3
28.7
70.8
67.6
30.2
18.3
25.0
20.0
79.0
76.5
61.2
40,9
22.4
35.3
GCN (Drop)
82.8
82.0
75.8
75.7
62.5
49.5
72.3
70.6
61.4
57.2
41.6
34,4
79.6
79.4
78.1
78.5
77.0
61.5
JKNet
80.2
80.7
80.2
81.1
71.5
68.7
67.7
69.8
68.2
63.4
78.0
78.1
72.6
72.4
74.5
JKNet (Drop)
83.3
82.6
83.0
82.5
72.6
71.8
72.6
70.8
72.2
78.7
78.7
79.7
79.2
78.9
Ineep
77.6
76.5
81.7
81.7
68.4
70,2
68.0
67.5
74.9
Ineep (Drop)
82.9
82.5
83.1
83.1
83.5
72.7
71.4
72.5
72.6
71.0
79.5
78.6
79.0
GCNII
82.2
82.6
84.2
84.6
85.4
85.5
68.2
68.8
70.6
72.9
73.4
73.4
78.2
78.8
79.3
80.2
79.8
79.7
GCNII
80.2
82.3
82.8
83.5
84.9
85.3
66.1
66.7
70.6
72.0
73.2
73.1
77.7
78.2
78.8
80.3
79.8
80.1
PDE-GCND
82.0
83.6
84.0
84.2
84.3
84.3
74.6
75.0
75.2
75.5
75.6
75.5
79.3
80.6
80.1
80.4 80.2
80.3
EGNN
83.2
85.4
85.7
79.2
80.0
80.1
wGCN (Ours)
82,6
83.8
84,2
84.4
85.5
85.9
71.3
71.6
72.1
72.4
73.3
73.3
79.7
80.2
80.1
80.5
80.8
81.1
WGAT (Ours)
83.4
83.7
84.0
84.3
84.4
84.8
72.5
73.1
73.3
73.5
73.9
74.0
80.3
81.0
81.2
81.3
81.5
81.8
4.1 SEMI-SUPERVISED NODE CLASSIFICATION
We employ the Cora, Citeseer and Pubmed (Sen et al., 2008) datasets using the standard train- ing/validationntestinn split by Yang al. (2016), with 20 nodes per class for training, 500 validation nodes and 1, 1,000 testing nodes. We follow the training and evaluation scheme of Chen et al. (2020b) and compare with models like GCN, GAT, superGAT (Kim & Oh 202T). Inception (Szegedy et 2017). APPNP (Klicpera et al. (1,,2019), JKNer Xu et al. (0018). DropEdge (Rong et al. 2020). GCNIT
(Chnn et al. 2020b), GRAND [Chamberlain et al. 202 PDE-GCN (Eliasof et al. 2021) and EGNN better
par performance with other state-of-the oftt-of-the-rt methods. Additionally, we report the accuracy per number of layers, from
(Zhou et al. 2021). We summarize the results in Tab. where
2 to 64 In Tab. [ where it is evident that wGCN and wGAT do not over-smooth. To ensure the robustness of our method, we also experiment with 100 random splits in Appendix where our wGCN and wGAT continue to perform better par with state-of-the-ar methods.
4.2 FULLY- SULLY-SUPERVISED NODE CLASSIFICATION
To further validate the efficacy of our method on fully-supervised node classification, both on homophilic and heterophilic datasets as defined Pei al. (2020). Specifically, examine our wGCN and wGAT on Cora, Citeseer, Pubmed, Chameleon (Rozemberezki et al. 2021). Cornell, Texas and Wisconsin using the identical vrain//vlidation//ess splits of 48%. 32%, 20%, respectively, and report the average performance over 10 random splits from Pei et al. (202). We compare our performance with, GCN, GAT, Geom-GCN, APPNP, JKNet, Inception, GCNII, PDE-GCN and others, as presented in Tab. 3 Additionally, we evaluate our wCCN and wGAT on the Actor (Rozemberezki al.) 2021 and Ogbn-arxiv (Hu et al., (220)) datasets, as reported Tab. 4 We see an accuracy improvement across all benchmarks compared to the considered methods. In Appendix J we present and discuss the learnt w for homophilic and heterophilic datasets.
4.3 INDUCTIVE LEARNING
We employ the PPI dataset (Hamilton et al. 2017) for the inductive learning task. We use 8 layer wGCN and GAT, with learning rate of 0.001, dropout of 0.2 and no weight-decay As a comparison consider several methods and report the micro-averaged F1 score in in Tab. Our wGCN achieves
7

---

Under review as a conference paper at ICLR 2023
Table 3: Fully-supervised node classification accuracy (%). (L) denotes the number of layers.
Method
Cora
Cite.
Pubm.
Chum.
Corn.
Texus
Wisc.
GCN
Kipf Welling
2016
85.77
73.68
88.13
28. 18
52.70
52.16
45.88
GAT Vellckovic cl al.
2018
86.37
74.32
87.62
42.93
54.32
58.38
49.41
GioomGG..N (Pen el 20200
85.27
77.99
90.05
60.90
61181
67.57
64.12
APPNP Klicpera
87.87
76.53
89.40
54.30
73.51
65.41
69.02
H2GCN Zhu et 2020
87.87
77.11
89,49
60.11
82.70
84.86
87.65
SD (Bodhar el al.
2022
87.30
74.14
89.49
68.
86.49
85.95
89.41
JKNel [Xu al 2018
85.25
75.85 (8)
(64)
60.07 (32)
57.30
56.49 (32)
48.82 (8)
JKNet (Drop) [Rong
2020
(16)
75.96 (8)
89.45 (64)
62.08 (32)
61.08
$7.30 (32)
50.59 (8)
Ineep (Drop) (Kong ot a..
2020
86.86 (8)
76.83 (8)
89.18 (4)
61.71 (8)
61.62 (16)
57.84 (8)
50.20 (8)
GCNII (Chen cl 20200
88.49 (64)
77.08 (64)
89,57 (64)
60.61 (8)
74.86 (16)
69.46 (32)
74.12 (16)
GCNII Chinn 20206
88.01 (64)
77.13 (64)
90.30 (64)
62.48
76.49
77.84
81.57 (16)
PDE-GCNyf Ehasol et
2021
88.60 (16)
78.48 (32)
89.93 (16)
66.01 (16)
89.73 (64)
93.24 (32)
91.76 (16)
wGCN (Ours)
89.30 (16)
77.88 (16)
90.45 (8)
70.02 (16)
91.35 (32)
94.05 (32)
92.35 (32)
wGAT (Ours)
89.25 (8)
78.01 (16)
90.65 (8)
72.23 (8)
91.62 (16)
94.59 (16)
92.94 (16)
Table 4: Fully-supervised node classification accuracy
Table 5: Inductive learning PPI dataset. Results are reported micro-averagee Fl score.
(%).
Method
Actor
Ogbn-arxiv
Method
Micro-averaged FI
GCN
Kipf & Welling
2016
26.86
71.74
GCN Kipf & Welling 2016
60.73
GAT
Velckovie et 2018
28.45
71.59
GraphSAGE Hamilton et al. 2017
61.20
GATvZ Brody el ar. 2022
71.87
VR-GCN (Chen et al 2018
97.80
APPNP
Kheeper el al 2019
31.26
71.82
GaAN (Zhang el al. 2018a
98.71
Geom-GU
(Pei of al. 2020
31.63
GAT (Veickovic el al. 2018
97.30
JKNNtt [Xu
2018
29.81
72.19
JKNer (Xu 2018
97.60
SGC Wu
30.98
69.20
GenicPäth (Liu
2018
98.50
GCNI Chen
Z0206
32.87
72.74
Cluster-GCN (Chiang
2019
99.36
EGNN Zilou er
4121
72.70
GCNII" (Chn et al. 2020h
99.58
GRAND Chamberlai of al.
2021
72.23
PDE-GCNg (Eltaso et al.
2021
99.18
wGCN (Ours)
38.94
73.02
wGCN (Ours)
99.60
wGAT (Ours)
38.64
72.76
wGAT (Ours)
99.48
a score of 99.60, which is significantly superior than its baseline GCN, and also performs better than methods like GAT, JKNet, GeniePath, Cluster-GCN and PDE-GCN.
4.4 GRAPH CLASSIFICATION
Previous experiments considered the node-classification task. To further demonstrate the efficacy of our WGNNs experiment with graph classification TUDatasets (Morris et al. 2020). Here, we follow the same experimental settings from Xu et al. (2019), , and report the fold cross-validation performance MUTAG, PTC, PROTEINS. NCII and NC1109 datasets. The aaper-parameters determined by grid search, as in Xu et al. (219) and are reported in Appendix E. We compare our wGCN and GAAT with recent and popular methods like GIN (Xu et al. 2019), DGCNN (Zhang jt al. 2018b), IGN (Maron et 2018). GSN (Bouritsas et al., 2022). SIN (Bodnar et al. (021b)) CIN (Bodnar et al. 2021a) and others. We also compare with methods that stem from "classical' graph algorithms like RWK (Gärtner et al. (2003) and WL Kernel (Shervashidze et al. (001T). All
the results summarized in Tab. 66) with evident improvement similar results current deep learning as well as classical methods, highlighting the efficacy of our approach.
4.5 ABLATION STUDY
In this section we study the different components and configurations of our GGNN. We start by allowing global (single) w to be learnt throughout all the layers-tth this architecture is dubbed as wGCNg. We validate that this simple variant does not over-smooth, depicted in Tab. 7 The table also shows GCNPL. that includes single parameter (") per layer, and wGCN shown in the results earlier that has ( i.e., parameter per layer and channel, which yields further accuracy improvements.
8

---

Under review as a conference paper at ICLR 2023
Table 6: Graph classification accuracy (%) on TUDatasets (Moris al. 2020
Method
MUTAG
PTC
PROTEINS
NCI1
NCT109
RWK (Gärtner el al.
2003
79.2 +: 2.1
55.9 0.3
59.6
GK
Shervashidze el al. 2009
81.4 +
4.5
71.4 0.3
62.5 0.3
0.34-0.3
PK
NNumaan et al. 2016
76.0
2.4
73.72
82.54 0.5
WL Kernel (Shervashidze et al.
2011
5.7
4.39+
7.10+
86.0+ 1.8
DGCNN (hhang et al. 2018b
85.811.88
58.6122.5
75.5+1..9
74.410.5
IGN (Maron al. 2018
83.9+13.0
58.5+6699
76.6+5.55
74.3+2277
72.8 1.5
PPGNS Maron of al.
2019
90.6+8.7
66.2+6.6
77.2+4.7
83.2+1.1
82.2 1.4
NATURAL GN (d Taan et al.
2020
89.411.6
66.811177
71.7-11.0
82,411.3
GSN (Bouritsas
2022
92.247.5
68.217.2
76.6+5.0
83.5+2.0
SIN [oddnr al.
76.4
82.7:22.1
Bodnar et al.
2021a
92.743..6
68.2413.5
77.0+3.4
83.6+3.11
84.0=3.1
GIN Xu et al. 2019
89.415.6
64.6:17.0
76,24228
82.7+1.7
82.2=1.6
GIN +
ID You ct al
2021
90.4+5.4
67.2+-4.3
75.4+22.7
82.6+1.6
82.1+1.5
DROP (Rnn et al. 2020
91.015.7
64.512.6
73.5
82.012.6
8.
GCONV Morris al. 2019
90.514.6
64.9110.4
73.916.1
82.412.7
81.7=10
RNI (Abboud et al. 2020
91.0++4.9
64.3+6..1
73.3+3.3
82.1+1.7
81.7-1.0
GCN (Ours)
94.6 4.1
73.8 4.3
80.2 1: 2.5
84.1 +: 1.2
84.5 = 1.8
w GAT (Ours)
95.2 + 3.7
75.8 + 3.5
80.7 + 3.7
84.4 + 1.7
83.6 1.2
3
Coca
Cineseer
Pobcsed
Table 7: Accuracy (%) of variants of wGCN on semi-
WGCNg
supervised classification.
2.5
Layers
Data.
Variant
8
16
32
Cora
GGCNg
83.4
84.3
84.2
84.1
84.3
84.4
GCNNg
83.0
83.6
84.0
84.2
84.5
84.8
wGCN
82.6
83.8
84.2
84.4
85.5
85.9
Cite.
GGCNa
71.3
71.7
72.0
xGCN
71.1
71.3
71.5
71.8
72.4
72.6
1.5
wGCN
71.3
71.6
72.1
72.4
73.3
73.3
2
4
8
16
32
64
Pub:
GGCNg
79.8
80.4
80.5
80.4
80.2
80.3
Layers
wGCNR.
79.8
80.0
80.2
80.4
80.5
80.8
wGCN
79.7
80.2
80.1
80.5
80.8
81.1
Figure 4: The summation of weighting factors @ vs. the number layers for wGCNg g and wGCNpL
In addition, we empirically verify our theoretical results from Sec. 2 Fig. where we show that
a Lw and / = LL-1 w(() is similar for varying number of layers I. as Theorem and Corollary
suggest. For completeness, we also perform the ablation study on GAA Appendix H
SUMMARY
In this work we proposed an effective and computationally efficient modification that applies to large family of GNNs that carry the form of a separable propagation and 1 x convolutions, and in particular we demonstrate its efficacy on the popular GCN and GAT architectures. We provide theorems that reason about the smoothing nature of GCN and through the lens of operator analysis suggest to learn weighting factors learn and mix smoothing and sharpening propagation operators. Through extensive set of experiments graph classification, as well as an ablation study that validates our theoretical findings, we demonstrate the contribution of our GNN, reading on par achieving sate-of-the-art performance.
numerous datasets, ranging from node classification to

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.0117 2020.
Filipe de Avila Belbute-Peree Peres, Thomas D. Economon, and J. Zico Kolter. Combining Differentiable PDE Solvers and Graph Neural Networks for Fluid Flow Prediction. In International Conference on Machine Learning (ICML), 2020.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 14:2625-26440 2021a.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang. Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026-1037, PMLR, 2021b.
Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. arXiv preprint arXiv:2202.04573 2022.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations, 2022. URL httpp:://pperreii.t.. net/
forum? 7=x msx
Benjamin Paul Chamberlain, James Rowbottom, Maria Gorinova, Stefan Webb, Emanuele Rossi, and Michael M Bronstein. Grand: Graph neural diffusion. arXiv preprint arXiv:2106. 10934, 2021.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Artificial Intelligence, 34:3438-3445, 04 2020a. doi: 1...16//aai..34444...7.7...
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 950. PMLR, 10-15 Jul 2018. URL httt:://proceeeeee
mlr.. www.mmrrr..s....... perress/ve v
Shten8p.htmi. html
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1725-1773 1735. PMLR, 13-18 Jul 2020b. URL http:://pppp/e/cc
ngs mlr
press/v www www./0ee..... htmml
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2019. URL htttt::t/aaaxtt org org/pdf/Ins 1905. 07953. pdf
Pim de Haan, Taco S Cohen, and Max Welling. Natural graph networks. Advances in Neural Information Processing Systems, 33:3636-3646, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 11:448448555 2016.
Moshe Eliasof and Eran Treister. Diffgen: Graph convolutional networks via differential operators and algebraic multigrid pooling. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada,, 2020.
10

---

Under review as a conference paper at ICLR 2023
Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. Advances in Neural Information Processing Systems, 34, 2021.
Moshe Eliasof, Eldad Haber, and Eran Treister. pathgen: Learning general graph spatial operators from paths. In International Conference on Machine Learning, pp. 5878- 18.1. PMLR, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129-143, 143. Springer, 2003.
Johannes Gasteiger, Stefan Weißenherger, and Stephan Günnemann. Diffusion improves graph learning. In Conference Neural Information Processing Systems (NeurlPS), 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
William I.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pp. 770-778, 2016.
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint wxxv:22005.00685 2020.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowic, Bernardino Romera- Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Applying and improving alphafold at casp14. Proteins, 2021. ISSN 1097-0134, doi: 10.1002/ppot.66257. _eprint:
wttp://iiiiiiiiaa.iiileeooooo/// http://wwwciiiio0000oooooo.55550 p022/
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. International Conference on Learning Representations, 2021. URL
https::/openre//
net www.moormiioooooooo..o wtt.:/ewwwee//oorm1ldd/// wow.:mmmd--1150U11....
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6990, 2014.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint 1rxiv:6609 02907, 2016.
Johannes Klicpera, Alcksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference Learning Representations, 2019. URL URL/htttss://ppenreeee
net/ www.mooruuioooooo www.ooowmm..111112211121.1
A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. Ady Neural Inf Process Syst, 61:1097-1105 2012.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirfy-Second AAAI conference artificial intelligence, 2018.

---

Under review as a conference paper at ICLR 2023
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattem Recognition, pp. 11976-1 11986, 2022.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, and Le Song. Geniepath: Graph neural networks with adaptive receptive paths. Proceedings of the AAAI Conference Artificial Intelligence, 33, 02 2018. doi: 10.1609/aaai. v33101.330144424
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ICLR, 2018
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. Advances Neural Information Processing Systems, 10:11449--15055 2020.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115-5124, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kensting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benehmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL
www. graphhearnin..........
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning. 102(2):20--245, 2016.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference Learning Representations, 2020. URL
https: htttps://openreviee net S1d1mmm2
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http: /ttttes//ppppss....t www.:ennuiiipcomm http://pppprrrenrrpss...cccseees
library.
pdf
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020. URL https:://penxeviiew net forum? ldd
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2020.
Benedck Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
12

---

Under review as a conference paper at ICLR 2023
T Konstantin Rusch, Benjamin P Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M Bronstein. Graph-coupled oscillator networks. arXiv preprint arXiv:2202.02296. 2022.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bileNetV2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4510-4520 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Radd. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficiint graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception- resnet and the impact of residual connections on learning. In Thirty-Firsl AAAI Conference on Artificial Intelligence, 2017.
Mingxing Tan and Quoe Le. Efficientner: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pp. 6105-6114 14. PMLR, 2019.
Matthew Thorpe, Tan Minh Nguyen, Hedi Xia, Thomas Strohmer, Andrea Bertozzi, Stanley Osher, and Bao Wang. GRAND++: Graph neural diffusion with a source term. In International Confer- ence on Learning Representations, 2022. URL
net www.::/wwwwnt..tuneeem.mm ferumfrr
EMxu- dzvJk]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
URL /tttps://openreve
net. / forum? inborummid=ein id=rJXMpikcK
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin-based based constraints. arXiv preprint arXiv: 1945, 2019.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning point clouds. arXiv preprint arXiv: 2018
David Williamson. Lecture notes in spectral graph theory course, https://people.ort pdf 2016.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453-5462, PMLR, 10-15 Jul 2018.
URL http:tt/p/ccoeiii..... http://..........e.eeeee.reeeeee
m.r. www.s/.wee......... 110000/xx188- http:ulllc...cc html
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference on Learning Representations, 2019. URL https:
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with
graph embeddings. In International conference on machine learning. pp. 40-48. PMLR, 2016.
Jiaxuan You, Jonathan M Comes-Selmant Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
13

---

Under review as a conference paper at ICLR 2023
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma. Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In Proceedings of the Thirty- Fourth Conference on Uncertainty in Artificial Intelligence, pp. 339-349--999 2018a.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-second AAAI conference on artificial intelligence, 2018b.
Lingxiao Zhao and Leman Akoglu. Paimorm: Tackling oversmoothing in gnns. In International Conference Learning Representations, 2020.
Id=rkecllrtwä
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances Neural Information Processing Systems, 33:7793-7804, 2020.
14

---

Under review as a conference paper at ICLR 2023
A PROOFS OF THEOREMS
Here we repeat the theorems, observations and corollaries from the main paper, for convenience, and provide their proofs derivation.
P is a scaled diffusion operator. Assume that A is the adjacency matrix, and D is the degree matrix. Denote the adjacency matrix with added self-loops by Á I Then, the convolution operator from GCN (Kipf & Welling 2016) is
(12)
We first note that the Laplacian including self loops is the same as the regular Laplacian:
Í-D-A=D+I-A A
(13)
Therefore, holds that:
P I I-I+D-
= I- D-D-DDD -ー
I I-D- A-D
(14)
= I D (D A)D-
I-D LD
Theorem 1. Consider the L times application of equation from the main paper, i.e,, f(L) = (Pw) 'p(0) with a shared parameter ( = w that used in all the layers. Also assume that there some optimal Dirichlet energy of the final feature map that satisfies 0 < Eope(f(L)) < E(f())).
Then, the limit, as more layers are added, converges to / //Li L up to first order accuracy, where L the number of layers and w is a value that is independent of L and leads to Eogt-
Proof. First, note that equation from the main paper can be written as
E(P()) = Σ
= 1 | GIGD--P01
(15)
V(+dd) v(++d)) 2
LEV JEN.
where G is the graph gradient operator, also known the incidence matrix, that for each edge subtracts the features of the two connected nodes, i.c., Gr(l) (k.)) F.") 1 for (i.j) E E. Let us
assume that the initial feature f(0) has some Dirichlet energy Eo Eopt defined in equation 15 Since
= GT GD-1((0
we see that the forward propagation through GCN approximates the gradient flow of the Dirichlet energy. That is, for given L. and and we have that
p(++) = (() w = (() - - GGGGD--pl = (I -I- LD 1 1)r0)
(16)
where we used that G G L. Equation 16 can be seen both as a gradient descent step to reduce E, and also as a forward Euler approximation with step size w of the solution of
@f(t)
DD LD 1r())
f(0) f()).
(17)
Øt
It is known that the solution equation 17 given by
f(t) = exp (-ID-ALD-)) f(0).
(18)
Since the Dirichlet energy of f(t) is continuous in é and decays monotonically from Eg to zero, there exists T such that E(f(T) = Eapt- Now, considering discrete time intervals fo....,t t T.
then, similarly to equation 18 for any two subsequent time steps f++1 and t we have that
f((+1) exp (-(1et L f(()).
(19)
15

---

Under review as a conference paper at ICLR 2023
Taking time steps such that 8141
T/L for O,.... L, we get
f(t(+1) = exp (-wD LD f(tt) = (I - wD LD f))((t))))) O(w2),
(20)
where the rightmost approximation holds due to to the Taylor expansion up to first order approxima- tion. Denoting f()) = f(tz) and x T. we complete the proof.
Corollary 1. Allowing a variable w > Theorem I, yields E wil) w up to first order accuracy.
Proof.
The proof follows immediately by setting variable 4+1 - = wl() and placing in equation 20
Remark (The non-negativity of P.). By definition, for 0 < w S all the spatial weights of Pa defined in equation aare non-negative, and it is that the operator is smoothing filter. For w > or w < O, by definition we have an operator with mixed signs.
is a low-pass
Theorem 2. Assume that the graph is connected. Then, there exists some wh 2 where for all 0 < w < Wo, the operator Pw in equation from the main paper is smoothing and the leading eigenvector is D For w > wo or w < 0, the leading eigenvector changes.
Proof. Assuming that the graph is connected, it is known that the graph Laplacian matrix has the cigenvector 1 whose cigenvalue is 0, i.c. L1 = 0. Hence, we get that D LD D = 0 so D the eigenvector of the normalized Laplacian with eigenvalue of
Furthermore, denote the normalized Laplacian by L = D LD +. Consider the range
2 P(L)
0
wi:
where p(L) denotes the spectral radius of the matrix L. It is easy to verify that for this range of values for w. the largest eigenvalue in magnitude of P., is 1, and corresponds to the null eigenvector of L, i.c., 1 1. Hence, for this range, P is smoothing. For > wo and w < O, the leading eigenvector of P., becomes the leading eigenvector of L. Furthermore, it can be shown that p(L) I 2 (see Williamson (2016) for the proof), hence wi 2
B SYNTHETIC EXPRESSIVENESS TASK
To demonstrate the importance and benefit of learning sharpening propagation operators in addition to smoothing operators, we propose the following synthetic node gradient regression task. Given a graph (V,E) with some input node features f "xin,, wish GNN regress the node features gradient, Viin, where the node feature gradient of the i-th node is defined as an upwind gradient operator:
V maxjeM fj),
(21)
where the goal of the considered GNN is to minimize the following objective:
|GNN(F" 9) v
(22)
As comparison, we consider two GNNs: GCN Kipf Welling, 2016 and our wGCN with 64 channels and 2 layers. In both cases we use a learning rate of le 4 without weigh decay and train the network for 5000 iterations (no further benefit was obtained with any of the considered methods). The input graph is random Erdös-Rényi graph with 8 nodes and an edge rate of 30%, with input node features sampled form a uniform distribution in the range of O to The obtained loss GCN of order 1e 1, while our wGCN obtains loss of order 1e 12. also therefore conclude that introducing the ability learning mixed-sign operators by w is beneficial to enhance the expressiveness of GNNs.
be seen in Fig. 2 We
16

---

Under review as a conference paper at ICLR 2023
C DATASETS
In this section we provide the statistics of the datasets used throughout our experiments. Tab. presents information regarding node-classification datasets, and Tab. summarizes the graph- lassification datasets. For each dataset, we also provide the homophily score as defined by Pei et al. (2020).
Table 8: Node classification datasets statistics, Hom. score denotes the homophily score.
Dataset
Cora
Citeseer
Pubmed
Chameleon
Actor (Film)
Cornell
Texas
Wisconsin
PPI
Ogbo-arxiv
Classes
6
5
5
5
5
121
40
Nodes
2,708
3,327
19.717
2,277
7,600
183
183
251
56,944
169,343
Edges
5,429
4,732
44,338
36,101
33,544
295
309
499
818.716
1,116,243
Features
1,433
3,703
500
2,325
932
1,703
1,703
1.703
50
Hom.
0.81
0.80
0.74
0.23
0.22
0.30
0.11
0.21
0.17
0.63
Table 9: TUDatasets graph classification statistics.
Dataset
MUTAG
PTC
PROTEINS
NCII
NCI109
Classes
2
2
2
2
2
Graphs
188
344
1113
4110
4127
Avg. nodes
17.93
14.29
39.06
29.87
32.13
Avg. edges
19.79
14.69
72.82
32.30
32.13
D OVER-SMOOTHING IN GAT
In addition to the observation presented in Sec. 2.1 and specifically in Fig. 3b where we see that recurrent applications of GAT reduces the node feature energy from equation 11 which causes over-smoothing as shown by Wu et al. (2019); Wang et al. (2019) (as discussed in the main paper), here, also show that the same behaviour is evident with Citeseer and Pubmed datasets in Fig.
W
0.1 w 0.001 W 0.0001 Wlearn!
/(F()/(((())
0.5
0.5
14 8
16
32
64
14
16
32
64
Layer
Layer
(a) Citeseer
(b) Pubmed
Figure 5: Node features energy the [-th layer relative to initial node embedding energy Citescer 5ala and Pubmed wGAT controls the energy from Eq. equation TT avoid over-smoothing, while the baseline GAT with w = reduce the energy to and over-smooth.
E ARCHITECTURES IN DETAILS
We now elaborate on the specific architectures used in our experiments in Sec. 4
As noted the main paper, all our network architectures consist of an opening (embedding) layer (1 convolution), sequence of GGNN (i.e., GCCN or wGAT) layers, and a closing (classifier) layer (1 x convolution). In total, we have two types of architectures one that is based GCN, for node classification tasks
17

---

Under review as a conference paper at ICLR 2023
reported in Tab. 10 and the other for the graph classification task which is based on Xu et al. (2019)
and is reported in Tab. I1 Throughout the following, we denote by Cin and Cout the imput and output channels, respectively. and denotes the number of features in hidden layers (which is reported in Appendix F.. We initialize the embedding and classifier layers with the Glorot (Glorot & Bengio 2010) initialization, and K (1) from equation 2 initialized with an identity matrix of shape e x c.
The initialization of Q also starts from a vectors of ones. We note that our initialization yields standard smoothing process, which is then adapted to the data as the learning process progresses, and needed also changes the process to non-smoothing one by the means of mixed-signs, as discussed earlier and specifically in Theorem. 2 We denote the number of wGNN layers by L, and the dropout probability by p. The main difference between the two architectures are as follows. First, for the graph classification global graph feature. Second, we follow GIN and in addition to the graph layer (which is wGNN in our work), we add batch normalization (denoted by BN), 1 convolution and ReLU activation past each graph layer.
the standard add-poo operation as in GIN (Xu et al., 2019) to obtain
Table 10: The architecture used for node classification and inductive learning.
Input size
Layer
Output size
Y. X Cin
1 X Dropout(p)
n. X Cin
n X Gin
1 X Convolution
T
T1 X
ReLU
TU X
n X
Lx wGNN layers
n. X
n X
1 1x 1 Dropout(p)
n. X
n X
1 1x Convolution
n X Caut
Table 11: The architecture used for graph classification.
Input size
Layer
Output size
7. X Cin
1 X Convolution
n X c n X
ReLU
T. X C
x [WGNN, BN, X Convolution, ReLU
]
n. X c 1 X
1 Add-pool
X C 1 X
1 X Convolution
1 x c 1 1
C
1 Dropout(p)
1 x 1 Convolution
1 x Cout
F EYPER-PARAMETERS DETAILS
We provide the selected hyper-parameters in our experiments. denote the learning rate of our wGNN layers by LRGNN. and the learning rate of the 1 opening and closing well any additional classifier layers by LR Also, the weight decay for the opening and closing layers is denoted by WD.c. We denote the parameter learning rate and weight decay by LR and W D... respectively. e denotes the number of hidden channels. In the case of wGAT, the attention head vector are learnt with the same learning rate as LRGNN N and W DGNN-
F.1 SEMI-SUPERVISED NODE CLASSIFICATION
The hyper-parameters for this experiment are summarized in Tab. 12
F.2 FULL-SUPERVISED NODE CLASSIFICATION
The spper-parameters for this experiment summarized in Tab. B The number of layers used in Tab. are mentioned in brackets in the table. For Ogbn-arxiv and Actor from Tab. layer wGCN and GAT were employed.
18

---

Under review as a conference paper at ICLR 2023
Table 12: Semi-supervised node classification hyper- parameters.
Architecture
Dataset
LRNNN
LRoc
LR
W WDONN
WDoc
WD
p
wGCN
Cora
0.01
0.01
0.01
le-4
8e-5
2e-4
64
0.6
Citeseer
le-4
0.005
0.005
le-5
5e-6
2e-4
256
0.7
Pubmed
0.001
5e-4
0.005
2e-4
le-4
le-4
256
0.5
wGAT
Cora
0.01
0.01
0.005
le-5
le-5
le-5
64
0.6
Citeseer
0,005
0,005
0.001
lc-4
le-5
le-4
256
0.7
Pubmed
0.005
0.001
0.05
4e-5
le-5
lc-4
256
0.5
F.3 INDUCTIVE LEARNING
The hyper-parameters for the inductive learing on PPI are listed in Sec. the same for wGCN and wGAT.
4.3 in the main paper, and are
Table 13: Full-supervised node classi fication hyper-parameters.
Architecture
Dataset
LRGNN
LRge
LR
W DGNN
WDoc
WD
p
GCNN
Cora
0.01
0.05
0.005
0.01
lc-4
le-4
64
0.5
Citesear
0.001
0.08
0.005
0.005
le-4
0
64
0.5
Pubmed
0.005
0.005
0.01
0.003
5e-5
0.01
64
0.5
Chameleon
lc-4
0.005
5c-4
lc-4
lc-4
le-5
64
0.5
Actor (Film)
0.05
0.01
0.05
le-4
le-4
le-5
64
0.5
Cornell
0.01
0.05
0.01
0.005
le-4
0
64
0.5
Texas
0.08
0.08
0.005
0.005
5e-4
64
0.5
Wisconsin
0.001
0.05
0.005
le-4
3e-4
3c-4
64
0.5
Ogbn-arxiv
0.01
0.01
0.01
0
0
256
0
wGTT
Cora
0.001
0.01
0.05
0.001
5e-4
0
64
0.5
Citeseer
0.005
0.05
0.03
0.005
5e-4
0.001
64
0.5
Pubmed
0.05
0.005
0.005
0.003
le-6
0.003
64
0.5
Chameleon
0.005
0.005
3e-4
5e-4
5c-4
le-5
Actor (Film)
0.05
0.01
0.01
5e-4
0.001
4e-4
64
0.5
Cornell
0.001
0.01
0.005
le-4
lc-5
0
64
0.5
Texas
lc-4
0.02
0.05
5e-4
5c-4
0
64
0.5
Wisconsin
0.01
0.05
0.005
0.001
5e-4
64
0.5
Ogbn-arxiv
0.01
0.01
0.01
0
256
F.4 GRAPH CLASSIFICATION
The hyper-parameters for the graph classification experiment TUDatasets reported in Tab. 14 We followed the same grid-search procedure as in GIN (Xu et al.) 2019). all experiment, a 5 layer (including the initial embedding layer) wGCN and wGAT are used, similarly to GIN.
F,5 ABLATION STUDY
In this experiment used the same
reported in Tab. 12
G RUNTIMES
Following the computational cost discussion from Sec. 2.4 in the main paper, we also present Tab. 15 the measured training and inference times of our baselines GCN and GAT with 2 layers, where we see that indeed the addition of w per layer and channel requires a negligible addition time, at the return of significantly more accurate GNN. We note that further accuracy gain can be achieved
19

---

Under review as a conference paper at ICLR 2023
Table 14: Graph classification hyper-parameters. BS denoted batch size.
Architecture
Dataset
LRGNN
LRoc
LRw
WDGNN
De
W D
e
p
BS
wGCN
MUTAG
0.01
32
PTC
0.01
0.01
0.01
0
32
0
PROTEINS
0.01
0.01
0.01
0
0
32
0
128
NCII
0.01
0.01
0.01
0
0
32
0.5
32
NCT109
0.01
0.01
0.01
0
O
32
0
32
GGAT
MUTAG
0.01
0.01
0.01
0
0
32
0
32
PTC
0.01
0.01
0.01
0
32
0
128
PROTEINS
0.01
32
0
NCII
0.01
0.01
0.01
0
32
0.5
128
NC1109
0.01
0.01
0.01
0
0
32
0.5
32
when adding more WGNN layers as reported in Tab. inn the main paper. However, since GCN and GAT over-smooth, the comparison here done with layers, where the highest accuracy obtained for the baseline models.
Table 15: Training and inference GPU runtimes [ms] on Cora.
Runtime
GCN
GAT
wGCN (Ours)
wGAT (Ours)
Training
7.71
14.59
7.79
14.95
Inference
1.75
2.98
1.88
3.09
Accuracy (%)
81.1
83.1
82.6
83.4
H ABLATION STUDY USING wGAT
To complement our ablation study on WGCN in Sec. 4.5 in the main paper, we perform as similar study on wGAT. Here, show Tab. [6 that indeed the single variant, dubbed wAAT does not over-smooth, and that by allowing the greater flexibility of per-layer and per layer and channel of our wGATpt. and wGAT, respectively, better performance is obtained.
Table 16: Ablation study wGAT
Layers
Data.
Variant
2
4
16
32
64
Cora
wGAT
83.3
83.3
83.4
83.6
83.7
83.9
wGATpL
83,4
83.5
83.8
84.0
84.1
84.0
wGAT
83.4
83.7
84.0
84.3
84.4
84.8
Cite.
wGATG
71.5
71.8
71.9
72.2
72.4
72.9
wGAT
72.1
72.3
72.4
72.8
73.1
73.2
wGAT
72.5
73.1
73.3
73.5
73.9
74.0
Pub.
wGATG
80.0
80.2
80.3
80.5
80.6
80.9
wATTPL
80.0
80.4
80.7
81.1
81.2
81.4
GGAT
80.3
81.0
81.2
81.3
81.5
81.8
20

---

Under review as a conference paper at ICLR 2023
Table 17: Semi-supervised node classification test accuracy 100 random train-val val---vll-stttt-eeee splits.
Method
Cora
Citeseer
Pubmed
GCN
Kipf & Welling
2016
81.5
71.9
77.8
GAT Velıčković al. 2018
81.8
71.4
78.7
MoNet (Monti et al. 2017))
81.3
71.2
78.6
GRAND-I (Chamberlain et al. 2021
83.6
73.4
78.8
GRAND-nl Chamberlam et al 2021
82.3
70.9
77.5
GRA Chhambellan et al. 2021
83.3
74.1
78.1
GraphCON-GCN (Rusch et al. 2022
81.9
72.9
78.8
GraphCON-Gar GAT Rusch et al. 2022
83.2
73.2
79.5
GraphCON-TH - (Rusch al.
2022
84.2
74.2
79.4
wGCN (ours)
84.5
73.8
82.9
wGAT (ours)
84.3
73.6
82.6
I STATISTICAL SIGNIFICANCE OF RESULTS
NODE CLASSIFICATION
Throughout semi-supervised node classification experiment in Sec. on Cora, Citeseer and Pubmed, the standard split from Kipf & Welling (2016) was considered, to direct comparison with many as possible methods. However, since this result reflects the accuracy from single split, also repeat this experiment with 100 random splits as in Chamberlain et al. 2222 I) and compare with applicable methods that also conducted such statistical significance test. In Tab. 17 we report our obtained accuracy on Cora, Citeseer and Pubmed. It is possible to see that in this experiment our wGCN and wGAT outperform obtain similar results compared with the considered methods, which further highlight the performance advantage of our method.
J THE LEARNT O
One of the main advantages of our method in Sec. is that our method is capable of learning both smoothing and sharpening propagation operators, which cannot be obtained in most current GNNs.
In Fig. 6 we present the actual (///// as matrix of size L X that learnt for two dataset of different types-wiith with high and low homophily score (as described Pei al. (2020)). Namely, the Cora dataset with high homophily score of 0.81, and the Texas dataset with low homophily score of 0.11 (i.e., heterophilic dataset). We see that homophilic dataset like Cora, the network learnt to perform diffusion, albeit in controlled manner, and not simply employ the standard averaging operator P. We further that for heterophilic dataset the ability to learn contrastive (i.e., sharpening) propagation operators in addition to diffusive kernels is beneficial, and also reflected in our results Tab, 3 where larger improvement is achieved in datasets like Cornell, Texas and Wisconsin, which have low homophily scores (Rusch et al. 2022).
21

---

Under review as a conference paper at ICLR 2023
Cora
Texas
Channels
Channe's
11.0
0.8
20
20
40
Layers
Layers
Figure 6: The Icarnt E 664466 of wGCN with 64 layers (x-axis) and 64 channels (y-axis) for Cora (homophilic) and Texas (heterophilic) datasets. Smoothing operators appear in blue, while sharpening operators appear in red. White entries are obtained for w
22


Reviews:
[{"review_id": "wQyX2APbM9", "reviewer": "Reviewer_shzp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a new GNN architecture, omega-GNN, which learns a filtering coefficient for each feature channel and each layer. The introduced omega parameter scales the graph convolution and thus enables \"sharpening\" operation in addition to the \"smoothing\" performed by traditional GNNs. By properly setting the omega parameters, the authors claim that omega-GCN does not oversmooth. A more expressive variant performing channel-wise scaling has been proposed and instantiated on the GCN and GAT backbones. Extensive experiments have been performed on both node-level and graph-level tasks to show the accuracy improvements. ", "summary_of_the_review": "In summary, I think this is a well-written paper with reasonable architecture design. The idea bears similarity with a few existing works. The theoretical analysis seems problematic. And it would be better to also (informally) analyze the benefits beyond addressing oversmoothing -- a phenomenon already with many solutions. \n\nOverall, in its current form, I think the paper is still below the bar of acceptance. ", "strength_and_weaknesses": "## Summary of strengths\n\n+ The paper is well-structured and easy to read. The motivation is clearly stated and the problem is well defined. \n+ The overall architecture design is reasonable. \n+ Extensive experiments have been performed on many datasets and across different tasks. \n\n## Summary of weaknesses\n\n- Theoretical proof is problematic. The derivation is based on an improper discretization process that results in the residue error to accumulate. \n- The significance of the theoretical results is limited. First of all, it only discusses the basic version of omega-GNN with shared omega across channels. Further understanding is needed regarding the channel-wise scaling. Secondly, the analysis only discusses the prevention of oversmoothing. Many existing works can already address oversmoothing and it is not clear what are the advantages brought by omega-GNN. \n- Scaling the propagation matrix either channel-wise or layer-wise has already been proposed in the literature. \n- For experiments, most baselines are relatively old. Some more recent SOTA methods are missing. e.g., [a] which also addresses oversmoothing. \n\n## Detailed comments\n\n### Proof of Theorem 1 and Corollary 1 \n\nFirst, there is no guarantee that the Dirichlet energy of a multi-layer omega-GNN can converge to a target energy level, $E_{opt}$. It is true that Equation 16 defines a gradient descent operation with the Dirichlet energy as the minimization objective. However, iteration by Equation 16 is based on a constant step size omega, which is independent of both $E_{opt}$ and the iteration number (i.e., layer number). It is likely that $E(l+1) < E_{opt} < E(l)$ and thus there does not exist a layer $l$ to exactly achieve $E_{opt}$. \n\nSecond, the process of converting discrete form of Eq. 16 to the continuous form of Eq. 17, and then converting back to the discrete form of Eq. 20 is problematic. The discretization process introduces errors depending on omega, and such error accumulates with the layer number. Eventually, the second order term accumulated across the full GNN becomes a first order term and is not negligible. \n\nSpecifically, let $M = \\tilde{D}^{-1/2}L\\tilde{D}^{-1/2}$. Then Eq. 20 becomes \n\n$f(t_{l}) = exp(-\\omega M)f(t_{l-1}) = exp(-L\\omega M)f(t_0)$\n\nThe target $\\omega$ value is derived by setting $L\\omega=T$. \n\nHowever, if we look at the Taylor expansion:\n\n$f(t_{l+1}) = (I-\\omega M)f(t_l) + O(\\omega^2) =  (I-\\omega M)^2 f(t_{l-1}) + (I-\\omega M)O(\\omega^2) + O(\\omega^2)= ...$\n\nWhen the recursion is applied from $f(t_L)$ until $f(t_0)$, there will be $L$ terms of $O(\\omega^2)$. Since $L=T/\\omega$, then $L\\cdot O(\\omega^2) = O(\\omega)$ and the residue error becomes non-negligible due to the recursive expansion. \n\nTherefore,  Theorem 1 and Corollary 1 are problematic. \n\n### Related works with similar ideas\n\n* The idea of layerwise scaling the propagation matrix is known. Could you please discuss how omega-GNN improves methods such as GCNII?\n* Channel-wise scaling the propagation matrix is also known. For example, in [b]. Please discuss the relation between omega-GNN and [b]. \n* Oversmoothing is a classic issue and there have been many solutions proposed, from many different perspectives. In addition to the ones in Sec 3, [a] also provably avoids oversmoothing without changing the GCN architecture. The theoretical analysis presented in the paper mostly focuses on the oversmoothing perspective. Could you please illustrate the advantages of addressing oversmoothing via omega-GNN compared with the many existing solutions?\n\n### Experiments\n\nThanks for evaluating omega-GNN with many graphs and baselines. It would be more convincing if more recent SOTA methods (e.g., [a]) are included. \n\nFigure 4 does not really demonstrate the similarity between solid and dashed lines. I'm not sure if it can really validate the theorems. \n\n\n## References\n\n[a] Decoupling the depth and scope of graph neural networks. In NeurIPS 2021.\n\n[b] How Powerful are Spectral Graph Neural Networks. In ICML 2022. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "p6OkeWT3D6", "reviewer": "Reviewer_UJFL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Simple changes are proposed to overcome expressivity limits of GNN propagation. The changes involve new parameters $\\omega$, which very naturally allow both smoothing-type propagations and sharpening-type propagations. Instantiations of the proposed changes in GCNs and GATs are empirically tested in both node and graph level tasks.\n\n\n\n\n*Correctness\n3\n\n*Technical Novelty and Significance\n2\n\n*Empirical Novelty and Significance\n2\n\n*Flag for ethics review:\nNo\n\n*Recommendation\n3\n\n*Confidence\n4\n", "summary_of_the_review": "It is good to see simple and reasonable changes to GNNs that can help with some of the known issues of these models. However, the exact novelty is unclear, as several other similar methods (some of which are quite prominent) have been proposed. Moreover, the choice of datasets is not great for showing significant empirical benefits.", "strength_and_weaknesses": "Strengths:\n1. Simple approach that is easy to implement\n2. Use of multiple omegas gives a flexible class of operators in an efficient manner\n3. Experiments on both node and graph classification tasks, while other works often do one or the other.\n\nWeaknesses:\n1. Should cite [1], which analyzes oversmoothing using the Dirichlet energy.\n2. Missing citations to other mixed sign propagations in GNNs, this is done by others besides Eliasof et al. 2022. See [2], [3], [7] for prominent examples. Moreover, this is also mentioned in [4]. Please compare and explain the differences.\n3. Why would you not also run your method on the Squirrel dataset in Pei et al. 2020?\n4. The datasets tested on for the most part have been noted to have a lot of issues. For instance, the Pei et al heterophily datasets were covered in [5] and Cora + Citeseer + Pubmed were covered in [6]. New datasets were introduced, which your method is clearly scalable enough to run. Further, many methods do quite well on PPI, and your gain is only 00.02 better than the next best method. Also, there are better baselines that outperform your method on ogbn-arxiv, such as Correct and Smooth [8] from 2020.\n\n\nOther notes:\n1. Should be $\\vec \\omega^{(l)} \\in \\mathbb{R}^c$ right before equation (3)\n\n[1] Cai and Wang. A Note on Over-Smoothing for Graph Neural Networks. https://arxiv.org/abs/2006.13318\n\n[2] Bo et al. Beyond Low-frequency Information in Graph Convolutional Networks. https://arxiv.org/abs/2101.00797\n\n[3] Yan et al. Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. https://arxiv.org/abs/2102.06462\n\n[4] Di Giovanni et al. Graph Neural Networks as Gradient Flows: understanding graph convolutions via energy. https://arxiv.org/abs/2206.10991\n\n[5] Lim et al. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. https://arxiv.org/abs/2110.14446\n\n[6] Shchur et al. Pitfalls of Graph Neural Network Evaluation. https://arxiv.org/abs/1811.05868\n\n[7] Yang et al. Diverse Message Passing for Attribute with Heterophily. NeurIPS 2021\n\n[8] Huang et al. Combining Label Propagation and Simple Models Out-performs Graph Neural Networks. https://arxiv.org/abs/2010.13993\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZXGyT2Ehvy2", "reviewer": "Reviewer_cjVH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper attempts to address the shortcomings in GNNs by modifying the propagation operator and thus propose an approach called $\\omega$GNN, as two instances, $\\omega$GCN and $\\omega$GAT. It is justified that $\\omega$GNN can prevent over-smoothing issue, and the parameterized propagation operator in $\\omega$GNN enable variant operators to use. Extensive experiments are conducted and shown superior accuracy. \n", "summary_of_the_review": "The paper is well-motivated and clearly written. The idea is interesting and novel. The empirical evaluation is extensive. Nevertheless, it is suspecious that the contribution is somewhat over-claimed. To be specific, the over-smoothing issue is just alleviated, but not resolved yet. For details, please refer the \"weaknesses\". ", "strength_and_weaknesses": "The strengths of the paper: \n\n+ It is quite interesting to develop a parameterized graph convolution operator that is able to prevent the over-smooth issue and is able to implement variant operators. \n\n+ The empirical evaluation is extensive and the experimental results show notable improvements. \n\nThe weaknesses of the paper: \n\n- Note that the graph convolution operation in GCN is a step of gradient-based node updating to optimize an objective in label propagation. Here, a parameter $\\omega$ introduced in Eq. (2), serves as a step size parameter. If the parameter $\\omega$ is learnable, does it still converge in the perspective of understanding the graph convolution as optimizing a label propagation objective (e.g. Ma et al.'21)? Where does it converge to? \n\nRef. \n[a] Yao Ma et al. 2021. A Unified View on Graph Neural Networks as Graph Signal Denoising. \n\n- Note that, the parameter $\\omega$ is a step size to control the degree of incorporating the graph convolution to modify the node feature. Of course, using a smaller $\\omega$, the smoothing issue could be slower as shown in Fig.3. However, it does not resolve the smoothing issue at all. When using a smaller $\\omega$, more layers of graph convolusions are needed to yield an equivalent node feature. Thus, it is NOT to avoid over-smoothing issue at all ---the over-smoothing issue is still hidding in the problem formulation! \nLooking into the curve in Fig.3(b) for $\\omega$GAT, it seems not showing a convergence. If many iteratons (i.e., layers) are conducted, does it converge or not? \n\n- It is interesting to have a theorem to justify the convergence for the proposed methods. However, the Theorem 1 strongly relies on the assumption that there is some optimal Direchlet energy of the final feature map that satisfies $0 < E_{opt} (f^{(L)}) < E(f^{(0)})$. Does it really exist an optimal value that is strictly greater than 0? In such case, what is the condition on the property of the objective function or on the graph Laplacian? Is the implicit optimization problem a well-defined, in the sense that not having a trivial solution? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "B3AAI2SQZC", "reviewer": "Reviewer_ZYQh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an extension to GCN-style GNNs, where the propagation operator is extended with a ω factor. This allows for expressing non-smoothing transformations. The authors show theory backing the design of their model, and then perform a sequence of experiments to show its effectiveness. ", "summary_of_the_review": "While from the theoretical side the work looks strong, I am not yet sure if it's SotA in practice when compared to all the available results, and the current discussion of the GNN landscape seems biased. Therefore, for my initial evaluation I lean towards rejection, but I'm happy to adjust it after discussions with the authors and the other reviewers.", "strength_and_weaknesses": "=== Strengths === \n\n(S1): The addition of the ω component to the base GNNs is clearly explained and motivated, with useful visualization showing how different values of ω induce different kinds of behaviour. \n\n(S2): The theoretical results, showing how repeated application of the propagation operator with a given value of ω corresponds to gradient descent steps on an appropriately defined energy, are interesting. \n\n(S3): The paper is well-written and easy to read. \n\n \n\n=== Weaknesses === \n\n(W1): The paper seems to be biased towards GCN-style GNNs, and largely omits generalized message-passing-based ones. It focuses on GCN and GAT, as these are the kinds of GNNs where most of the statements made in this work apply. However, GNNs based on general message passing don't seem to be affected by the pitfalls discussed here. GCN in its plain form usually doesn't work very well anyway, due to being rather constrained (as the authors note), and often more flexible variants such as GGNN [1] or PNA [2] work better (in practice, the latter is a good default choice). Both the message function and the update function can be implemented with arbitrary MLPs, and as far as I understand, GNNs that do so don't suffer from the \"non-negativity\" problems that the authors seek to solve. The statement that the propagation is often shared across channels doesn't seem to apply to things like GGNN, while the statement that it is shared across layers doesn't seem to apply to most practical models (it seems un-tied weights tend to work better due to higher flexibility?). Things like PNA are available in `pytorch_geometric` (which the authors use), so a direct comparison could be straight-forward. In any case, I think the discussion could be adjusted to better position this work in relation to a larger body of papers on GNNs, noting how these other models don't suffer from the problems the authors focus on. \n\n(W2): While the empirical results look good compared to the models included in the tables, I'm not sure to what extent are these comparisons exhaustive. For example, [3] shows better results on PROTEINS, while [4] better results on ogbn-arxiv. Did the authors intend to compare to all the available results? Claiming that e.g. ωGNNs are SotA among a particular style of GNNs is a reasonable thing to aim for too, but I'd like to understand exactly what the claim here is. \n\n \n\n=== References === \n\n[1] Li et al., \"Gated Graph Sequence Neural Networks\" \n\n[2] Corso et al., \"Principal Neighbourhood Aggregation for Graph Nets\" \n\n[3] Zhang et al., \"Hierarchical Graph Pooling with Structure Learning\" \n\n[4] Sun et al., \"Adaptive Graph Diffusion Networks\" \n\n \n\n=== Nitpicks === \n\nHere I include some final nitpicks, which did not affect my score; they are here just to help improve the paper. \n\n- \"indistinguishable from one and other\": maybe \"one another\"? \n\n- missing space before parenthesis in Section 2.1 \n\n- first sentence of Section 4.2 reads off ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject