ReD-GCN: Revisit the Depth of Graph Convolutional Network
Authors: Yuchen Yan
Yuzhong Chen
Mahashweta Das
Hao Yang
Hanghang Tong
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph convolutional network
the depth of graph convolutional network

Abstract: Finding the proper depth $d$ of a GNN that provides strong representation power has drawn significant attention, yet nonetheless  largely  remains an open problem for the graph learning community. Although noteworthy progress has been made, the depth or the number of layers of a corresponding GCN is realized by a series of graph convolution operations, which naturally makes $d$ a positive integer ($d \in \mathbb{N}+$). An interesting question is whether breaking the constraint of $\mathbb{N}+$ by making $d$ a real number ($d \in \mathbb{R}$) can bring new insights into graph learning mechanisms. In this work, by redefining GCN's depth $d$ as a trainable parameter continuously adjustable within $(-\infty,+\infty)$, we open a new door of controlling its expressiveness on graph signal processing to model graph homophily/heterophily (nodes with similar/dissimilar labels/attributes tend to inter-connect). A simple and powerful GCN model ReD-GCN, is proposed to retain the simplicity of GCN and meanwhile automatically search for the optimal $d$ without the prior knowledge regarding whether the input graph is homophilic or heterophilic. Negative-valued $d$ intrinsically enables high-pass frequency filtering functionality for graph heterophily. Variants extending the model flexibility/scalability are also developed. The theoretical feasibility of having a real-valued depth with explainable physical meanings is ensured via eigen-decomposition of the graph Laplacian and a properly designed transformation function from the perspective of functional calculus. Extensive experiments demonstrate the superiority of ReD-GCN on node classification tasks for a variety of graphs. Furthermore, by introducing the concept of eigengraph, a novel graph augmentation method is obtained: the optimal $d$ effectively generates a new topology through a properly weighted combination of eigengraphs, which dramatically boosts the performance even for a vanilla GCN.

Under review as a conference paper at ICLR 2023
RED-GCN: REVISIT THE DEPTH OF GRAPH CONVOLU- TIONAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Finding the proper depth d of GNN that provides strong representation power has drawn significant attention, yet nonetheless largely remains an open problem for the graph learning community. Although noteworthy progress has been made, the depth or the number of layers of a corresponding GCN realized by a series graph convolution operations, which naturally makes d positive integer (d N-). An interesting question is whether breaking the constraint of N+ by making d real number (d R) can bring new insights into graph learning mechanisms. In this work, by redefining GCN's 's depth as a trainable parameter continuously adjustable within (-oc, +oo), we open new door of controlling its expressiveness on graph signal processing to model graph similar/dissimilar labels/attributes tend to inter-connect). A simple and powerful GCN model RED-GCN, is proposed to retain the simplicity of GCN and mean- while automatically search for the optimal d without the prior knowledge regarding whether the input graph is homophilic or heterophilic.
(nodes with
regative-valure d intrin- sically enables high-pass frequency filtering functionality for graph heterophily. Variants extending the model flexibiiity/scalabiiit are also developed. The theoret- ical feasibility of having a real-valued depth with explainable physical meanings is ensured via eigen-decomposition of the graph Laplacian and a properly designed transformation function from the perspective of functional calculus. Extensive experiments demonstrate the superiority of RED-GCN on node classification tasks for a variety of graphs. Furthermore, by introducing the concept of eigengraph, a novel graph augmentation method is obtained: the optimal d effectively generates a new topology through properly weighted combination of eigengraphs, which dramatically boosts the performance even for a vanilla GCN.
INTRODUCTION
Graph convolutional network (GCN) (Kipf & Welling 2016: Veličković et al. 2017 Hamilton et al. 2017) has exhibited great power in variety of graph learning tasks, such node classification
(Kipl & Welling 2016 Luan et al. 2019 2022a). link prediction (Zhang & Chen 2018). community detection (Chen al. 2020), and many more. Since the representation power of GCN is largely determined by its depth, i.e., the number of graph convolution layers, tremendous research efforts have been made on finding the optimal depth that strengthens the model's ability for downstream tasks. Upon increasing the depth, the over-smoothing issue arises: a GCN's performance is deteriorated if its depth exceeds a uncertain threshold (Kipf & Welling 2016). It is unveiled in (Li et al. 2018) that a graph convolution operation is a special form of Laplacian smoothing (Taubin 1995). Thus, the similarity between the graph node embeddings grows with the depth so that these embeddings eventually become indistinguishabl.. Various techniques are developed to alleviate this issue, e.g., applying pairwise normalization can make distant nodes dissimilar (Zhao & Akoglu 2019). and dropping sampled edges during training slows down the growth of embedding smoothness as depth increases (Rong et al. 2019).
Other than the over-smoothing issue due large GCN depth, another fundamental phenomenon widely existing in real-world graphs is homophily and heterophily. a homophilic graph, nodes with similar labels attributes tend to inter-connect, while in heterophily graph, connected nodes usually have distinct labels or dissimilar attributes. Most graph neural networks (GNNs) are developed based on homophilic assumption (Yang et al. (016), while models able perform well on heterophilic

---

Under review as a conference paper at ICLR 2023
graphs often need special treatment and complex designs (Bianchi al. 2021 Zhu al. 2020).
Despite the achievements made by these methodologies, little correlation has been found between the adopted GNN model's depth and its capability of characterizing graph heterophily.
For most GNNs, if not all, the depth needs to be manually set as a hyper-paree parameter before training, and finding the proper depth usually requires considerable amount of trials good prior knowledge of the graph dataset. Since the depth represents the number of graph convolution operations and naturally takes only positive integer values, little attention has been paid to the question whether non-integer depth is realizable, and if yes, whether it is practically meaningful, and whether it can bring unique advantages to current graph learning mechanisms.
This work revisits the GCN depth from spectral and spatial perspectives and explains the inter- dependencies between the following key ingredients in graph learning: the depth of a GCN, the spectrum of the graph signal, and the homophily/hettrophiiyy of the underlying graph. Firstly, through digen-decomposition of the symmetrically normalized graph Laplacian, we present the correlation between graph homophily/heterophilyy and the eigenvector frequencies. Secondly, by introducing the concept eigengraph, we show the graph topology is equivalent to weighted linear combination of eigengraphs, and the weight values determine the GCN's capability of capturing ho- mophilic/heterophilicc graph signals. Thirdly, we reveal that the eigengraph weights can be controlled by GCN's depth, so that automatically tunable depth parameter is needed to adjust the eigengraph weights into the designated distribution in match of the underlying graph homophily/heeterpphe
To realize the adaptive GCN depth, extend its definition from positive integer arbitrary real number with theoretical feasibility guarantees from functional calculus (Shah & Okutmuştur (2020) With a trainable depth parameter, we propose simple and powerful model, Redefined Depth-GCY (ReD-GCN), with two variants. Extensive experiments demonstrate the automatically optimal depth searching ability, and it found that negative- vaalued depth plays the key role handling heterophilic graphs. Systematical investigation on the optimal depth is conducted in both spectral and spatial domains. It in turn inspires the development of novel graph augmentation methodology. With clear geometric explanability, the augmented graph structure possesses supreme advantages over the raw input topology. especially for graphs with heterophily. The main contributions of this paper are summarized as following:
The interdependence between negative GCN depth and graph heterophily is discovered; In-depth geometric and spectral explanations are presented.
A novel problem of automatic GCN depth tuning for graph homophilyyheterophily detection is formulated. To our best knowledge, this work presents the first trial to make GCN's s depth trainable by redefining it on the real number domain.
A simple and powerful model RED-GCN with two variants DED-GCN-S and
D) is proposed. A novel graph augmentation method is discussed.
Our model achieves superior performance on semi-supervised node classification tasks on 11 graph datasets.
2 PRELIMINARIES
Notations. We utilize bold uppercase letters for matrices (e.g., A), bold lowercase letters for column vectors (e.g., u) and lowercase letters for scalars (c.g., a). We use the superscript T for transpose of matrices and vectors (c.g., A and u J). An attributed undirected graph g = {A, X} contains an adjacency matrix A E "R" and an attribute matrix X E Rxx with the number of nodes and the dimension of node attributes D denotes the diagonal degree matrix of A. The adjacency matrix with lelf- is given by A = A + I I is the identity matrix), and all variables derived from À are decorated with symbol e.g., D represents the diagonal degree matrix of A. Md stands for the d-th power of matrix M, while the parameter and node embedding matrices in the d-th layer of a GCN are denoted by ((d) and (4).
Graph convolutional network (GCN) and simplified graph convolutional network (SGC). The layer-wis wise message- passing and aggregation of GCN (Kipf & Welling 2016) is given by
H (d+1) aD AD H (4) ((d))
(1)
2

---

Under review as a conference paper at ICLR 2023
D"EAD"
eigengraph
eigengraph
eigengraph
Us
nommaliattion
1- 1.0,
A2
Figure 1: Decompose the symmetrically normalized adjacency matrix into three eigengraphs.
where H stands for the embedding matrix (H X) in the d-th/(d + 1)-th layer; W(d) the trainable parameter matrix; and (-)) the non-linear activation function. With a(-) removed in each layer, SGC (Wu et al. 2019) is obtained as below:
H (d) Xw,
where 5 D- AD 2, and the parameter of each layer w are compressed into one trainable W [1-1 W().
Graph Laplacian and spectrum. In graph theory, graph Laplacian L = D A and its symmetrically
normalized correspondence Laym = - D AD- possess critical properties of the underlying graph G. Lewm has eigenvalues [^1, A AnJ. where X E [0, 2), E 21. (Chung & Graham 1997). Here they are put in ascending order: Leym UAUT, where U [ug, u...... un is the eigenvector matrix
S X2 S I An 2. It can
be eigen- decemppec
(u, u,, vi j), and A is the diagonal eigenvalue matrix:
A1
0
An.
For each eigenvector u, we have u E Raxx. As we will show in Section 3 this n x n matrix be viewed weighted adjacency matrix of graph with possible negative edges, which name u as the i-th eigengraph of G. Accordingly, Leym can be written as the linear combination of all eigengraphs weighted by the corresponding eigenvalues (Chung Graham 1997):
L Lagm nn +.... Auu +... Xx u,u
where the first eigenvalue A 0, and the corresponding eigengraph inun has identical value for all entries (Shuman et al. 2013). Thus, for SGC, we have
n
I Laym Ú(I A)Ü \11
SGC with layers requires consecutive graph convolution operations, which involves the multiplication of $ by times. Due to the orthogonality of U, namely, Ü Ü we obtain
Sd AUL-AJÜTCE -UU--AÜÜT Ú(I ÂJ Ú(I U Σ (1 ū, (5)
where 1 1- 1 (-1, and the depth d of SGC serves the power of S's eigenvalues. Šd can be viewed the sum of eigengraphs ú,ú weighted by coefficients (1 X.)
Graph homophily and heterophily. Graph homophily describes to what extent edges tend to link nodes with the same labels and similar features. In this work, focus edge homophily (Zhu et al. 2020p: h(G)) E. -obll-yll =xbl=
E [0, 1]. where (I:) 1 if is true and 0 otherwise. A graph is more homophilic for ((()) closer to 1 or more heterophilic for h(G) closer to O.
Ei, Alj.
3 MODEL
Firstly, we establish the intrinsic connections between eigengraphs with small/large weights, graph signals with high/low frequencies, and graphs with homopphilccheetrrohiiic properties. Secondly, we
This work focuses connected graph without bipartite components (i.e., connected component which is bipartite graph)
3

---

Under review as a conference paper at ICLR 2023
show how the positive/negative depth d of GCN affects the eigengraph weights and in turn deter- mines the algorithm's 's expressive power to process homophilichheterophil graph signals. Thirdly, with the help of functional calculus (Shah & Okutmuştur 2020), we present the theoretical feasi- bility of extending the domain of from N+ to R. Finally, by making d a trainable parameter, we present our model RED-GCN and its variants, which are capable of automatically detecting the homophilyyhheterohiily of the input graph and finding the corresponding optimal depth.
The eigenvectors of graph Laplacian form complete set of basis vectors in the n-dimensional space capable of expressing the original node attribute X as a linear combination. From the perspective of graph spectrum analysis (Shuman et al., 2013). the frequency of eigenvector u, reflects how much the j-th entry [ deviates from the k-th entry u, [k] for each connected node pair by and Ey in G. This deviation is measured by the set of zero crossings of u,: 2(u,) == {e = (Vy, ) E & u. Iu [k] < 0). where & is the set of edges in graph G. Larger/smaller 2 indicates higher/lower eigenvector frequency. A zero-crossing also corresponds negative weighted edge in an eigengraph. Due to the widely existing positive correlation between A; and [z(u.) (Shuman et al. 2013). large/small eigenvalues mostly correspond to the high/low frequencies of the related eigenvectors. As illustrated by the toy example of n = 3 in Figure 1 for \ O, we have (2(uz) ) 0, and eigengraph un u well-connected with identical edge weight 1: negative edge weights exist in the 2nd and 3rd eigengraphs, indicating more zero crossings (Z²(uz) 1 and ((u)) 2) and higher eigenvector frequencies.
Since node labels correlate with their attributes (Zheng et al. 2022a), and node attribute similarities indicate the extent of smoothness/homophiyy (Luan et al. 2020 2021), plus node attributes can be expressed by eigenvectors, the deviation between eigenvector entry pairs naturally implies the extent of heterophily. Apparently, high frequency eigenvectors and their corresponding eigengraphs have advantage on capturing graph heterophily. High frequency eigengraphs should accordingly take larger weights when modeling heterophilic graphs, while low frequency ones should carry larger weights when dealing with homophilic graphs. In turn, eigengraph weights are controlled by GCN/SGC's depth e.g., for a SGC of depth d, the weight of the i-th eigengraph (1 - xx)%, and changing the layer d of SGC adjusts the weights of different eigengraphs. Therefore, depth d controls the model's expressive power to effectively filter wwwhigh-frequenne signals for graph homophilyyheterrophily.
A question is naturally raised: instead of manually setting the depth d, can d be built into the model as a trainable parameter so that a proper set of the eigengraph weights matching the graph homoohily/heetroohhily can be automatically reached by finding the optimal d in end-to-end fashion during training? Differentiable variables need continuity, which requires the extension of depth from the discrete positive integer domain (N+) to the continuous real number domain IR. According to functional calculus (Shah & Okutmuştur 2020), applying an arbitrary function f on a graph Laplacian Laym is equivalent applying the same function only on the eigenvalue matrix A:
f((1)
[ [(Lsym) = US(AUUT U
U
s(A.))
which also applies to Laym and S. Armed with this, we seek to realize an arbitrary depth SGC via
power function as f($) Sd = Ú(I AJOUT- = Em Au,ū (d R).
However, since A E [0, 2). we have -xa) < when 1 S A, < 2, and
for (1 X,) taking zero or negative val- ues, (1 (1-X,)d is not well-defined or involy- ing cumplex-nnumer-baaeee
calculations for (Shah & Okutmustur 2020). Moreover, even for integer-valued ds under which (1 - ) is easy to compute, the behavior of (1 )d is complicated versus X, and diverges when x, for negative ds, shown in Fig- ure 2a Thus, the favored weight distribu- tion may be hard to obtain by tuning d.
real-valued d (c.g..(-0.5)3
(a) (1 Xyd.
(b) (1
Figure 2: Eigengraph weight versus eigenvalue for (a)
SGC and (b) RED-GCN-S under different depth ds.
4

---

Under review as a conference paper at ICLR 2023
To avoid such complications and alleviate the difficulties for manipulating the eigengraph weights, a transformation function g(-) operating on the graph Laplacian Legm or eym is in need to shift g(>,) or 9(x,) into a proper value range so that its power of real-valued d is easy to obtain and well-behaved versus A; or d; Without the loss of generality, our following analysis focuses on Lag and A There may exist multiple choices for g(.) satisfying the requirements. In this work, we focus on the following form:
= =g ((Leym)) = - - -2mm-
(7)
2
This choice of g(-) holds three properties: (1) Positive eigenvalues. Since we have Leym 's i-th
eigenvalue X E 2). the corresponding eigenvalue of $ is g(>,) = 12 A,) E (0, 1]. Thus, the d-th power of ((A:) is computable for any d E IR. (2) Monotonicity versus eigenvalues X. As shown in Figure 2b g (A,) (1 - 2) is monotonically increasing/decrrasingg when À varies between 0
and 2 under negative/positive depth. (3) Geometric interpretability. Filter Ó can be expressed as:
1 $ UÂUT U(I AJUT I 2 [g-Lm))) 2 (I+ +++ D AAD #).
(8)
As shown in Figure normalization, adding self-loops, and scaling all edge weights by (a type of lazy random walk (Luan et al. 2020)), while $ in vanilla GCN/SGC contains 2 operations: adding self-loops and normalization.
in spatial domain, $ is obtained via 3 operations on adjacency matrix A:
With the help of transformation g. the depth is redefined on real number domain, and the message propagation process of depth d can be realized via the following steps: (1) Eigen-decompose Laym (2) Caleulate $d via weight g(,,) and the weighted sum of all eigengraphs: Sa UÁ
(e: (3) Multiply Sd with original node attributes X. Negative depth explained. An intuitive expla- nation of negative d can be obtained from the perspective of matrix inverse and message diffu- sion process when d takes integer values. Since S = UÁ UT UÂ = I, $-1 is the inverse matrix of S. In diffusion dynamics, X can be viewed as an intermediate state generated in a series of message propagation steps. Sx effectively propagates the message one-step for- ward, while $-1 can cancel the effect of S on X and recover the original message by moving backward: S- X. Accordingly, $-1X
RAD
D
S
O P2
Figure 3: The difference between S (left) for GCN/SGC and $ (right) for RED-GCN.
traces back to the message's 's previous state in the series. However, neither A or L has inverse due to their non possiiiiive cigenvalues. More discussions on the impact of negative depth in spatial domain are presented in Section 4.4. Non-integer d indicates the back- or forward propagation can be a continuous process.
RED-GCN-S. By further making a trainable parameter, we present our model, Redefined Depth- GCN-Single (RED-GCN-S), whose final node embedding matrix is given by
= XW))
where (-)) is the nonlinear activation function: W is trainable parameter matrix; and d is the trainable depth parameter. As observed from Figure 2b weight distribution of different frequen- cies/eigengraphs is tuned via d: (1) for d 0, the weight is uniformed distributed among all frequency components (A,)) 1), which implies that no particular frequency is preferred by the graph signal; (2) for 0, weight g(,.) decreases with the corresponding frequency, which indicates the low frequency components are favored that RED-GCN-S effectively functions as a low-pass filter and therefore captures graph homophily; (3) for d < 0, high frequency components gains amplified weights so that RED-GCN-S serves high-pass filter capturing graph heterophily. During train- ing, RED-GCN-S tunes its frequency filtering functionality to suit the underlying graph signal by automatically finding the optimal d.
RED-GCN-DD During optimization, graphs and selects its preferences for either homophily heterophily. However, RED-GCN-S
embraces a single depth d unified for all eigen-
5

---

Under review as a conference paper at ICLR 2023
requires full dige-ddccoppoitioon of Legm, which can be expensive for large graphs. Additionally, the high and low frequency components in a graph signal may not be mutually exclusive, namely, there exists the possibility for graph to simultaneously possess homophilic and heterophilic coun- terparts. Therefore, we propose the second variant of RE.D-GGN: RED-GGN-D (Dual), which introduces two separate trainable depths, da and d; to gain more flexible weighting of the high and low frequency related cigengraphs respectively. Arnoldi method (Lehoucq et al.) 1998) is adopted to conduct EVD on Laym and obtain the top-K largest and smallest eigen-pairs (A;, u.)s. By denoting
U, U : K] and U2 Ulin n matrix Suaat (dt; da, K) as
K= n| (Uz and Un R=*K), we define new diffusion
Sduat (di, dn, K) U, + UUANAU
(10)
where A, E RKKK and An E RRKK are diagonal matrices of the top- smallest and largest eigenvalues. p The final node embedding of RED-GGN-D is presented as
H = (Sduat d,. K)XW).
(11)
where depths di and da are trainable; and W is a trainable parameter matrix. We make RED-GCN-D scalable on large graphs by choosing K < n. so that S (dy, d,. K) approximates the full diffusion matrix by covering only small subset of all eigengraphs. For small graphs, we use K | to include all eigengraphs, and (d,, d,, K) thus gains higher flexibility than S with the help of the two separate depth parameters instead of unified one.
Differences with ODE-based GNNs. Previous attempts on GNNs with continuous diffusion are mostly inspired by graph diffusion equation, an Ordinary Difference Equation (ODE) characterizing the dynamical message propagation process versus time. In contrast, our framework starts from discrete graph convolution operations without explicitly involving ODE. CGNN (Xhonneux et al. 2020) aims to build deep GNN immune to -moothing by adopting the neural ODE framework (Chen al., 2018). But its time parameter t is a non- non-trainable hyper-parameter predefined within the positive domain, which is the key difference with RED-GCN. A critical CGNN component for preventing over-smoo restart distribution (the skip connection from the first layer), is not needed in our framework. Moreover, CGNN applies the same depth to all frequency components, while RED-GCN-D has the flexibility to adopt two different depths respectively to be adaptive to high and low frequency components. GRAND (Chamberlain lain et al. 2021) introduces non-Eular multi-step schemes with adaptive step size to obtaín more precise solutions of the diffusion equation. Its depth (total integration time) is continuous but still predefined/non -aatee//oo-trraiaalle and takes only positive values. DGC (Wang et al. (021)) decouples the SGC depth into two prefinded non-trainable hyper-parameters: positive real-valued 7' controlling the total time and a positive integer-valued Kdge corresponding to the number of diffusion steps. However, realizing negative depth in DGC is non-applicable since the implementation is through propagation by Kage times, rather than through an arbitrary real-valued exponent d on eigengraph weights in RED-GCN.
4 EXPERIMENT
In this section, we evaluate the proposed RED-GCN on the semi-supervised node classification task on both homophilic graphs and heterophilic graphs.
4.1 EXPERIMENT SETUP
Datasets. We use 1I datasets for evaluation, including 4 homophilic graphs: Cora Kipf & Welling
2016), Citeseer (Kipl & Welling 2016), Pubmed (Kipl & Welling 2016) and DBLP (Bojchevski &
Günnemann] 2017). and 7 heterophilic graphs: Cornell (Pei et al. 2020). Texas (Pei et al.. 2020).
Wisconsin (Pei et al. 2020). Actor (Pei al. 2020), Chameleon (Rozemberezki et al. 2002 Squirrel (Rozemberczki et al. 2021). and cornell5 (Fey & Lenssen 2019). We collect all datasets from the public GCN platform GrooericGe (Fey & Lenssen] 2019). For Cora, Citeseer, Pubmed with data splits in Welling 2016). For the remaining 8 datasets, we randomly split every dataset into 20/20/60% for training, validation, and testing. The statistics of all datasets are presented in Appendix.
we keep the training/valiiatiinnn validaaioon/eestnng set split as in GCN (Kipf &
"CCaee X, 2, namely g(Ax) is excluded since corresponds to the existence of bipartite components.

---

Under review as a conference paper at ICLR 2023
Baselines and Metries. We compare model with 7 baseline methods.includdin 4 classic GNNs: GCN (Kipf & Welling 2016). SGC (Wu et al. (019). APPNP (Kliepera et al. 2018) and ChebNet (Defferrard et al. (016)) and 3 GNNs tailored for heterophilic graphs: FAGCN (Bo et al. 202I),
GPRGNN (Chien et al. 2020) and H2GCN (Zhu et al. 2020). Accuracy (ACC) is used as the evaluation metric. We report the average ACCs with the standard deviation (std) for all methods, each obtained by 5 runs with different initializations.
Implementation Details. See Appendix due the page limit.
4.2 NODE CLASSIFICATION
The sumi-superrised node classification performances on homophilic graphs and heterophilic graphs are shown in Table I and Table respectively.
Homophilic graphs. From Table I is observed that different methods have similar performance on homophilic graphs. RED-GCN-S achieves the best accuracies on two datasets: Cora and DBLP. On the remaining two datasets, RED-GCN-S only 1.1% and 0.4% below the best baselines (APPNP on Citeseer and SGC on Pubmed). For RED- GCN-G, it obtains similar performance as the other methods, even though only uses the top-K K largest/smallest eigen-pairs.
Table 1: Performance comparison (mean=std accuracy) on homophilic graphs
Datasets
Cora
Citeseer
Pubmed
DBLP
GCN
80.800.8
70.5:0.6
788840.6
84.120.2
SUC
8099:0.4
70.::0.88
79.6:0.4
84.120.2
$1.011.0
71.910.4
79.3:10.2
83.010.5
GPRGNN
82.0+0.7
69.34:0.9
78.620077
84.5+0.3
FAGCN
80.31:0.4
71.7100.8
78.51.0.9
82410.7
H2GCN
7.881.00
7.05
77.910.3
82.40033
ChebNet
78.810.5
7111:0.4
78.11:0.8
83.120.1
1.1
70.8:0.7
79.2.10.2
8..7
RED-GCN-D
82.4 00.7
70.6 #0.6
77.9 #0.3
84.2+0.2
Table 2: Performance comparison tsd accuracy) on heterphilic graphs.
Dalmett
Texas
Comeel
Wisconsin
Actor
Squirre
Chameleon
comeel5
GCN
35,923.1 4
1..
51.4+2.2
0..
1..8::133
58,2+1.8
67.9=0.2
SGC
58.7433.1
43.81:4.4
47.312.1
28.0.1..8
1..24..8
1..311..0
67.4-0.5
APPNP
55.1+3.77
$1.5+2.4
58.043.1
3288:0.8
29.5::0.9
46.72:088
68.3=0.5
GPRGNN
61.3 #5.8
53.34-1.
71.04:888
34.1+110
55.0+3.9
67.3=0.3
FAGCN
60.2:1.88
$4.817.4
60.115.2
32.3:1..5
31221:16
50.411.9
68.3:0.77
H2GCN
68.8.6..5
69.915.3
13.910.3
30.110099
4.9
68.4-..2
ChehNet
76.2422.9
66.743.9
75.4+3..5
34.3+005
31.8:0055
49.6+t
0OM
RED GCN.S
77.615.9
72.015.8
82.012.6
35.3.10.7
38.2.11.2
56.7
68.5
RED-GCN-D
77.1 42.55
72.0
27.6
44.2:0.9
$6.920099
70.0:10.2
Heterophilic graphs. graphs, as shown in Table 2 These results demonstrate that without manually setting the model depth and without the prior knowledge of the input graph, RED-GGT has the capability of automatically detecting the underlying graph heterophily. We have interesting observation: 3 large datasets, Squirrel, Chameleon, and cornel15, even with only a small portion of the eigengraphs, RED-GCN-D able to achieve better performance than RED-GCN-S with the complete set of eigengraphs. This suggests that the graph signal in some real-world graphs might be dominated by a few low and high frequency components, and allowing two independent depth parameters RED-GCN-D brings the flexibility to capture the low and high frequencies at the same time.
DOD--GNN-SRRE--GGEO
outperforms every baseline on all heterophilic
4.3 TRAINABLE DEPTH
systematic study conducted on the node classification performance w.r.t the trainable depth d.
Optimal depth. In Figure the optimal depths and their corresponding classification accuracies are annotated. For two homophilic graphs, Cora and Citeseer, the optimal depths are positive (5.029 and 3. 3.7) in terms of the best ACCs, while for two heterophilic graphs, Actor and Squirrel, the optimal depths are negative (-0.027 and - -.7751). These results demonstrate our model indeed automatically capture graph heterophily/homophily by finding the suitable depth suppress amplify the relative weights of the corresponding frequency components. Namely, high/low frequency components are suppressed for homophilichhhterophiiii graphs respectively.
7

---

Under review as a conference paper at ICLR 2023
the opt 22 11.4%)
the optimaa (-173224455))
(a) Cora
(b) Citeseer
(C) Actor
(d) Squirel
Figure 4: Node classification accuracy w.r.t the trainable depth d on four datasets: Cora. Citeseer,
Actor and Squirrel. (the optimal d, accuracy) is annotated (e.g. (-0.027, 36.9%) for Actor).
Close to zero depth. For the two homophilic graphs in Figures 4a and 4b sharp performance drop observed when depth d approaches O, since the eigengraphs gain close-to-uniform weights. For the heterophilic Actor dataset, its optimal depth -0.027 is close to as shown in Figure 4c| addition, the performance of RED-GCN-D (27.8 (7.6%) is similar to that of GCN 27)5%), both of which are much worse than RED-GCN-S (35.3%). This result indicates that Actor is special graph where all frequency components have similar importance. Due to the absence of the intermediate frequency components hetween the high- and low-end ones, the performance of RED-GCN-D is severely impacted. For vanilla GCN, the suppressed weights of the high frequency components deviate from the near-uniform spectrum and thus lead to low ACC on this dataset.
4.4 GRAPH AUGMENTATION AND GEOMETRIC INSIGHTS
is especially interesting to analyze what change a negative depth brings the spatial domain and how such change impacts the subsequent model performance. Graph augmentation. By picking the optimal depth d ac- cording to the best performance on the validation set, new diffusion matrix S:1 is obtained. With the optimal d fixed, substituting the normalized adjacency matrix D- ADD in Eq. I by Sd is equivalent to applying the vanilla GCN to a new topology. This topology effectively plays the role of structural augmentation for the original graph. The impact of such augmentation on performance tested on 3 heterophilic graphs: Texas, Cornell and Wisconsin, as shown in Table Apparently, for the vanilla GCN, the performance obtained with this new topology superior over that with the raw input graph: it dramatically brings 20%-30% lifts in ACC. Moreover, the augmented topologies also make vanilla GCN outperform RED-GCN-S and RED-GCN-D on 2 out of the 3 datasets. By nature, the augmented graph is a re-weighted linear combination of the eigengraphs, and its topological structure intrinsically assigns higher weights eigengraphs corresponding higher frequencies, as shown in Figures 5
Table 3: The performance of one-layer
vanilla GCN over the augmented Sd.
Datasets
Texas
Coreell
Wisconsin
GCN
55.9
44.3
51.4
RED-GCN-S
77.6
72.0
82.0
RED-GCN-D
77.1
72.0
81.5
GCN (S")
75.9
72.7
83.4
Geometric properties. To further understand how the topology of Sd with a negative optimal differs from that of S and why the performance is significantly boosted, a heat map of (Ša S) is presented in Figure 6 for Cornell. [] First, the dark red diagonal line in the heat map indicates the weights of self-loops are signif- icantly strengthened in the augmented graph, and a result, in consistency with the previous findings (Zheng et al.) 2022a), the raw node attributes make more contributions in determining their labels. These strengthened self-weights also play the similar role as restart distribution or skip connections (Xhonneux al. 2020) preventing the node embeddings becoming over-smoothed. In addition, there a horizontal line and a vertical line (light yellow line marked by dashed ovals) in the heat map in Figure correspond to the hub node the graph, namely the node with the largest degree, Interestingly, the connections between this node and most other nodes in the graph experience a negative weight change. Therefore, the influence of the
3.0
Figure 5: The weights of eigengraphs w.r.t. eigenval- ues on the augmented diffu- sion matrix Sd and original $ for Cornell (d = 00.322).
Heaat maps for Texas and Wisconsin in Appendix with similar observations.
8

---

Under review as a conference paper at ICLR 2023
hub node most other nodes systematically reduced. Consequently, the augmentation amplifies the deviations between node embeddings and facilitates the characterization of graph heterophily.
RELATED WORKS
Graph Convolutional Network (GCN), GCN models can
be mainly divided into two categories: (1) spectral graph convolutional networks and (2) spatial convolutional net-
works. In (1), Spectral CNN (Bruna al. 2013) borrows the idea from convolutional neural network (Goodfellow
et al. (016) to construct a diagonal matrix the convo-
lution kernel. ChebNet (Defferrard et al. (016) adopts a polynomial approximation of the convolution kernel. GCN
00
(Kipf & Welling 2016) further simplifies the ChebNet via
the first order approximation. Recently, (He et al.) 2021
125
Bianchi et al. 2021; Wang & Zhang]] 2022) propose more
150
0.5
advanced filters as the convolution kernel. Most works
(2) follow the message-passing mechanism. GraphSAGE (Hamilton et al., 2017) iteratively aggregates features from local neighborhood. GAT Veličkovié et al. 2017) applies self-attention to the neighbors. APPNP (Klicpera et al.)
175
-10
25
1.0
125
130
175
Figure 6: The difference between the augmented diffusson matrix and the orig- inal one Sá - S for Cornell in heat map. Best viewed in color.
2018) deploys personalized pagerank (Tong et al. 20066 to sample nodes for aggregration. MoNet (Monti et al. 2017 unifies GCNs in the spatial domain.
The Depth of GCN and Over-smoothing. A large amount of works focus on the over-smoothing issue. Its intrinsic cause is demystified: a linear GCN layer is Laplacian smoothing operator (Li ctt al. 22188) [Wu et al. 2019). PairNorm (Zhao & Akoglu 2019) forces distant nodes to be distinctive by adding an intermediate normalization layer. Dropedge (Rong et al. 2019), DeepGCN (Li et al. 2019), AS-GCN (Huang et al. 2018), and JK-net (Xu et al. 2018) borrow the idea of ResNet (He al. 2016) to dis-intensify smoothing. DeeperGXX (Zheng al. 202T) adopts topology-gun guided graph contrastive loss for connected node pairs to obtain discriminative representations. Most works aim to build deep GCNs (i.e., d is a large positive integer) by reducing over-smoothing. while RED-GCN extends the depth from N+ to R and explores the negative depth.
Node Classification on Homophilic and Heterophilic Graphs. GCN/GNN models mostly follow the homophily assumption that connected nodes tend to share similar labels (Kipf & Welling 2016 Veličković et al., 2017 Hamilton et al. 2017). Recently, heterophilic graphs, in which neighbors often have disparate labels, attract lots of attention. Geom-GCN (Pei et al., (020) and H2GCN (Zhu et al.
2020) extend the neighborhood for aggregation. FAGCN (Bo et al. (021]) and GPRGNN (Chien
2020 adaptively integrate the high/low frequency signals with trainable parameters. Alternative
mnessage-passing mechanisms have been proposed in HOG-GCN (Wang & Zhang 2022) and CPGNN
(Zhu et al. 2021). The latest related works include ACM-GCN (Luan et adl.:22222222 [021] LINKX
(im et al. 2021), BernNet (He et al. (02I), GloGNN (Li et al. 2022) and GBKGNN (Du et al.
2022).
Other works can be found in a recent survey (Zheng et al. 2022b
6 CONCLUSION AND FUTURE WORK
To our best knowledge, this work presents the first effort to make GCN's depth trainable by redefining it on the real number domain. We unveil the interdependence between negative GCN depth and graph heterophily. A novel problem of automatic GCN depth tuning for graph homophilyhectroopily detection is formulated, and we propose a simple and powerful solution named RED-GCM with two variants (RED- DCD-- and CED-GCN-AN via the new understanding on the message propagation mechanism generated by the negative depth. Superior performance of our method is demonstrated via extensive experiments with semi-supervised node classification on 11 graph datasets. The new insights on GCN's 's depth obtained by our work may open new direction for future research spectral and spatial GNNs. Since RED-GCN requires to conduct sigem-dcoomositionn of the graph Laplacian, it is not directly applicable to inductive and dynamic graph learning problems, which we leave for future exploration.
An effective graph augmentation method is also discussed

---

Under review as a conference paper at ICLR 2023
REFERENCES
Filippo Maria Bianchi, Danicle Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters, IEEE Transactions on Pattern Analysis and Machine Intelligence. 2021.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low- wwwfrequency information in graph con- volutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950-3957, 2021.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv: 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1312.2223 2013.
Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pp. 1407-1418. PMLR, 2021.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International conference on learning representations, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint wrXiv:2006.07988 2020.
Fan RK Chung and Fan Chung Graham. Spectral graph theory, volume 92, American Mathematical Soc., 1997.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk- gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pp. 1550-1558, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. IEEE
Signal Processing Magazine, 30:83-98, 2019.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances Neural Information Processing Systems, 34:14239-14499 2021.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph
representation learning. Advances in neural information processing systems, 31, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609v 1609.02907, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 1rXiv:1810.0599) 2018.
10

---

Under review as a conference paper at ICLR 2023
Richard B Lehoueq, Danny C Sorensen, and Chao Yang. ARPACK users' guide: solution of large- scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM, 1998.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference computer vision, pp. 9267-9276, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference artificial intelligence, 2018.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. arXiv preprint M0xv::2005007388 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-hooophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Sitao Luan, Mingde Zhao, Xiao Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. Advances in neural information processing systems, 32, 2019.
Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao Wen Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint arXiv:2008. 2008040000008444 2020.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Wen Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint urXiv:2109.0566 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang, and Doina Precup. When do we need gnn for node classification? arXiv preprint arXiv:2210. 16979, 2022a
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wei Chang, and Doina Precup. Revisiting heterophily for graph neural networks. arXiv preprint arXiv:2210.07600 2022b.
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. 51 5115-5124, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification, arXiv preprint arXiv:1907.10900 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2)cnabb014, 2021.
Kamal Shah and Baver Okutmuştur. Functional Calculus. BoD-Booos on Demand, 2020.
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.
The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Gabriel Taubin. A signal processing approach to fair surface design. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pp. 351-358, 1995.
Hanghang Tong, Christos Faloutsos, and Jia-Yt Pan. Fast random walk with restart and its applications. In Sixth international conference on data mining (ICDM '06), pp. 613-622, IEEE, 2006.
Petar Veličković, Guillem Cucurull, Arantx Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.

---

Under review as a conference paper at ICLR 2023
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks, arXiv preprint arXiv: 2022.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. Advances in Neural Information Processing Systems, 34: 5758-5769, 2021.
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.
Louis-Paseal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In International Conference on Machine Learning, pp. 10432-10441. PMLR, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. PMLR, 2018.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. International conference on machine learning, pp. 40-48. PMLR, 2016.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2019.
Lecheng Zheng, Dongqi Fu, and Jingrui He. Tackling oversmoothing of gnns with contrastive learning. arXiv preprint arXiv:2110. 100.1988, 2021.
Wenqing Zheng, W Edward Huang. Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node represen- tations with incomplete missing neighbor- hoods. In International Conference on Learning Representations, 2022a.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07080 07082, 2022b.
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 in Neural Information Processing Systems, 33:7793-7804, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11168-11176. 2021.
12


Reviews:
[{"review_id": "npK-j_dZIlN", "reviewer": "Reviewer_Qq6e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of investigating the depth of GNN. The authors propose a novel and interesting method to extend the depth of GNNs from a positive integer to a real value. It is claimed that negative depth enables high-pass frequency filtering functionality for graph heterophily while positive value enables low-pass filter and is to model homophily. Experimental studies have been conducted on both homophilous and heterophilous graphs and the results show that the proposed method can achieve comparable or better performance in both types of graphs compared to baselines.", "summary_of_the_review": "This paper studies an interesting and important problem. Overall this paper is well-organized. Experiments from different aspects have been conducted. Although experimental studies can be further improved by providing more insight into investigations and comparing the proposed method to more representative methods, the method is novel from the methodological perspective and effective from the experimental perspective. Thus, I will recommend a weak acceptance of the paper.", "strength_and_weaknesses": "Strength:\n- Both problems of GNN depth and adaptive GNN for modeling homophily and heterophily are interesting and important. \n- The proposed method to extend positive integer depth to real value is novel.\n- The experimental results of the method demonstrate the effectiveness of the proposed method compared to previous baselines.\n\nWeakness:\n- The claims are based on empirical results and theoretical analysis is not provided.\n- Experimental results demonstrate the effectiveness of the proposed method, it is also important to show the efficiency of the method, e..g, presenting the complexity or comparing running time.\n- More insights can be provided to better show the correlations between homophily/heterophily and positive/negative depth, for example, analyzing the learn representations rather than just reporting the overall classification accuracy in the downstream task.\n- The size of the benchmark dataset is relatively small to show the ability of generalization. I suggest conducting experiments on larger datasets such as OGB.\n- In the experimental studies, some representative methods can be compared including (1) GAT, as an attention method, and (2) some recent work on adaptive GNN for modeling homophily and heterophily, for instance, GBK-GNN [1].\n\n\n[1] GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mmNvqhhZ5fF", "reviewer": "Reviewer_gHVm", "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 a novel graph convolutional network to address the over-smoothing and heterophily issue. The proposed model is equipped with a trainable depth parameter $d$ and a selection of the spectrum of the graph signal. Based on such modeling, this paper discovers a connection between negative GCN depth and graph heterophily. The experimental results on 11 graph datasets show the proposed model outperforms baseline methods.", "summary_of_the_review": "I recommend a weak reject for this paper because of its limited novelty and the lack of analysis of expressive power.", "strength_and_weaknesses": "Strengths,\n\nS1: This paper models the depth of GCN as a trainable parameter by eigen decomposition.\n\nS2: Experiments validate the effectiveness of the trainable depth, especially negative depth for disassortative graphs.\n\nWeaknesses,\n\nW1: Adaptive and continuous depth is not new for GCN, e.g., in Graph Neural Diffusion (GRAND).\n\nW2: Negative depth may not be a correct choice, which loses most of the topology information.\n\nW3: This paper does not analyze the expressive power of the proposed model. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "KmFmhfyHq6P", "reviewer": "Reviewer_NDJu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors define GCN’s depth as a trainable continuous parameter within (−∞,+∞) and propose RED-GCN which can automatically search for the optimal depth without the prior knowledge regarding whether the input graph is homophilic or heterophilic.", "summary_of_the_review": "This is a borderline paper and if the authors can address my concerns satisfactorily, I will consider raise my score.", "strength_and_weaknesses": "## Strength\nThe idea of setting the depth as trainable continuous value and the concept of eigengraph are interesting.\n\n## Weaknesses\n1. The writing needs to be improved.\n2. Some experiments and comparisons are missing.\n\n\n## Questions and Comments\n\n1. “Apparently, high frequency eigenvectors and their corresponding eigengraphs have advantage on capturing graph heterophily” This is not apparent, need more explanation.\n\n2. “High frequency eigengraphs should accordingly take larger.  weights when modeling heterophilic graphs, while low frequency ones should carry larger weights when dealing with homophilic graphs.” This is similar as [5]. \n\n3. Equation (7) is actually lazy random walk affinity matrix and see [5] for the generalized lazy random walk matrix.\n\n4. Red-GCN is essentially a linear model without any non-linearity?\n\n5. The reported results of FAGCN, GPRGNN and H2GCN in table 2 are not the same as the results in the original papers and not consistent with my personal experience.\n\n6. Some missing comparisons, e.g. ACM-GCN [1], LINKX [2], BernNet [3] and GloGNN [4].\n\n[1] Luan S, Hua C, Lu Q, et al. Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?[J]. arXiv preprint arXiv:2109.05641, 2021.\n\n[2] Lim D, Hohne F, Li X, et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods[J]. Advances in Neural Information Processing Systems, 2021, 34: 20887-20902\n\n[3]  He M, Wei Z, Xu H. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation[J]. Advances in Neural Information Processing Systems, 2021, 34: 14239-14251.\n\n[4] Li X, Zhu R, Cheng Y, et al. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily[J]. arXiv preprint arXiv:2205.07308, 2022.\n\n[5] Luan S, Zhao M, Hua C, et al. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks[J]. arXiv preprint arXiv:2008.08844, 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DgG8Rbrcm_", "reviewer": "Reviewer_ZTa3", "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": "In this work, by redefining GCN’s depth d as a trainable parameter continuously adjustable within positive infinity and negative infinity, a simple and powerful GCN model RED-GCN is proposed to retain the simplicity of GCN and meanwhile automatically search for the optimal d without the prior knowledge regarding whether the input graph is homophilic or heterophilic.", "summary_of_the_review": "The problem is interesting and the proposed method is novel. But the physical meaning of negative results is not clear.", "strength_and_weaknesses": "Strength: The problem is interesting and usefull for GCN designing.\nWeaknesses: The motivation and the physical meaning of the negative depth value are not clear. When the depth of GCN is negative, what dose it mean?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject