From Trainable Negative Depth to Edge Heterophily in Graphs
Authors: Yuchen Yan
Yuzhong Chen
Huiyuan Chen
Minghua Xu
Mahashweta Das
Hao Yang
Hanghang Tong
Venue: NeurIPS 2023 poster (2023)
Keywords: graph convolutional network

Abstract: Finding the proper depth $d$ of a graph convolutional network (GCN) that provides strong representation ability 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 signal processing capability to model graph homophily/heterophily (nodes with similar/dissimilar labels/attributes tend to be inter-connected). A simple and powerful GCN model TEDGCN, 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 via augmented topology for graph heterophily. Extensive experiments demonstrate the superiority of TEDGCN on node classification tasks for a variety of homophilic and heterophilic graphs.

From Trainable Negative Depth to Edge Heterophily in Graphs
Yuchen Yan', Yuzhong Chen', Huiyuan Chen', Minghua Xu?, Mahashweta Das Hao Yang", Hanghang Tong' University of Illinois at Urbana Champaign, IL, USA
2 Visa Research, CA, USA {yucheny5, htong/@illinois edu fyuzchen, hchen, mixu, mahdas, (ooyang)@visaa com
Abstract
Finding the proper depth of a graph convolutional network (GCN) that pro- vides strong representation ability has drawn significant attention, yet nonetheless largely remains an open problem for the graph learning community. Although noteworthy progress has been made, the depth the number of layers of cor- responding GCN is realized by series of graph convolution operations, which naturally makes d positive integer (d E N+). An interesting question whether breaking the constraint of N+ by making d real number (d E 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 (-o0, +oo), we open a new door of controlling its signal processing capability to model graph homoohill/heterophily (nodes with similar/dissimilar labels/attributes tend to be enter-connecte),. simple and powerful GCN model TEDGCN, 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- Negative-valued d intrinsically enables high-pass frequency filtering functionality via augmented topology for graph heterophily. Extensive experiments demonstrate the superiority of TEDGCN on node classification tasks for variety of homophilic and heterophilic graphs.
Introduction
Graph convolutional network (GCN) 28
50 19
47
has exhibited superb power in myriad of
36], network alignment networked time series 3 and many more. Since the representation capability of GCN largely determined by its depth, i.c., 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: GCN's performance is deteriorated if its depth exceeds a certain threshold (28 It found in 32) that graph convolution operation is special form of Laplacian smoothing 48 Thus, the similarity between the graph node embeddings grows with the depth so that these embeddings eventually become indistinguishable. Various techniques have been developed alleviate this issue, e.g., applying pairwise normalization can make distant nodes dissimilar [69], and dropping sampled edges during training slows down the growth of embedding smoothness the depth increases 43
graph learning tasks, such as knowledge graph reasoning 56
53
54
52
63
68
74
20
35
67 multi-network mining 66
73
13
27
imputation 51
25
55
16 node recommendation 26 2
Other than the over-smoothing issue due to a large GCN depth, another fundamental phenomenon widely existing real-world graphs is homophily and heterophily. homophilic graph, nodes with
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

similar labels or attributes tend to be inter-connected. while in a heterophilic graph, connected nodes usually have distinct labels or dissimilar attributes. Most graph neural networks (GNNs) are developed based on the homophilic assumption [66]. while models able to perform well on heterophilic graphs often need special treatment and complex designs 4 76 [2]. 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 almost any GNN model, the depth needs to be manually set as a hyper-parameter before training, and finding the proper depth usually requires considerable amount of trials or 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 of whether a non non-integer depth is realizable, and if yes, whether it is practically meaningful, and what kind of unique advantages it can bring to current graph learning mechanisms.
This work revisits the GCN depth from spectral and spatial perspectives and explains the intrinsic connections between the following key ingredients in graph learning: (i) the depth of a GCN, (ii) the spectrum of the graph signal, and (iii) the homophilyhhetcrophily of the underlying graph. Firstly, through cigen-decomposition of the symmetrically normalized graph Laplacian, we present the connection between graph homophily/heterohhi introducing the concept of eigengraph, we show the graph topology equivalent linear combination of cigengraphs, and the weights determine the GCN's capability of capturing ho- mophilic/heterophilic graph signals. Thirdly, we reveal that the eigengraph weights can be controlled by GCN's depth, so that an automatically tunable depth parameter is needed to adjust the eigengraph weights into the designated distribution in match of the underlying graph homophily/heteroohhly
and the eigenvector frequencies. Secondly, by weighted
To realize the adaptive GCN depth, we extend its definition from positive integer to an arbitrary real number with theoretical feasibility guarantees from functional calculus 45). With trainable depth parameter, we propose a simple and powerful model, Trainable Depth-GCN (TEDGCN), with two variants. Extensive experiments demonstrate TEDGCN's ability of automatically searching for the optimal depth, and it is found that negative-valued depth plays the key role in handling heterophilic graphs. Systematical investigation on the optimal depth is conducted via various real- wollw and synthetic datasets. It in turn inspires the development of a novel graph augmentation methodology. With clear geometric interpretability, 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 follows:
Analysis. The intrinsic relationship between the negative GCN depth and graph heterophily is discovered; In-depth geometric and spectral explanations are presented.
Problem. A novel problem of automatic GCN depth tuning for graph homophily/heteropphe detection is formulated. To our best knowledge, this work presents the first trial to make GCN's depth negative and trainable by redefining on the real number domain.
Model. A simple and powerful model TEDGCN with two variants (TEDGCN-S and TEDGCN-D) is proposed. A novel graph augmentation method is discussed.
Experiments. Our model achieves superior performance on semi-supervised node classifi- cation tasks on 11 graph datasets.
2 Preliminaries
Notations. We utilize bold uppercase letters for matrices (c.g., A), bold lowercase letters for column vectors (e.g., u) and lowercase letters for scalars (e.g., a). We use the superscript T for the transpose of matrices and vectors (e.g., A T and u ). An attributed undirected graph g = {A, X) contains an adjacency matrix A E x and an attribute matrix X E Rx with the number of nodes and the dimension of node attributes q. D denotes the diagonal degree matrix of A. The adjacency matrix with self- is given by A = A + I (I is the identity matrix), and all variables derived from A 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 (44)

---

$ = =AD" 7
eigengraph 1
eigengraph 2
eigengraph 3
V1
Pa
Pa
normaliation
1-4 L.
1-
2 04
Figure 1: Decompose the symmetrically normalized adjacency matrix into three eigengraphs.
Graph convolutional network (GCN) and simplified graph convolutional network (SGC). The layer-wise message-passing and aggregation of GCN [28] is given by
H (++1) o (D AD
H 4 w()),
(1)
where H H (d+1) stands for the embedding matrix (H (0) X) in the d-th/(d + 1)-th layer; W(4) the trainable parameter matrix; and or-) the non-linear activation function. With (()) removed in each layer, SGC [59] is obtained as below:
SW.
(2)
where $ D Ä and the parameter of each layer (()) are compressed into trainable W(9,
W
Graph Laplacian and spectrum. In graph theory, graph Laplacian L = D and its symmetrically
normalized correspondence Lyym = D AD possess critical properties of the underlying
graph g. Lyy has eigenvalues [Λg, A An). where \ E [0, 2). vi E f1.2..... < A, 2. It can be eigen-decomposed as: Laym = UAUT, where U = [ui U2,.... un] is the eigenvector matrix (u, U,, Vi & j), and is the diagonal eigenvalue matrix. For each eigenvector u, we have u,u E RRnx. As we will show in Section 3 this
Here,
they are put in the ascending order: 0 X1 X2
matrix can be viewed as the weighted adjacency matrix of a graph with possible negative edges, which we name as the i-th eigengraph of G. Accordingly, Laym can be written the linear combination of all eigengraphs weighted by the corresponding eigenvalues
L sym \ n +... + nnn +... An u.
(3)
where the first eigenvalue A1
46) Thus, for SGC, have
= L sym
ū(I - ÁJÜT 11-Aaa.
(4)
1=0
SGC with layers requires d consecutive graph convolution operations, which involves the multiplication of S by times. Due the orthogonality of U, namely, Ü Ú I, we obtain
= -IU ÂJŪT Ū(I ÁJÚJ = Ú(I - A
(1
Aū,ū, (5)
where 1 1- E E 11, and the depth d of SGC serves as the power of S's eigenvalues. Sd can be viewed as the sum of eigengraphs ü,ū weighted by coefficients (1 (1)
Graph homophily and heterophily. Various homophillyhhetrrohiily measures are developed to capture how edges tend to link nodes with the same labels and similar attributes, such as
edge homophily [
76 75 37], node homophily[4I] and class homophily Without the loss of generality, we focus on one mostly used homophily metric, the edge homophily: h(g)
EL (xl)==b))) E [0, 1], where (z) = 1 if x is true and 0 otherwise. A graph is more Erg Abdl
homophilic for (()) closer to or more heterophilic for h(g) closer to 0.
'This work focuses on connected graph without bipartite components (i.e., connected component which is bipartite graph).

---

3 Model
Overview. Firstly, we establish the intrinsic relationship between graph spectrum and graph het- erophily. Secondly, we show how the positive/negative depth d of GCN affects the eigengraph weights which in turn impacts the algorithm's ss capability to capture homophilichheerophiiii graph signals. Thirdly, with the help of functional calculus [45, we present the theoretical feasibility of extending the domain of d from N+ to IR. Finally, by making d a trainable parameter, we present our model TEDGCN and its variants, which are capable of automatically detecting the homophily/heterophily of the input graph and finding the optimal depth.
Eigenvector frequency and entry deviation. The frequency of graph Laplacian eigenvector u, reflects how much the j-th entry [ن] deviates from the k-th entry u, [K]] for each connected node pair "y and un in G [46]. This deviation is measured by the set of zero crossings of u,: 2(u,) == {e
(15, vx) E & n. j [A] < 0. * k), where & is the set of edges in graph G. Larger/smaller |2 (u.)) indicates higher/lower eigenvector frequency. A zero-crossing also corresponds a negative weighted edge in an eigengraph. Due to the widely existing positive correlation between A, and [Z(u,)] [46). large/small eigenvalues mostly correspond to the high/low frequencies of the related eigenvectors. As illustrated by the toy example of n = in Figure I for A = O, we have |Z(u))] = 0, and eigengraph u, i fully-connected; negative edge weights exist in the 2nd and 3rd eigengraphs. indicating more zero crossings (12(l)) 1 and [uu)) 2) and higher eigenvector frequencies.
Entry deviation and graph heterophily. Reflected by entry deviations, eigenvector frequency and zero-crossings determine the number of negatively weighted edges [kk] < 0, j # k) in corresponding eigengraph u,u." For a GCN/SGC, conducting peessage-passingg along negatively weighted edges makes the embeddings of the connected node pairs (uz. v%.) dissimilar. Naturally, higher embedding dissimilarity is more likely to render different label predictions between the node pair, and this generates heterophily. Thus, eigenvectors with higher frequencies and accordingly higher entry deviations contribute more to heterophilic graph signals, and vice versa.
Graph heterophily and GCN's depth. Based on above analyses, high frequency eigenvectors and their corresponding eigengraphs have advantage on capturing graph heterophily. A graph neural network should be able to give high frequency eigengraphs larger weights when modeling heterophilic graphs, whereas low frequency ones should carry larger weights when dealing with homophilic graphs The weights of eigengraphs are controlled by GCN/SGC's depth d as follows. For SGC of depth d, the weight of the i-th eigengraph is (1 - X)d, and changing the depth d of SGC adjusts the weights of different eigengraphs. Therefore, depth d controls the model's capability of effectively filtering low/high-frequency signals for graph hhhoopilyylhtterphilly.
Redefined GCN's depth. A question is naturally raised: instead of manually setting the depth d, can d be built into the model as a trainable parameter? If yes, proper set of the eigengraph weights matching the graph honophilyyhettrophily can be automatically reached by finding the optimal d in an 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 R. According to functional calculus (45). applying an arbitrary matrix function f on graph Laplacian Laym is equivalent to applying the same function only on the eigenvalue matrix A:
f(A))
[[Lsym) =f(A) U
UT.
(6)
f(An)]
which also applies to Laym and Š. Armed with this, we seek to realize an arbitrary depth SGC via a power function as /($) Sd = Ū(I Á = E' - X,) ū. (d E IR). However, since A, E |0, 2). we have (1 (1- ),) < 0 when 1 s A < 2, and for (1 - x.) taking zero negative values, (1 - -,) d is not well-defined involving complex- maanlee-number-baaede calculations for real-valued d (e.5-.-0.55))
45 Moreover, even for integer- valued ds under which (1 Xx) is easy to compute,
the behavior of (1 X,)d is complicated versus X, and diverges when X, = for negative ds, as
shown in Figure 2a Thus, the favored weight distribution may be hard to obtain by tuning d.

---

To avoid such complications and alleviate the difficulties for manipulating the eigengraph weights, a transformation function g(-) operating on the graph Laplacian Lyym or sgm is in need to shift g(>e) 9(ù,) into proper value range that its power of real-valued d is easy to obtain and well-behaved versus X or X₁ Without the loss of generality, following analysis focuses on Laym and A, There may exist multiple choices for g()) sat- isfying the requirements. In this work, focus on the following transformation function:
1 (21 (2I- Laym)) (7)
= ((syym))
This choice of g(-) holds three properties:
(1) Positive eigenvalues. Since we have
Laym's 's i-th eigenvalue X; [0, the
corresponding eigenvalue of S is g(A,) 1 >x) (0, I]. Thus, the d-th power of ((a)) is computable for any d E R. (2) Monotonicity versus eigenvalues X. As shown in Figure 2b ((A,)'
05
(a) (1 X)
(b) 11)
A) is monotonically increasing/decreasing when À varies between O and 2 under nega- tive/positive depth. (3) Geometric inter-
Figure 2: Eigengraph weight versus eigenvalue for (a)
SGC and (b) TEDGCN-S under different depth ds.
pretability, Filter S can be expressed as:
1 1 I L.-ms (I+ 4). 2
$ = UAU U(I AJUT
(8)
As shown in Figure in the spatial domain. $ obtained via 3 operations on adjacency matrix A: normalization, adding self-loops, and scaling all edge weights by 2 (a type of lazy random walk 39 while $ in vanilla GCN/SGC contains 2 operations: adding self-loops and normalization.
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 Leymi
(2) Calculate Std via weight (A,,)* )d and the weighted sum of all eigengraphs: Sat UA'UT
E (',) u, (3) Multiply Sa with original node attributes X.
Negative depth explained. First, an intuitive explanation of negative d can be obtained from the perspective of matrix inverse and message diffusion process when d takes integer values. Since $-1$ = UÁ -'UT UÂ'UT = I, $-1 is the inverse matrix of S. In diffusion dynamics, X can be viewed as an intermediate state gen- erated in series of message propagation steps. SX effectively propagates the message one-step forward, while $-1 can cancel the effect of Ó X and recover the original message by moving backward: $- S šx = X. Accordingly, S traces back the message's previous state in the series. Non-integer d indicates the back- or forward propagation can be continuous process. Second, as the depth becomes negative, it primarily keeps the eigengraphs of high frequency (See Figure(b, which have more negative edges. Therefore, it is equivalent to turning some positive edges in the original graph into negative edges in the augmented graph, which turn makes node embeddings dissimilar in the pessage-passing process and thus naturally handles the heterophilic graphs (See Figure IT. More discussions on the impact negative depth spatial domain are presented in Section
D FAD
O:S
Figure 3: The difference between Š (left) for GCN/SGC and S (right) for TEDGCN.
TEDGCN-S algorithm. By further making d a trainable parameter, we present our model, Trainable Sypth-GCN-Singlee (TEDGCN-S), whose final node embedding matrix is given by
H (S XW),
(9)
5

---

where a--) 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 = O, the weight is uniformly distributed among all frequency components (g(A.) = 1), which implies that no partieular frequency is preferred by the graph signal; (2) for O, weight g(A:) decreases with the corresponding frequency, which indicates the low frequency components are favored so that TEDGCN-S effectively functions as low-pass filter and therefore captures graph homophily; (3) for d < O, high frequency components gains amplified weights so that TEDGCN-S S serves as a high-pass pass filter capturing graph heterophily, During training. TEDGCN-S tunes its frequency filtering functionality to suit the underlying graph signal by automatically finding the optimal d.
TEDG algorithm. During optimization, TEDGCN-S embraces single depth d unified for all cigengraphs and selects its preferences for either homophily or heterophily. However, TEDGCN-S requires full cigen-decomposition of Laym. which can be expensive for large graphs. Additionally, the high and low frequency components in graph signal may not be mutually exclusive, namely, there exists the possibility for graph to simultaneously possess homophilic and heterophilic counterparts. Therefore, we propose the second variant of TEDGCN: TEDGCN-D (Dual), which introduces two separate trainable depths, dn and d; to gain more flexible weighting of the high and low frequency related eigengraphs respectively. Arnoldi method [30] is adopted to conduct EVD on sym and obtain the top- largest and smallest eigen-pairs (A,; u.)s. By denoting U,- U(; : K] and
U, = Ui: n - K : n] (U, and U E RR*K)), we define a new diffusion matrix Saual (di, dn, K) as
Saual (d1, dn, K) U, + UUAAN
(10)
where À kxx and As E K are diagonal matrices of the top-K smallest and largest eigenvalues The final node embedding of TEDGCN-D is presented as
H = aSSsuat dr, K))
(1I)
where depths di and da are trainable; and W is a trainable parameter matrix. We make TEDGCN-D scalable on large graphs by choosing K < so that Sauat (di, da. K) approximates the full diffusion matrix by covering only a small subset of all eigengraphs. For small graphs, we use K = | to include all eigengraphs, and (di, dn, K) thus gains higher flexibility than S with the help of the two separate depth parameters instead of unified one.
Complexity Analysis. TEDGCN has two major steps: (I) conduct iigen-decomposition of A; (2) train a one-layer GCN on the augmented graph Stt For Step (1), naive baggen-decompositiee has a time complexity of O(n²). However, by adopting the Lanczos method [30 and only keeping the top- K largest/smallest eigenvalues in TEDGCN-D, the time complexity can be reduced to O(n + mk) [2], where is the number of edges and K << n. For Step (2), via dense matrix multiplications, computing the approximated Sd takes O(n + k², and conducting message propagation takes O(n²q + nge), where and e denote the dimension of node feature vectors and the number of node classes. Potential improvements of efficiency: since the diffusion matrix in Subsection (f.4 the augmented graph is sparse for known real-world graphs, the complexity of Step (2) can also be further simplified: the O(n K) term can be reduced to O([Eaug K ), where Eoug the edge set of the augmented graph.
Differences with ODE-based GNNs. Previous attempts on GNNs with continuous diffusion 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 [60] aims to build deep GNN immune over-smoothing by adopting the neural ODE framework (9] But its time parameter I is a non-trainable hyper-parameter predefined within the positive domain, which is the key difference with TEDGCN. A critical CGNN component for preventing over-smoothing, 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 TEDGCN-D has the fiexibility to adopt two different depths respectively to be adaptive to high and low frequency components. GRAND g introduces non-Eular multi-step schemes with adaptive step size to obtain more precise solutions of the diffusion equation. Its depth (i.e., the total integration time) is continuous but still
Cass A = 2, namely g(Ac) 0, is excluded since corresponds to the existence of bipartite components.

---

cetttmedddoo-trainnaae and only admits positive values. DGC [58] decouples the SGC depth into two predefined non- trainable hyper- parameerrt a positive real-valued T controlling the total time and positive integer-valle enteger-valued Kdge corresponding to the number of diffusion steps. However, realizing negative depth DGC is non-applicable since the implementation through propagation by Kdge times, rather than through an arbitrary real-valued exponent d on eigengraph weights in TEDGCN.
4 Experiment
In this section, we evaluate the proposed TEDGCN on the semi-supervised node classification task on both homophilic and heterophilic graphs.
4.1
Experiment Setup
Datasets. We use 11 datasets for evaluation, including 4 homophilic graphs: Cora (28). Citeseer
28
Pubmed [28) and DBLP [6] and 7 heterophilic graphs: Cornell [4]] Texas [4]]. Wisconsin
41. Actor [1). Chameleon 44), Squirrel [44]. and cornell5 [15] We collect all datasets from the public GCN platform Pytorch- Geometric [5]] For Cora, Citeseer, Pubmed with data splits in Pytorch-Geomette Geometric, we keep the same training wainiing/vllddtoiootttsnngg set split in GCN (28). For the remaining datasets, we randomly split every dataset into 20/20/60% for training, validation, and testing.
Baselines and metrics. Here, we compare our model with baseline methods, including 4 classic GNNs: GCN (28). SGC (59), APPNP 29 and ChebNet [12. and 3 GNNs tailored for heterophilic graphs: FAGCN [5), GPRGNN [0] and H2GCN [76]. Accuracy (ACC) is used as the evaluation metric. We report the average ACCs with the standard deviation (std) for all methods, each obtained by runs with different initializations.
Additional contents. In Appendix, we provide more contents related to experiments including (1) the statistics of all datasets (Appendix(A.I):: (2) experimental results on synthetic graphs with controllable edge comophily/heterpphhe
levels demonstrate the effectiveness of negative depth (Appendix A.2
(3) comparison with additional methods including ACM-GCN (37 38, LINKX 34 BernNet [22].
GBK-GNN [14. HOG-GCN [57]. Geom-GCN [1] and GloGNN 33 under the commonly used
fully-supervised setting that srining/vallddatoon/essinn set split 48/32/20% for training, validation, and testing based on the results reported in the original papers (Appendix A.3); (4) implementation
details (Appendix A.44); and (5) visualization node embeddings w.r.t. d (Appendix A.5
4.2 Node Classification
The semi-supervised node classification performances homophilic graphs and heterophilic graphs are shown Table and Table 2
respectively.
Homophilic graphs. From Table it is observed that different methods have similar performance on homophilic graphs. TEDGCN-S achieves the best accuracies on two datasets: Cora and DBLP. On the remaining two datasets, TEDGCN-S is only 1.1% and 0.4% below the best baselines (APPNP on Citeseer and SGC on Pubmed), For TEDGCN-D, it obtains similar performance as the other methods, even though it only uses the top K largest/smallest eigen-pairs.
Table 1: Performance comparison (te accuracy (%) )) homophilic graphs.
Datasets SGC
Cora
Citesoer
Pubmed
DBLP
70.34:0.6
78.840.6
$4.120.2
80.9+0.1
7088+00.8
79.6+0.44
84.1=0.2
APENP
81.0+1.0
71910.4
79.34..22
83.0=0.5
GPRGNN
82.0+0.7
69330.9
78.6+0.77
84.5=0.3
BAGCN
80.340.4
71740.88
78.5+:..9
82440.7
H2GCN
7..8+1.0
70.5
71940.3
824-0.3
ChebNet
78.8+0.5
71110044
78.14:0.8
83.1=0.1
TEDGCN-S
82.541.1
70.8:0.77
79.240.22
84.7=0.3
TEDGCN-D
82.4 10.7
70.6 10.6
10.3
84...0.2
Heterophilic graphs. Our TEDGCN-S or TEDGCN-D outperforms every baseline on all het- erophilic graphs, shown in Table 2 These results demonstrate that without manually setting the

---

Table 2: Performance comparison (tean accuracy (%)
heterophilic graphs.
Dalasets
Texas
Coreell
Wisconsin
Aclor
Squirel
Chameleon
comell5
GCN
55.943.1
44.31:1.1
514122
21.54:0.5
35.8 1.38
55.221.8
67.910.2
SGC
58.7413.1
43.81:4.4
47.31.2.1
28.0:10.8
37.24..88
55.31:1.0
67.410.5
APPNP
55.143.77
58.0.3.11
29.510.9
46.7400.8
GPRGNN
45.8
53.3+4.6
71.04488
33.6+0.4
3..1
55,0=3.9
67.3#0.3
FAGCN
60.2.1.88
54.817.44
60.115.2
32.3:10.5
31.2.1.66
50411..9
68.310.7
H2GCN
68.846.5
61444.4
69.95..3
33.940.3
30.40.99
4..8+1.9
68.420.2
ChebNet
76.2422.9
66.7+3.99
33.
34.3=20.5
318+00.5
49.6-11.8
OOM
TEDGCN-S
7..615.99
72.0+5.8
820122.6
35.3+..7
38241.2
68.540.44
TEDGCN-D
77.1 +2.5
72.0 22.8
42.4
27.6 +0.8
44.2=0.9
56.90099
70.0=
optimal 15:326, 12,859
2s 11.4%
catine 10 227, 16.6)
aecastinal (ecortnnal (3.7544159))
Performance on Cara
marormarce or Cheeser
To formrce Acter
Performans on Sourme
(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).
model depth and without the prior knowledge of the input graph (i.c., whether the input graph is homophilic or heterophilic), TEDGCN has the capability of automatically detecting the underlying graph heterophily. We have interesting observation: cornel15, even with only a small portion of the eigengraphs, TEDGCN-D is able to achieve better performance than TEDGCN-S with the complete set of eigengraphs. This suggests that the graph signal in some real-world graphs might be dominated by few low and high frequency components, and allowing two independent depth parameters in TEDGCN-D brings the flexibility to capture the low and high frequencies at the same time.
large datasets, Squirrel, Chameleon, and
4.3 Trainable Depth
systematic study is conducted on the node classification performance w.r.t. the trainable depth 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.735) in terms of the best ACCs, while for two heterophilic graphs, Actor and Squirrel, the optimal depths are negative (-0.027 and -3 -3.751.. These results demonstrate that our model indeed automatically capture graph beterophily/homophily by finding the suitable depth to suppress or amplify the relative weights of the corresponding frequency components. Namely, suppressed for homophilichettrophiiii graphs respectively. Close to zero depth. For the two homophilic graphs in Fig- ures 4aland 4b) sharp performance drop is observed when depth d approaches 0, since the eigengraphs gain close-to- uniform weights. For the heterophilic Actor dataset, its optimal depth -0.027 is close to O, as shown in Figure 4c In addition, the performance of TEDGCN-D (27.6% 27.6%) similar to that of GCN (7)5%) both of which are much worse than TEDGCN-S (35.3%). This result indicates that Actor is special graph where all frequency compo- nents have similar importance. Due to the absence of the intermediate frequency components between the high- and low-end ones, the performance of TEDGCN-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.
high/low frequency components
Table 3: The performance of one-layer vanilla GCN over the augmented Std.
Dalasets
Texas
Comell
Wisconsin
GCN
53.9
44.3
31.4
TEDGCN-S
77.6
72.0
82.0
TEDGON-D
GCN (S')
75.9
72.7
83.4

---

4.4 Graph Augmentation and Geometric Insights
is especially interesting analyze what change a negative depth brings to the spatial domain and how such change impacts the subsequent model performance.
Graph augmentation via negative depth. By picking the optimal depth d according to the best performance on the validation set, new diffusion matrix $ is obtained. With the optimal fixed,
0.3
64
(a) Texas (d - 0.328)
(b) Cornell (d = 0.3622
(c) Wisconsin (d = -0.280)
Figure 5: The weights of eigengraphs w.r.t. eigenvalues on the augmented diffusion matrix S and original S.
10
100
158
60
125
-525
200
25
75
300
176
275
125
-16
(a) Texas
(b) Comell
(c) Wisconsin
Figure 6: The difference between the augmented diffusion matrix and the original one Se S.
substituting the normalized adjacency matrix D AD : in Eq. ①I by Šc is equivalent to applying the vanilla GCN new topology. This topology effectively plays the role of a structural aug- mentation for the original graph. The impact of such augmentation on performance is tested on heterophilic graphs: Texas, Cornell and Wisconsin, shown in Table B Apparently, for the vanilla GCN, the performance obtained with this new topology is superior over that with the raw input graph: dramatically brings 20%-30% lifts in ACC. Moreover, the augmented topologies also make vanilla GCN outperform TEDGCN-S and TEDGCN-D on 2 out of the 3 datasets. By nature, the augmented graph is re-weighted linear combination of the eigengraphs, and its topological structure intrinsically assigns higher weights to eigengraphs corresponding to higher frequencies, as shown in Figure
Geometric properties. To further understand how the topology of Šd with negative optimal d differs from that of S and why the performance significantly boosted, heat maps of (S S)s presented in Figure 6 First, the dark red diagonal line the heat map indicates the weights self-loops are significantly strengthened in the augmented graph, and result, in consistency with the previous findings [71). the raw node attributes make more contributions in predicting their labels. These strengthened self-weights also play the similar role restart distribution or skip connections [60] preventing the node embeddings becoming over- smoosheo In addition, there is a horizontal line and a vertical line (light yellow line marked by dashed ovals) each heat map in Figure correspond to the hub node in 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 hub node on most other nodes are systematically reduced. Consequently, the augmentation amplifies the deviations between node embeddings and facilitates the characterization of graph heterophily.

---

5
Related Works
Graph convolutional network (GCN), GCN models can be mainly divided into two categories: (1) spectral graph convolutional networks and (2) spatial convolutional networks. In (1), Spectral CNN
7 borrows the idea from convolutional neural network [18] to construct diagonal matrix as the
convolution kernel. ChebNet [12 adopts a polynomial approximation of the convolution kernel. GCN
28 further simplifies the ChebNet via the first order approximation. Recently, [22 4 57 propose
more advanced filters as the convolution kernel. Most works in (2) follow the message-paseee mechanism. GraphSAGE [99 iteratively aggregates features from local neighborhood. GAT [50]
applics self-attention to the neighbors. APPNP [29] deploys personalized pagerank [49 to sample nodes for aggregration. MoNet [40] 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 [32 [59]
PairNorm 66 forces distant nodes to be distinctive by adding an intermediate normalization layer.
Dropedge 43 DeepGCN [I], AS-GCN 233 and JK-net [61] borrow the idea of ResNet [2]]
to dis-intensify smoothing. DeeperGXX 77 adopts a topology-guidest 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 TEDGCN 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 [28 50 19.. Recently, heterophilic graphs. in which neighbors often have disparate labels, attract lots of attention. Geom-
GCN [4 and H2GCN [76] extend the neighborhood for aggregation. FAGCN [5) and GPRGNN
10 adaptively integrate the high/low frequency signals with trainable parameters. Alternative message-pas mechanisms have been proposed in HOG-GCN [57] and CPGNN 75 The latest.
related works include ACM-GCN (37 38), LINKX (34, BernNet 22 GloGNN 3 and GBB-GNN
[1]. Other works can be found in recent survey 72
6 Conclusion and Future Work
To our best knowledge, this work presents the first effort to make GCN's depth become negative and trainable by redefining it on the real number domain. We unveil the intrinsic connection between negative GCN depth and graph heterophily. A novel problem of automatic GCN depth tuning for graph homophily/heterophily detection is formulated, and we propose a simple and powerful solution named TEDGCN with two variants (TEDGCN-S and TEDGCN-D), An effective graph augmentation method is also discussed 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 on spectral and spatial GNNs. Our paper studies the depth of graph convolutional network and graph spectrum, which has no negative ethical impacts on society. Since TEDGCN requires to conduct ggen-decomposition of the graph Laplacian, it is not directly applicable to inductive and dynamic graph learning problems. In addition, there may exist other options for the transformation functions such as the pseudoinverse of the Laplacian. We leave these for future exploration.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36 th International Conference on Machine Learning, 2019.
[2] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Ee-net: Exploitation-explortiio neural networks in contextual bandits. arXiv preprint arXiv:2110.0311 2021.
[3] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Neural exploitation and exploration of contextual bandits. arXiv preprint arXiv:2305.03784, 2023.
10

---

[4] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[5] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3950-3957, 2021.
[6] Alcksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsu- pervised inductive learning via ranking, arXiv preprint (rxXiv:/07.0333 2017.
[7] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprini arXiv: /3/1:::::2/ 2.62003, 2013.
[8] Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pages 1407-1418. PMLR, 2021.
[9] Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018.
[10] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07990 07988, 2020.
[11] Fan RK Chung and Fan Chung Graham. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[12] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[13] Boxin Du Si Zhang, Yuchen Yan, and Hanghang Tong. New frontiers of multi-network mining: Recent developments and future trend. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 4038-403330 2021.
[14] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk-gnn: Gated ki-ker graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pages 1550-1558, 2022.
[15] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. IEEE Signal Processing Magazine, 30:83 2019.
[16] Dongqi Fu, Liri Fang, Ross Maciejewski, Vetle I Torvik, and Jingrui He. Meta-learned metries over muult--vvllttion temporal graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 367-37 2022.
[17] Dongqi Fu, Zhe Xu, Bo Li, Hanghang Tong, and Jingrui He. A view-adversarial framework for multi-view network embedding. In Proceedings of the 29th ACM International Conference on Information& & Knowledge Management, pages 2025-2028, 2020.
[18] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
[19] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[20] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference Machine Learning, pages 8230-8248.
PMLR, 2022.
[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
[22] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 14255, 2021.
[23] Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances neural information processing systems, 31, 2018.
[24] Zexi Huang, Arlei Silva, and Ambuj Singh. A broader picture of random-walk based graph embedding. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 685-695, 2021.
11

---

[25] Baoyu Jing, Hanghang Tong, and Yada Zhu. Network of tensor time series, In Proceedings of the Web Conference 2021, pages 2425-2437, 2021.
[26] Baoyu Jing, Yuchen Yan, Kaize Ding, Chanyoung Park, Yada Zhu, Huan Liu, and Hang- hang Tong. Sterling: Synergistic representation learning on bipartite graphs. arXiv preprint arXiv:2302.05428, 2023.
[27] Baoyu Jing, Yuchen Yan, Yada Zhu, and Hanghang Tong. Coin: Co-cluster infomax for bipartite graphs. arXiv preprint arXiv:2206. 00006, 2022.
[28] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609. 2016.
[29] Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: (110:0091000999 2018.
[30] Richard B Lehoucq, Danny Sorensen, and Chao Yang. ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM, 1998.
[31] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pages 9267-9276, 2019.
[32] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
[33] 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 arXiv:2205.0 07300 2022.
[34] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non non-homonhee homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
[35] Hongyi Ling, Zhimeng Jiang, Meng Liu, Shuiwang Ji, and Na Zou. Graph mixup with soft alignments. arXiv preprint arXiv:2300.000 06788, 2023.
[36] Lihui Liu, Boxin Du, Jiejun Xu, Yinglong Xia, and Hanghang Tong. Joint knowledge graph completion and question answering. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1098-1108, 2022.
[37] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.0560
2021.
(38] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. arXiv preprint arXivv2210.07600 2022.
[39] Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint arXiv:2008.088:: 2020.
[40] 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, pages 5115-5124, 2017.
[41] 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.
[42] Shane Roach, Connie Ni, Alexei Kopylov, Tsai-Ching Lu, Jiejun Xu, Si Zhang, Boxin Du, Dawei Zhou, Jun Wu, Lihui Liu, et al. Canon: Complex analyties of network of networks for modeling adversarial activities. In 2020 IEEE International Conference on Big Data (Big Data), pages 1634-1643. IEEE, 2020.
[43] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 1xxiv:1907.10900 2019.
[44] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding.
Journal of Complex Networks, 92)xenab014, 2021.
12

---

[45]
Kamal Shah and Baver Okutmuştur. Functional Calculus. BoD-Bood on Demand, 2020.
[46]
David 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,
[47] Yuxin Tang, Zhimin Ding, Dimitrije Jankov, Binhang Yuan, Daniel Bourgeois, and Chris Jermaine. Auto-differentiation of relational computations for very large scale machine learning. arXiv preprint arXiv:2306. 200.002300.00088,, 2023.
[48] Gabriel Taubin. A signal processing approach to fair surface design. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pages 351-358, 1995.
[49] Hanghang Tong, Christos Faloutsos, and Jia- Yu Pan. Fast random walk with restart and its applications. In Sixth international conference on data mining (ICDM 006), pages 613-622. IEEE, 2006.
[50] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1.1.. 10903, 2017.
[51] Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hanghang Tong. Networked time series imputation via position-aware graph enhanced vari- ational autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2256-2268, 2023.
[52] Ruijie Wang, Baoyu Li, Yichen Lu, Dachun Sun, Jinning Li, Yuchen Yan, Shengzhong Liu, Hanghang Tong, and Tarek F Abdelzaher. Noisy positive-unlabell learning with self- teffniga for speculative knowledge graph reasoning. arXiv preprint arXiv:2336.0075: 2023.
[53] Ruijie Wang. Zheng Li, Dachun Sun, Shengzhong Liu, Jinning Li, Bing Yin, and Tarek Abdelzaher. Learning to sample and aggregate: Few-shot reasoning over temporal knowledge graphs. Advances in Neural Information Processing Systems, 35:16663-16876, 2022.
[54] Ruijie Wang, Zheng Li, Jingfeng Yang, Tianyu Cao, Chao Zhang, Bing Yin, and Tarek Ab- delzaher. Mutually-pan paced knowledge distillation for pross-lingual temporal knowledge graph 2023.
reasoning. In Proceedings of the ACM Web Conference 2023, pages
[55] Ruijie Wang, Zheng Li, Danqing Zhang, Qingyu Yin, Tong Zhao, Bing Yin, and Tarek Abdelza- her. Rete: retrieval-enhanced temporal event forecasting on unified query product evolutionary graph. In Proceedings of the ACM Web Conference 2022, pages 462-472, 2022.
[56] Ruijie Wang, Yuchen Yan, Jialu Wang, Yuting Jia, Ye Zhang, Weinan Zhang, and Xinbing Wang. Acekg: A large-scale knowledge graph for academic data mining. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 1487-1490, 2018.
[57] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. arXiv preprint arXiv:2205. ///2, 2022.
(58) 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.
[59] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[60] Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In International Conference on Machine Learning, pages 10432-10441. PMLR, 2020.
[61] 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, pages 5453-5462. PMLR, 2018.
[62] Zhe Xu, Yuzhong Chen, Qinghai Zhou, Yuhang Wu, Menghai Pan, Hao Yang, and Hanghang Tong, Node classification beyond homophily: Towards a general solution. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2862-2873, 2023.
[63] Yuchen Yan, Lihui Liu, Yikun Ban, Baoyu Jing, and Hanghang Tong. Dynamic knowledge graph alignment. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 4564-4572,
2021. 2021.
13

---

[64] Yuchen Yan, Si Zhang, and Hanghang Tong. Bright: A bridging algorithm for network alignment. In Proceedings of the Web Conference 2021, pages 3907-3917, 2021.
[65] Yuchen Yan, Qinghai Zhou, Jinning Li, Tarek Abdelzaher, and Hanghang Tong. Dissecting cross-layer dependency inference on multi-layered inter-dependent networks. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pages
2341-2351, 2022.
[66] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference machine learning, pages 40-48. PMLR, 2016.
[67] Zhichen Zeng, Boxin Du, Si Zhang. Yinglong Xia, Zhining Liu, and Hanghang Tong. Hierarchi- cal multi-marginal optimal transport for network alignment. arXiv preprint arXiv:23 2023.
[68] Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. Parrot: Position-awart regularized optimal transport for network alignment. In Proceedings of the ACM Web Conference 2023, pages 372-382, 2023.
[69] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International
Conference on Learning Representations, 2019.
[70] Lecheng Zheng, Dongqi Fu, and Jingrui He. Tackling oversmoothing of gnns with contrastive learning, arXiv preprint arXiv:2110.1 1377998, 2021.
[71] Wenqing Zheng, W Edward Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node represen- tations with incomplete or missing neighbor- hoods. In International Conference on Learning Representations, 2022.
[72] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip $ Yu. Graph neural networks for graphs with heterophily: survey, arXiv preprint arXiv:2202.07082. 2022.
[73] Qinghai Zhou, Liangyue Li, Nan Cao, Lei Ying, and Hanghang Tong. Admiring: Adversarial multi-network mining. In 2019 IEEE International Conference on Data Mining (ICDM), pages 1522 1527. IEEE, 2019.
[74] Qinghai Zhou, Liangyue Li, Xintao Wu, Nan Cao, Lei Ying, and Hanghang Tong. Attent: Active attributed network alignment. In Proceedings of the Web Conference 2021, pages 3896-3906, 2021.
[75] 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, pages 11168- 111811176,611 2021.
[76] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs, Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
14

---

A Appendix
The appendix is structured follows:
Subsection A.I presents the statistics of datasets used in the Experiment Section (Section the main contents.
Subsection A.2 presents the experimental results on synthetic datasets with controllable homophily/heterophiin level.
Subsection A.3 compares TEDGCN with some latest methods on different split (48%, 32%, 20%) for training. validation and testing of benchmark datasets. In this subsection, we also compare all methods (15 baselines and TEDGCN) under a unified setting on Texas, Cornell, Wisconsin and Actor datasets.
Subsection A.4 introduces the details of the implementation of TEDGCN.
Subsection A.5 is visualization of node embeddings w.r.t. different depths (d values) on both homophilie (Cora) and heterophilic (Texas) graphs.
A.1
The Statistics of Datasets
Table 4:
The statistics of datasets.
Dalusett
Cura
Citeseer
Pubindd
DBLP
Texas
Wisconsin
Cornell
Actor
Chameleon
Squimel
curnell5
#Nodes
2,708
3.327
19,717
17,716
183
251
183
7,600
2,277
5,201
18,660
#Edges
10,556
9.104
88,648
105,734
325
515
298
30,019
62,792
396,846
158,1554
#Fcatures
1,433
3,703
500
1,639
1,703
1,703
1,703
932
2,325
2,089
4,735
#Classes
A.2 Experiments on Synthetic Datasets
Table 5: Performance comparison of TEDGCN and 2-layer SGC on synthetic datasets. (%)
Homophily Level h(g)
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
SGC
44.8
53.2
58.3
67.9
73.0
77.6
81.6
83.5
90.7
TEDGCN
67.3
68.5
60.3
72.3
78.3
78.6
82.7
84.0
91.5
Optimal d
-3,24
-0.75
-0.60
0.74
0.94
1.01
2.69
2.98
3.58
To better demonstrate the relation between the negative depth d and edge homophilyfheterphilly construct synthetic datasets with different homophily levels. The synthetic graphs are generated via scheme adopted in ACM-GCN (8). Specifically, there are 5 classes, each with 400 nodes. For fixed homophily level h()) (e.g., h(g) 0.1), the node degree 8, is sampled for each node via multinomial distribution. With the sampled 8.. (GG),, intra-class edges and (1 h())), inter-class edges are randomly generated. We compare TEDGCN with two-layer SGC. The results on the synthetic datasets with different homophily levels are presented Table We can observe that (1) as the homophily level h(G) decreases, the optimal d turns from positive to negative; and (2) under low homophily levels, the performance of TEDGCN significantly better than SGC.
A.3 More Baselines and Unified Setting
Table 6: Performance comparison (mean std accuracy))(5) on benchmark datasets.
Pataeers
Texas
Carell
Wiscomsin
Actor
Squirel
Clumckcon
Cum
Fuhmel
Cieeseer
RerNer
22.00.2.0
1.0
87.05225
14.4690.77
14.0211.14
41.0
$7.31
85 35
162200.5
LINKX
74 24.0018.37
77.8415.81
75.995.72
36.10 11.55
618111.80
68. 18.42.1..58
$16111.13
87.3610.17
73.1910.90
GloGNN
84.3214.15
83.511126
87.0613.33
37
37.5611.99
69.812.42 42
83.1111 1.13
6..61...55
77.41 1.65
ACMAION
87342-4.40
85.1426.07
884333422
36652084
25.1911.49
09.441.9
87912000
90.000.52
17.32 1.70
TEDGON-S
30337-4.71
8581-199 1.11
88631-4.3
37.4--1111
48.45+1.42
670041.81
8841-1.78
34-11-111
1.50
28.0311000
62.2233.3
67.3311.71
1.
1.72
Under fully-supervised setting, we compare TEDGCN with ACM-GCN, LINKX, BernNet and GloGNN with the standard split of 48%/329%/20.. We directly use the performances of ACM-GCN, LINKX and GloGNN reported in the ACM-GCN paper. For BernNet, we obtain its performance by running its open-sourced code. The results are shown in Table 6 It is observed that the latest
15

---

methods, such as ACM-GCN and GloGNN do perform strongly. However, our model achieves the best classification accuracy on of the datasets, which demonstrates the effectiveness of TEDGCN.
We also compare all methods (15 baselines and TeDGCN) under unified setting. Since some methods do not report their performances on some datasets in their original paper and have not made their code publicly available, we compare all methods' performances on commonly used heterophilic graph datasets: Texas, Cornell, Wisconsin and Actor, under the same public 48%/32%/20%% split for training. validation and testing.
Table 7: Performance comparison (mean) on benchmark datasets.
Datasets
Texas
Coreell
Wisconsin
Actor
GCN
54,05
53.78
50.39
28.78
SGC
45.80
43.72
45.13
27.52
GAT
$7.30
54.59
54.31
28.99
APPNP
58.92
51.12
58.84
31.83
GPRGNN
81.35
78.11
82.55
35.16
FAGCN
76.76
H2GCN
79.73
78.38
82.55
36.71
ChebNet
82.14
72.16
78.82
36.04
BerNet
82.70
81.35
87.05
34.46
LINKX
74.60
77.84
75.49
36.10
GloUNN
37.35
ACM GCN
87.84
85.14
88.43
36.63
GeomGCN
66.76
GBK-GNN
70.27
75.66
68.63
36.12
HOG-GCN
85.17
84.32
86.67
36.82
TeDGON
90.32
85.81
88.63
37.40
TeDGCN-D D
91.41
86.53
91.42
29.03
From Table we can observe that TeDGCN-S/TeDGNN-D outperforms all the remaining baselines.
A.4 Implementation Details
We set the learning rate 0.005 or 0.01, the decaying weight for the learning rate 5e-4, the number of training epochs to 500. The K largest/smallest eigenvalues for TEDGCN-D is max{1000 0. 0.1n), where the number of nodes in the input graph. For all baselines. the parameters are according to their original papers. All experiments are run on a Tesla-V Resla-V100 100 GPU. Since this work is conducted during internship in Visa Research and the code can not be made public according the policy of Visa Research. If you have any questions about the implementation, please email yucheny5 Saaeenyy@e @lllinois.edu get some help.
A.5
Visualization of Node Embeddings w.r.t. Negative Depth d
We conduct visualization of node embedding generated by TEDGCN under different depths for homophilic (Cora) and heterophilic (Texas) graphs. As shown in Figure 7 for Cora, when d the nodes in different classes form clearly distinguishable clusters (ACC=82.4%) When the depth decreases from a positive value d 5 (ACC=82.4%)) to negative value nodes belonging to different classes/colors mix with each other, and the clearly clustered structure does exist anymore. However, for Texas shown Figure X when decreasing the depth from d = 4 (ACC=50%) to d' = -0.35 (ACC=80%), the clusters of different classes/colors become well- separated. Especially, the purple nodes spread randomly all over the embedding space when d but concentrate in one cluster when d = -0.35. The spatial distribution of the node embeddings reveals that TEDGCN with positive and negative depths respectively models graph homophily and heterophily in a proper way.
(ACC=29.55)
the
16

---

(a) d = 2. ACC-29.5% (b) d= 0, ACC-46.6%
(c) 5, ACC-82.4% (d) GCN, ACC=81.0%
Figure 7: Visualization of node embeddings by t-SNE on Cora (homophilic).
(a) d -0.35, ACC=80.0% (b) d 2, ACC=59.0% (c) d 4, ACC=50.0% (d) GCN, ACC=55.0%
Figure 8: Visualization of node embeddings by t-SNE on Texas (heterophilic).
17


Reviews:
[{"review_id": "xam2lEq80x", "reviewer": "Reviewer_yXi3", "summary": "This paper proposes two algorithms to learn GNN with a trainable depth. At first, the authors exploit previous theoretical results about the correlation between frequency and zero crossings and the intuition that capturing heterophily needs more zero crossings to motivate adjusting the weights of eigen-graphs. Then it is natural to achieve this goal by tuning the depth of a GNN, where the authors propose to extend the possible space of depths to real numbers. To my knowledge, it is the first attempt to train a GNN with trainable and possibly negative depth, especially since the proposed algorithms are not built upon continuous-time diffusions. Extensive experiments are conducted, showing that the proposed algorithms are quite effective for heterophilic graphs, and they tend to learn the optimal depth.", "questions": "In line 130, the cardinalities of examples are 1 and 2. As the considered graph is undirected, why not 2 and 4?", "limitations": "There is a complexity analysis of the proposed algorithms, which can be regarded as a discussion of the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. This well-written paper enables me to pick up its core ideas effortlessly. Particularly, the provided examples are quite helpful for understanding the corresponding definitions and formulas.\n2. Learning a negative depth to encourage larger weights for eigen-graphs that provide more zero crossing interests me. More importantly, it is well-motivated and demonstrates significant advantages in capturing heterophilic graph patterns.\n3. The empirical studies seem to be comprehensive. At first, both homophilic and heterophilic graphs are included. I am glad to see that the authors honestly report the results on those four homophilic graphs, where the proposed algorithms have not achieved a consistent improvement. And it is great to see the dramatic improvements on heterophilic graphs, which strongly support the idea of this paper. Second, the detailed analysis confirms that the proposed algorithms can truly learn the optimal depth. This lets us attribute the successes in capturing heterophilic graph patterns to such a mechanism and its consequence of up-weighting zero crossings.\n4. I am quite fond of the interpretation of augmenting original graph structure, which perfectly obeys our intuition.", "weaknesses": "1. How to apply the proposed algorithms to large graphs is a critical question that has not been fully resolved.\n2. The motivation of proposed algorithms seems to be entirely built upon previous theoretical results. I am curious about what is exactly the contribution of this paper.\n3. To achieve a trainable and negative depth, the designed GNN is in a similar form to SGC, which also sacrifices some non-linearity (or expressiveness) to gain simplicity.\n4. The rescaling of the base into (0, 1) is reasonable and explainable, which is satisfactory to me. Yet, it would be better to justify its expressiveness and numerical properties as original bases (i.e., original frequencies).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: In line 130, the cardinalities of examples are 1 and 2. As the considered graph is undirected, why not 2 and 4?**\n    \n**Response**: Thank you for raising this question. In undirected graph, we regard edge $(v\\_{j}, v\\_{k})$ and edge $(v\\_{k}, v\\_{j})$ as one edge. We will add a footnote here to clarify this point in the revised version of this paper.\n\n\n**Other points in Weaknesses/Comments/Limitations**:\n\n**P1:How to apply the proposed algorithms to large graphs is a critical question that has not been fully resolved.**\n\n**Response**: We think that the TEDGCN-D in the paper is proposed from the *spectral domain* to reduce the time complexity on large graphs. An alternative solution is from the *spatial domain*: Since each node is closely related with the nodes within a multi-hop receptive field, we can divide the large graph into several connected components (i.e., subgraphs), set a maximum node number limit for each subgraph and run TEDGCN-S on each subgraph. For example, for a graph with 10000 nodes, we can divide it into 10 connected components/subgraphs and each subgraph has about 1000 nodes. In a vanilla implementation of eigen-decomposition with time complexity of $O(n^3)$, this solution can accelerate the algorithm on each subgraph by about 1000 times. We leave the exploration to this tentative idea in future works.\n\n**P2: The motivation of proposed algorithms seems to be entirely built upon previous theoretical results. I am curious about what is exactly the contribution of this paper.**\n\n**Response**: The graph spectrum analysis is indeed a commonly used tool in many works (e.g.,GCN). We look at the the existing theory from a novel angle and our core contributions can be summarized as below: (1) From the theoretical aspect: to our best knowledge, we are the first to unveil the intrinsic relationship between the negative GCN depth and edge heterophily in graph. We also provide in-depth geometric and spectral explanations for negative depth. (2) From the model aspect, we propose a simple and powerful model TEDGCN with two variants (TEDGCN-S and TEDGCN-D) and discuss a novel graph augmentation method based on TEDGCN.\n\n**P3: To achieve a trainable and negative depth, the designed GNN is in a similar form to SGC, which also sacrifices some non-linearity (or expressiveness) to gain simplicity.**\n\n**Response**: First, our results show that with a proper depth, nonlinearity may be not be a critical factor to determine the performance, and the simplicity is a natural byproduct of our framework which requires no sacrifice of the performance. Second, as pointed by Reviewer `wZLL`, one possible solution for this question is to leverage the augmented graph obtained by TEDGCN as the input for other non-linear GNNs, in which we can add non-linearity between each layer. \n\n**P4: The rescaling of the base into (0, 1) is reasonable and explainable, which is satisfactory to me. Yet, it would be better to justify its expressiveness and numerical properties as original bases (i.e., original frequencies).**\n\n**Response**: Actually, we do have thought about using the original frequencies in TEDGCN. However, every connected graph has an eigenvalue 0, which will lead to problem when we have negative depth (e.g., -1) because $0^{-1} = \\frac{1}{0}$ is meaningless, and this makes it hard to explain the numerical properties in the original spectrum. Thus, we propose a transformation function $g(\\lambda)=1-\\frac{1}{2}\\lambda\\in (0,1]$ to solve this problem. "}, {"review_id": "3Mt2FLZmqm", "reviewer": "Reviewer_wZLL", "summary": "This paper shows a connection between the depth of a GCN and it's suitability for homophilic / heterophilic graphs, by analyzing graph spectra. It proposes to address heterophily with negative depth and presents a GNN architecture called TeDGCN which allows for trainable and negative depth. TeDGCN outperforms / is competitive with other GCN variants on a number of graph datasets. It further leads to a graph augmentation approach when the optimal depth is known.", "questions": "On line 262 the split should be 60/20/20 right?\n\nRecent work [1] has shown pressing issues in old benchmarks of heterophilic datasets, which have been used here. Can you also include / replace with the results on the newer datasets proposed in [1]?\n\nThe same paper also shows that standard architectures like SAGE and GAT can outperform heterophily-specific architectures. Can you include these as baselines? Even if not adding datasets from [1], these baselines would be representative of models with higher expressive power than GCN or GCN-variants.\n\n[1] Platonov et. al. \"A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\" ICLR 2023.", "limitations": "The limitation to transductive problems is mentioned briefly in the appendix, but the limitation to linear models and expressive power is not discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper tries to extend GCN with trainable real-valued depth. This has consequences for automatic tuning of the GCN depth, and for better addressing heterophilic datasets, both of which make it a significant novel contribution to the community. It establishes the connection between positive/negative depth with low/high frequency components of the graph signal and homophily/heterophily.\n\nThe analysis results in a new architecture TeDGCN. The paper further extends it to two variants, dealing with both low- and high-frequency components and addressing scalability challenges for large graphs. The method gives superior results, especially for heterophilic datasets. The trained depths are analyzed and also used to propose a graph augmentation mechanism which sometimes outperforms TeDGCN.\n\nThe paper is well-written and the ideas are presented clearly.", "weaknesses": "To enable trainable depth, the paper operates on a simplification of GCN which removes the intermediate non-linearities. Thus the resulting model is a linear model, which limits the expressive power of the approach. Also, as a GCN variant it is not applicable to the inductive setting.\n\nIt is not clear whether the lessons from this paper can be applied to more advanced GNNs or hold more broadly. Essentially trainable depth results in an augmented graph. Can this augmented graph be used with non-linear GNNs to still capture heterophily?\n\nSome baselines with trainable depth (ODE-based GNNs) could be compared against. Is it possible to realize negative depth by inverting the graph Laplacian first?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: On line 262 the split should be 60/20/20 right?**\n    \n**Response**: Thanks for your question. As we mentioned in line 254, we adopt the **semi-supervised** node classification task to evaluate TEDGCN and other baselines with the split 20/20/60\\% for training/validation/testing set. The reason is that in real-world applications, it is very difficult to have the fully supervised setting with a large ratio of nodes' labels known and marked as training data points (e.g., 48\\% or 60\\%). Therefore, we believe the semi-supervised setting with much less than 50\\% nodes functioning as training set is more reasonable to evaluate different methods, so without the loss of generality, we choose 20\\%. For the fully supervised setting: (1) we have the results on benchmark datasets with the given 48/32/20\\% split provided in [2] in Appendix A.5, which demonstrates the effectiveness of TEDGCN. Please refer to Appendix A.5 for more details. (2) We also evaluate TEDGCN on the given split of the revised chameleon dataset and the revised squirrel dataset provided by [1] during the rebuttal period. The accuracies for TEDGCN-S are $42.12 \\pm 4.33$ (\\%) on the revised chameleon and $41.70 \\pm 1.97$ (\\%) on the revised squirrel, both of which outperform all results from Table 2 in [1].\n\n[1] Platonov et. al. \"A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\" ICLR 2023.\n[2] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.\n\n**Q2: Recent work [1] has shown pressing issues in old benchmarks of heterophilic datasets, which have been used here. Can you also include / replace with the results on the newer datasets proposed in [1]? The same paper also shows that standard architectures like SAGE and GAT can outperform heterophily-specific architectures. Can you include these as baselines? Even if not adding datasets from [1], these baselines would be representative of models with higher expressive power than GCN or GCN-variants.**\n\n**Response**: Thanks a lot for reminding us of this ICLR2023 paper, we will add this paper and some other works discussed in this paper into related works in the revised version of our paper. Following reviewer's suggestion, we have evaluated TEDGCN-S on 5 new datasets provided in [1] (Revised Chameleon, Revised Squirrel, Tolokers, Minesweeper and Roman Empire) with same semi-supervised setting as other datasets in our paper. We also include SAGE and GAT as baselines. **The results are as presented in Table 1 in the general response.** We can observe that (1) as mentioned in **Q2**, SAGE is a strong method and achieves the best accuracy on Minesweeper and Roman Empire; and (2) TEDGCN-S outperforms all baselines on Revised Chameleon, Revised Squirrel and Tolokers and achieves the second best performance on Minesweeper and Roman Empire, which demonstrates the effectiveness of TEDGCN-S on these 5 new datasets in [1].\n\n**Other questions in Weaknesses/Comments/Limitations**:\n\n**P1: The resulting model is a linear model, which limits the expressive power of the approach. Also, as a GCN variant it is not applicable to the inductive setting.**\n\n**Response**: (1) For the limited expressive power of linear model, first, our results show that with a proper depth, nonlinearity may be not be a critical factor to determine the performance, and the simplicity is a natural byproduct of our framework which requires no sacrifice of the performance. Second, one possible solution for this question is to leverage the augmented graph obtained by TEDGCN as the input for other non-linear GNNs, in which we can add non-linearity between each layer. (2) For the inductive setting, one possible solution is to borrow the idea from (Graph)SAGE about how to generalize the transductive GCN to the inductive setting. Following the same idea in (Graph)SAGE, since each node is closely related with the nodes within a multi-hop receptive field, we can sample a multi-hop subgraph (e.g.,3-5 hops) for the center node $v$ whose embedding needs to be optimized. Then, we can run TEDGCN-S on this small subgraph around the center $v$ to learn the optimal depth on this small subgraph. This design offers the flexibility for different subgraphs to learn different optimal depths. Furthermore, this can be applied to the inductive setting, when unseen/new node arrives, we can simply sample such a subgraph and run TEDGCN-S on this subgraph without re-training TEDGCN/conducting eigen-decomposition on the whole large graph, which can save a lot of time. We will leave the implementation of this idea to future works.\n\n**P2: Essentially trainable depth results in an augmented graph. Can this augmented graph be used with non-linear GNNs to still capture heterophily?**\n\n**Response**: Yes, the augmented graph can be used with non-linear GNNs, which only need to treat the augmented graph as input. One example is that in Subsection 4.4, we use the augmented graph as input for normal (non-linear) GCN, which achieves even better performance than TEDGCN-S/TEDGCN-D in capturing heterophily on the Cornell dataset and the Wisconsin dataset. \n\n**P3: Is it possible to realize negative depth by inverting the graph Laplacian first?**\n\n**Response**: We are afraid that this is not mathematically feasible. Actually, we do have thought about directly inverting the graph Laplacian first. However, the graph Laplacian for any connected graph has an eigenvalue 0, which makes the graph Laplacian non-invertible. "}, {"review_id": "XTx06QuE8B", "reviewer": "Reviewer_iB1Z", "summary": "The paper proposes a new GCN that is capable of handling both homophilic and heterophilic networks. This method can be interpreted as generalizing the depth of the GCN, which is generally a natural number and a hyperparameter, to an arbitrary real number that is a trainable parameter. The first version of this method is essentially a variant of the well-known SGC method that makes the exponent on the graph matrix (corresponding the the depth) a trainable parameter. This can be computationally expensive, so the paper also proposes a second version which extracts the lowest frequency components and highest frequency components of the graph, and gives two tunable depth parameters to both sets of components. Experiments show that these versions generally achieve comparable or superior performance on the standard set of benchmark networks for homophilic/heterophilic node classification, relative to some prior methods. Some other experiments examine the depth parameters found by the method on various networks, as well as other insights from the method.", "questions": "- The Squirrel and Chameleon datasets were recently found to have a lot of erroneous duplicates (\"A critical look at the evaluation of GNNs under heterophily: are we really making progress?\" by Platonov et al.). Is this paper using the revised datasets or the originals?\n\n- The current method does not apply to the inductive setting, which is noted as a limitation of the work. Do the authors have any ideas on how the insights here could apply to that setting?\n\n- The depth parameter found by the single variant often seems to be interpretable. Are the two depth parameters found by the dual variant also interpretable?", "limitations": "Limitations are very briefly discussed in the appendix and pertain to the limited setting to which the method is applicable (static/transductive). There could be more discussion of limitations beyond this, such as limitations about the evaluation.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is organized well and easy to read.\n- The proposed method is relatively simple as compared to similar recently proposed methods like GPR-GNN, but still demonstrates comparable or superior performance.\n- The paper proposes and evaluates both a conceptually simple version of the method, as well as a slightly more complex but scalable version.", "weaknesses": "- As the authors note, this method is only directly applicable to the most basic setting of static undirected graphs in the transductive setting. Many of the competing methods to which this paper provides comparisons also apply to the inductive setting.\n\n- While the simplicity of the method is appealing, since its dual variant (which is the only scalable variant) discards intermediate frequency components, it may struggle with graphs like Actor to which these components also seem crucial. The paper notes this.\n\n- While the number of datasets is quite reasonable, and these have been the most popular ones in this field recently, I would have liked to see evaluations on different datasets. 3 of the datasets are very small, and two others (Squirrel/Chameleon) have recently been shown to have other issues - see the paper cited below. That paper also introduces other heterophilic datasets, which could yield a better evaluation.\n\n- This is not really a weakness, but I do not see a significant conceptual contribution here prior to the introduction of the new method. There has been an abundance of recent papers on handling heterophily, and hence an abundance of discussion of various spectral filters and their interpretations.\n\n### Typos/minor\n- Line 101: \"and the corresponding eigengraph $\\mathbf{u}_1 \\mathbf{u}_1^\\top$ has an identical value $\\frac{1}{n}$ for all entries\" - isn't this only true for regular graphs?\n- Line 125: \"also corresponds a\"\n- Line 153-154: \"applying an arbitrary function on a graph Laplacian is equivalent to applying the same function only on the eigenvalue matrix\" - I think \"arbitrary\" has to be specified a bit here, e.g., this is true a matrix squaring function but not an entrywise squaring function\n- Table 2 caption: \"heterphilic\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The Squirrel and Chameleon datasets were recently found to have a lot of erroneous duplicates (\"A critical look at the evaluation of GNNs under heterophily: are we really making progress?\" by Platonov et al.). Is this paper using the revised datasets or the originals?**\n\n**Response**: We use the original datasets in our submitted paper. Thanks a lot for reminding us of the issues reported in this ICLR2023 paper. We will add this paper and some other works discussed in this paper into related works in the revised version of our paper. In addition, during the rebuttal period, we have evaluated TEDGCN-S on 5 new datasets provided in this ICLR 2023 paper by Platonov et al. (Revised Chameleon, Revised Squirrel, Tolokers, Minesweeper and Roman Empire) with same semi-supervised setting as other datasets in our paper. **The results are presented in Table 1 in the general response above** . We can observe that TEDGCN-S outperforms all baselines on Revised Chameleon, Revised Squirrel and Tolokers and achieves the second best performance on Minesweeper and Roman Empire, which demonstrates the effectiveness of TEDGCN-S on these 5 new datasets from Platonov et al.\n\n**Q2 and Weakness 1: The current method does not apply to the inductive setting, which is noted as a limitation of the work. Do the authors have any ideas on how the insights here could apply to that setting?**\n\n**Response**: For the inductive setting, one possible  solution is to borrow the idea from GraphSAGE about how to generalize the transductive GCN to the inductive setting. Following the similar idea as in GraphSAGE, since each node is closely related with the nodes within a multi-hop receptive field, we can sample a multi-hop subgraph (e.g.,3-5 hops) for the center node $v$ whose embedding needs to be optimized. Then, we can run TEDGCN-S on this small subgraph around the center $v$ to learn the optimal depth on this small subgraph. This design offers the flexibility for different subgraphs to learn different optimal depths. Furthermore, this can be applied to the inductive setting, when unseen/new node arrives, we can simply sample such a subgraph and run TEDGCN-S on this subgraph without re-training TEDGCN/conducting eigen-decomposition on the whole large graph, which can save a lot of time/space. \n\n**Q3: The depth parameter found by the single variant often seems to be interpretable. Are the two depth parameters found by the dual variant also interpretable?**\n    \n**Response**: The two depths can be explained as follows: as we point out in the analysis part, every graph can be regarded as a combination of many eigengraphs (Figure 1 and Eq. (3)). TEDGCN-D will merge $K$ eigengraphs corresponding to the highest frequencies into a high-frequency augmented graph and merge $K$ eigengraphs corresponding to the lowest frequencies into another low-frequency augmented graph. Then, the high-frequency augmented graph and the low-frequency augmented graph will be considered together to learn the optimal combination of depths on both augmented graphs. The obtained depth on each augmented graph can be interpreted similarly as single depth in TEDGCN-S.\n\n**Response to Weakness 2**: It is true that TEDGCN-D may discard intermediate frequency components and this is reflected in the results of TEDGCN-D on Actor.  One possible solution for this problem (also a possible solution for the scalability issue) can be as follows: Since each node is closely related with the nodes within a multi-hop receptive field, we can divide the large graph into several connected components (i.e., subgraphs), set a maximum node number limit for each subgraph and run TEDGCN-S on each subgraph. For example, for a graph with 10000 nodes, we can divide it into 10 connected components/subgraphs and each subgraph has about 1000 nodes. In a vanilla implementation of eigen-decomposition with time complexity of $O(n^3)$, this solution can accelerate the algorithm on each subgraph by about 1000 times. In addition, this design will not sacrifice/discard low/high/intermediate frequency components. We leave the exploration to this tentative idea in future works.\n\n**Response to Weakness 3**: Thanks for the suggestion. Please refer to our response to **Q1** for this point.\n\n**Response to Weakness 4**: The graph spectrum analysis is indeed a commonly used tool in many works on handling heterophily. We will consider to move part of the background of spectrum graph theory to appendix in the revised version of our paper. Furthermore, as we describe in the introduction section, our core theoretical contribution can be summarized as below: To our best knowledge, we are the first to unveil the intrinsic relationship between the **negative GCN depth** and edge heterophily in graph. We also provide in-depth geometric and spectral explanations for negative depth.\n\n**Minors 1: Line 101: \"and the corresponding eigengraph $\\mathbf{u}\\_{1}\\mathbf{u}\\_{1}^{\\top}$\n has an identical value $\\frac{1}{n}$ for all entries\" - isn't this only true for regular graphs?**\n\n**Response**: It is true for the symmetrically normalized graph Laplacian ($\\mathbf{L}\\_{sym}$) for **any** connected undirected graph. This is because any $\\mathbf{L}\\_{sym}=\\mathbf{I} - \\mathbf{D}^{-\\frac{1}{2}}\\mathbf{A}\\mathbf{D}^{-\\frac{1}{2}}$ for a connected undirected graph has a eigenvalue $0$, which has one corresponding eigengraph $\\mathbf{u}\\_{1}\\mathbf{u}\\_{1}^{\\top}$.\n\n**Response to other minors/typos**: Thanks for the comments.  We will fix the typos and polish the text according to your suggestions in the revised version of our paper."}, {"review_id": "qLFZaLhQqD", "reviewer": "Reviewer_jrHF", "summary": "This paper tackles the problem of graph heterophily in training Graph Neural Networks. Through graph spectral analysis, the authors decompose the graph Laplacian matrix into eigengraphs. Dwelling on the observation that low/high-frequency eigengraphs correspond to homophily/heterophily, the authors propose to use a continuous and trainable depth parameter to model the weight of the eigengraphs so the trained GNN can be adaptive to the level of heterophily in the target graph. The authors also realize the efficiency issue of eigendecomposition in large graphs and hence propose an approximation method that only considers the top-k largest/smallest eigenvectors and two trainable depth parameters to improve the efficiency. Experimental results show promising improvement over baseline methods on heterophily datasets.", "questions": "- line 187. I do not fully understand the negative depth explained for integer values. Since the proposed method only use either positive or negative depth, when does the model perform both positive message passing and negative message passing?\n- The value of K is max(1000, 0.1n), I think 0.1n is still a very large value. (1) what is the processing time for TEDGCN-D on larger dataset, e.g. ogbn-arxiv. (2) What happens when a smaller K is used for a larger graph? Is the top few components sufficient?\n- line 305. How is the optimal depth calculated? If it is a trainable parameter, how do you plot the full range of all depth?\n- Is using a single depth parameter d necessary? For example, you can use trainable d for all different eigengraphs. Note that this should bring minimal extra computation cost as the complexity is still the same. This potentially provide more flexible adaptation to different graphs.", "limitations": "The proposed method uses spectrum and hence require additional computation for new and changed graphs. The cost of computing eigendecomposition for large graphs, even using the approximation method, is still unclear.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I enjoy reading the paper as the authors explain the details and intuition behind the equations very well. The experiments are also solid verification of the proposed methods. The functional calculus trick to transfer the depth from the integer domain to the real domain is interesting and novel. The approximation method TEDGCN-D seems like a good alternative to using the full eigendecomposition and is organically developed from the original version. ", "weaknesses": "My primary concern lies in its comparison to existing work. The related work section only mentioned some work in the related field. However, a large body of work also realizes the importance of incorporating high-frequency passes in heterophilic graphs. How is the proposed method different from the existing ones? More specifically, note that in the formulation of the paper, the eigenvalues are shifted to (0,1] and d is uniform to both low/high frequency eigengraphs, meaning that d only shifts the focus on high/low frequency (amplifying the gap between eigenvalues too), what makes this different from other adaptive methods as the authors themselves point out in the paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: line 187. I do not fully understand the negative depth explained for integer values. Since the proposed method only use either positive or negative depth, when does the model perform both positive message passing and negative message passing?**\n\n**Response**: When the depth is negative, it does not mean **all** edges in the augmented graph are negatively weighted. As we point out in the analysis part, every graph can be regarded as a combination of many eigengraphs (Figure 1 and Eq. (3)). (1) Even the eigengraph corresponding to the highest frequency (e.g., the red eigengraph 3 in Figure 1) may still own some positively weighted edge (e.g. $\\frac{1}{6}$ in eigengraph 3 in Figure 1). (2) After we obtain the negative depth, it is equivalent to merging all eigengraphs back into an augmented graph, where the eigengraph corresponding to the highest frequency may achieve large weight after merging. Due to reasons (1) and (2), these positively weighted edges in eigengraphs corresponding to high frequency may still be positively weighted, while some other edges may be changed from positively weighted to negatively weighted. In this case, there will exist both positive and negative edges in the augmented graph and the model performs both positive message passing and negative message passing simultaneously. This can also be verified in Figure 6: some red points represent that the original positive weights for some edges in the graph are still increased.\n\n**Q2 and Limitations: The value of K is max(1000, 0.1n), I think 0.1n is still a very large value. (1) what is the processing time for TEDGCN-D on larger dataset, e.g. ogbn-arxiv. (2) What happens when a smaller K is used for a larger graph? Is the top few components sufficient?**\n\n**Response**: It is true that 0.1n could be still large for a very large graph. (1) The processing time (most time is for the eigen-decomposition) for ogbn-arxiv is about 1 hour. (2) If the graph is only dominated by low/high frequency components, a smaller $K$ is sufficient for TEDGCN-D, which is validated by the results in Table 1 and Table 2. However, if the dataset contains non-trivial portion of intermediate frequency components, the top/bottom few components would not be sufficient, and TEDGCN-D may have a relatively poor performance, which can be observed in Table 2 on the Actor dataset: TEDGCN-S's accuracy (35.3\\%) is much better than TEDGCN-D's (27.6\\%). One possible solution for this problem (also a possible solution for the scalability issue) can be as follows: Since each node is closely related with the nodes within a multi-hop receptive field, we can divide the large graph into several connected components (i.e., subgraphs), set a maximum node number limit for each subgraph and run TEDGCN-S on each subgraph. For example, for a graph with 10000 nodes, we can divide it into 10 connected components/subgraphs and each subgraph has about 1000 nodes. In a vanilla implementation of eigen-decomposition with time complexity of $O(n^3)$, this solution can accelerate the algorithm on each subgraph by about 1000 times. In addition, this design will not sacrifice/discard low/high/intermediate frequency components. We leave the exploration to this tentative idea in future works.\n\n**Q3: line 305. How is the optimal depth calculated? If it is a trainable parameter, how do you plot the full range of all depth?**\n\n**Response**: Firstly, for each result in Tables 1 and 2, we set an initial depth value and then start training the model. During this process, the depth changes. When the best **validation accuracy** is reached, we compute the testing accuracy. Secondly, for Fig. 4, it is slightly different. Since it is only for illustration purpose, we skip the validation step and the initial unstable several training epochs. We directly plot the test accuracy that changes with the depth value on the fly during the training process, so that the plotted testing accuracy for the optimal depth in Fig. 4 is slightly higher than that in Tables 1 and 2. Different initial depths are tried, but the optimal values are very similar/close. Fig. 4 shows one realization in each case.\n\n**Q4: Is using a single depth parameter d necessary? For example, you can use trainable d for all different eigengraphs. Note that this should bring minimal extra computation cost as the complexity is still the same. This potentially provide more flexible adaptation to different graphs.**\n\n**Response**: This is a really good suggestion. It may open a door for broad future models. While single depth or dual depth are simple and effective, they are not the only strategies. For example, current TEDGCN-D can capture both low and high frequency components but may discard the intermediate frequency components. We may design models that can capture both low and intermediate frequency components or both high and intermediate frequency components in the future work. We may design models with three/four depths or even more complex/specific model with stronger expressive power in the spectrum domain.\n\n**Response to Weakness**: The graph spectrum analysis is indeed a commonly used tool in many works on handling heterophily. The differences between various models lies in the specific ways of manipulating the high/low-pass filters. As we describe in introduction, our **core theoretical contribution** can be summarized as below: To our best knowledge, we are the *first* to unveil the intrinsic relationship between the *negative GCN depth* and edge heterophily in graph. We also provide in-depth geometric and spectral explanations for negative depth.  We will include some discussions about this point in related works section in the revised version of our paper."}]

Author rebuttal:
**General Response for All Reviewers**:

We sincerely thank all reviewers for their valuable time and insightful feedbacks which are very helpful for further improving the quality of our paper. We are grateful that the reviewers appreciate the novelty of our work (`wZLL`:"a significant novel contribution to the community", `yXi3`:"to my knowledge, it is the first attempt", `jrHF`: "interesting and novel"). We are also encouraged that reviewers think that (1) our paper is well-written and the key idea is presented clearly and easy to follow (`yXi3`, `wZLL`, `iB1Z` and `jrHF`); and (2) the empirical experiments are comprehensive (`yXi3`) and solid (`jrHF`). We have provided our point-to-point response to the questions of each reviewer below and we sincerely invite the reviewers for further discussion.

In addition, during the rebuttal period, as suggested by Reviewer `wZLL` and Reviewer `iB1Z`,  we have evaluated TEDGCN-S on 5 new datasets provided in the ICLR 2023 paper by Platonov et al [1]. (Revised Chameleon, Revised Squirrel, Tolokers, Minesweeper and Roman Empire) with same semi-supervised setting as other datasets in our paper. The results are as presented in Table 1.

[1] Platonov et. al. "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?" ICLR 2023.

Table 1: Performance comparison on 5 new datasets in [1] ($ACC \pm std$(\%))

| Model | Revised Chameleon | Revised Squirrel | Tolokers | Minesweeper | Roman Empire|
| ------------ | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
|  SGC  | $35.92 \pm 2.06$ | $29.70 \pm 1.25$ | $78.31 \pm 0.64$ | $80.02 \pm 0.39$ | $39.01 \pm 0.78$ |
|  GCN  | $36.70 \pm 2.72$ | $30.75 \pm 2.09$ | $78.49 \pm 0.51$ | $79.92 \pm 0.41$ | $39.27 \pm 0.42$ |
|  SAGE  | $35.43 \pm 3.80$ | $31.75 \pm 1.67$ | $\textit{78.54} \pm \textit{0.65}$ | $\textbf{82.22} \pm \textbf{0.32}$ | $\textbf{65.57} \pm \textbf{0.92}$ |
|  GAT  | $36.59 \pm 1.18$ | $31.53 \pm 0.89$ | $78.01 \pm 0.51$ | $80.02 \pm 3.30$ | $38.71 \pm 0.98$ |
|  APPNP  | $37.00 \pm 2.18$ | $31.91 \pm 1.19$ | $78.05 \pm 0.49$ | $80.04 \pm 0.37$ | $62.03 \pm 0.41$ |
|  GPRGNN  | $\textit{37.08} \pm \textit{1.88}$ | $\textit{36.60} \pm \textit{0.73}$ | $78.09 \pm 0.51$ | $80.06 \pm 0.78$ | $57.28 \pm 0.49$ |
|  FAGCN  | $35.96 \pm 2.61$ | $32.50 \pm 4.58$ | $78.37 \pm 0.54$ | $80.11 \pm 0.40$ | $62.81 \pm 0.89$ |
|  TEDGCN-S  | $\textbf{40.03} \pm \textbf{1.60}$ | $\textbf{37.21} \pm \textbf{1.70}$ | $\textbf{78.58} \pm \textbf{0.78}$ | $\textit{80.41} \pm \textit{0.70}$ | $\textit{63.05} \pm \textit{0.96}$ |

We can observe that TEDGCN-S outperforms all baselines on Revised Chameleon, Revised Squirrel and Tolokers and achieves the second best performance on Minesweeper and Roman Empire, which demonstrates the effectiveness of TEDGCN-S on these 5 new datasets from Platonov et al. 

Meta-review: The paper introduces a novel approach to adaptively train Graph Neural Networks (GNNs) by proposing trainable depth parameters to handle graph heterophily. The theory is based on graph spectral analysis and supported by exhaustive experiments. Reviewers value the presentation's clarity, innovative contribution, and empirical validity.

While reviewers acknowledge the strengths, they do raise some considerations. These include the applicability of the approach to advanced GNNs, potential limited expressiveness attributed to linearity, and the concentration on transductive settings. However, the substantive value of contributions and the comprehensive evaluation outweigh these concerns. Therefore, the paper is recommended for acceptance. The authors are suggested to incorporate the reviewers' feedback during the preparation of the final version of the paper.
Decision: Accept (poster)