EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks
Authors: Runlin Lei
Zhen WANG
Yaliang Li
Bolin Ding
Zhewei Wei
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Homophily
Robustness

Abstract: Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Despite their extraordinary predictive accuracy, existing approaches, such as GCN and GPRGNN, are not robust in the face of homophily changes on test graphs, rendering these models vulnerable to graph structural attacks and with limited capacity in generalizing to graphs of varied homophily levels. Although many methods have been proposed to improve the robustness of GNN models, most of these techniques are restricted to the spatial domain and employ complicated defense mechanisms, such as learning new graph structures or calculating edge attentions. In this paper, we study the problem of designing simple and robust GNN models in the spectral domain. We propose EvenNet, a spectral GNN corresponding to an even-polynomial graph filter. Based on our theoretical analysis in both spatial and spectral domains, we demonstrate that EvenNet outperforms full-order models in generalizing across homophilic and heterophilic graphs, implying that ignoring odd-hop neighbors improves the robustness of GNNs.  We conduct experiments on both synthetic and real-world datasets to demonstrate the effectiveness of EvenNet. Notably, EvenNet outperforms existing defense models against structural attacks without introducing additional computational costs and maintains competitiveness in traditional node classification tasks on homophilic and heterophilic graphs.

EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks
Runlin Lei Renmin University of China runlin rucicuududucn
Zhen Wang Alibaba Group
Yaliang Li Alibaba Group yaliang. li@ @liixba-inc.com
jones. wze www.wwaabaa-iiieccoo
Bolin Ding Alibaba Group bolin.ding alibaba-inc.com
Zhewei Wei
Renmin University of China
zhewei@ruc.edu..
Abstract
Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Despite their extraordinary pre- dictive accuracy, existing approaches, such as GCN and GPRGNN, are not robust in the face of homophily changes on test graphs, rendering these models vulnerable to graph structural attacks and with limited capacity in generalizing to graphs of varied homophily levels. Although many methods have been proposed to improve the robustness of GNN models, the majority of these techniques are restricted the spatial domain and employ complicated defense mechanisms, such as learning new graph structures or calculating edge attention. this paper, we study the problem of designing simple and robust GNN models in the spectral domain. We propose EvenNet, spectral GNN corresponding to an even veen-polynomial graph filter. Based our theoretical analysis in both spatial and spectral domains, we demonstrate that EvenNet outperforms full-order models in generalizing across homophilic and heterophilic graphs, implying that ignoring odd-hop neighbors improves the robustness of GNNs. We conduct experiments on both synthetic and real-world datasets to demonstrate the effectiveness of EvenNet. Notably, EvenNet outperforms existing defense models against structural attacks without introducing additional computational costs and maintains competitiveness in traditional node classification tasks on homophilic and heterophilic graphs. Our code available in https: bettps///gitee //gp::/btttttttt./e www.thub.comm...... www.o//weewwnnn//oo.ooo......eee Envenneett
Introduction
Graph Neural Networks (GNNs) have gained widespread interest for their excellent performance in graph representation learning tasks [10 13. (28). GCN is known to be equivalent to a low-pass filter [2) 21), which leverages the homophily assumption that "connected nodes more likely to have the same label" as the inductive bias. Such assumptions fail in heterophilic settings [37] where connected nodes tend to have different labels, encouraging research into heterophilic GNNs 22 37).
Among them, spectral GNNs with learnable polynomial filters B g [4] adaptively learn suitable graph filters from training graphs and achieve promising performance on both homophilic and heterophilic graphs. If the training graph is heterophilic, a high-pass or composite-shapee graph filter empirically obtained.
'Zhewei Wei is the corresponding author. The work was partially done Gaoling School of Artificial Intelligence, Peng Cheng Laboratory, Beijing Key Laboratory of Big Data Management and Analysis Methods MOE Key Lab Data Engineering and Knowledge Engineering.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

While GNNs are powerful in graph representation learning, recent studies suggest that they are vul- nerable to adversarial attacks, where graph structures are perturbed by inserting and removing edges
on victim graphs to lower the predictive accuracy of GNNs 38 31 Zhu et al. [6] first established the relationship between graph homophily and structural attacks. They claimed that existing attack mechanisms tend to introduce heterophily to homophilic graphs, which significantly degrades the
performance of GNNs with low-pass filters. On the one hand, several attempts are made to improve
the robustness of GNNs against the injected heterophily from the spatial domain [1]6 22 34 35)
These methods either compute edge attention or learn new graph structures with node features, requiring high computational costs in the spatial domain. On the other hand, while spectral GNNs hold superiority on heterophilic graphs, their performance under structural perturbation is unsatis- factory as well, which arouses our interest in exploring the robustness of current spectral methods.
In this study, we consider sumophily-hetterohiiy inductive learning tasks, which naturally model non-targeted structural at- tacks. We observe that structure attacks enlarge the homophily gap between training and test graphs besides introducing het- erophily, challenging spectral GNNs generalize across differ- ent homophily levels. Consequently, despite their outstanding performance heterophilic graphs, spectral GNNs such as GPRGNN have poor generalization ability when the training and test graphs have different homophily. For example, sup- pose we now have two friend-enemy networks like the ones in Figure [ If friends more likely become neighbors, repre- senting the relationship "like", the network is homophilic. If enemies form more links corresponding to the relationship "hate", the network becomes heterophilic. If we apply spectral GNNs trained on "like" networks (where a low-pass filter is obtained) to "hate" networks, we will mistake enemies for friends on "hate" networks. Despite the strength of spectral GNNs in approximating optimal graph filters of arbitrary shapes, the lack of constraints on learned filters makes it difficult for them to generalize.
Friends
Hetarn
Eremies
Two friend-enemy net- works of opposite homophily.
Figure 1:
To improve the performance of current spectral methods against non-targeted structural adversar- ial attacks, we design novel spectral GNN that realizes generalization across homophily. Our contributions are:
We proposed EvenNet, a simple yet effective spectral GNN that can be generalized to graphs of different homophily. EvenNet discards messages from odd-order neighbors inspired by balance theory, deriving a graph filter with only even-order terms. We provide a detailed theoretical analysis in the spatial domain to illustrate the advantages of EvenNet in generalizing to graphs of different homophily.
We propose Spectral Regression Loss (SRL) to evaluate the performance of graph filters on specific graphs in the spectral domain. We theoretically analyze the relationship between graph filters and graph homophily, confirming that EvenNet with symmetric constraints is more robust homophily- heterohhhyyy inductive learning tasks.
We conduct comprehensive experiments on both synthetic and real-world datasets. The empirical results validate the superiority of EvenNet in generalizing to test graphs of differ- ent homophily without introducing additional computational complexity while remaining competitive in traditional node classification tasks.
2 Preliminaries
Notations. Let G = (V,E) denote an undirected graph, where N = |V] is the number of nodes. Let A E (0, 1 NNN denote the adjacency matrix. Concretely, Aij indicates an edge between nodes and Uj. Graph Laplacian is defined as L = D A, along with a normalized version -=I- D- 1/2 AD- where I is the identity matrix and D is diagonal degree matrix with each diagonal element Dü. - Aij. It is known that İ is symmetric positive semidefinite matrix that can be decomposed as T. UATT, where = (oigg.o...... AN-1) is a diagonal eigenvalue matrix with 0 = do < < ... S Aw-1 1 < 2, and U is a unitary matrix consisting of cigenvectors.

---

For multi-class node classification tasks, nodes in G are divided into K classes Each node v; is attached with an F dimension feature and a one-hot class label. Let X R be the input feature matrix and Y E TRNNK (Yo- ........ WK-1) be the label matrix, where y, is the indicator vector of class C. Let R Y and the size of class C.. be Ra.
CK-1)
Graph filtering. The graph filtering operation on graph signal X is defined as = (UUg(A))" X). where g(A) is the so-called graph filter, and a is the normalization function. Directly learning g(A) requires eigendecomposition (EVD) of time complexity O(N3). Recent studies suggest using polynomials to approximate g(A) instead, which is:
K-1 Σ
Ug(A)
Σ W U x-
W
where }w&} are polynomial coefficients. We can also denote K-order polynomial graph filter filter function g() Ek=o w that maps eigenvalue À E [o. 2] to g
Homophily. Homophily reflects nodes' preferences for choosing neighbors. For a graph of strong homophily, nodes show tendency to form connections with nodes of the same labels. The ratio of homophily measures the level overall homophily
graph. Several homophily metrics have We adopt edge homophily following (37), defined by
been proposed with different focuses 20 22
([ v) (u yo =..l
h
(1)
[3]
By definition, e: [0, 1] is the fraction of intra-class edges in the graph. The closer h is to 1, the more homophilic graph is.
3 Our Proposed Method: EvenNet
In this section, we first introduce our motivation and the methodology of EvenNet. We then explain how EvenNet enhances the robustness of spectral GNNs from the perspective of both spatial and spectral domains.
3.1 Motivations
Reconsider the toy example in Figure Relationships between nodes are opposite on homophilic and heterophilic graphs, being straightforward but erratic under changes the graph structure. Unconstrained spectral GNNs tend to overuse such unstable relationships and fail to generalize across homophily. In contrast, a robust model should rely on more general topological information beyond homophily.
Balance theory 6 which arose from signed networks, offers a good perspective: "The enemy my enemy is my friend, and the friend of my friend is also my friend." Balance theory always holds as more general law, regardless of how structural information is revealed on the graph. As result, can obtain more robust spectral GNN under homophily change by incorporating balance theory into graph filter design.
3.2 EvenNet
Denote propagation matrix as P P -. D-LAD- A K-order polynomial graph filer is defined as g(L) = = W,LL* k where Wx, 1 = ..... K are learnable parameters. We can rewrite the filter as g()) = Et w/ (I ř). Ek k=u us pk since we is learnable. Then, we discard the monomials in g() containing odd-order P, obtaining:
[K/2] Σ k=
K/2 Σ
Deven (.))
wh(T
1.22
we
p2k
k=
In practice, we decouple the transformation of input features and graph filtering process following 9 [8] Our model then takes the simple form:
3

---

12/2| we p (x))
2 = f(x, =
where is an input transformation function (e.g. MLP), and Z is the output node representation that be fed into a softmax activation function for node classification tasks.
From the perspective of the spectral domain, Jeven keeps both low and high frequencies components and suppresses geedium-frequency components, which is band-reject filter with the filter function symmetric about X = 1. We provide a theoretical analysis to demonstrate further the advantages of Jeven in Section 3.3 and 3.4
3.3 Analysis from the Spatial Domain
Recently, Chen et al. 8 analyzed the performance of graph filters under certain homophily. They concluded that graph filters operate a potential reconstruction mechanism of the graph structure. A graph filter (L) achieves better performance in binary node classification task when the homophily of the transformed graph is high. The transformed homophily can therefore be seen as an indicator of the performance of graph filters specific tasks. We now provide the well-defined transformed homophily adopted from (
Definition 1. (k-step interaction probability) For propagation matrix = DD- the k-step interaction probability matrix
= S-RR-YyP'YRR
Definition 2. (k-homophily degree) For a graph with the k-step interaction probability Íi its k-homophily degree H4&(TT) is defined
K-1 Σ
H4
Σ
Rm, Riltii)
N
t=
mygld
The transformed I-homophily degree with filter g(L) is Hi IT)).
By definition, the t-homophily degree reflects the average possibility deriving a node's label from its k-hop neighbors. In Theorem show that even-order filters achieve more robust performance under homophily change by enjoying lower variance of transformed homophily degree without losing average performance. Detailed proof is provided in the appendix, including discussions about multi-class cases.
Theorem 1. In binary node classification task, assume the edge homophily h [0, is random variable that belongs to uniform distribution. An even-order graph achieves no less [[]] with lower variation than the full-order version.
En Mi (9(I-17))
3.4 Analysis from Spectral Domain
proposed Spectral Regression Loss (SRL) as evaluation metric of graph filters in the spectral domain. In a binary node classification task, suppose the dimension of inputs
Similar to Section 3.3
F = 1. Denote the difference of labels as Ay Yn y A graph filtering operation is defined as Z = a (Ug(A) X). Desirable filtering produces distinguishable node representations correlated to Ay identify node labels. Let a U Ay and , U X. The classification task in the spectral domain is then a regression problem in the form of ((x) (g(A33)
We adopt Mean Squared Error (MSE) the objective function of the regression problem and vector normalization as a. Then SRL is defined as follows:

---

Definition 3. (Spectral regression loss.) Denote a = (ao....,ay, -N-1) T = (Su.... ( B1- In
a binary node classification task, Spectral Regression Loss (SRL) of filter ((A) on graph 9 is:
L(G) = Σ 1=0
N-1
04
(A:).33 N g(>3)83
(4)
Σ
N-1
agg(>,))
=
(5)
N-1 Ž== 9(>3)33
The constant VN comes from the fact Ei of N. A detailed illustration is included in the appendix. A graph filter that achieves lower SRL is of higher performance in the task.
Filters that Minimize SRL. Suppose a; w + e, where w > 0 reflects the correlation between labels and features in the spectral domain and is the noise term. If e is close O. indicating features are free of noise and highly predictive, an all-pass filter (for example, MLP) with g(A,) =
already minimizes SRL. If the noise becomes dominant, SRL approximately equals to E (
o(A,) ) this noise-dominant case, an ideal filter is linearly correlated to a and structure- VE, 9(2,)=
based to achieve a lower SRL. Most real-world situations lie between these two opposite settings. As result, the shape of an ideal graph filter lies between an all-pass filter and an a-deepedent filter.
From the discussion above, we have shown that the performance of graph filters is related to the correlation between g(A) and a. By connecting and h in Theorem 2 we establish the relationship between graph homophily and the performance graph filters.
Theorem 2. For a binary node classification task on k-regular graph G. let h be edge homophily and X be the i-th smallest eigenvalue of L,, then
N-1 at>
1
0==0
(6)
2 2 A
The above equation can be extended general graphs by replacing the normalized Laplacian L with the unnormalized L.
Notice that Lien a is a convex combination of non-decreasing {A; with weights af. On homophilic graph where h is close to 1, the right-hand side of Equation 6 close to O, implying larger weights for smaller A₃. low-pass filter that suppresses nighfrreuency components is more correlated with such a and therefore achieves lower SRL. From previous works, we have known that low-pass filters hold superiority on homophilic graphs, which consistent with our analysis.
In the case of generalization, the distribution of {as) ) is not fixed. A graph filter that minimizes the test graph of different homophily. Remember
SRL training graphs could achieve poor results that vanilla GCN could be worse than MLP on many heterophilic graphs. The same conclusion can be applied learnable filters without any constraints, as they only tried to minimize the SRL of training graphs. In Theorem 3 we prove that even-order design helps spectral GNNs better generalize between homophilic and heterophilic graphs as practical constraint to current filters.
Theorem 3. Suppose AN-1 2 for homophilic graph G1 with non-increasing {as). and heterophilic graph G2 with non-decreasing {a:}. Then an even-order filter Jeven achieves a lower SRL gap [L(G,) L(G2) than than oull- filters when trained on one the graphs and test on the other.
Theorem 3 reveals trade-off in filter design between fitting the training graph and generalizing across graphs of different homophily. While naive low-pass filters and high-pass filters work better on graphs with certain homophily, EvenNet tolerates imperfect filter learning and becomes more robust under homophily changes. A specific example on ring graphs is given in the following corollary. We that EvenNet intrinsically satisfies the necessary condition for perfect generalization.
Corollary 1. Consider two ring graphs G1 and G2 of 2n nodes, E N+ Suppose h(G1) = and h()))) 1. Assume the spectrum of input difference B = cl, where e > a constant. Then the necessary condition for graph filter g()) to achieve L(G,) = L(G2) is 9(0) = g(2).
5

---

3.5 Complexity
Denote N the number of nodes, d the size of hidden channels (we assume it is of the same order as the size of input features), | the number of edges, L the number of MLP layers used in feature transformation and K the order of the propagation layer.
Compared with structural learning methods which usually have space complexity of ( EvenNet takes up O Fil) space complexity, as it only needs to store the input sparse adjacency matrix during training. For the time complexity of EvenNet, the transform process has time complexity of I.) and the propagation process has a complexity (K'd d] E)) during each forward pass.
In practice, H2GCN (37 and ProGNN 16 require O space complexity and are thus not scalable to large graphs. GCNII 7 achieves its best performance with multiple stacked layers which is slow to train. FAGCN 4. GAT [26) and GNNGuard [34 with attention calculations are also inefficient during training. Notice that the space and time complexity of EvenNet are both linear to N and [E), which is highly efficient.
We report the computational time and an experiment on a larger dataset ogbn-arxiv G5 in the appendix to further verify the efficiency of EvenNet.
Related Work
Spectral GNNs. GNNs have become prevalent in graph representation learning tasks. Among them, Spectral GNNs focus on designing graph filters with filter functions that operate on eigenvalues of graph Laplacian [S]. Graph filters could be fixed [7 18 28 or approximated with polynomi- als. ChebNet [10 adopts Chebyshev polynomials to realize faster localized spectral convolution. ARMA 3 achieves a more flexible filter approximation with Auto-Regressive Moving Average filters. GPRGNN [9] connects graph filtering with graph diffusion and learns coefficients of poly- nomial filters directly. BernNet 114 utilizes Bernstein approximation to learn arbitrary filtering functions. Although learnable graph filters perform well on heterophilic graphs, they have difficulties generalizing if a homophily gap exists between training and test graphs.
GNNs for Heterophily. Previous works pointed out the weakness of vanilla GCN on graphs with heterophily. Recently, various GNNs have been proposed to tackle this problem. Geom-GCN 22
uses novel neighborhood aggregation scheme to capture oong-distance information. Zhu et al. 37 introduces several designs that are helpful for GNNs to learn representations beyond homophily. adaptively combines signals of different frequencies in message passing via a self- gating mechanism. While these methods can handle heterophilic graphs, they are not guaranteed to generalize across graphs of different homophily.
FAGCN 4
Robust GNNs. In the field of designing robust GNNs, existing methods can be divided into two main categories: 1) Models utilizing new graph structures. GNN-Jaccard [29] and GNN- SVD preprocess the input graph before applying vanilla GCN. ProGNN [16] jointly learns
better graph structure and robust model. 2) Attention-based models. RGCN [35 uses variance-
based attention evaluate the credibility of nodes' neighbors. GNNGuard 34 adopts neighbor
importance estimation, aligning higher scores to trustworthy neighbors. TWIRLS [22 applies an attention mechanism inspired by classical iterative methods PGD and IRL.S. These methods are effective against structural attacks. However, the learned graph structure cannot be applied to inductive learning settings and requires additional memory. At the same time, mttettoon-bsedd models are limited in the spatial domain and need high computational costs. On the contrary, EvenNet improves the robustness of spectral GNNs without introducing additional computational costs.
5 Experiment
We conduct three experiments to test the ability of EvenNet in (1) generalizing across homophily on synthetic datasets, (2) defending against non-targeted structural attacks, and (3) supervised node classification roal-world datasets.

---

5.1 Baselines
We compare our EvenNet with the following methods. (1) Method only using node features: A
2-layer MLP. (2) Methods achieving promising results on homophilic graphs: GCN [7]. GAT 22)..
GCNII 77. (3) Methods handling heterophilic settings: H2GCN [37] FAGCN A. GPRGNN [9]
We also include five advanced defense models the experiment about adversarial attacks, including
RobustGCN B5 GNN-SVD [1,, GNN-Jaccard (29). GNNGuard [34], and ProGNN [16]. We
implement the above models with the help of PyTorch Geometric and DeepRobust libraries [19
5.2 Evaluation on synthetic datasets
Datasets, In the first experiment testing generalization ability, we use cSBM model to generate graphs with arbitrary homophily levels following [ Specificclly, divide nodes into two classes of equal size. Each node is attached with a feature vector randomly sampled from a class-specific Gaussian distribution. The homophily level of graph is controlled by parameter & E [-1, A larger [6] indicates that the generated graph provides stronger topological information, while & =0 means only node features are helpful for prediction. Note that if Φ > 0, the graph is more homophilic and vice versa.
Settings. We set up node classification tasks in the inductive setting. We generate three graphs of the same size for each sub-experiment, one graph each for training, validation, and testing. Graphs for validation and testing share the same Ptest. while training graphs either take Otrain Ptest
or Φtrain = -test- If Otrain = - @test. the training and test graphs are of opposite homophily but provide the same amount of topological information. A model manages generalize across homophily when it realizes high prediction accuracy in both scenarios. In practice, we choose (Otvain, Ptest) {(10.5, +0.5,, (=00.5,, 0.75))
Results. The results are presented in Table When Ptrain = Ptest, GPRGNN achieves the highest predictive accuracy as it best fits the desired graph filter. However, when diyaán -eest. all methods except EvenNet suffer from huge performance drop. Vanilla GCN, which corresponds to a low-pass filter, achieves desirable performance only when the test graph is homophilic. GPRGNN overfits training graphs most, resulting in more severe performance degradation on test graphs of opposite homophily. EvenNet is the only method that achieves more than 75% accuracy all datasets among all the models, which robust in generalization across homophily.
Table 1: Average node classification accuracy(% (%) and absolute performance gap(% (%) between experi- ments of the same étrain over ten repeated experiments on synthetic cSBM datasets. The best result is highlighted by bold font, the second best result is underlined.
Otrain
0.75
0.50
-0.50
-0.75
Prest
0.75
-0.75
gap(()
0.50
-0.50
gap(U)
-0.50
0.50
gap(1)
-0.75
0.75
gap(L)
MLP
$7.92
57.24
0.68
63.65
64.26
0.61
63.28
63.83
0.55
56.92
$9.24
2.32
GCN
75.24
60.31
15.11
78.98
63.21
15.77
63.27
76.67
13.40
60.48
77.88
17.40
GAT
74.15
60.55
13.60
75.64
61.96
13.68
64.43
71.02
6.59
63.19
71.61
8.42
GCNII
83.12
54.30
28.82
78.07
58.43
19.64
72.32
67.68
4.64
65.93
62.92
3.01
H2GCN
76.41
54.81
21.60
78.86
58.89
19.97
78.43
59.77
18.66
76.29
55.92
20.37
FAGCN
81.29
60.44
20.85
78.73
60.28
18.45
79.45
60.62
18.83
85.78
57.34
28.44
GPRGNN
95.93
53.52
42.41
84.42
56.16
28.26
84.18
63.76
20.42
95.99
66.49
29.52
EvenNet
95.29
94.59
0.70
82.37
82.57
0.20
81,99
79.81
2.18
94.79
96.25
1.46
5.3 Performance under non-targeted structural adversarial attacks
Datasets. For adversarial attacks, we use four public graphs, Cora, Citeseer, PubMed 24 33 and
ACM [30 available in DeepRobust Library [19]. We use the same preprocessing method and splits as B8 where the node set is split into 10% for training, 10% for validation, and 80% for testing, and the largest connected component of each graph for attacks selected.
We include the experiment against nor-teree attacks on heterophilic datasets in the appendix as well, in which we use the same preprocessing methods and dense splits following [9]
7

---

Train
Train
Homophilly level
Train
DICE
Meta
MinMax
Perturb Ratio
Perturb Ratio
Perturb Ratio
Figure 2: Homophily level of training graphs and test graphs on Cora after DICE attack, Metattack, and MinMax attack. All attacks result in a homophily gap between training and test graphs.
Attack methods. Graph structural attacks can be categorized into poison attacks and evasion attacks. In poison attacks, attack models are trained to lower the performance of surrogate GNN model. The training graph and the test graph are both allowed to be perturbed but only with a limited amount of modifications, which are referred to perturb ratios. Evasion attacks only happen during inference, meaning GNNs are trained on clean graphs. In our study, we include two poison attacks, Mctattack (Meta) (38) and MinMax attack [31) with GCN the surrogate model, and evasion variant of DICE attack 27 Notice that we mainly focus on modification attacks, which are strictly structural attacks. A discussion of GNNs under graph injection attacks is included in the appendix.
For poison attacks, we use the same setting in 34 and set the perturb ratio for poison attacks be 20%. For the evasion DICE, we randomly remove intra-class edges and add inter-class edges on the test graph while keeping the graph structure between labeled nodes unchanged. We set the perturb ratio of DICE attack in {0.4, 0.8, 1.2, 1.6]. From Figure 2 it can be seen that all attacks result in homophily gaps between the training graphs and the test graphs. Besides the 1-hop homophily gap, in Table 2, we present the change in two-hop homophily for learnable attacks with perturb ratio of 0.2. As can be seen, the two-hop homophily gap is relatively smaller than the one-hop homophily gap, which is in accordance with analysis that homophily between even-hop neighbors is more robust.
Table 2: Homophily gaps between training and test graphs after Meta/MinMax attacks with 20% the perturb ratio.
Homophily Vdataset
Meta-Cora
Meta-Citeseer
Meta-ACM
MinMax-Cora
MinMax-Citesen
MinMax-ACM
1-hop Train
0.42
0.4
0.49
0.36
0.38
0.49
1-hop Test
0.7
0.65
0.72
0.69
1-hop Gap
0.28
0.25
0.23
0.38
0.31
0.23
2-hop Train
0.52
0.55
0.54
0.37
0.40
0.36
hop Test
0.65
0.66
0.61
0.69
0.68
0.56
2-hop Gap
0.28
For the DICE attack, the performance of all methods significantly decreases along with the increase of the homophily gap except EvenNet. Interestingly, when the homophily gap is enormous, EvenNet enjoys performance rebound, consis- tent with our topological information theory (strong homo. and strong hetero. are both helpful for prediction). For poison attacks, EvenNet achieves SOTA compared with advanced defense models. Unlike spatial defense models, EvenNet is free of introducing extra time or space complexity.
Results. Defense results are presented in Table and Figure 3
5.4 Performance on real-world graph datasets
We evaluate EvenNet on real-world datasets to examine the performance of EvenNet on clean graphs. Besides datasets used Section 5.3 we additionally include four public heterophilic datasets:
Actor, Cornell, Squirrel, and Texas 22 23 25 The statistics of real-world Datasets are included in Table In the node classification task, we transform heterophilic datasets into undirected ones following 9

---

Table 3: Average node classification accuracy (%) against non non-targeted poison attacks Metattack and MinMax attack with perturb ratio 20% over different splits. The best result is highlighted by bold font, the second best result is underlined.
Dataset
Meta-cora
Meta-citeseer
Meta-acm
MM-cora
MM-citeseer
MM-acm
MLP
58.60
62.93
85.74
59.81
63.72
85.66
GCN
63.76
61.98
68.29
69.21
68.02
69.37
GAT
66.51
63.66
68.50
69.50
67.04
69.26
GCNII
66.57
64.23
78.53
73.01
72.26
82.90
H2GCN
71.62
67.26
83.75
66.76
69.66
84.84
FAGCN
72.14
66.59
85.93
64.90
66.33
81.49
GPRGNN
76.27
69.63
88.79
77.18
72.81
88.24
RobustGCN
60.38
60.44
62.29
68.53
63.16
61.60
GNN-SVD
64.83
64,98
84.55
66.33
64.97
81.08
GNN-Jaccard
68.30
63,40
67.81
72.98
68.43
69.03
GNNGuard
75.98
68.57
62.19
73.23
66.14
66.15
ProGNN
75.25
68.15
83.99
77.91
72.26
73.51
EvenNet
77.74
71.03
89.78
78.40
73.51
89.80
Accuracy
NLF
CCV
Cora
Citeseer
GEN JE
0.2
10
HOVED
GEN
Acouracy
CFTISN
37
ACM
PubMed
26
24
64
0.
13
1.4
66
1.0
14
1.0
Perlurb Ratio
Perturb Ratio
Figure 3: DICE attack four homophilic datasets. EvenNet is marked with "A".
For all datasets, we adopt dense splits the same as [22] to perform full-supervised node classification tasks, where the node set split into 60% for training, 20% for validation, and 20% for testing.
Table 4: Statistics of real-world datasets.
Cora
Citeseer
PubMed
ACM Chameleon
Squirrel
Cornell
Texas
Actor
Nodes
2,708
3,327
19,717
3,025
2,277
5,201
183
183
7,600
Edges
5,278
4,552
44,324
13,128
31,371
198,353
277
279
26,659
Features
1,433
3,703
500
1,870
2,325
2,089
1,703
1,703
932
Classes
3
5
Homophily Level
0.81
0.74
0.80
0.82
0.23
0.22
0.30
0.09
0.22
The results are shown in Table competitive on most datasets.
While EvenNet sacrifices its performance for robustness, it is still
5.5 Ablation study
To analyze the effect of introducing odd-order components into graph filters, we develop regularized variant of EvenNet named EvenReg. EvenReg adopts a full-order learnable graph filter, with the coefficients of odd-order monomials being punished as regularization term. The training loss of EvenReg then takes the form: L Lpred + Σ [K/2] |w2x+11 where Lpred the classification loss and 17 is a hyper-parametee parameter controlling the degree of regularization.
k

---

Table 5: Average node classification accuracy(%) on real-world benchmark datasets over 10 different splits. The best result is highlighted by bold font, the second best result underlined.
Model
Cora
Cite.
Pubm.
Cham.
Texas
Corn.
Squi.
Actor
MLP
74.88
74.82
85.58
46.65
89.50
90.17
32.33
41.30
GCN
87.19
80.87
87.51
63.28
80.66
74.09
46.42
34.21
GAT
88.21
81.36
89.42
64.02
81.63
81.97
47.87
36.21
GCNII
87.91
82.13
86.41
50.76
86.23
89.83
36.35
41.68
FAGCN
88.83
80.35
89.34
56.67
89.18
90.16
39.10
41.18
H2GCN
87.59
79.69
88.68
55,88
88.52
85.57
34.45
39.62
GPRGNN
88.34
80.16
90.08
67.13
93,44
92.45
51.93
41.62
EvenNet
87.25
78.65
89.52
66.13
93.77
92.13
49.80
40.48
We set 7 = 0.05 and repeat experiments Section 5.2 The results are presented in Table The performance of EvenReg lies between full-order GPRGNN and EvenNet, indicating the introduced odd orders impede spectral GNNs to generalize across homophily.
Table 6: Average node classification accuracy(%) of EvenReg 10 repeated experiments synthetic cSBM datasets.
Otrain Øtest
0.75
0.50
-0.50
-0..5
0.75
-0.75
0.50
-0.50
-0.50
0.50
-0.75
0.75
GPRGNN
95.93
53.52
84.42
56.16
84.18
63.76
95.99
66.49
EvenNet
95.29
94.59
82.37
82.57
81.99
79.81
94.79
96.25
EvenReg
95.44
93.90
84.05
78.06
83.72
75.33
95.40
95.73
Conclusion
In this study, we investigate the ability current GNNs to generalize across homophily. We observe that all existing methods experience severe performance degradation if large homophily gap exists between training and test graphs. To overcome this difficulty, we proposed EvenNet, a simple yet effective spectral GNN which is robust under homophily change of graphs. We provide detailed theoretical analysis to illustrate the advantages of EvenNet in generalization between graphs with homophily gaps. We conduct experiments on both synthetic and real-world datasets. The empirical results verify the superiority of EvenNet in inductive learning across homophily and defense under non non-targeted structural attacks by sacrificing only a tiny amount of predictive accuracy on clean graphs.
7 Acknowledgement
This research supported in part by the major key project of PCL (PCL2021A12), by National Natural Science Foundation of China (No. 61972401, No. 61932001, No. 61832017), 7), by Beijing Natural Science Foundation (No. 4222028), by Beijing Outstanding Young Scientist Program No. by Alibaba Group through Alibaba Innovative Research Program, by CCF-Baidu Open Fund (NO.2021PH P001PPP50000000 and by Huawei-Renmin University joint program on Information Retrieval. We also wish to acknowledge the support provided by Engineering Research Center Gext--eneeationn Intelligent Search and Recommendation, Ministry of Education. Additionally, we acknowledge the support from Intelligent Social Governance Interdisciplinary Platform. Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" Initiative, Public Policy and Decision-making Research Lab, Public Computing Cloud, Renmin University of China.
10

---

References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In /CML, 2019. [
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Séhastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. ICLR, 2020. !
[3] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1-1, 2021
[4] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen.
Beyond low-frequency information in graph
convolutional networks. AAAI, 2021. 3.5 15545. S.
[5] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014. 4
[6] Dorwin Cartwright and Frank Harary. Structural balance: a generalization heider's theory. Psychological review, 63(5):277, 1956.
3.1
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolu- tional networks. In ICML, pages 1725-1735. PMLR, 2020. 3.5
[8] Zhixian Chen, Tengfei Ma, and Yang Wang. When does spectral graph neural network fail in node classification? arXiv preprint arXiv:2202. 07902, 2022.
3.3
[9] Eli Chien, Jianhao Peng, Pan Li. and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. ICLR, 2021.
1 3.2
5.2 5.3
5.4
[10] Michaöl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. NeurIPS, 2016.
[11] Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need is
low (rank): Defending against adversarial attacks on graphs. In WSDM, 2020. 4 5.1
[12] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. ICLR, 2019. 5.1
[13] William L. Hamilton, Zhitao Ying, and Jure Leskovee, Inductive representation learning on large graphs. NeurIPS, 2017.
[14] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. NeurlPS, 34, 2021. 4
[15] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Ties Tien Lin, editors, NewrIPS 2020, 2020. 3.5
[16] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In SIGKDD, pages 66-74, 2020. 3.3 4 S.T
[17] Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. ICLR, 2017. 5.1
[18] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Combining
neural networks with personalized pagerank for classification on graphs. In ICLR, 2018. 3.2
[19] Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint 2oXxx:0005061144 2020. 5.1 5.3
[20] 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. NewrIPS, 34, 2021. 2
[21] Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv: Machine Learning, 2019. [

---

[22] Hongbin Pei. Bingzhe Wei, Kevin Chenn Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
5.4
[23] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9(2)enab0144 2021. 5.4
[24] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data, magazine, 29(3):93 93, 2008 [.3
[25] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In SIGKDD, pages 807-816, 2009. 5.4
[26] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
3.5 5.1
[27] Marein Wamiek, Tomasz Michalak, Talal Rahwan, and Michael Wooldridge. Hiding individuals and communitics a social network. Nature Human Behaviour, 2016. 5.3
[28] Felix Wu, Amauri Holanda Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
[29] Huijun Wu, Chen Wang, Yuriy Tyshetskiy. Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In IJCAI, 2019.
5.1
[30] Wang Xiao, Houye, Shi Chuan, Wang Bai, Cui Peng, Yu P., and Ye Yanfang. Heterogeneous graph attention network. WWW, 2019. 5.3
[31] Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui- Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In IJCAL, 2019. 5.3
[32] Yongyi Yang. Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. In ICML, pages 11773-11783. PMLR, 2021.
[33] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, pages 40 48-48. PMLR, 2016. 53
[34] Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. NeurlPS, 2020. 3.3
533
[35] Dingyuan Zhu, Ziwei Zhang. Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In KDD, 2019.
[36] Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. On the relationship between heterophily and robustness of graph neural networks. arXiv preprint 107.776 2021.
[37] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily graph neural networks: Current limitations and effective designs. NeurlPS, 2020.
4 5.]
[38] Daniel Zügner Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. ICLR, 2019.
533
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Section 5.4 and in Section 6
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
12

---

(b) Did you include complete proof' of all theoretical results? [Yes] Included in Appendix due to space limitation.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Splits specified in the experiment chapter, and hyperparameters are specified in supplementary materials.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No] We only report mean accuracy.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] Included in supplementary materials.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the creators of used datasets.
(b) Did you mention the license of the assets? [No]
URL? [No] (d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes] We mention that all used datasets are public in our experiments. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] We mention that all used datasets are public in experiments without personally identifiable information offensive content.
(c) Did you include any assets either in the supplemental material
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qvKNnwwy8es", "reviewer": "Reviewer_FdNz", "summary": "This paper proposes to ignore odd-hop neighbors to improve the robustness of graph neural network. The authors analyze the influence of odd and even-hop neighbors to the graph filters and reveal that using only even-hop neighbors can improve the robustness of spectral graph neural networks. Based on the theoretical findings, the authors propose EvenNet and conduct several experiments to validate the effectiveness of EvenNet.", "questions": "After the rebuttal, the authors resolve most of my concerns. Thus I raise my ratings to 6.\n\n===========\nThe motivation of the paper is confusing:\n- The EvenNet design seems to be heuristic, which tends to assume the task is binary thus the neighbors of heterophilic neighbors tend to have homophilic to the central nodes. I am not sure why this heuristic is a more general topological information beyond homophily. \n\n- Furthermore, the theoretical analysis throughout the paper including the synthetic experiments inherent the strong assumption on the problem structure, i.e., binary classification. Under binary classification, incorporating even-hop neighbors is straightforward as shown in Figure 1 by the author, which may weakens both the significance and novelty of the paper.\n\nThere are several missing important comparisons and experiments:\n- Comparisons between existing spectral GNNs which are also designed to work on both homophily and heterophily GNNs are missing, e.g., Fu et al., 2021[1].\n- The paper focuses on a inductive setting and discusses the homophily changes under adversarial attacks. In fact, Chen et al., 2022[5] established the same discussion in this setting under a more ``powerful’’ graph adversarial attack, i.e., Graph Injection Attack (GIA) [2,3,4,5]. More discussions and comparisons are required to distinguish the contributions of the paper, and more importantly, the effectiveness of EvenNet (See more details in the next point).\n- In fact, most of existing graph adversarial attacks are limited to small scale graphs [6] in contrast to GIA which works on both small and large scale graphs [4,5], making the evaluations less convincing [4,5,6]. It would strengthen the claims and further improve the impact of the paper if the authors could validate the high robustness of EvenNet in large scale graphs.\n- The authors claim the proposed method enjoys cheaper computational overhead than existing robust GNNs, yet did not provide any justifications.\n\nThe writing of the paper also misses several important details. Here are few:\n- In Theorem 1, how the expectation is taken given the subscript as H and inputs \\PI?\n- In Line 150, why the regression problem of \\alpha and \\beta can be seen as linear?\n- In Theorem 3, what is the relationship between homophily/heterophily and the non-increasing/non-decreasing \\alpha?\n- In experiments, how the threshold in GNNGuard is chosen?\n- In all tables of the experiments, why are the standard variances are missing?\n- How robust are EvenNet under Metattack with different budgets?\n\nReferences:\n\n[1] Guoji Fu, Peilin Zhao, Yatao Bian. p-Laplacian Based Graph Neural Networks. arXiv 2021.\n\n[2] Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, Jiliang Tang. Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies. SIGKDD Explorations 2020.\n\n[3] Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S. Yu. Adversarial Attack and Defense on Graph Data: A Survey. arXiv 2020.\n\n[4] Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, Jie Tang. Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning. NeurIPS 2021 Datasets and Benchmark Track.\n\n[5] Yongqiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, James Cheng. Understanding and Improving Graph Injection Attack by Promoting Unnoticeability. ICLR 2022.\n\n[6] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, Stephan Günnemann. Robustness of Graph Neural Networks at Scale. NeurIPS 2021.\n\n", "limitations": "Could not find the corresponding discussion in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Originality & Significance*: Improving the robustness of graph neural networks is of great importance to the community. The proposed solution enjoys lots of theoretical insights from the spectral graph neural networks and the balance theory. However, the motivation is confusing and the empirical evidences may not be sufficient to support the authors’ claims.\n\n*Quality*: Despite of certain theoretical supports for the design of EvenNet. The theoretical analysis tend to put strong assumptions on the underlying graph homophily/heterophily. The empirical analysis might not be sufficient, as several important experiments are missing. See the questions for more details.\n\n*Clarity*: Overall, the paper is well-organized, however, there are several important details are missing, making readers hard to follow.\n", "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_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Mo4qeozX3k", "reviewer": "Reviewer_cSNX", "summary": "This paper studies GNN robustness against homophily changes (e.g., whether direct neighborhoods belong to the same class). It proposes a spectral graph filter that only considers even-polynomial signals, so that it’s robust to odd-hop changes.", "questions": "See above", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe paper gives clear motivation of why only considering odd-order might tackle homophily changes.\nThe paper gives theoretical analysis from both spatial and spectral perspectives.\n\nWeaknesses (or questions)\n\n1. Is EvenNet only effective in homophily change?\n\nI think the paper is based on an assumption that most perturbation comes from homophily changes, more specifically, label changes of the direct neighborhood. Based on this assumption, taking even-hop and ignoring odd-hop could increase robustness and loss accuracy. However, this is a very specific type of attack (and from my understanding, people mainly study this to show the weakness of vanilla GCN). So I have the following two questions: is Evennet only effective for homophily changes? What if you also consider some general graph attack, such as random perturbation, a trained attacker? Or more specifically, what if we change the association of label correlation at even-hop (say 2) instead of the direct hop? It would be better if the authors could give an analysis to let people know at which scope the proposed method is effective; \n\n2. Will ignoring odd-hop affect performance? \n\nFrom my understanding of most graph datasets, first-hop neighborhoods contain the most information. If simply ignoring all odd-hop neighbors, will the performance be influenced a lot? Table 3 shows that EvenNet achieves competitive results with many old baselines, but it would be more convincing if the authors could conduct some ablation study, because the proposed approach and baselines could be run in different evaluation settings.\n\n3. Theoretical analysis might not support the claim\n\nTheorem 1 talks about whether an even-order graph filter has lower variation than full-order given different edge homophily. This could not support the author’s claim of “without losing average performance”. If we don’t do graph filtering and only use each node’s own feature the variance is 0, but it doesn't mean this baseline is better than a graph filter.\n\nThe result of Theorem 3 is very interesting, however, I could not really get how you estimate L(G), as it should depend on the filter parameter g, which I couldn’t figure out how you get even after reading the appendix. If you have some assumptions about this Theorem, it would be better to clearly state it so people might understand when the conclusion holds.\n\n\n4. Experiment-wise, it would be better to test on larger-scale and more standard datasets such as OGB. Also, it would be good to show results with real-world distribution shifts instead of only synthetic shifts.", "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_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Aztkjm-L9E", "reviewer": "Reviewer_Pbwq", "summary": "This work designs a simple and robust GNN model, EvenNet, in the spectral domain. EvenNet discards messages from odd-order neighbors. Authors analyze this method theoretically. In the spatial domain, authors define homophily degree, which reflects the average possibility of deriving a node's label from its k-hop neighbors, and then prove that even-order filter can benefit from a lower variance of homophily degree. In the spectral domain, the author proves that an even-order filter can achieve a lower loss gap between the homophilic training graph and the heterophilic test graph. EvenNet exhibits generalization ability across homophily and robustness to many attacks in experiments. Moreover, it also keeps competitive performance and low time complexity.", "questions": "Why not use $\\phi_{test}\\neq\\pm\\phi_{train}$ in experiments? For example, can we use a setting like $\\phi_{test}=0.3, \\phi_{train}=0.75$?\n", "limitations": "Not related.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The method is simple but novel.\n2. Experiments are persuasive.\n3. The paper is well-written.\n\nWeakness\n\nTheoretical analysis is largely based on heuristics. In the spatial domain, whether the homophily degree change represents the effects of homophily change on GNN is doubtful. In the spectral domain, the analysis is based on too many unnatural assumptions like 1-dimensional feature, non-increasing and non-decreasing $\\alpha$, and ring. \n\n\n\n", "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_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept