Node Classification Beyond Homophily: Towards a General Solution
Authors: Zhe Xu
Yuzhong Chen
Qinghai Zhou
Yuhang Wu
Menghai Pan
Hao Yang
Hanghang Tong
Venue: Submitted to ICLR 2023 (2023)
Keywords: node classification
structure learning
homophily
heterophily

Abstract: Graph neural networks (GNNs) have become core building blocks behind a myriad of graph learning tasks. The vast majority of the existing GNNs are built upon, either implicitly or explicitly, the homophily assumption, which is not always true and could heavily degrade the performance of learning tasks. In response, GNNs tailored for heterophilic graphs have been developed. However, most of the existing works are designed for the specific GNN models to address heterophily, which lacks generality. In this paper, we study the problem from the structure learning perspective and propose a family of general solutions named ALT. It can work hand in hand with most of the existing GNNs to decently handle graphs with either low or high homophily. The core of our method is learning to (1) decompose a given graph into two components, (2) extract complementary graph signals from these two components, and (3) adaptively merge the graph signals for node classification. Moreover, analysis based on graph signal processing shows that our framework can empower a broad range of existing GNNs to have adaptive filter characteristics and further modulate the input graph signals, which is critical for handling complex homophilic/heterophilic patterns. The proposed ALT brings significant and consistent performance improvement in node classification for a wide range of GNNs over a variety of real-world datasets.

Under review as a conference paper at ICLR 2023
NODE CLASSIFICATION BEYOND HOMOPHILY: TOWARDS A GENERAL SOLUTION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) have become core building blocks behind myriad of graph learning tasks. The vast majority of the existing GNNs are built upon, either implicitly or explicitly, the homophily assumption, which is not always true and could heavily degrade the performance of learning tasks. response, GNNs tailored for heterophilic graphs have been developed. However, most of the existing works are designed for the specific GNN models to address heterophily, which lacks generality. In this paper, we study the problem from the structure learning perspective and propose a family work hand in hand with most of the existing GNNs to decently handle graphs with either low or high homophily. The core of our method is learning to (1) decompose given graph into two components, (2) extract complementary graph signals from these two components, and (3) adaptively merge the graph signals for node classification. Moreover, analysis based on graph signal processing shows that our framework can empower a broad range of existing GNNs to have adaptive filter characteristics and further modulate the input graph signals, which is critical for handling complex homophilichheterophiiii patterns. The proposed ALT brings significant and consistent performance improvement in node classification for a wide range of GNNs over variety of real-world datasets.
general solutions named ALT. It
INTRODUCTION
Graph neural networks (GNNs) have demonstrated the great power as building blocks for variety of graph learning tasks, such as node classification (Kipf Welling 2017), graph classification (Xu et al. 2018), 8), link prediction (Zhang & Chen 2018). clustering (Bianchi et al., (020), and many more. Most of the existing GNNs follow the homophily assumption, i.c., edges tend to connect nodes with the same labels and similar node features. Such assumption holds true for networks such as citation networks (Yang et al. 2016 Bojchevski & Günnemann 2018) where a paper tends to cite related literature. However, in many other cases, the heterophilic settings arise. For instance, to form a protein structure, different types of amino acids are more likely to be linked together (Zhu et al. 2020). On such heterophilic networks, the performance of classic GNN models (Klicpera et al.) 2018 Veličković et al. 2018; Hamilton et al. (017) could degrade greatly and might be even worse than an MLP which does not utilize any topology information at all (Zhu et al. 2020).
In response, researchers have analyzed the limitations of the existing GNNs in the presence of node heterophily and further proposed specific models to address it from both the spatial and spectral perspectives. For instance, an important design by H2GCN (Zhu et al., 2020 is that high-order neighbors should be considered during message aggregation. GPRGNN (Chien al.. 2021] also aggregates messages from multi-hop neighbors but it emphasizes that messages can also be negative via a set of learnable aggregation weights. From the spectral perspective, FAGCN (Bo et al. 202T) points out that low-pass based GNNs smooth the node representations between connected nodes, which is not desirable for the heterophilic settings where connected nodes are more likely to have different labels. Hence, FAGCN (Bo et al. 2021) adaptively mixes the low-pass graph filter with the high-pass graph filter via an attention mechanism to tackle this problem. A more detailed review of related work can be found in Section [
Despite the theoretic insights and empirical performance gain, most of the existing works focus on the model level, i.e., they aim to propose better GNNs models to handle the heterophilic graphs. In

---

Under review as a conference paper at ICLR 2023
other words, the success of their methods relies on specific designs of GNN models. In this paper, we take a step further and ask: how to develop a generic method to benefit a broad range of GNNs for node classification beyond homophily, even if they are not originally tailored for the heterophilic graphs? To this end, we address this problem from a structure learning (Zhu et al. 202 perspective, that is, we optimize the given graph structure benefit downstream tasks (e.g., node classification). Different from the existing approaches that refine the specific GNNs models, our approach focuses on the data level by optimizing the input graph topology to tackle heterophily.
Challenges. In pursuing such a data-centric general solution, here are the key challenges. First (model diversity), our goal is to strengthen a broad range of established GNNs so that they can handle graphs with arbitrary homophily. However, the aggregation mechanism and the graph convolution kernels are different between various GNN models. It is unknown how to accommodate diverse GNNs seamlessly. Second (theoretical foundation), analyses on the success of some specific GNNs for heterophilic graphs have recently emerged (e.g.. from the graph signal processing perspective (Shuman et al. 2013)). However, few works focus on the theoretical foundation of structure learning and its connection to dealing with graphs with low homophily. Our main contributions are listed as follows: (1) We propose a general graph structure learning- based framework named duAL sTructure learning (ALT), which can accommodate a variety of GNN models. Specifically, after removing the activation function from the last layer, any GNN can be plugged into our framework and be trained end-to-end with common optimizers. (2) We provide a detailed analysis from the graph signal processing perspective. Our analysis guides the design of ALT and validates its effectiveness theoretically. (3) Experiments show that with the help of ALT, the node classification accuracy of a broad range of existing GNNs is boosted on heterophilic graphs, and meanwhile kept competitive on homophilic graphs.
2 PRELIMINARIES
Notations. We use bold uppercase letters for matrices (e.g., A), bold lowercase letters for column vectors (e.g., u), lowercase and uppercase letters in regular font for scalars (e.g., d, K), and calli- graphic letters for sets (e.g.. T). We use A [i. j] to represent the entry of matrix A at the i-th row and the j-th column, Aii to represent the i-th row of matrix A, and A [ to represent the j-th column of matrix A. Similarly, u[i] denotes the i-th entry of vector u. Superscript T denotes the transpose of matrices and vectors. @ denotes the Hadamard product.
An attributed graph can be represented as {A, which is composed of an adjacency matrix A E _=*nn and an attribute matrix X E Rnxd where n is the number of nodes and d is the node feature dimension. In total, nodes can be categorized into a set of classes C. The normalized Laplacian matrix is L - D decomposed as L UAUT where U- E Raxa is the eigenvector matrix and E R is the diagonal eigenvalue matrix. In graph signal processing (Shuman et al. (013), the diagonal entry of A represents frequency and A i| = A; Given a signal x E K", its graph Fourier transform (Shuman et al. 2013) is represented as & = Ux, and its inverse graph Fourier transform is defined as x U x. For a diffusion matrix C E R"*", its frequency response (or profile (Balcilar et al. 2021 is defined as Epp diag - (U CU) where diag returns the diagonal entries. This frequency response is also known as the filter and the convolution kernel.
AD AD
where D the diagonal degree matrix of A. It can be
Semi-supervised Node Classification. In this paper, we study semi-superrised node classifica- tion (Yang et al. 2016 Kipf & Welling (017)) where the graph topology A, all node features X, and part of node labels are given and our goal is to predict the labels of unlabelled nodes. Numerous works (Kipl & Welling 2017: Veličković et al. 2018: Klicpera et al., 2018) achieve impressive performance on this problem. However, recent studies show that their successes heavily rely upon the homophily assumption of the given graphs (Zheng et al. 2022) Zhu et al. (2020). In general, homophily describes to what extent edges tend to link nodes with the same labels and similar fea- tures. Following previous works (Zhu et al. 2020: Pei et al. 2019). this paper focuses on the node label homophily. There are various homophily metries and we introduce one of them named edge
homophily (Zhu et al. 2020) as: h(G)= [y]]
[0, 1], where [<>] = 1 if is true and 0 otherwise. The more homophilic a given graph is, the closer its h(g) is to 1.
Σn, AfF.J.
2

---

Under review as a conference paper at ICLR 2023
Amplitude (o)
Amplitude (0)
Amplitude
-1
Frequency (A)
Frequency
Frequency (A)
(a) A given filter
(b) Reflection
(c) Reflection + offiet
Figure I: The Illustration of obtaining a filter with complementary filter characteristics. Given a filter (a), its reflected frequency response (b) with offset (c) has complementary filter characteristies.
PROPOSED METHODS
In this section, we first propose flexible method named ALT-global which empowers any GNN with an adaptive filter characteristics. Next, we carefully analyze the expressiveness of -LT-al from the graph signal processing perspective (Shuman et al. 2013). This analysis guides the design of another more advanced method named ALT-local which enhances the spectral expressiveness of any GNN to local adaptive filter by modulating the input graph signals.
3.1 ALT-GLOBAL: GLOBAL ADAPTIVE METHOD
Intuitively, nodes with different labels should located as far as possible in the embedding space and nodes with the same labels should be assigned closely. This intuition is aligned well with the utility of many classic GNNs (c.g., GCN (Kipf & Welling, (017 on homophilic graphs. That is because, on homophilic graphs, many same-label nodes connected, whose embeddings will be smoothed by those classic low-pass filter GNNs (Bo et al. 2021 Balcilar et al.) 202I). In contrast, the low- low-pass filter GNNs' performance degrades significantly embeddings should not be smoothed. Many efforts (Bo et al. 202 Chien et al., 2021) point out that key design deal with graphs with unknown homophily to equip GNNs with an adaptive filter.
heterophilic graphs since the connected nodes'
We aim to propose a data-centric solution such that minimal modification on the given GNNs (e.g.. low-pass filter GNN) is needed. As we do not make any assumption about the model structure of the given GNN, its filter can be either low-pass, high-pass, band-pac or others. To equip the given GNN with an adaptive filter, our core idea is adaptively combine signals from two filters with the complementary filter characteristics. For example, if low-pas, -pass filter GNN is given, it should be adaptively combined with another high-pass filter. To find such a complementary filter, two-step modification of the frequency response is needed. Figure ssoows that we can first reflect the frequency response curve over the frequency axis and then set an appropriate offset to the reflected frequency response. Guided by this idea, the mathematical details of the proposed ALT-global are as follows.
H, = GNN(WA, X,O)),
(la)
H2 GNN (1 A)A, 02),
(Ib)
H offsat (L.P(X,0)) 0z),
(1c)
Z = sc soffmax - H2 + (1HHHrrsst))
(Id)
where O and 02 are the parameters of the backbone dual GNNs (i.e., GNNs from Eq. and Eq. 1b 0g is the parameter of a multi-layer perceptron (MLP), 1) E and w E [0, 1] are learnable parameters, and Z E ] is the prediction matrix. Here the softmax is applied row-wise. For models using the normalized adjacency matrix (c.g., A (D + +I) (A + (D I 1) as the diffusion matrix (c.g., GCN (Kipi & Welling (017)), )), the re-wcighting can be set over the normalized adjacency matrix (i.e., A and (1 A).
We elaborate more the design of ALT-global. First, all the insights obtained from Figure I are still applicable to the convolution kernel directly. Nonetheless, since our method works in a plug- and-play fashion which does not modify the backbone GNNs, it uses well-designed aggregation
3

---

Under review as a conference paper at ICLR 2023
[d to achieve an equivalent effect. Specifically, (1) H₃ is the signals from a backbone GNN with positive re-scaling; (2) -He is the negative signals that correspond to the signals from a reflected filter: (3) nHoffset is the offset term which is equivalent signals from an all-pass filter. Second, the adaptive mixture of the above three sets of graph signals is controlled by the learnable parameters and 1j. Other aggregation functions are also applicable. One of the options is MIP whose input is the concatenation of H,, Hg, and Horrset. However, it is not used in this paper because (1) increases the analysis difficulties dramatically and (2) empirically, no performance advantage is observed in the ablation study (Section 4.3). Analysis in the following section shows that ALT-global bears strong flexibility in filter characteristics.
(i.e., Eq.
3.2 ANALYSIS OF ALT-GLOBAL
For clarity and brevity, in the following analysis, we assume that the backbone GNNs graph- augmented MLPs (GA-MLPs) as defined below. This is because, first, many GNNs fall into the GA-MLP family if part of the nonlinear functions is removed; and second, GA-MLPs have shown strong empirical performance while enjoying provable expressiveness (Chen et al. 2021).
Definition 1. Graph--Agmented Multi-Layer Perceptron (GA-MLP) (Chen et al. 2021) is a family of GNNs that first conduct feature transformation via MLP and then diffuse the features. Mathematically they compute node embeddings as H = C (X) where is the diffusion matrix.
The (full) frequency profile (Balcilar al. 2021 is closely related the filter characteristics of GNNs and it is introduced as follows.
Definition 2. Frequency profile Balcilarr et al.
is defined as D = diag 'UT CU) where diag- returns the diagonal entries if U CU is a diagonal matrix. In case UT CU is not a diagonal matrix, full frequency profile (Balcilar et al. 2021 defined as + = CU.
2021
It is koll-nnown that the frequency profile of a diffusion matrix (if diagonal) is filter/convolution kernel for the input graph signal. Next, we show that ALT is indeed equipped with an adaptive filter. Lemma 1. The filter characteristic of the proposed ALT-global (Eq. Id) is adaptive regardless of the frequency filtering functionality of the backbone GNNs (Eq. Ta and Eq.
Proof. For analysis convenience, we assume (1) the learnable weight w is multiplied with the diffusion matrix, and (2) the backbone GNNs are GA-MLPs whose MLP modules (from Eq. La and Eq. [b) share common parameters with the offset MLP (from Eq. Tc). We start from the case where backbone GNNs are fixed low-pass filters. Without loss of generality, their corresponding full frequency profiles can be presented as + = I É(A) where & is monotonically increasing function. Then, in this case, the diffusion matrices from two GNNs are re-weighted as wC and (1 w w)C respectively. Considering the offset MLP as a special GA-MLP whose diffusion matrix is I, the combined graph signals are wC MLP X) - (1 - w) C MLP (X) + 7/I MLP (X) = Č MLP (X) where the combined diffusion matrix is C = WC - (1 w) C + n/I. Hence the diagonal entry of the corresponding full frequency profile is
$ ( i) (Ax)) (2w 1)(1 {(>,)) +
When > 0.5, i.e., 2w 1 > 0. (Ax)) is monotonically decreasing function. The proposed method is a low-pass filter when 7) > 0. Similarly, is a high-pass filter when w is close to 0 and 77 1. The above conditions are sufficient and in fact, there are many other combinations of w and which can produce low www-pass/hhhhhpeee shahhiggghssssssee filters. Similar results can be obtained when the backbone GNNs fixed high-pass filters and we omit that part for brevity.
Remarks. The filter characteristics of the ALT-global can also be interpreted from the Graph Diffusion Equation (GDE) (Newman 2018) perspective and we provide the GeEetel analysis Appendix.
3.3 GLOBAL FILTERS vs. LOCAL FILTERS
We have shown that ALT ALT-global is equipped with adaptive filter characteristics. However, ALT ALT-global fundamentally applics a global filter to every node, which could lead to suboptimal performance. Recent studies (Zhu et al. 2021a: Wang et al. 2022a) reveal that heterophilic connection patterns
4

---

Under review as a conference paper at ICLR 2023
differ between different nodes. Take gender classification dating network as example. While node pairs are often of different labels (i.e., genders), homosexuality also exists between some node pairs. Therefore, simply applying global low-pass or high-pan pass filter over all the nodes can degrade the overall classification performance.
Next, will study how generalize our proposed ALT-global local (i.e., node-specific) and adaptive filter. Before that, let us take closer look at the full frequency profile (Balcilar et al. (021): & U' CU. In the following proposition, we point that & describe both the filter and modulator characteristics of a given diffusion matrix C.
Proposition The diagonal entries of the full frequency profile & of the diffusion matrix serve as the filter and the non-zero off-diagonal entries are the frequency modulator.
Proof. The diffusion of the input graph signal Xin = MLP(X) can be represented as CX = U$U X U())).n, where Xin is the input graph signal in spectral domain. According to the definitions of graph signal processing (Shuman et al. 2013)), (IXin)li :] represents the amplitude of output graph signal whose frequency is A₁. We further expand the computation and obtain
+ (xX.)i
Σ 2 E - X.......
In the summation, if j. it represents the filter/convolution kernel which has been adopted by many spectral GNNs (Balcilar et al. 202I). If i A (i.e., non-zero off-diagonal entries of +b exist), it shows that the X.-component of the output graph signal is merged with scaled (by l ,l) Ay Ay-oomponent of the input graph signal which is essentially the modulation (Shuman et al. (013).
Based on the above property of the full frequency profile Φ the following proposition points out the key design for local filter characteristics.
Proposition 2. Modulation of the input graph signal (i.e., non-zero off-diagonal entries in the full frequency profile) is necessary for local filters.
Proof. We follow the terminology used in the proof of Proposition 1 If the full frequency profile + only contains non-zero diagonal entries, we can obtain
+ (i, (diag
[in
(2)
where diag- extracts the diagonal entries into vector from the input square matrix. Hence, if we define the scaling of the X--frequnccy signal over node after and before the operator & as SCALING(i, 4) (.x..)((.))) based on Eq, 2 we obtain
vi,p. SCALING(i, +b SCALING(i,
ie., for any specific frequency (e.g., Ag), its scaling over any two nodes (p and q) are equal. In other words, the filter & works globally over every node. If we expect the filter & to not work globally, i.c.
p. 9, SCALING(i. b) & SCALING(i, q, b)
The above inequality is equivalent to
ΣR $ k)
Kiilk, En D k)
X1n lk;
#
(inli.g)
Assume that Vk, if A D(i, = O, and then the left-hand side is equal to the right-hand side which leads to contradiction. Hence, non-zero off-diagonal entries of the full frequency profile & must exist if we expect the filter to not work globally. Notice that the above definition of scaling
(e.g., (..e))) ) is not fully aligned with the classic graph filtering (Shuman et al. 2013) but
[t.lt.))
combination of filtering and modulation as we mentioned in Proposition 1
Next, we present a family of GA-MLPs whose spectral expressiveness is limited to a global filter. Proposition 3. A family of GA-MLPs are global filters their full frequency profiles are in the form of C Ee A + bl which only contains non-zero diagonal entries.
5

---

Under review as a conference paper at ICLR 2023
Augmenter
Decomposed Graphs
Backbone Dual GNNs
Original Graph
Embodeing
GNN
WGA
H1
Aggregated Representation
Node Classffication
A.X
Girbodding
Euge giring
GNN
WjGIA
H:
Node Features
Offece MLLP
MILP
Baifon
Figure 2: The proposed ALT-local.
We prove Proposition 3 in the Appendix. A wide range of GA-MLPs (e-g.. SGC (Wu al. 2019) APPNP (Klicpera et al. 2018)) follow the above form and therefore cannot modulate graph signal. Unfortunately, even when they are equipped with our proposed ALT-global, they are still global filters because ALT-global assigns the same weight to every edge (i.e., W.A. and (1 (--w)A A).
3.4 ALT-LOCAL: LOCAL ADAPTIVE METHOD
In this subsection, we propose more flexible method based on -LT--llobal. Our goal is to empower the backbone GNNs with local adaptive signal filtering capabilities, which an essential property for capturing complex heterophilic connection patterns. (Zhu et al.] 202 Wang et al., 2022a).
According to Proposition 3 we know that if all the edges are assigned with the same weight (e.g..
wA) the corresponding full frequency profile will only contain diagonal non-zero entries. Lemma provides a clue how to bring non-zero off-diagonal entries in full frequency profiles.
Lemma 2. By re-weighting the edge weights non-unifornly (i.e., if re-weighting by W
Á, ki Wiijj] # W[k, l)), the off-diagonal entries of & can be non-zero.
We prove Lemma in the appendix. Guided by Lemma] we modify ALT-global follows so that the edge weights are different:
Hi GNN W 2 A, X,0 01),
(3a)
H2 = GNN (1- - W) @ A, 0,),0),
(3b)
H satfstt MLP 0z),
(3c)
Z = softmax(H, - H2 + H)Horret)
(3d)
One option is to set W learnable parameter which is prune to overfitting as the number of parameters is equal to the number of edges. Therefore, we parameterize the edge weight W by an edge augmenter as follows,
H = GNN (A,
(4a)
W W Way sigmoid (ILP H (i. [ H(.+),
(4b)
where Φi and 22 are the parameters of the augmenter GNN and multi-layer perceptron (MLP) respectively. Here we first obtain the node embedding matrix via the augmenter GNN (i.e., GNN.ug)
in Eq. 4al Then we concatenate node embeddings into edge embeddings (i.e., Hi edge weight (i.e., Wiy) is computed via MLP with s sigmoid activation. Naturally, the node embeddings from the augmenter GNN (Eq. 4ap should be as discriminative as possible so that the
The
edge importance be better measured. Thus,
two-layer high-pass filter GNN as the GNNaug whose mathematical formulation as follows,
GNN (A X, Φ1) = 2 high MLP Φ1).
(5a)
À Anigh = - D AAD-
(5b)
where e a scaling hyper- parameter to adjust the amplitude of the high filter. We name the above model (i.e., Eqs 5b) ALT-locca which is summarized in Figure]]

---

Under review as a conference paper at ICLR 2023
Remarks. Our method is partly inspired by FAGCN (Bo et al. 2021) and we claim the uniqueness and advantages of our work compared with FAGCN as follows. From the method perspective, FAGCN explicitly mixes freeufreuenccy and low-frequency signals. ALT generalizes this idea to the 'mixture of complementary filters'; thus, even though the backbone GNN's convolution kernel is unknown, ALT can still boost its performance decently, which provides great generality. For the theoretical contribution, [o et al. (2021) analyze the spatial effects of signals with different frequencies. Our analysis takes solid step forward to reveal the connections between the full frequency profile, graph signal modulation, and local adaptive filters.
3.5 TRAINING PROCEDURE
To train our models, we formulate the following bi-level optimization problem.
Φ' arg min Lupper (g(9,)g())))))) 6), 6", .raisa) s.t. 0 arg min Liower 0).
(6)
where the augmenter is denoted as g(.) whose parameter is o and the dual backbone GNNs are parameterized as for brevity. Specifically, for the AlT-global, 0 {81. fg 0g) and
from Eq la Eq lb and Eq Ic For ALT-local, 0 = {81. 22 02} is from Eq. 3a 3b and Eq. 3e f 22) from Eq. 4a and 4b Both Lupper and Liower are cross- cross-yntropy loss between the
classification results (Eq. Id -gT-bll and Eq. [3 for ALT--local and the labelled nodes. The difference lies in that, for the lower-level objective we compute the loss over the training nodes but for the upper-level one we compute the loss over the validation nodes. To solve such a bilevel optimization problem, we resort to the classic first-order approximation (Nichol et al. 2018 to compute the hyper-guu aeper-gradient V VoLupper and any gradient descent- -ased methods can then be used.
If all the feature dimensions of different layers (including the input layers) from different backbone GNNs and MLPs are denoted as d and all the models (GNNs and MLPs) contain 2 feature transfor- mation matrices, the number of trainable parameters of AL.T-local composed of three parts: (1) GNNaug (2d²), (2) MI. from Eq. 4b (2d2 + d). (3) GNN:, 2NN,, and offset MI. (3d2 + 3dc) where e is the number of classes. In practice, the parameter number much smaller than the estimated number. For example for datasets whose d > 500, empirically, setting the hidden dimension as 32 is enough. However, compared with vanilla backbone GNNs (e.g., a simple GCN (Kipf & Welling 2017), ALT-local inevitably contains more parameters as ALT-local is composed of 3 GNNs and 2 MLPs in total. Even for ALT-global, it is still composed of 2 GNNs and 1 MLP. Hence, the increased number of parameters is potential limitation of A AlT-local and -LT-global. Besides, our theoretical analysis relies on the assumption that the backbone GNNs are GA-MLPs. Generalizing our theoretical results a broader range of GNNs is our future work.
4 EXPERIMENTS
4.1 EXPERIMENT SETTINGS
Datasets, We use 16 datasets, including Cora (Yang et al.)
2016),
Citeseer (Yang et al. 2016)).
Pubmed (Yang et al., 2016). DBLP (Bojchevski & Günnemann, 2018).
Computers (Shehrr et al..
2018), Photos (Shchur et al. 2018). CS (Shchur et al. 2018), Physics (Shchur et al. 2018)) Cor-
nell (Pei et al. 2019), Texas (ei et al. 2019). Wisconsin (Pei et al.
2019
Chameleon (Rozemberczki
cet al. 2021). 1) Squirrel (Rozemberezki et al. 2021). Film (Pei et al.
2019
Cornell5 (Lim et al. (022))
and Penn94 (Lim et 2021p. For Cora, Citeseer, and Pubmed, we follow the dataset split from (Kipl
& Welling 2017). We randomly split the other datasets into 20/20/ 10020/660) /60% for training, validation, and
test. Detailed statisties of the datasets are presented in the Appendix Dataset Statistics.
Baseline Methods and Metric. We use 6 baseline methods including 3 classic GNNs; GCN (Kipf & Welling 2017), SGC (Wu et al., 2019), and APPNP (Klicpera et al. 2018)) and 3 adaptive GNNs:
GPRGNN CChien et 2021). FAGCN (Bo et al.) (021). and H2GCN (Zhu et al.) 2020) which use specific designs to tackle graphs with low homophily. Thanks to the flexibility of our method, we equip the above baseline methods with our proposed ALT to validate the effectiveness. As ALT-local is more powerful than Alobgl, we mainly show the performance comparison with ALT-local (short as ALT). The comparison between ALT-local and ALT-globe will be presented in the ablation study. We use the accuracy (ACC) as the metric and report the average accuracy with the standard deviation in 10 runs.
7

---

Under review as a conference paper at ICLR 2023
Table 1: Performance comparison (meanistd accuracy) on heterophilic graphs. The last column indicates the average performance boosting for specific backbone GNN over all the datasets.
Backhone
ALT?
Chamelcon
Squirrel
Texas
Wisconsin
Cornell
Film
Cornell5
Penn94
Avg. A
No
58.4+0.4
35.440.6
57.6+33.5
1.
55.9+0.6
28.1 1
72.8+002
75. 15.1404
GCN
+10.5
Yos
61 6.66
41.940.4
70.3:1111
79.0=0.7
73.9+14
34.820.3
73.520.3
76.9=0.8
No
58.4+0.6
36.8+0.4
58.6+19
46.5+18
57.0=04
27.3=0.1
73,5+0.3
75.7=0.2
SGC
+10.6
Yes
61.940.8
42.24:10
70.040.4
82.0=0.9
78.420.6
32,9=0.2
74.4204
77.4=0.4
No
43.0+0.9
24.240..
19.5
45.7+2.0
56.3+14
28.7+0.3
72.24002
74.0=0.1
APPNP
Yes
55.0110.7
33.51117
72.11:177
76.31333
75.011.
33.610.55
74.110.1
75.7:0..5
+11.5
GPRENN
No
59.240.5
38.410.88
69.11:.0
7..421.6
69.622.5
31.32111
74.1=0.4
78.620.4
+2.5
Yes
59.4.11.2
38.2.10.9
7..3....5
79.5
70.912.9
32.110.8
75.910.3
80.4.10.2
FAGEN
Yes
No
54.3++1.9 9
57.3-11.0
35.6.11.8
32.5++1.4
61.5+113
69.0.1
56.6+55.2
67.914499
66.0+117
36.1
33.8+0.7
71.71:0.9
69.6+-0.8
73.5+0.4
75.8:10.8
+4.1
H2GCN
Yes
No
49.9+0.4
54.0+0.3
29. 89..8
35.34+0.9
65 8+
72.44-2.8
69.5+2.11
77.740.3
63.7+00.
68.5+33.5
34.5+0.3
34.4+-0.4
73.24-0.1
70.8+00.4
73.9=0.3
76.2+-0.4
+4.2
Table Performance comparison (mean accuracy (%)) on homophilic graphs. The last column indicates the average performance boosting for specific backbone GNN over all the datasets.
Backbone
ALT?
Cora
Citeseer
Pubmed
DBLP
Computers
Photos
CS
Physics
Avg. A
No
81.1-0.3
71.2.10.7
79.0-0044
83.7.10.1
6..2.11.D
84,1-0.5
88.2.10.2
95.3 0,1
GCN
Yes
80.9-0.5
71.540.2
79.2-0.3
83.4+0.1
77.8+0044
88.4-0.1
92.040.2
95.6-0.1
+2.5
No 80.8=0.1
71010.2
79.5=0.5
83.84:000
69.1
86.2-0.4
89.7:0.11
95.3=0.0
SGC
Yes
0.56.0.5
71.310.1
79.6-0.44
83.1100.2
79.910033
88.6-1.5
92.8:10.1
95.9-0.0
+2.1
No 82.1=0.1
718100.1
79.8=0.5
83.810.2
66.711.1
83,4=1.2
87.810.1
94.9=0.0
APPNP
+2.7
Yes
82.4=0.4
71.7002
79.5=0.8
84.4+0.1
77.620088
88.3=0.7
92.4#00.4
95.5=0.1
GPRGNN
Yes
No
78.6=1.5 1.5
80.9=033
68 68.9+-0.9
68.8400.2
78.2=004
77.6=0.9
84.4+:0.
84.4+002
85.921.5
85.0=0.5
92.6=0.3
92.4-0.2
93.2::0.
92.3++0.1
95.7=0.1
95,5-0.4
+0.6
FAGCN
No 7..0-0.6
72.1110.5
7..0=1.1
81.E111
74.81:3.4
91.2-003
93.011144
95.7=0.3
+0.5
Yes
79.0-0.4
71.9+0.5
77.9
82.5+-0.7
+6.1
0.7
93.6-+0.2
96.0 0.1
No
78.9=0.6
70.3+10
78.2=1.0
82.4+0000
75.8::0.3
89.7=0.2
92.5+002
96.2=0.1
H2GCN
Yes
7.73=0.7
70.5113
77.9=10
82.24:0.2
80.410.88
90.3=1.0
93.51:0.2
96.3-0.1
+0,8
4.2
MAIN RESULTS
We present the performance comparison heterophilic graphs in Table First, on the heterophilic graphs, general, our method ALT can significantly improve the performance of most of the existing GNNs, especially for methods originally not designed for the heterophilic graphs (e.g.. GCN, SGC, and APPNP). On average, over 10% improvement is obtained among the heterophilic graphs Second, the heterophilic graphs, for adaptive GNNs (e.g., GPRGNN, FAGCN, and H2GCN), their performance improvement is not as significant as low-pass filter GNNs. This expected since these methods have already dealt with heterophily to some extent. Nonetheless, we still gain 2 4% performance improvements averaged over all 8 heterophilic datasets.
The performance comparison homophilic graphs is presented in Table We test 48 graph-GNN combinations, out of which, 35 cases show improvements. It is worth noting that even though GCN, SGC, and APPNP are designed mainly for homophilic graphs, the proposed ALT is still able to significantly boost their performance on Computers by nearly 10%. Moreover, for each backbone GNN, the average gain of applying the proposed ALT over all 8 homophilic graphs is always positive. Most of the remaining cases bear very minor performance losses (12 out of 13 are below 0.5%). Thus, we conclude that ALT can retain or even boost the performance of given backbone GNNs on homophilic graphs.
4.3 ABLATION STUDY AND HYPERPARAMETER STUDY
In this section, we present systematic ablation study datasets: Chameleon (Rozemberczki et al. 2021). Squirrel (Rozemberczki et al. (021). Film Pei et al. 2019). Computers (Shchur et al.) 2018)) Photos (Shchur et al.) 2018), and CS (Shhhur et al. 2018). Specifically, we have the following ablated versions: (I) local, (2) ALT-local with a low-pass filter augmenter (i.e., change Eg as a two- layer SGC) which is named AL.--lcaal-low, (3) AL.T-local-concat whose aggregation step (Eq. 3d
8

---

Under review as a conference paper at ICLR 2023
Table Results of ablation study
(Backbone GNN: GCN).
Backbone
Version
Chameleon
Squirrel
Film
Computers
Photos
CS
None
58.420.4
35.420.6
28.11:0.3
66.2=100
84.120.5
88.2:0.22
Global
58.5+11.2
36.5=0.5
30.1+00.
67.5=11
85.9+0.77
89.5=0.11
GCN
Local-low
60.41:06
39.8=0.9
31.610.3
73.4=15
86,240.6
90.420.3
Local-concat
43.3+118
29.2=0.6
34.72110
72.1=4.0
85.1+-4.1
87.2=0.8
Local
61.6:10,9
41.9-04
34,8:1033
778:0044
88.410.1
92.0=0.2
is instantiated by 'concatenation' followed by an MLP (4) ALT-global, and (5) vanilla backbone GNNs without methods (named None). Results with GCN as the backbone are presented in Table 3 and results with SGC and APPNP as the backbones are presented in the Appendix Additional Experimental Results. From the above results we conclude that the ALT-local has consistent advantages over all ablated versions. In addition, we provide a hyperparameter sensitivity study in the Appendix Additional Experimental Results.
RELATED WORK
Graph Structure Learning. Graph structure learning aims modify the given graph structure to improve the performance of downstream tasks. For instance, to boost message propagation, inserting virtual nodes is an effective approach (Gilmer et al. 2017 Li al. 2017). For topology denoising, dropping some existing edges can improve the model robustness (Wu et al. 2020 Luo et al. 1
and climinate redundant information from the input (Yu et al. 2020). Another line research views the given graph as the optimization variable and updates them according
the performance of downstream node classifiers (e.g.. LDS (Franceschi et al. 2019) and Gasoline (Xu et al., 2022)). Other works which formulate the given graph random variable and infer its optimal parameters include Bayesian GCNN (Zhang et al.] 2019). GEN (Wang et al. (202I. and many more. Recently, Zhu al. (Zuu et al. 20216) provide comprehensive survey on this topic.
Graph Learning on Heterophilic Graphs. Heterophilic graphs are also known as disassortative graphs. Many message-passing based GNNs suffer from the performance degradation on the het- erophilic graphs and several approaches have been developed for that. For example, Geom-GCN (Pei al. 2019) and H2GCN (Zhu al.) 2020) expand the pesssagepaassing mechanism beyond the first-order neighbors. GPRGNN (Chien et al. 2021) and BernNet (He et al. (02T)) set the weights for different propagation results as learnalle parameters to work an adaptive graph filter. FAGCN (Bo) et al. 2021 GBK (Du et al. 2022), and ACM-GNN (Luan et al.) 2021) explicitly mix two convo- lution kernels through attention- mechanisms. Based on the above work, DMP (Yang et al.) 2021) studies this problem in finer granularity where it introduces feature specific message- passing mechanism. Yan et al. (202T) reveal the connections between oversmoothing and network heterophily. Other works which modify the propagation step of GNNs for the heterophilic graphs include CPGNN (Zhu et al.] 2021a), HOG-GCN (Wang et al.) 2022b), and GloGNN (Li et al. (022). Interestingly. Luan al. (Luan al., (021) and Ma et al. (Ma et al. (021) both report that there are some cases where high heterophily will not hurt the performance of low-pass filter GNN which reveals further unexplored space for this problem. Zheng al. (Zheng al., 2022) recently present survey on this topic. The only structure learning based solution on addressing graph heterophily, as far as authors' knowledge, WRGAT (Suresh al. 202T) which improves the graph homophily by a heuristic method. As comparison, our proposed framework is more flexible and theoretically solid.
6 CONCLUSION
In this paper, we propose a general framework ALT for the semi-supervised node classification problem on graphs beyond homophily. Our method introduces novel structure learning- based augmenter to decompose the given graph. After that, dual GNN module can be instantiated as most of the existing GNNs on the decomposed graphs. Systematic theoretical analysis shows that our proposed method can adaptively filter and modulate the graph signals which is critical to address complex heterophilic connection patterns. Comprehensive empirical evaluation and ablation study demonstrate that the proposed ALT obtains significant performance improvement for wide range of GNN models, on a variety of graph datasets with arbitrary homophily.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In ICLR, 2021.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In ICMI., 2020.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In AAAI, 2021.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In ICLR, 2018.
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented mlps. In ICLR, 2021.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk- gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In TheWebConf. 2022.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurlPS, 2017.
Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. NeurIPS, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2018.
Junying Li, Deng Cai, and Xiaofei He. Learning graph-level representation for drug discovery. arXiv preprint arXiv:/709 03741, 2017.
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.07308, 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang. Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. NeurlPS, 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Kiao-Wen Chang. and Doina Precup. heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109. 10t.::2109.0.41,,, 2021.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In WSDM, 2021.
Yao Ma. Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? arXiv preprint 106.v2/06.06/.33 06134, 2021.
Mark Newman. Networks. Oxford university press, 2018.
10

---

Under review as a conference paper at ICLR 2023
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meaa-lea algorithms. arXiv preprint arXiv:1803.025: 02999, 2018.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnabb01, 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: J. 1.05868, 2018.
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending -igh-dimessionl data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. Graph structure estimation neural networks. In The WehConf, 2021.
Tao Wang, Di Jin, Rui Wang, Dongxiao He, and Yuxiao Huang. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. In AAAI, 2022a.
Tao Wang, Rui Wang, Di Jin, Dongxiao He, and Yuxiao Huang. Powerful graph convolutioal networks with adaptive propagation mechanism for homophily and heterophily. In AAAI, 2022b.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICML, 2019.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. NeurlPS, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2018
Zhe Xu, Boxin Du, and Hanghang Tong. Graph sanitation with application to node classification. In Proceedings of the ACM Web Conference 2022, pp. 1136-1147, 2022.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06-42, 2021.
Liang Yang, Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, et Diverse message passing for attribute with heterophily. NeurIPS, 2021.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. In ICLR, 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurIPS, 2018.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI, 2019.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv22202.07008, 2022.
11

---

Under review as a conference paper at ICLR 2023
Jiong Zhu, Yujum Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In AAAI, 2021a.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure learning for robust representations: A survey, arXiv preprint arXiv:2103.03036 2021b.
12

---

Under review as a conference paper at ICLR 2023
A
REPRODUCIBILITY
Hardware V100 SXM2-32GB.
We implement ALT in pytorc and pytorch-geometric using one NVIDIA Tesla
Dataset statistics
The detailed statistics of datasets are presented in Table and Table 5
Table 4: Dataset statistics of heterophilic graphs
Chameleon
Squirrel
Texas
Wisconsin
Cornell
Film
Cornell5
Penn94
Nodes
2,277
5,201
183
7,600
18,660
41,554
# Edges
62,792
396,846
325
515
298
30,019
1,581,554
2,724,458
Features
2,325
2,089
1,703
1,703
1,703
932
4,735
4,814
# Classes
5
5
5
5
5
2
2
(g)
0.231
0.222
0.108
0.196
0.305
0.219
0.479
0.470
Table 5: Dataset Statistics of homophilic graphs.
Cora
Citeseer
Pubmed
DBLP
Computers
Photos
CS
Physics
# Nodes
2,708
3,327
19,717
17,716
13,752
7,650
18,333
34,493
# Edges
10,556
9,104
88,648
105,734
491,722
238,162
163,788
495,924
# Features
1,433
3,703
500
1,639
767
745
6,805
8,415
Classes
7
6
10
15
5
M())
0.810
0.736
0.802
0,828
0.777
0.827
0.808
0.931
Detailed Experimental Settings We obtain all the datasets from -rrooccggemmetric which public. We follow the given dataset split for Cora, Citeseer, and Pubmed. For the remaining datasets, randomly split them into 20/20/60% do not follow the dataset split from the paper of GPRGNN (Chien et al. (021) as they manually assign the same number of training samples each class and our dataset split is more practical. For all the GNNs (including the augmenter and backbone GNNs), we set the hidden dimension as 16, the learning rate as 0.05. For all the backbone GNNs, their weight decay is set as 0.0005. For the augmenter GNN, its weight decay is searched in (0.005, 0.0005, 0.00005) and its is set as 0.5. We are still going through our internal review process for releasing code, and we expect to able to release it before the conference.
training, validation, and test Notice that here
B ADDITIONAL EXPERIMENTAL RESULTS
The ablation study results with SGC and APPNP backbones are presented in Table and model ALT local obtains consistent advantages. The results are consistent with the ones presented in the main content whose backbone GNNs are GCN.
and 7 Our best
Table 6: Results of ablation study (Backbone GNN: SGC).
Backbone
Version
Chameleon
Squirrel
Film
Computers
Photos
CS
None
58.4+006
36.8-0.4
27.3+0.1
69.1+0.4
86.2+0..4
89.7+-0.1
Global
58.5+0.9
3..6=0.4
28.6+0.2
69.5+0.5
87.2+0.2
90.1++0.3
SGC
Local-low
60.8.11.5
40.6-0.5
29.510.2
76.410.2
87.910.2
90.8.10.3
Local-coneat
45.15
30.0=1.3
32.8+0.2
75.6+2.0
88.6+1.2
90.2+0.6
Local
61.9+0.8
42.2=1.0
32.9+0.2
79.9+-.3
88.6+11.5
92.8+0.1
hhtpss//pytorch.orrg
13

---

Under review as a conference paper at ICLR 2023
Table 7: Results of ablation study (Backbone GNN: APPNP).
Backbone
Version
Chameleon
Squirrel
Film
Computers
Photos
CS
None
43.0:1.9
2..2
28.7.1..3
66.711111
83,411.2
87.8:0.11
Global
45.9
28.5=0,6
31.1+0.3
70.1
84.9#1.2
89.3+0.1
APPNP
Local-low
51.0+1.3
30.0=1.2
32.2+1.4
74.3+:122
87.3+0.4
91.8:10.2
Local-concat
43.240.4
26.0=0.3
33,8:10.9
73.6+22.1
82.54:2.1
89.4:10.5
Local
55.0110.7
33.5=117
33.610.5
77.62:..8
88.3110.7
92.41104
We provide a hyperparameter sensitivity study follows. Specifically, we study the sensitivity of ALT-local concerning the amplitude of the high-pass filter for the augmenter GNN (i.e, e from 5b) We select GCN (Kipf & Welling 2017) and GPRGNN (Chien et al., (02I) backbone GNNs and conduct experiments over Cora Yang et al. 2016 Citeseer YYngg et al. 2016). Chameleon (Rozem- berezki et al.) (02I), Squirrel (Rozemberczki et al.) (202]) datasets. Results presented in Figure from which we observe that the model performance is stable for the selection over four datasets and two selections of the backbone GNNs (i.e., GCN and GPRGNN).
90
90
Cora
Cleseer
Chamelson
Squirnl
Cora
Cleeser
Chamelsen
Squirel
Accuracy (56)
Accuracy
60-
60
50
30
30
0.2
0.3
0.4
0.5
0.6
0.8
0.9
0.1
0.2
0.3
0.4
0.5
3.6
0.7
0.9
(a) GCN
(b) GPRGNN
Figure 3: Hyperparameter sensitivity of ALT with backbone GNN as (a) GCN and (b) GPRGNN.
C PROOF OF PROPOSITION 3
Proposition A family of GA-MLPs are global filters if their full frequency profiles in the form of C -x A A k + bi which only contains non-zero diagonal entries.
Proof. Since {Ā*) and share the same eigenvectors, the diffusion matrix can be decomposed as
C= Σ A + bi ==U
- a (I- T....
k
Hence, the frequency profile is +- Ee ax (I- Ay* + bI whose off-diagonal entries are zero.
D PROOF OF LEMMA 2
Lemma By re-weighting the edge weights non-uniformly (i.e., if re- weightntting by W
A, k, Wii.j] + W[k,)), the off-diagonal entries of & can be non-zero.
Proof. We follow the assumption mentioned in the proof of Lemma [ The diffusion matrix C can be decomposed as
T For the full frequency profile +, off-diagonal entry + $ii = Ex L U7, CI, A) J = 0, vi + j. If we re- weight the diffusion matrix by W @ C such that WIL, Kj wi and W
# Wik Vi * I and # k. In other words, start from the most basic case where only one edge (1, k) is re-ghithted by Wik and all the remaining edges are re-weighted w. Recall that क क
i] Σ., Ui, ClT. Ulk, which be non-zero. In other
14

---

Under review as a conference paper at ICLR 2023
words, it is common that U(k, + 0. Therefore, it should be easy to find pair of node and j such that U],, * and we obtain
& ree-weighed [i. = (UT (w o [
-U (w @ C)U) w
= Ult CI, k - w) + O.
Therefore, proved that if the edge weights re-weighted non-uniformly, the off-diagonal entries of Φ can be non-zero, i.e., the GNN can be local filter.
E ANALYSIS OF ALT-GLOBAL FROM THE GRAPH DIFFUSION EQUATION (GDE) PERSPECTIVE
As we claimed in Lemma I our proposed ALT-global can be an adaptive filter even if the given backbone GNNs only have fixed filters. Here, we prove this from the Graph Diffusion Equation (GDE) (Newman 2018) perspective. Our proof will focus on the case where the diffusion matrix is the normalized adjacency matrix A D -----=AA AD - whose convolution kernel is fixed. Other cases can be proved in similar ways.
Given graph signals H, its diffusion process can be presented H = AH( Thus, we have
HOO H - H(!
H(+1)
(++1)-E ÁH H
(7a)
In the GNN case, f 0 denotes the GNN depth and in the GDE context, it denotes the diffusion time. Thus, we the time interval as At, the graph diffusion dynamies can be presented as follows,
H(++1) H(O)
(H(
AH
-HO
(
(8a)
At
dt
where L - AD is the normalized Laplacian matrix. As ALT-global re- re-weights all the edges into w and (1 A, we have
HH (1)
dt WAH -H() (wA wI - I)) (-wL (1 w I)H (
(9a)
dH (1)
(1 (1- (1-
H (- -- wI)H
(9b)
dl
Recap that the prediction matrix of ALT-globe is by combining signals from dual backbone GNNs and an offset MLP as Z = softmax
H, + (orrse)). We keep the assumption that the dual backbone GNNs are both GA-MLPs (Chen et 2021 which shares parameters with our offset
MLP. Thus, we have H H = Haffse: H MLP (X)
As analyzing its diffusion dynamics, there is interaction between any two columns of the feature matrix (( (and ) Hence, for brevity, we only show analysis of a single feature h H [s, m]. h H [:, m)) h = hoffset Hoffset [3, ml] (t) (; m), Vmn E (1...., n).
The dual GNÑs" GDEs can be presented as follows,
dh (t)
(-wL- (1 w I1)
(10a)
dh (t)
(- L wI)h (4)
(10b)
dt
Proposition 4. The solutions Eq. T0a and Eq. 10b can be presented
h = Σ (
(0) (1)))( u; and h Er a. (0) ((1 u, where u, and
X; refers to the i-th eigenvector and eigenvalue L.; initial state a; is determined by h =h (0)
Σ, a Ui
15

---

Under review as a conference paper at ICLR 2023
Proof. Here prove the solution of Eq. and for Eq. 10b its solution can be obtained in similar way. For Eq. [0a] by decomposing the graph signal with the eigenvectors (fu,) }) of the normalized Laplacian L we have:
h = Σ u.
(11)
As only h and a₂ are the functions of i, based on the fact that Lu; Xuu, and Iu, u, we have:
Σ da: (t)
wd:a 19) + (1 :))a )u: O.
(12)
As all the cigenvectors are orthogonal with each other, by multiplying both sides of the above equation with u, we have
da!" v)aa ((1-w)a )u;
(13)
da (1)
+ weaa + - a (1) 0.
(14)
dt
Hence, the graph signal h, can be represented as
11
a e- (w>x++((1--01
(15a)
Similarly, the graph signal ho can be presented as
h
a (0) ((1 ((1=m))++t Ju.
(16a)
LI
Thus, aggregated signal can be presented as (here we use hareset
= hh) = Σm= ai u
u
(1) h - h2 + mooceset
(17a)
n (0) (w>c+ - (11 ((1-w))ctw) + +1 u,
(17b)
According to the graph signal processing (Shuman al. (013)) u, denotes the graph signal with A frequency. Hence, a(") (w( -e1((1 ww) denotes the amplitude of the the
X--frequency signal after filtered by ALT-global. We know the signal before filtering (i.e., diffusion)
(0)
h
=h offsst
(18)
and the amplitude of the the X;- X--freuuency signal before filtering is a. Hence, the filter response A; frequency is
a (0)
(((wxx+(1-w)) - - ((1- +1)
((,,)
(19a)
=c- (w))
+
(19b)
It is clear when 0,, 4(A,) is a monotonically decreasing function and when w < 0, ((A)) a monotonically increasing function. With appropriate and different w, ALT-global can be instantiated either low-pass filter high-pass filter.
16


Reviews:
[{"review_id": "yiDOQGTVLY", "reviewer": "Reviewer_Jqz9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Main concern. How to accommodate GNNs to deal naturally with heterophily and provide a theoretical analysis (from signal processing perspective). The core idea is to transform/combine low-pass filter into/with high-pass, for instance. There are two learnable parameters: w and \\eta whose values lead to low-pass or high-pass filters (adaptive filters): \n\nThe above conditions are sufficient and in fact, there are many other combinations of w and η that can produce low-pass/high-pass filters \nAs stated in the proof of Lemma 1. I found this idea very interesting, in particular the distinction between GLOBAL and LOCAL filtering. In particular, the insight of how GLOBAL filtering degrades the performance in a heterophilic scenario is useful. \n\nRelated work is analyzed and the contribution evolves from FAGCN which explicitly mixes high-frequency and low-frequency signals. ALT generalizes this idea to the ‘mixture of complementary filters’; thus, even though the backbone GNN’s convolution kernel is unknown \n\nResults are very challenging since for heterophilic graphs, the proposed approach ALT increases the performance and for homophilic case, it preserves it or even improves it. The ablation study is very useful to understand the contribution of the local filter. \n\nNotes. Please, clarify that the frequency profile is basically the function phi applied on the spectrum (e.g phi = exp() when we apply a heat kernel) under the spectral theorem: phi(A) = U*phi(lambda)*U^T.\n\n", "summary_of_the_review": "The paper provides nice results regarding how to minimally modify existing GNNs to deal with heterophilic graphs. The theory could be better explained but the paper is in general readable and direct. ", "strength_and_weaknesses": "* Strengths: results are very challenging and \n* Weaknesses: the underlying theory could be clarified more clearly for the nonexperts in spectral graph theory.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "y0WyNAlWfkz", "reviewer": "Reviewer_j7Qg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a general framework ALT to deal with the heterophily problem in GNNs. The main idea is to design multiple GNNs or MLP with different graph filters and it finally merges their predictions regardless of the GNN backbones. A local version is also developed for further improvement. ", "summary_of_the_review": "The paper proposes a general framework ALT to deal with the heterophily problem in GNNs. The main idea is to design multiple GNNs or MLP with different graph filters and it finally merges their predictions regardless of the GNN backbones. The novelty is limited compared with existing approaches, and it is unclear how it advances the state-of-art algorithms. Moreover, a local version is developed for further improvement but the proposed method is quite heuristic without clear justification and running time analysis.", "strength_and_weaknesses": "# Strength:\n\n1. The paper is well-written and easy to follow.\n\n2. The proposed idea can be used as a general framework to potentially improve any GNN models.\n\n3. The motivation of ALT-Global is clear and valid.\n\n# Weakness:\n\n1. The novelty of the proposed idea is limited. The idea of combining graph signals from different graph filters is implicitly encoded in polynomial filters of graph signals, and this is a well-studied problem in the literature. For instance, in the analysis of ALT-Global (Section 3.2), the paper assumes the GA-MLP architecture: $H=C~MLP(X)$ and all three MLPs share the same parameters. Then the proposed ALT essentially reduces to a specific case of GPRGNN [1] whose polynomial filter is even more flexible and adaptive. \n\n2. The proposed framework might be able to improve some classic GNN backbones (such as GCN, SGC, and APPNP) that intrinsically adopt low-pass filters and therefore can not handle heterophilic data. However, it is unclear how the proposed idea improves stronger approaches such as GPRGNN [1] and other approaches with high-frequency filters. \n\n3. In the ablation study (Table 3), even for GCN, the ALT-Glocal variant only improves the performance very marginally. I suspect that ALT-Global can not improve the performance of GPRGNN, APPNP, or GCNII. The paper only presents the ablation study on GCN, but more results are needed to clarify this concern.\n\n4. The local adaptive method proposed in Section 3.4 is heuristic and ad-hoc. The training procedure in Section 3.5 seems to be computationally expensive but there is no discussion on the running time and training cost. \n\n5. There is a lack of comparison with other local adaptive approaches which also adaptively adjust the edge weight as in ALT-Local. For instance, graph attention networks [2] adjust the weight by attention scores; ElasticGNN [3] models the locally adaptive smoothness over the graph by graph trend filtering; DAGNN [4] adjusts the feature combination from different propagation layers by attention scores; More discussion and comparison will be helpful to justify the advantages of the proposed idea. Overall, it will be beneficial to show how the proposed idea improves state-of-art algorithms instead of old algorithms.\n\n[1] Adaptive Universal Generalized PageRank Graph Neural Network, ICLR 2021\n\n[2] Graph Attention Networks, ICLR 2018\n\n[3] Elastic Graph Neural Networks, ICML 2021\n\n[4] Towards Deeper Graph Neural Networks, KDD 2020\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ll5SN9bhzA2", "reviewer": "Reviewer_qBZ9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "**Summary**\nThe paper proposed a method ALT to convert any graph neural network to be effective for non-homophily graphs. The key idea is to use two backbone GNNs and an additional MLP to shift (or adapt) the frequency response function of the diffusion filter. The authors also propose a more complicated version of ALT which compute a weight of edges with an additional GNN. The resulting model is optimized with a bi-level optimization method on both the train and valid vertices. ALT shows good empirical performance, especially on non-homophily graphs and on top of the classical GNNs.", "summary_of_the_review": "Borderline accept, would be stronger if issue with experiments fixed.", "strength_and_weaknesses": "**Good Empirical Results**\nThe authors performed a very comprehensive study on a wide range of datasets. The authors also compared against a wide range of baselines. Overall the improvement is quite significant. Also, the authors conducted a detailed ablation study of ALT-local. That highlight the importance of frequency modulator.\n\n**Well Motivated/Explained Architecture Design**\nThe ALT design is well motivated by the combination of two filters with complementary characteristics. The edge reweighting is well motivated by the need to switch from global filter to local filter. The augmentation GNN is also well motivated by the discriminative argument to use a high pass filter.\n\n**Issue with Experiments**\nOne complain I have is that the bi-level optimization explicitly use the validation vertices to train the augmentation. This makes the empirical comparison unfair for the baselines. My suggestion would be to split part of the training nodes for training the backbone and augmentation separately.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "h5otkeaFU7", "reviewer": "Reviewer_AcUh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors ALT to handle graphs with either low or high homophily by decomposing a given graph into two components, extracting complementary graph signals from these two components, and adaptively merge the graph signals for node classification. ", "summary_of_the_review": "Although some theoretical analysis is interesting, this paper lacks novelty and strong experimental support. Thus, I don't think it is ready to be published.", "strength_and_weaknesses": "## Strength\nThe frequency analysis is somehow interesting.\n\n## Weaknesses\n1. The writing needs to be improved.\n2. The idea is not novel.\n\n\n## Questions and Comments\n\n1. “our core idea is to adaptively combine signals from two filters with the complementary filter characteristics. For example, if a low-pass filter GNN is given, it should be adaptively combined with another high-pass filter.” Combining low-pass filter and high-pass filter adaptively is exactly the same as [3] and as the author mentioned, “equip GNNs with an adaptive filter” is not a new idea.\n\n2. The authors show that “The filter characteristic of the proposed ALT-global (Eq. 1d) is adaptive…”. How does the learned filter compared with GPRGNN and BernNet?\n\n3. “applies a global filter to every node, which could lead to suboptimal performance.” Any evidence to this claim?\n\n4. The ALT-LOCAL is very similar to FB-GAT, which combines low-pass filter, high-pass filter and learnable edge weights adaptively.\n\n5. It is invalid to use validation label in the training process.\n\n5. Some recent works find some empirical and theoretical  evidence that heterophily is not always harmful and homophily is not always necessary for GNNs [1,2,3]. How.does this work align with the previous works.\n\n6. Some missing comparison, e.g. LINKX [4], BernNet [5], ACM-GCN [3] and GloGNN[6].\n\n[1] Zhu J, Yan Y, Zhao L, et al. Beyond homophily in graph neural networks: Current limitations and effective designs[J]. Advances in Neural Information Processing Systems, 2020, 33: 7793-7804.\n\n[2] Ma Y, Liu X, Shah N, et al. Is homophily a necessity for graph neural networks?[J]. arXiv preprint arXiv:2106.06134, 2021.\n\n[3] Luan S, Hua C, Lu Q, et al. Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?[J]. arXiv preprint arXiv:2109.05641, 2021.\n\n[4] Lim D, Hohne F, Li X, et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods[J]. Advances in Neural Information Processing Systems, 2021, 34: 20887-20902\n\n[5]  He M, Wei Z, Xu H. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation[J]. Advances in Neural Information Processing Systems, 2021, 34: 14239-14251.\n\n[6] Li X, Zhu R, Cheng Y, et al. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily[J]. arXiv preprint arXiv:2205.07308, 2022.\n\n[7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank\ngraph neural network. In International Conference on Learning Representations, 2021.\n\n[8] Luan S, Zhao M, Hua C, et al. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks[J]. arXiv preprint arXiv:2008.08844, 2020.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject