HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations
Authors: Shuaicheng Zhang
Haohui Wang
Junhong Lin
Xiaojie Guo
Yada Zhu
Si Zhang
Dongqi Fu
Dawei Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Graph heterophily
graph signal processing
model generalization
Primary area: general_machine_learning

Abstract: Graph heterophily, where connected nodes have different labels, has attracted significant interest recently. Most existing works adopt a simplified approach - using low-pass filters for homophilic graphs and high-pass filters for heterophilic graphs. However, we discover that the relationship between graph heterophily and spectral filters is more complex - the optimal filter response varies across frequency components and does not follow a strict monotonic correlation with heterophily degree. This finding challenges conventional fixed filter designs and suggests the need for adaptive filtering to preserve expressiveness in graph embeddings. Formally, natural questions arise: Given a heterophilic graph $\mathcal{G}$ , how and to what extent will the varying heterophily degree of $\mathcal{G}$ affect the performance of GNNs? How can we design adaptive filters to fit those varying heterophilic connections? Our theoretical analysis reveals that the average frequency response of GNNs and graph heterophily degree do not follow a strict monotonic correlation, necessitating adaptive graph filters to guarantee good generalization performance. Hence, we propose HeroFilter, a simple yet powerful GNN, which extracts information across the heterophily spectrum and combines salient representations through adaptive mixing. HeroFilter's superior performance achieves up to 9.2% accuracy improvement over leading baselines across homophilic and heterophilic graphs.

HEROFILTER: Adaptive Spectral Graph Filter for Varying Heterophilic Relations
Shuaicheng Zhang" Virginia Tech 2shuai8@vt.edu
Haohui Wang" Virginia Tech
Junhong Lin MIT j junhongdmit.edd
Xiaojie Guo IBM Research xiaojie guo@ibm...... com
hachuivevt.co edu
Yada Zhu IBM Research yzhu@ibm. com
Zhang Meta AI s sizhang@meta..cmm com
Dongqi Fu
Dawei Zhou Virginia Tech zhoud@vt.. edu
Meta AI
dongqifußmeta. com
Abstract
Graph heterophily, where connected nodes have different labels, has attracted significant interest recently. Most existing works adopt simplified approach using low-pass filters for homophilic graphs and high-pass filters for heterophilic graphs. However, we discover that the relationship between graph heterophily and spectral filters more complex the optimal filter response varies across frequency components and does not follow strict monotonic correlation with heterophily degree. This finding challenges conventional fixed filter designs and suggests the need for adaptive filtering to preserve expressiveness in graph embeddings. Formally, natural questions arise: Given a heterophilic graph G, how and to what extent will the varying helerophily degree How can we design adaptive filters to fit those varying heterophilic connections? Our theoretical analysis reveals that the average frequency response of GNNs and graph heterophily degree do not follow strict monotonic correlation, necessitating adaptive graph filters to guarantee good generalization performance. Hence, we propose HEROFIT FILTER, a simple yet powerful GNN, which extracts information across the heterophily spectrum and combines salient representations through adap- tive mixing. HEROFILTER ' superior performance achieves up to 9.2% accuracy improvement over leading baselines across homophilic and heterophilic graphs.
affect the performance of GNNs?
Introduction
Graph Neural Networks (GNNs) have emerged as powerful tools for learning from graph-structured data across broad range of domains 2 are known to suffer performance degradation when applied to graphs that exhibit heterophily, structural property where connected nodes tend to have dissimilar features or labels. This stands in contrast to the homophily assumption, foundational to many GNN architectures, which presumes that adjacent nodes share similar attributes. A growing body of work [TO, [2 I3 [4] has shown that this mismatch in assumptions significantly limits the effectiveness of conventional GNNs, often rendering them less effective than simple multilayer perceptrons (MLPs).
Despite their empirical success, GNNs
To better understand and mitigate the limitations of GNNs under heterophily, researchers have adopted spectral view grounded in graph signal processing (GSP) [15]
16 17 [8. In this framework, graph signals are decomposed into frequency components via the eigen decomposition of the graph Laplacian, where low-frequency components capture smooth variations across the graph, and high-
Equaal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

frequency components capture rapid, localized changes. Classic GNNs such as Graph Convolutional Network (GCN) [9] and Graph Attention Network (GAT) 20 can thus be interpreted as applying low-pass filters, effectively amplifying low-frequency components and suppressing high-free -reeueryy noise 15] This design aligns well with homophilic structures, where relevant information is concentrated in the low-frequency spectrum. However, it is often inadequate for heterophilic graphs, where informative signals may lie in higher-frequency bands.
To address this, recent works have proposed filter-based GNNs that explicitly incorporate high-frequency information [22 23), and em- pirical studies have supported the effectiveness of high-pass or mixed filters for heterophilic settings [24 23 Nevertheless, most existing approaches rely on simplifying assumption: low-pass filters are used for homophilic graphs, and high-pass filters are used for heterophilic ones. This binary perspective assumes a mono- tonic relationship between the heterophily level of a graph and its optimal spectral filter, an as- sumption that show is often violated in prac- tice.
Heterophily Degree mrequen Respon Respons
150
12.5
10.0
2.5
a, 9. 9,9 4
0:00
a L00 125 1.50 Eigenvalues'
To investigate this assumption, we conduct con- trolled experiments on synthetic graphs with varying heterophily degrees. As shown in Fig- ure[ we observe that the frequency responses of trained spectral filters [21] exhibit complex, non-monotonic behavior across the spectrum. For example, in graphs with low heterophily (e.g.. 0.1), the learned filters reveal significant activation in both low- and mid fid-frruuency bands, contrary to the expectation of a purely low- pass response. Similarly, graphs with high het- erophily (e.g.. 0.9) do not exhibit a purely high-pass response, retaining strong low-frequency components. These findings suggest that the relationship between heterophily and spectral response is more intricate than previously assumed, and that fixed filter types (low-pass or high-pass) are insufficient for capturing this complexity. These observations motivate two central research questions:
2.00
Figure 1: 3D visualization showing the underly- ing relationship among eigenvalues, heterophily degree, and frequency response (in log scale). In particular, we synthesized nine graphs with het- erophily degrees ranging from 0.1 to 0.9. Each curve with a unique color corresponds to well- trained spectral graph filter [2] on each graph.
QI (Theoretical Understanding): How can we characterize the relationship belween gruph het- erophily, spectral filters, and the prediction performance of GNNs?
Q2 (Adaptive Computation): How can we design adaptive filters and GNN models that perform robustly across graphs with varying and possibly mixed heterophily patterns?
To address Q1, conduct theoretical analysis that formally establishes the connection between the heterophily degree of a graph, its spectral representation, and the performance of GNNs. We introduce a novel spectral-domain measure of heterophily and derive error bound that highlights the limitations of fixed filtering strategies and motivates the need for adaptivity in spectral design.
To address Q2. we propose HEROFILTER, novel GNN architecture inspired by the MLP- Mixer (25] 26). HEROFILTER consists of two key components: (1) a Patcher that identifies spectrally relevant neighbors for each node via adaptive polynomial filters, and (2) Mixer that aggregates and transforms patch representations along both the patch and feature dimensions. This architecture allows HEROFILTER modulate its spectral response based on the graph structure and heterophily level, while remaining computationally efficient. We further introduce Hess-HEROFing variant that avoids eigen decomposition through efficient approximation.
a scalable
Beyond conceptual proof and proposed theories, we conduct extensive experiments on homophilic, heterophilic, and large-scale real-world graphs. HEROFILTER consistently achieves otate-of-the-art accuracy, improving over strong baselines by up to 9.2%. Data and code are available

---

2 Preliminaries
Notation. We denote scalars by regular lowercase letters (e.g., c), vectors by bold lowercase letters (e.g., r), and matrices by bold uppercase letters (e.g., X). A graph is represented as G (V,8, X), where the set of nodes, & S V is the set of edges, and X is the node feature matrix. Let |V] be the number of nodes. We denote by A and L the adjacency and Laplacian matrices, respectively, and by A and L their normalized forms. A summary of key notations is provided in the Appendix B
Graph Spectral Filters. Spectral GNNs leverage the graph signal processing framework to define convolutional operations in the spectral domain. The eigendecomposition of the normalized Laplacian yields L UAUT, where U E R**" is the matrix of orthonormal eigenvectors forming the graph Fourier basis, and A is a diagonal matrix containing the corresponding eigenvalues. Given graph signal x E IR",, its graph Fourier transform defined as x U x, and the inverse transform x Ux. The spectral graph convolution between signal x and a filter is defined as:
* g Ug(A)U x.
(1)
where ((A) is a learnable filter function applied in the spectral domain.
The GCN [9 can be interpreted spectral GNN that employs first-order Chebyshev polynomial
to approximate the filter function, yielding ( = (I + A)- This corresponds to a low-pass
filter, which suppresses higu-freyuency components and retains smooth signal patterns across the
graph [15
Graph Heterophily. Many GNN models implicitly assume homophily, where connected nodes expected to have similar features or labels [15]. However, in practice, numerous real-world graphs connections
violate this assumption and instead exhibit high heterephlly-commecioon between nodes of differing labels or characteristics (27]. To quantify this, we adopt the notion of node-level heterophily [[]],
defined as follows:
Definition 1 (Node Heterophily). Let (w:)) = [ug E (Us, Uz) } denote the neighbors of node Us and let yi denote its label. The node heterophily for node vs is defined as:
h4 H2, E (N(.)) y, + voll
(2)
[((x,)
The heterophily degree vector h (ho. f E R" captures the heterophily level of each node, and the overall heterophily of the graph is computed as the average: J -rr h4-
High-heteroohill graphs are common in domains such as social networks, citation graphs, and web hyperlinks. Benchmark datasets including Texas, Squirrel, Chameleon, Cornell, Wisconsin, and Actor [28] 29 30 are representative examples. In such settings, conventional GCN-based message passing, which aggregates information from neighboring nodes, often leads to feature smoothing that can obscure useful class-distinetive signals, resulting in suboptimal performance.
3 Theoretical Bound in Terms of Graph Heterophily, Graph Filter, and Prediction Performance
In this section, we address Q1 by theoretically analyzing the relationship among the graph filter, the heterophily degree of graph G. and the generalization performance of GNNs. We begin by demonstrating that the average spectral response of a filter and the heterophily level of the graph do not follow simple monotonic relationship. This result, formalized Proposition] motivates the need for adaptive filtering. We then establish that adaptive filters can, in principle, align closely with arbitrary label distributions (Proposition (2). Finally, we derive generalization error bound (Theorem I) that quantifies how graph heterophily and spectral filter design jointly affect learning performance. Full proofs of results are provided the Appendix
Spectral Characterization of Heterophily. While graph filters are naturally defined in the spectral domain, heterophily typically measured in the spatial domain. To bridge this gap, we introduce a heterophily degree vector in the spectral domain via the graph Fourier transform.
3

---

Definition 2 (Heterophily Degree Vector in Spectral Domain), Ler À UAUT be the eigende- composition of the normalized adjacency matrix A. where U contains the eigenvectors and A is the diagonal matrix of eigenvalues. Then the heterophily degree vector in the spectral domain h E R is defined as:
U h. where h is the heterophily degree vector (spatial) and h -ho .in-1), i-th element in the spectral domain.
hy is heterophily of the
non-Monotonicity of Frequency Response and Heterophily. We next examine how the average spectral response of graph filter relates the heterophily in the spectral domain.
Proposition Let A be the normalized adjacency matrix with eigendecomposition À = UAUT, where An Aa-1 = =. Then the average filter response lower bounded by:
n-1 Σ
(A.))
Ei=0 log [hg
n
log Ei=o (A.)ll log E s(Ai))
This result reveals that the average filter response 1 (A,) and the average heterophily in the
spectral domain 1 Σ; hy do not follow a monotonic relationship. As shown in Figure | graphs with low overall heterophily in the spatial domain exhibit strong responses mid-frequency bands, contradicting the assumption that low-pass filters are always optimal in such cases.
Need for Adaptive Filtering. The non-monotonic and deph-dependent nature of het- Hoophll-frrqqeeee interactions suggests that fixed filters (e.g., purely wwwppass high-pass) suboptimal. To accommodate diverse frequency needs, we consider an adaptive polynomial filter:
K Σ (Ww A**,
g(A)
where is activation function, W R. learnable weights, and denotes the Hadamard product. GCN [99 is special case where g(A) = (I A)-1 corresponds to a low-pass filter [1]]
We next show that such adaptive filters match any label pattern in the frequeecy domain. Proposition 2. Let Y = (U1...., Vv) be the label vector with yi E (0...., C 1}, and let A be the eigenvalue matrix of A, assuming all eigenvalues nonzero. Then there exist weights { such that:
Align(g(A), 1,
where
a(w, A²), (0) and Align(:,-) denotes cosine similarity.
This proposition highlights the expressive power of adaptive filters align with the target signal, particularly under varying heterophily.
Generalization Error Bound. domain affect generalization error.
We now quantify how filter design and heterophily in the spectral
Theorem 1. Consider binary classification task on a graph & with n nodes. Let X = (Xo, X1) be the filtered node features for nodes belonging class 0 and class respectively. Y (yo. be the label indicators for classes 0 and 1. Let 8. be the spectral coefficients of the label and feature differences, respectively. Then the error upper bounded as:
min + 90 AcTo (m)
8, VEIs.n
Σ log [hg
Er 8)
(5)
2n log
Σ
g(l - Xr) 2n log Σ g(1 - (1))
$EIs.n
iEIA.
where is constant, Iς = {i 8; * 0}, and (xx minfmaxfo, - -1,, 1}.

---

HeroFilter Framework
Input Heterophilic Graph
Herokilter Patcher
HeroFilter Mixer
Adaptive Spectral
Aggreptte
High
fiters
LayesBom
MEP diaceskos
Class O Class Class C Class
À
Top extracted nodes
Patch Micins
MLP ond the petch divcsiioo
Figure Overview of the HEROFILTER framework, consisting of (1) the HEROFILTER Patcher, which adaptively selects spectrally relevant neighbors using learned filters, and (2) the HEROFILTER Mixer, which aggregates patch features across nodes and dimensions.
Theorem formally characterizes how filter choice and heterophily in the spectral domain influence prediction performance. To explore this relationship, we synthesized nine graphs with heterophily degrees ranging from 0.1 to 0.9 as shown in Figure 2 For each graph, we employed five learnable spectral filters passing specific eigenvalue segments: 0-0.4, 0.4-0.8, 0.8-1.2, 1.2-1.6, and 1.6-2.0. Our synthetic ex- periments demonstrate that different frequency regions contribute variably to accuracy depend- ing the heterophily level. This further sup- ports the need for flcxible, graph-specific filter- ing strategies.
04
02
by So Heceronhily Degres
Esgenvauue
Figure 2: An interpolated figure demonstrating the relationship between filtered eigenvalues, het- erophily degree, and accuracy.
HEROFILTER Framework
The theoretical analysis in Section 3 highlights key limitations of existing GNN approaches when applied to heterophilic graphs. First, the spectral behavior of real-world graphs with varying heterophily complex and non-monotonic, rendering uniform low-pass high-par pass filters ineffective, Second, different frequency bands contribute differently to prediction performance depending on the graph's 's heterophily structure. These insights motivate the design of HEROFILTER, a graph learning framework that adaptively aligns its spectral processing with the graph's heterophily profile.
HEROFILTER consists of two modules: (1) The HEROFILTE Patcher, which dynamically selects spectrally relevant neighbors for each node by learning adaptive polynomial filters. This step enables the model attend contextually important nodes across spectral bands, beyond simple local neighborhoods, and (2) The HEROFILTER Mixer, which processes each node's patch using dual-axis MLP architecture that mixes across both spatial (patch) and feature dimensions. This ensures that the model can effectively combine diverse signals arising from the selected patches.
Together, these components allow HEROFILTER to flexibly adapt its receptive field and frequency sensitivity, providing an interpretable and scalable mechanism for handling graphs with varying or mixed heterophily.
4.1 HEROFILTER Patcher
The goal of the patcher is to construct, for each node, set of contextually informative neighbors that reflect spectral, rather than purely topological, similarity. Traditional GNNs aggregate over immediate neighbors, implicitly assuming local homophily. This assumption breaks down in heterophilic settings.
5

---

Thus, we propose to learn a filter ( that scores nodes based on their spectral alignment, enabling a more adaptive notion of neighborhood.
We define the filter using a learnable polynomial function over the eigenvalues the normalized adjaceney matrix:
((A) σ (wk @
(6)
where a is non-linear activation function and are learnable frequency-specin weights. This pa- rameterization allows the model to selectively emphasize different frequency bands based on training data, consistent with our theoretical observation that fixed low/high-pass filters suboptimal.
To apply this filter in the graph domain, we transform it via the graph Fourier basis U, resulting in the node-node relevance matrix:
K R = U
Σ A=1
we o A VooOAAOUT
UT.
Here, R, measures the spectral relevance of node j node under the learned filter. For each node, we sort all other nodes by their relevance scores and select the top-p most aligned ones to form the patch. Mathematically:
< A) top-Peol (R).
The resulting patches are structurally diverse and frequency-aware, allowing the model to capture high-order or cross-cluster interactions often present in heterophilic graphs.
For each selected patch, we extract the corresponding feature vectors from X, yielding a patch tensor:
P. X(top-p(R.)), P R=xpxd
where is the patch size and is the feature dimension. These patches now serve as the input for the step of the model.
4.2 HEROFILTER Mixer
Once patches are constructed, we need to aggregate and transform them into useful node-level representations. Unlike traditional GNNs that rely fixed aggregation schemes (c.g.. mean, sum), our objective is to allow richer, learnable interactions both across patch elements (spatial mixing) and across features (feature mixing). This is motivated by the observation that information relevant to classification may lie in combinations of both positional and attribute-level patterns.
We adapt the MLP-Mixer architecture this setting by defining two mixing layers: Patch-Mixing Layer. For each node's patch P Rexd we apply MLP across the patch dimension:
P (Lyyrroooor)
(10)
This operation allows the model to reason over relationships between the selected nodes in the patch, independently for each feature. It enables the capture of role-based, cross-hop, or structurally asymmetric dependencies.
Feature-Mixing Layer. Next, we apply an MLP across the feature dimension:
P MLP(LayyrNorm((P.)))
(11)
This allows the model to learn joint representations over node features, enabling flexible composition and transformation of feature information within each patch.
The output of the mixer is tensor P E xxx We then apply a global aggregation function (e.g., mean, sum, or flatten) over the patch dimension produce final node representation, This aggregated output is passed to classification layer.

---

4.3 Why Mixing Both Dimensions
Patch-mixing captures the heterophily in node context by modeling which other nodes influence the representation of given node. reature-mixing captures intra-node complexity by transforming raw input features into abstract representations. Therefore, the combination is essential: patch mixing enables adaptivity to structural irregularities (e.g., in heterophilic regions), while feature mixing enables expressive node-level reasoning.
4.4 Fast-HEROFILTTER Patcher
Although the HEROFILTER Patcher is expressive, its reliance eigen decomposition can be pro- hibitive for large-scale graphs. To improve scalability, we propose Fast-HEROFILTER, an efficient variant that approximates the patcher using iterative proximity ranking, inspired by personalized PageRank and diffusion- similarity.
We define the following objective for each node U:
[(r,) ax. (I- A)r, (1 c) -2.122
(12)
where is ranking vector and e,, is one-hot vector. This objective balances global smoothness and local personalization.
Minimizing I (r+) yields the recurrence:
r, A + c) cc e
(13)
which has the closed-form solution:
= (1- cA) (I-A))(--AA-+
To avoid matrix inversion, we approximate this with a truncated Neumann series:
K
ry R (1 C)
A e..
(14)
k==
This expansion be interpreted as diffusing information K steps away from v, with attenuation ct. Since A & UT this operation also approximates spectral filtering.
Finally, we construct patches by selecting the top-p entries in each res with the FESt-HEROFILTER patching rule:
Crast ( (A) top-Peot (Iri... ra]).
(15)
Since R can be efficiently precomputed and patch extraction is fully parallelizable, this formulation enables scalable and adaptive patch construction, serving as a practical alternative to spectral filtering. Full pseudocode is provided in the Appendix
5 Experiment
We empirically evaluate HEROFILTER to validate the key claims made in this work: (1) that adaptive spectral filtering enables robust performance across both homophilic and heterophilic graphs; (2) that our proposed patching and mixing modules contribute significantly to model generalization; and (3) that HEROFILTER offers scalable, interpretable, and architecture-agnoste foundation for future graph learning models. Due space constraints, we include additional experiments (scalability, sensitivity, and runtime) the Appendix G and Appendix
We evaluate HERoFIlTeR on 16 node classification benchmarks encompassing diverse graph het- erophily degrees. The homophilic graphs include Cora, CiteSeer, PubMed, and OGBN-Aree -Arxiv, where neighboring nodes tend to share similar labels. The heterophilic graphs consist of Texas, Squirrel, Chameleon, Cornell, Wisconsin, Actor, Arxiv-Year, and Snap-Patents which feature connections between dissimilar nodes and present greater challenges for conventional GNNs. Notably, Arxiv- and Snap-Pat Patents also serve as large-scale datasets, with up million nodes and million edges, enabling assessment of the model's scalability and efficiency in high-voluma scenarios.
7

---

Table 1: Comparison of different methods in node classification task homophilic graph datasets. We denote red, green, blue as the best, second best, and third best performance, respectively. OOM denotes "Out of Memory".
Model
Cora
CiteSeer
PubMed
OGBN-Arxiv
Σhi
0.19
0.26
0.20
0.34
R
MLP
72.0 + 1.7
71.8
1.7
85.3 + 0.4
49.7 = 0.6
GPRGNN
86.2 + 1.1
74.7 + 1.8
87.6 + 0.5
64.6 1.2
ChebNet
85.5 1.1
75.4 1.4
87.7 0.5
0OM
ChebNetll
84.0 1.2
71.111 1.8
86.2 1 0.3
67.0 0.8
APPNP
86.7 1.0
74.5
86.9 + 0.3
62.4 1.4
GCNJKNet
86.5 1.1
1.5
87.4 + 0.4
65.1 0.6
GCN
86.1 1.0
86.9 0.4
64.9 0.5
GAT
85.9 1.0
$5.8
65.7 0.6
GraphSage
84.9 1.4
1.0
86.4 + 0.5
64.7 0.7
FAGCN
85.5 0.7
87.0 + 0.3
64.1 0.2
HGGCN
86.5 1.2
1.7
87.7 + 0.4
OOM
BM-GCN
86.1 1.1
1.3
86.8 + 1.1
OOM
BernNet
84.9 1.7
1.4
87.6 0.4
0OM
G²-GCN
80.2 1.7
1.4
87.0 + 0,4
62.6 + 1.3
GOAT
84.0
1.6
87.1 + 0.8
70.0 0.4 0.4
NAGphormer
8.2
1.2
87.3 1 0.3
68.1
PolyFormer
2.5
2.3
87.5 + 0.2
70.4 0.2
Exphormer
0.5
7 1.2
87.6 + 0.3
69.2 = 0.5
VCR- CCR-Graphormer
83.8 + 2.1
73.7 + 0.5
87.7 + 0.4
68.2 + 0.2
HEROFILTERROurS)
86.8 + 1.5 75.0 + 1.2 87.6 + 0.3
70.5 + 0.4
Table 2: Comparison of different methods in node classification task on heterophilic datasets. We denote red, green, blue as the best, second best, and third best performance, respectively. OOM denotes "Out of Memory".
Snap-
Year
Texas
Squirrel
Chameleon
Cornell
Wisconsin
Actor
0.93
0.78
0.89
0.78
0.77
0.89
0.84
0.76
MLF
1.100.1
3.1
74,4
33.6
49.4
69.9
3.74337
35.0
GPRONN
45.2
64.2
5.3
30.4
2.0
39.2 2.0
39.1
4.4
72.8 2 4.5
30.9
0.7
ChebNet
OOM
46.3
74.4
33.4 =
49.4
69.7 +
71.9
3.0
34.8
ChebNeill
0OM
40.4
82.1
37.5
522
72.2
83.8
222
35.1
APPNP
40.9 1 0.1
44.1 0.6
56.3
3.9
27.8
0.7
44.3 1.5
42.9 1 3.7
52.3 4.9
28.4
0.6
GUNJKNe
OOM
46.7
37.8
26.3 20
42.2
40.9
49.6 4.8
27.9
GCN
46.1 0.1
46.2 46.2.00.
58.7
27.1
0.
41.4 1.7
40.3
49.4
28.4=00 0.7
GAT
0OM
47.14 0.1
58.3
4.8
28.7 +: 0.9
43.9 +: 1.6
46.3 + 4.3
51.1
6.2
28.9
0.5
GraphSage
48.9 0.1
48.1::02
74.3
36.2
002:000
0.8
46.2
69.1
76.9 4.5
34.620.7
FAGCN
0OM
41.7..3.
63.4
33.9
0.8
43.2 0.9
53.4
63.1 4.3
34.4
0.5
H.GCN
0OM
48.4
81.1 5.2
32.2 12
$4.0 1.1
18.5
78.0
=4.9=0.4
BM-GCN
COM
0OM
75.4
04.2=09
53.6
55
34.7=05
BemNett
0OM
38.2440.2
80.7 3.3
38.7 0674400
50.9
1.2
71.8 4 2,8
84.3 4 4.3
35.4
0.6
G'-GCN
0OM
0.52
81.3
0..
52.9 1.3
71.144.1
84.1 +
34.3-02 04
GOAT
$5.0 0.2
53.
62.2 5.3
1.2
1.29.:2..4
52.4.11.
74.6
34.2 00
NAGphormer
54.8
47.81022
6.71
36
47.6112
63.8141
76.1240
34.8066
PolyForner
0OM
4.2
5,4
1.
1.9
60.833
15
34.9=03
Exphormer
OOM
47.0 0.2
76.3
0.5
46.5
63.5
71.2 1.0
34.7=006
Gmphorrr
COM
55.7
64.2 4.0
34.2=20
3.9
38.9
53.1
99
3488
0.
(FROFILTER(Oums)
64.2 0.1
54.6 + 0.1
85.0 3.5
47.7 2.2
$7.3
72.5 + 388
85.1 + 3.1
37.8
0.7
We compare against classical GNNs (GCN, GAT, GraphSAGE, ChebNet), spectral models (BernNet, GPRGNN), heterophily-aware methods (H,GNN, BM-GCN, G²GCN), and graph transformers (GOAT, NAGphormer, Exphormer, PolyFormer, (CR-Grrphormer)) Detailed dataset and model descriptions provided in the Appendix

---

Table Patchers on Cora and Chameleon.
Table 4: Random vs, ranked patch order.
Patchers
Cora
Chameleon
Dataset
Random
Ranked
Change
Bandpass Filter
71,3 = 0.8
52.1 + 1,5
Cora
71,4 1.1
77.3 + 0,6
1 5.9%
Heat Filter
70,4 +: 1.7
47.7 1: 1.7
Citeseer
60.7 + 1.4
64.5 1 1.8
1 3.8%
Shared parameters
73.0 + 1.3
$2.2 + 1.1
Squirrel
35,4 1.2
37.8 1 1.6
2.4%
HEROFILTER
77.3
0.6
57.3 1.2
Chameleon
51.0
57.3 +
6.3%
Table 5: Accuracy on patch-induced graphs.
Table 6: Indivdual component effectiveness in HEROFILTER.
Model
Cora
Chameleon
GCN
76.1 + 2.3
39.9 + 2.0
Ablation
Arxiv-Year
Snap-Pateents
GCN-Patch
74.1 1.0
56.0 2.0
HEROFILTER
54.66 + 0.28
65.05 0.04
FAGCN
73.2 + 0.7
43.2 0.9
Patch-Mixing
54.49 + 0.04
64.97 0.05
FAGCN-Patch
74.8 + 0.4
48.3 2.2
w/ Feature-
53.85 + 0.20
63.00 0.01
Both Removed
52.81 + 0.10
62.95 + 0.09
HEROFILTER
77.3 + 0.6
57.3 1.2
5.1 Overall Performance
Tables 1 and
summarize classification accuracy across all datasets. Three core insights emerge:
(1) HEROFILTER achieves strong performance across both homophilic and heterophilic regimes. On homophilic graphs, HEROFILTER matches or exceeds state-of-the-at performance (e.g., 70.5% on OGBN-Arxiv). More importantly, HEROFILTER substantially outperforms baselines on heterophilic datasets. For instance, on Squirrel and Snap-Patents, HEROFILTER improves model by 9.0% and 9.2%, respectively. This validates the theoretical claim that a fixed low-pass high-pass filter is insufficient for generalization across heterophily levels and underscores the effectiveness of adaptive spectral filtering.
the next-best
(2) HEROFILTER remains effective on large and noisy graphs. While several baselines fail on large graphs (marked 0OM), HEROFILTER maintains strong accuracy (e.g., 64.2% on Snap-Patents) without sacrificing runtime scalability. This highlights the value of patch-based processing and Fast- HEROFILTER for memory efficiency- an increasingly critical concern in modern GNN deployments.
(3) HEROFILTER bridges gaps between GNNs, spectral methods, and transformers. Transformer models with strong inductive biases underperform on small irregular graphs (e.g., Texas, Wiscon- sin). In contrast, HEROFILTER'S simpler design generalizes well without architectural complexity. Compared BernNet GPRGNN, HEROFILTER does not require fine-tuned frequency designs and yet achieves superior results, highlighting its robustness and ease of use.
5.2 Ablation Studies
To better understand HEROFILTER's 's internal design, we conduct controlled experiments analyzing the contributions of the Patcher, Mixer, and positional structure.
Effectiveness of Patchers. We compare HEROFILTER's adaptive polynomial patcher against several alternatives: heat filter, bandpass filter, and a shared-parameter variant. As shown in Table 3, our method consistently outperforms others, especially on heterophilic graphs (e.g., 57.3% Chameleon). This highlights the importance of a learnable and flexible filter form, consistent with our theoretical insights from Section 3 While bandpass and heat filters capture fixed spectral bands, they lack the adaptability needed for general graphs.
We assess the role of node order within each patch. As shown in Table 4 randomly shuffling the patch degrades performance on all datasets, with up to 6.3% accuracy loss Chameleon. This demonstrates that patch structure encodes meaningful spectral and positional information, and that the model effectively leverages this structure, an important design signal for future permutation-sensitive architectures.
Importance of Patch Order.
Patch-Induee Graphs. isolate the value of the patcher, we create graphs by linking each node only to its selected patch neighbors, then apply cxisting GNNs (GCN, FAGCN), Results in Table 5

---

show significant performance gains, especially for GCN on Chameleon (+16%), validating that HEROFILTER Patcher successfully surfaces informative neighbors even for GNNs not explicitly tuned to heterophily. Conversely, slight degradation on Cora for GCN confirms that fixed low-pass assumptions may conflict with spectrally diverse patches.
Component- Analysis. We remove or replace individual layers in the HEROFILTER Mixer to evaluate their contribution (Table 6). Removing the patch-mixing or mixune layers causes consistent drops in performance across datasets, confirming their complementary roles. Notably, the patch-mixing layer provides the largest standalone gain (e.g.. +2.02% on Snap-Patents), suggesting its importance in modeling structural diversity within patches.
6 Related Work
Learning on Heterophilic Graphs. Traditional GNNs, including GCN [9). GAT 22), and APPNP [31] are grounded in the homophily assumption, neighboring nodes tend to share simi- lar labels. However, real-world networks often violate this assumption, exhibiting heterophily where connected nodes belong to different classes [32 [7 This has motivated a range of models that en- hance GNN performance under heterophily. H₂GCN to multi-hop neighborhoods or learn block-level compatibility. Other methods like FAGCN [4 and BernNet [22] leverage spectral insights, using learnable filters to balance low- and
32 and BM-GCN {3 extend message passing
information. ChebNetll [35) revisits Chebyshev polynomials for deeper spectral modeling, while G² GCG 36 introduces gradient gating mechanisms. These works highlight the importance of high- frequency components in heterophilic settings but often rely on heuristic assumptions or task-specific filter tuning.
Spectral GNNs and Frequency-Adaptee Filters. A complementary line of work focuses on understanding GNNs from the spectral perspective. The view of GNNs as graph filters in the spectral domain, applying transformations g() via eigen decomposition of the Laplacian, has been formalized in studies such as [15 37). Spectral GNNs such as ChebNet [2]] and GPRGNN [37 design polynomial filters to capture information across the graph spectrum. While these methods enhance theoretical interpretability and offer flexibility, most assume a global, fixed filter shape (e.g., low-pass or Dand-pass), which limits adaptivity. As recent theoretical works note [77] [6]. the relationship between graph heterophily and optimal spectral response is non-monotonic and dataset-dependent, suggesting the need for instance-level adaptivity filter design.
Graph Transformers and Global Attention. Transformer architectures have been adapted to graphs to address the limitations of locality in message passing. Approaches such as NAGphormer (38), GOAT 339, Exphormer [40), VCR "CR-Graphormer [41], and PolyFormer (42) integrate global attention mechanisms, often augmented with positional encodings or spectral bias terms. While effective on large-scale and heterophilic graphs, these models tend to be computationally expensive and architec- turally complex. Moreover, their reliance on learned positional encodings can make generalization brittle, especially on smaller graphs or graphs with evolving structure.
Our proposed HEROFILTER bridges the gap between the spectral flexibility of filter-based GNNs and the architectural simplicity of transformer-free encoders. Instead of hard-code frequency biases or depending on hand-tuned spectral forms, HEROFILTER introduces adaptive polynomial filter that dynamically aligns its frequency response with the graph's 's heterophily structure. Theoretical results provide the first formal link between graph heterophily, spectral filter response, and generalization error. This connection not only strengthens empirical observations from prior work [27] [22]. but also introduces framework for future frequency-awe aware and architecture aggnssicc GNN design.
7 Conclusion
In this paper, we make three key contributions: (1) a theoretical analysis that, for the first time, formally connects graph heterophily, spectral filter response, and generalization error challenging the prevailing assumption of monotomic filter-heteroe heteropilyyp correlation; (2) a modular architecture that integrates adaptive polynomial filters with a lightweight MLP-Mixer backbone, enabling interpretable and efficient spectral reasoning across diverse graph structures; and (3) extensive empirical validation across 16 benchmark datasets, where HEROFILTER consistently outperforms state-of-the-an GNNs and graph transformers on both homophilic and heterophilic graphs, including large-scale settings.
10

---

Acknowledgements
We thank the anonymous reviewers for their constructive comments. This work is supported by the MIT-IBM Watson AI Lab, National Science Foundation under Award No. IIS- 23399399 and No. 2406439, DARPA under contract No. HR001 12490370 and No. HR001 124S0013, U.S. Department of Homeland Security under Grant Award No. PTSTCIN00001-08-000
Amazon- Amazon-Virginia Tech Initiative for Efficient and Robust Machine Learning, Amazon AGI Team, Amazon AWS, Google, Cisco, 4-VA, Commonwealth Cyber Initiative, National Surface Transportation Safety Center for Excellence, UIUC AICE Center, and Virginia Tech. The views and conclusions are those of the authors and should not be interpreted representing the official policies of the funding agencies or the government. We thank Professor Julian Shun (MIT) for his insightful discussions and feedback that improved this manuscript.
References
[1] Kexin Huang, Cao Xiao, Lucas M Glass, Marinka Zitnik, and Jimeng Sun. Skipgnn: predicting molecular interactions with skip-graph networks. Scientific reports, 10(1):1-16, 2020.
[2] Donggi Fu and Jingrui He. SDG: A simplified and dynamic graph neural network. In Fernando Diaz, Chirag Shah, Torsten Suel, Pablo Castells, Rosic Jones, and Tetsuya Sakai, editors, SIGIR '21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual Event, Canada, July 11-15, 2021, pages 2273-2277. ACM, 2021.
[3] Shuaicheng Zhang, Qiang Ning, and Lifu Huang. Extracting temporal event relation with syntax-guide graph transformer. In Findings of the Association for Computational Linguisties: NAACL 2022, pages 379-390, Seattle, United States, July 2022. Association for Computational Linguistics.
[4] Long Zhao, Xi Peng, Yu Tian, Mubbasir Kapadia, and Dimitris N Metaxas. Semantic graph convolutional networks for 3d human pose regression. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3425-3435, 2019.
[5] Haohui Wang, Baoyu Jing, Kaize Ding, Yada Zhu, Wei Cheng, Si Zhang, Yonghui Fan, Liqing Zhang, and Dawei Zhou. Mastering long-tail complexity on graphs: Characterization, learning, and generalization. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Dis- covery and Data Mining, KDD '24, page 3045-3055 for Computing Machinery.
New York, NY, USA, 2024. Association
[6] Haohui Wang, Yuzhen Mao, Yujun Yan, Yaoqing Yang, Jianhui Sun, Kevin Choi, Balaji Veeramani, Alison Hu, Edward Bowen, Tyler Cody, and Dawei Zhou. Evolunet: advancing dynamic non-iid transfer learning on graphs. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024.
[7] Lecheng Zheng, Dongqi Fu, Ross Maciejewski, and Jingrui He. Drgnn: Deep residual graph neural network with contrastive learning. Trans. Mach. Learn. Res., 2024, 2024.
[8] Zihao Li, Lecheng Zheng, Bowen Jin, Dongqi Fu, Baoyu Jing, Yikun Ban, Jingrui He, and Jiawei Han. Can graph neural networks learn language with extremely weak text supervision? In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar, editors, Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), ACL 2025, Vienna, Austria, July 27 August 1, 2025, pages 11 11138- 11165. Association for Computational Linguistics, 2025.
[9] Xinyu He, Dongqi Fu, Hanghang Tong, Ross Maciejewski, and Jingrui He. Temporal hetero- geneous graph generation with privacy, utility, and efficiency. In The Thirteenth International Conference Learning Representations, ICLR 2025, Singapore. April 24-28, 2025. OpenRe- view.net, 2025.
[10] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11168-11111 11176, 2021.
11

---

[11] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang. Di Jin, and Philip S. Yu. Graph neural networks for graphs with heterophily: A survey, 2022.
[12] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In NewrIPS, 2022.
[13] Shichang Zhang. Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old MLPs new tricks via distillation. In International Conference on Learning Representations, 2022.
[14] Limei Wang, Kaveh Hassani, Si Zhang, Dongqi Fu, Baichuan Yuan, Weilin Cong, Zhigang Hua, Hao Wu, Ning Yao, and Bo Long. Learning graph quantized tokenizers. The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025.
[15] Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. ArXiv, abs/1905.095535 2019.
[16] Yuan Gao, Xiang Wang. Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang. Addressing heterophily in graph anomaly detection: A perspective of graph spectrum. In Proceedings of the ACM Web Conference 2023, pages 1528-1538, 2023.
[17] Fan Xu, Nan Wang, Hao Wu, Xuezhi Wen, Xibin Zhao, and Hai Wan. Revisiting graph-based fraud detection in sight of heterophily and spectrum. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9214-9222, 2024.
[18] Katherine Tieu, Dongqi Fu, Jun Wu, and Jingrui He. Invariant link selector for spatial-temporal out-of-distribution problem. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Moham- mad Emtiyaz Khan, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2025, Mai Khao, Thailand, 3-5 May 2025, volume 258 of Proceedings of Machine Learning Research, pages 4753 4761. PMLR, 2025.
[19] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.
[20] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
[21] Shanshan Tang, Bo Li, and Haijun Yu. Chebnet: Efficient and stable constructions of deep neural networks with rectified power units using chebyshev approximations, arXiv preprint arXiv:1911.05465 2019.
[22] Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In NeurlPS, 2021.
[23] Shouheng Li, Dongwoo Kim, and Qing Wang. Beyond low-pass filters: Adaptive feature propagation on graphs. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part 11 21, pages 450-465. Springer, 2021.
[24] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Was Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1375 2022.
[25] Yang Liu, Yao Zhang, Yixin Wang, Feng Hou, Jin Yuan, Jiang Tian, Yang Zhang, Zhongchao Shi, Jianping Fan, and Zhiqiang He. A survey of visual transformers. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[26] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. Al Open, 2022.
12

---

[27] Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wei Chang, Doina Precup, Rex Ying, al. The heterophilic graph learning hand- book: Benchmarks, models, theoretical analysis, applications and challenges. arXiv preprint arXiv:2407. 0961 2024.
[28] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnaab14,, 2021.
[29] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, page 807-816, New York, NY, USA, 2009, Association for Computing Machinery.
[30] Alberto P Garcfa-Plazt Victor Fresno, Raquel Martínez Unanue, and Arkaitz Zubiaga. Using fuzzy logic to leverage html markup for web page representation. IEEE Transactions Fuzzy Systems, 25(4)991--933, 2016.
[31] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019.
[32] Jiong Zhu, Yujun Yan. Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
[33] Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng. Block modeling-guided graph convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4022-4029, 2022.
[34] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low- fowffreuencyy information in graph convolutional networks. In AAAI. AAAI Press, 2021.
[35] Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. In NeurlPS, 2022.
[36] T Konstantin Rusch, Benjamin P Chamberlain, Michael W Mahoney, Michael M Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. In International Conference on Learning Representations, 2023.
[37] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
[38] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph trans- former for node classification in large graphs. In Proceedings of the International Conference on Learning Representations, 2023.
[39] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference on Machine Learning, pages 17375-17390. PMLR, 2023.
[40] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613-31632. PMLR, 2023.
[41] Dongqi Fu. Zhigang Hua. Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. Ver-graphormer: A mini-batch graph transformer via virtual connections. arXiv preprint arXiv:2403. /6030, 2024.
[42] Jiang Liu, Hui Ding, Zhaowei Cai, Yuting Zhang, Ravi Kumar Satzoda, Vijay Mahadevan, and R Manmatha. Polyformer: Referring image segmentation as sequential polygon generation. In Proceedings of the JEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 18653-18663 2023.
13

---

[43] DG Hoffman. Packing problems and inequalities. In The Mathematical Gardner, pages 212-225. Springer, 1981.
[44] Mingguo He, Zhewei Wei, zengfeng Huang, and Hongteng Xu. Bernnet:
Learning arbitrary graph spectral filters via bernstein approximation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14239-14251 Curran Associates, Inc., 2021.
[45] Hongbin Pei, Bingzhe Wei, Kevin ChennChuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations, 2020.
[46] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non non-homen non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20002, 2021.
[47] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[48] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
[49] 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. Advances in neural information processing systems, 33:22118-225
2020.
[50] Jure Leskovee and Rok Sosič. Snap: A general-purpose network analysis and graph- library, ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1-20, 2016.
[51] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5449-5458. PMLR, 2018.
[52] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the core contributions of HEROFIL. TER, including its theoretical analysis, adaptive filter design, and experimental improve- ments. These claims are supported throughout the paper with theoretical bounds, algorithmic innovation, and extensive empirical evaluation.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses the limitation on computation efficiency which they alleviate this limitation by introducing an efficient model variant.
3. Theory assumptions and prool's
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
The paper provides full assumptions and proofs in Appendix C for Propo- which establish the theoretical grounding for the
sition I Proposition [ and Theorem I proposed adaptive filtering mechanism.
4. Experimental result reproducibility
Question: Does paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper details datasets, baselines, metrics, and experimental setups, and refers to the appendices for parameter settings and runtime details, making reproduction
feasible.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The paper provides anonymous open repository link that includes code and datasets for
reproducing results.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Detailed descriptions of training settings, data splits, patch sizes, optimizers, and hyperparameter tuning procedures are included in the appendices.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All reported results include standard deviations (e.g., 86.8 # 1.5), indicating that experiments were repeated with multiple random seeds.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The runtime and scalability analysis are included in Appendix G
Fast-
HEROFILTER is proposed specifically for scalable deployment, and compute efficiency is discussed.
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research uses only public benchmark datasets, poses no human or environ- mental risk, and follows ethical machine learning practices.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
15

---

Justification: The impact statement notes that the work is intended to advance machine learning but does not specifically highlight societal impacts.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The work does not involve any high-risk models or data types.
12. Licenses existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets used publicly available and either CC BY 4.0 or MIT-licensed. Proper citations are provided.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new datasets or models requiring separate documentation are introduced beyond what is presented in the paper and repository.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any crowdsourcing human subject research. 15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research does not involve human participants or require IRB approval.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research?
Answer: [NA]
Justification: Large Language Models (LLMs) were used only for writing assistance (e.g.. editing and formatting) and had no role in the technical contributions of the research.
16

---

A
Appendix Content
Appendix
Key symbols and notations in this paper.
Appendix Detailed proofs Proposition T Proposition 2 and Theorem |
Appendix
D
Algorithm descriptions including HEROFILTER Framework and Fast-
HEROFILTER Framework.
Appendix H
Dataset statistics, including node count, edge count, number of classes, feature dimensions, and heterophily scores for both homophilic and heterophilic graphs. Details of baseline models used for comparison and implementation details.
Appendix F
Parameter settings and tuning procedures, including hyperparameter search
spaces.
Appendix G Scalability and runtime analysis of Fest-HEROFILTER and baseline models showing the inference speed of each model.
Appendix Parameter sensitivity studies showing the impact of patch size and filter numbers.
B Symbols and Notations
Table 7: Symbols and notations.
Symbol
Description
g
Graph
V
Set of vertices (nodes) of the graph G Set of edges the graph G
X
Node feature matrix of g. Number of nodes in the graph G
7
L, A
Laplacian matrix and adjacency matrix of g
L Ā
Normalized Laplacian matrix and adjacency matrix of G
((v)
Set of neighbors of node v
(A))
A spectral graph filter on eigenvalue matrix A
C Proofs of the Theorems
Proposition 1. Let Å be the normalized adjacency matrix with eigendecomposiiion À UAUT,
where do S ... & An-1 = 1. Then the average filter response is lower bounded by:
((A.)
El log 1ly
(3)
log - ((.))l log En-1 g(2i)
Proof. According to the weighted AM-GM inequality 43 we have
g(Ao)
g(2n-1)
E Eosiso- 1(11)) Ihol + .... Eosisn-1 ((2b)
hm--1
(16)
olAg) z z/h0l Casisn 10000
a(An-1)
[hn-1 Sasisn 19(0)
As we have valid polynomial filer g(Ai) E [0, for all i [44. then
Eosien g(Ae)(bea)
1mg Eosisn-
1b
Eosign-IRAy R0A
Eosisn-19h (1,,
(17)
II
hg Eocken-IDARE)
0SiSn-1
17

---

Since both sides of the inequality are greater than O, we take the logarithm
Cacisn-19(Ai)l
log
log lh:]-
(18)
Eosign-19(M 9(1,)
Coskgn-19(M) g(>x)
ugign-1
Hence, it completes the proof.
Proposition 2. Let Y = (y1...., be the label vector with yi E {0,.... C 13, and let A be the eigenvalue matrix of A, assuming all eigenvalues are nonzero. Then there exist weights {wx K such that:
k=1
Align(g(A). 11
where g(A) = E o(we C A*), (0) 0. and Align(;,)) denotes cosine similarity.
Proof. To match (A) with Y, require g(A) cY, where # 0 is scalar. This requires:
K
(wkss 2 = ay Vi (1,2.....
(19)
If Y; 0, then need (A) 0, Vi n... Let wk,i for all since a0)) 0, the conclusion holds.
If Y; > O. Case 1: or (z) bounded. Suppose (1x) E [0, M] for some M > 0. Since Y, E [0, C-11} 1], boundedd we have cY, K E [0, .)) by choosing e large enough. Since is continuous and monotonic, we can always find Wx,i satisfy (Ww,,((A,)*) X
Case 2: (x) unbounded. this case, no scaling constraints are required. The left term can be arbitrarily large if Wk, chosen large enough. So we can find WK,i. s.t. (A.).(A.. = *
Thus, we have
(A)
Σ 1=1
a (wk, (A,)) cY
(20)
for all i E {L....,n] n1. Then we have
s(A) = cYr
(21)
The cosine similarity is
s(A) Y Y
=
(22)
Hence, it completes the proof.
Theorem Consider binary classification task on a graph G with n nodes. Let (Xo; X1) be
the filtered node features for nodes belonging to class 0 and class 1, respectively. Y == (Yo. y1) be the label indicators for classes 0 and 1. Let n7 be the spectral coefficients of the label and feature differences, respectively. Then the error is upper bounded as:
min 4b VEIg.
(n:)
5, EEZs.9
Σ log 1h4
We1 A.
Er Y) < C1
(5)
2n log
Σ g(1 hu) -2n log Σ g(1 - X1) iETs.
iEIn
where Cj is constant, Iş = {i 8 + 0}, and (xx) 1anmmaxxx,-111111
Proof. Let sb be the clamp function defined
x x> 1
(x) A min *mmn(mar (max(x, -1),
-I<I4 <<<<1>
(23)
-1 x <<
18

---

2
d(a, vxx) -
y/
1+ ev(x) y
1 1 ct
[ ) 0]
<> 1
10, (1te 19
>>1,y=
(24)
10, (Ite) )1
.< 0
(1 ):00
2 -<
(1 (1+))
and for x E [-1, 1J. the first-order Taylor expansion of Ite is 1 fa. Denote R(x) as the remainder
term, that is, R(x) = Itc=
1 2 + x. since
1 (ator)))
6t (-4c² +620+1
1
1
(25)
(1+
(1+
8"
x=-
we have
|z|3
[R(x)] S max
(1+
(26)
3!
48
Therefore,
1 60 11 )2
)/² - [+te(t) -1) -1--
2 + d( bx))
1
2
(x)
y +[((x)))
2 4
(1+
1 1
1
1
(2)) -V)
+ (R(v(x))) +2R(v(x))
[xxx
8 + (1+
2 4
2
4
(27)
1
+ [1(1)1
2
[x)
1
(2)) -9)
[xxx
8/ + (1 + E)²
2 4
48
24
2
4
(1
222))((a)
(xx)
(x)) 66
13)
(1o(00o) + 1/ +
2 -
16
2304
24
(1 e]
(2)
(x))
(xx)11
(x))
4
4
16
48
96
2304
(1 c)
According to the above conclusion,
Er (o) = =Σ (1- 1 eg(l -A)(x xo1)
You
(28)
n 1
(V1 -Yo) (lzz) 11)(2))11
(2))2
(z) ||
(z) l1
n
S
4
16
48
96
2304
(1 + e)2*
z = =[[[- (X Xo): noting that C ~ [|b(()) < [z)(())] < (z) 11 < 1z) < then
we have
Er (Xo,
- 4 4 (y1 -Yo) 1b(z)+
-o0)7b(22) + 2304 [|0(2]]13 + (1 e)²
217
n
(29)
=c 1 Ee is ((r you) 13(X1-Xo))
where oj is constant. For any n, we construct 7i + o(1-A,)a, (n)) such that māg (1 - 111-xa)0 2,) $ and Eietyan & (ng (1 - 6,) = EiET n. (1 - 2x) 8, We define my min n.5
19

---

From the proof of Proposition
| for any g(-) and 6, we have
1 (nh (1 x:)
E
(m:
(1 - X:) 6:)
iEIn.A.n
Tky (1 Ax) 2 mg
Σ
9 - Ac)
i
=Mg
Σ
9 - Σ ( X1)
Σ 9 11)
(30)
iETs,5
iETn
i=0
=My
9 (1- X1)
kEIN,
EiEIon log lhsl
m
log Σie g(1 - Ax) hal - log Eiets, A.)
According to Eq. 29 and Eq. 30 we have
1 Er Y)
- XII
n
min v0 A,]6;
(1:) 8, EiEIs, log [hal
(31)
= Er (Xo, yo) C1 log Eiets, 9 - X₂) lhgl 2n log Eieta I (1- Xx)
Hence, it completes the proof.
D
Algorithm
Algorithm 1 HEROFILTER Framework
Require: source graph 8, adjacency matrix A; patch size p; layer number m Ensure: y
1: Preprocessing:
2: A < Normalization A)
3: A, U +- EigenDeecoppostionn
4: HEROFILTER Patcher ot
5: R < Ug(A)U²
Compute the patcher score matrix > Extract top-p nodes columnwise from patcher score matrix
6: P < X(top-Peot (R.p)
7: p <-P
Raxpxd
8: HEROFILTER Mixer:
9: for 7 m do
10: P <-
O (puch)) (lccttur))
Mixing along patch dimension
11: P <-
P
Mixing along feature dimension
12: P +- Aggregate(P Pm)
13: y + MLP(P, θ predict) & Aggregate along patch dimension via summation function and predict node label.
14: return y
In the standard HEROFILTER framework, we generate patches denoted by P = [P : eeeveee V} for all nodes using the patcher é. The patches P undergo multiple layers of HEROFILLER Mixer operations to yield pm, which is subsequently employed for node label prediction to obtain ). Initially, we preprocess the data by normalizing matrix A, followed by the extraction of A and
U from the modified adjacency matrix Å. Applying the patcher on X to our graph, we obtain patches of size [n dimension of the input node features. Each patch, represented by a [p x d) matrix, encapsulates the extracted features from node and its top p neighboring nodes. These patches are then processed by
d]. where denotes the number of nodes, the patch size, and d the
20

---

patch-mixing layer, which mixes information along the patch dimension p by transposing its feature dimension with its patch dimension and passing through an MLP layer. This process followed by Layer Normalization and an arbitrary activation function, after which another transpose operation is conducted between the feature and patch dimensions, resulting tensor of size [n x x d]. This tensor is further processed by a feature- mexture-mixing layer, utilizing an MLP to operate on the d-dimension. By passing P through m layers, the final Pm is constructed. Finally, we aggregate along the patch dimension p of pm using arbitrary aggregation function, yielding a final representation of size [n x d|. An additional MLP is applied to this final representation for classifying the label of each node, resulting in matrix of size [n [
2 Fast- Algorithm
Framework
Require: Source graph G(V, & E X); adjacency matrix A; patch size på layer number m,; dangling
scalar c
Ensure: Predicted labels y
1: Preprocessing:
2: < Normalization A)
3: HEROFILTER Patcher Ofast
4: for in [V] do
5: ry Minimize I (r.) given A,
Eq.
12
6: R < Stack(r,)
7: P <- (ctop-Peol (R.
D Extract top-p nodes column-wise P E Rexpxd
8: pd <- P
9: HEROFILTER Mixer:
10: for | = 1 to do
11: D' <- (MLP [[MLP((LayNNorm(PP (P (macc)) P <- (MLLP(LayrNNrm ( (cauure))
> Mixing patches Mixing features
13: P +- Aggregate Pm)
14: ) + MLP(P, predict
Predict node label
15: return y
In the Fast- HAss-HERFFILTER framework, generate patches P= (P. patcher diast, mix P using multiple layers of patch-mixing operations to obtain pm and predict node labels y/ using pmM The patcher process involves minimizing an objective function, in Eq. 12 to obtain the patcher scores r, for each node u. These scores are then stacked to form the patcher score matrix R. The dangling scalar e controls how the patcher adapts to different degrees of heterophily during score computation. When e is lower, the focus of the patcher score matrix R focuses on relationships between nodes with similar spectral properties. On the other hand, when e is higher, the patcher score matrix R captures relationships across nodes with varying spectral characteristics, allowing the model to adapt to more diverse heterophily patterns. The choice of e enables the framework to flexibly adjust its spectral response based on the underlying heterophily structure of different graphs. The rest of the framework remains the same as the standard HEROFILTeR framework.
E V) for all nodes using
described
E
Experiment Setup
Data Splits. In our experiments, we are strictly using the same training and testing environment across different baselines. Following the official data split provided by [45), heterophilic graph datasets (Texas, Squirrel, Chameleon, Cornell, Wisconsin, Actor) and homophilic graph datasets (Cora, CiteSeer, PubMed, OGBN-Arxiv) are split roughly by 48 32 : 20. Two large-scale heterophilic graph datasets (arxiv-year and snap-patents) are following [46). using 50 25 25 random data split. All datasets are provided with masks in the newest version of Pytorch Geometrics.
Implementation Details. We employ the Adam optimizer 47 with a learning rate of 0.01 and weight decay of 5e-4 for training the model. The default training setting for all models is performed using torch-geometre default masks (train, validation, and test) and trained for maximum of 500 epochs, hidden dimension of 64, a dropout rate 0.5, and a number of layers of 2. Early stopping applied with patience of 50 epochs, which monitors the validation loss and terminates the training if
21

---

Table 8: Dataset Statistics of homophilic and heterophilic graph datasets. The columns show the number of nodes (DV), the number of edges (IE)) the number of unique classes (())), the feature indicating the degree of heterophily within
dimension () and the average heterophily score 2> each dataset.
Dataset
[V
[3]
D
X
Ag
Cora
2708
5278
1433
0.19
Σ 0.5
Citeseer
3327
4676
3703
0.26
Pubmed
19717
44327
3
500
0.2
OGBN-Arxiv
169343
1116243
40
400
0.34
Snap-PPatents
2,923,922
13,975,788 788
269
0.93
Arxiv-Year
169,343
1,166,243
128
0.78
Texas
183
295
1703
0.89
Squirrel
5201
198493
2089
0.78
Σh B
Chameleon
2277
31421
2325
0.77
Cornell
183
295
1703
0.89
Wisconsin
251
499
5
1703
0.84
Actor
7600
33544
5
931
0.76
there no improvement observed within the specified patience. We employ each baseline method as a representation learner, subsequently concatenating their outputs with two-layer MLP to perform the node classification task. To assess the performance of the models, we use the standard accuracy metric, which is commonly adopted in node classification tasks.
Datasets. We evaluate model using several standard graph datasets originated from 48
30
28 46 49 50]:
Cora, Citeseer, PubMed, OGB-Arxiv, Snap-Patents, Arxiv- Year, Texas, Squirrel, Chameleon, Cornell, Wisconsin, and Actor. These datasets are diverse in terms of their sizes and degrees of heterophily. Specifically, homophilic graph datasets are Cora, Citeseer, and PubMed, while heterophilic graph datasets include Texas, Squirrel, Chameleon, Cornell, Wisconsin, and Actor To demonstrate the effectiveness of HEROFILTER on larger scale graph datasets, we also evaluate our model on Penn94 [46), Arxiv-Year OGBN-Arxi (49 and patent networks (50) datasets.
Comparison Methods. We benchmark our model against a variety of established methods. For homophilic graphs, consider: GCN [19], GAT (20), GPRGNN (37), ChebNet [2I]/ChebNetII [35). APPNP [31], GCN-JKNet [51], GraphSage [52 and FAGCN 23 J. For heterophilic graphs, we ex-
plore: H₂GCN 322, BM-GCN 33 BernNet 4. and G² For graph transformer based meth-
ods, compare with: NAGphormer (38), VCR- VCa-Graphrrmer 41. Exphormer [40), Polyphormer [2]
and GOAT 39] Lastly, we incorporate MLP.
Details of Parameter Settings and Tuning
We perform a grid search to find the optimal hyperparameters for our model, including the learning rate, patch size, and filter number. The search space is defined follows: the learning rate (0.01, 0.008, 0.005, 0.003, 0.001}, the patch size E {8, 16, 32, 64, 96], and the filter number E (10, 50, 100, 150, 200). For Fast-HERO,,,,ER, we across different frequency components. The optimal hyperparameters are determined based on the performance of the validation
0.5 to balance the spectral response
G Scalability and Runtime Analysis
Scalability Analysis on HEROFILTER Mixer. We analyze the runtime of the algorithm as the number of nodes and patch size varies to assess the scalability of our proposed approach in Figure 4a We perform experiments on synthetic datasets with varying numbers of nodes from {10, 100, 1,000. 10,000, 100,000). We also consider different patch sizes, specifically {8, 16, 32, 64). The runtime results are reshaped into a matrix for visualization purposes. Figure shows the runtime in seconds on a logarithmic scale for the different patch sizes as function of the number of nodes. As expected, the runtime increases with the number of nodes and patch size. Nevertheless, Fast-HEROFiLe demonstrates reasonable scalability as the growth in runtime is sub-linear, indicating that our approach
22

---

2-1
10
Patch size
Time (saconds in lag scale)
Runtime (seconds)
2-5
Patch size 16
Patch size 32
109
Patch size 64
10-14
10-2
2-9
10a
10a
10a
10*
10
Squinel
Chamellon
Snap patents
Number of Nodes
(a) Scalability analysis of Hest-HEROFILTER (b) Runtime results for epoch of inference (5 runs). Lower is The x-axis shows the number nodes pro- better. cessed, and the y-axis shows the running time per iteration.
0.84
0.83
Actuary
0.83
Accurry
0.82
0.74
0.00
0.72
0.74
0.79
0.80
50
6g
0.72
Panch Size
40 fo
Peach Sime
50
50
Nomber Fibees
150
Nomber of Fiters
150
Figure 5: Parameter sensitivity analysis results for Cora (left) and Texas (right) datasets, respectively.
handle large-scale graph datasets effectively. The results also highlight the importance of selecting an appropriate patch size to balance the trade-off between computational efficiency and performance.
Runtime Analysis HEROF ILTER Mixer. We further evaluate the runtime performance of HEROFILTER against existing bilter-based and graph transformer methods across four datasets: Squirrel, Chameleon, Arxiv-year, and Snap-patents. Since HEROFILTER patcher can be computed offline as a preprocessing step, we only record the inference time of HEROFILTER mixer. Shown from Figure 4b] findings reveal that HEROFILTER consistently achieves the fastest inference time across all datasets. Specifically, on Squirrel and Chameleon, HEROFILTER executes in 0.92 and 0.75 milliseconds, respectively, outperforming the next fastest method (Exphormer) 8 times. For larger datasets like Arxiv-year and Snap-patents, HEROFILTEE maintains its efficiency (45.60 and 71 71.66 milliseconds), while transformer-ban methods like VCR- CCR-Graphormer either require significantly more time (1832.73 milliseconds) or fail to complete due to out-of-memory (OOM) errors.
H Parameter Sensitivity Analysis
We conduct a parameter sensitivity analysis to investigate the impact of patch size and the number of filters in Figure The analysis was performed on two datasets, namely the Cora and Texas datasets. We varied the patch size from (8. 16, 32, 64) and the number of filters from [10, 50, 100, 200). We measure the accuracy of the model for each combination of parameters. Figure (Ssoosssssooss shows the results of the parameter sensitivity analysis. The plots reveal that for both datasets, increasing the patch size and the number of filters generally leads to higher accuracy, although the improvements tend to plateau beyond certain values. This indicates that our model can effectively handle different patch sizes and filter configurations while highlighting the importance of selecting appropriate parameters to achieve optimal performance.
23


Reviews:
[{"review_id": "vB3iBHbK5g", "reviewer": "Reviewer_Yps2", "summary": "The paper investigates graph heterophily, where connected nodes in a graph have different labels, challenging the conventional use of fixed spectral filters in Graph Neural Networks (GNNs). Traditional approaches apply low-pass filters for homophilic graphs and high-pass filters for heterophilic graphs, but the study reveals that the relationship between heterophily and filter response is complex and not strictly monotonic. This suggests that fixed filter designs are insufficient, as optimal filter responses vary across frequency components. Through theoretical analysis, they confirm that GNN performance does not correlate monotonically with heterophily, necessitating adaptive filters for better generalization. They propose HEROFILTER, a novel GNN that extracts and combines salient representations across the heterophily spectrum using adaptive mixing. HEROFILTER outperforms leading baselines by up to 9.2% in accuracy across both homophilic and heterophilic graphs, demonstrating its effectiveness and versatility.", "questions": "N.A.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. **Well-Motivated Approach:** The study clearly articulates the limitations of conventional fixed filter designs and effectively motivates the development of adaptive filtering to address varying heterophily degrees.\n\n2. **Robust Theoretical Analysis:** The paper provides a thorough theoretical foundation, demonstrating that the relationship between graph heterophily and GNN frequency response is not strictly monotonic, justifying the need for adaptive filters.\n\n3. **Strong Performance:** The proposed HEROFILTER achieves up to 9.2% accuracy improvement over leading baselines across both homophilic and heterophilic graphs, showcasing its effectiveness and versatility.\n\n## Weaknesses:\nThe paper appears comprehensive, with no clear weaknesses noted in the provided context.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Yps2,\n\nThanks very much for your review and appreciation. We greatly appreciate your recognition of our work's strengths, such as the rigorous theoretical connection between heterophily, spectral filters, and GNN performance; our challenge to oversimplified low/high-pass assumptions with empirical evidence of non-monotonic relationships; and our extensive experiments demonstrating HeroFilter's effectiveness across homophilic and heterophilic graphs. Your feedback validates the core contributions of our paper and motivates us to continue advancing this area. Should you have any additional questions, suggestions, or clarifications during the discussion phase, we would be delighted to address them promptly.\n\nBest,\n\nAuthors"}, {"review_id": "bWSvEv5TAK", "reviewer": "Reviewer_zcnE", "summary": "This paper presents HEROFILTER, an adaptive spectral graph filter framework designed to address performance challenges of Graph Neural Networks (GNNs) on heterophilic graphs. Through theoretical analysis and experiments, the authors demonstrate that the relationship between graph heterophily and optimal filter response is not simply monotonic but varies complexly across frequency components. This finding challenges the conventional fixed filter design paradigm. Based on this observation, the authors propose a framework capable of adaptively capturing information across different frequency ranges. Experimental results show that HEROFILTER performs excellently on both homophilic and heterophilic graphs.", "questions": "In addition to the issues mentioned in “Weaknesses,” there are the following questions. It would be greatly appreciated if the authors could respond.\n\n1. What is the significance of the spectral correlation matrix mentioned in Section 4.1? Please elaborate and explain further.\n\n2. How is the specific operation of selecting top-k performed, and how is gradient backpropagation implemented?\n\n3. It is recommended that the results of [1] and [2] be added to the experimental comparison, and that a qualitative analysis of the patcher and mixer be added.\n\n4. In the implementation details section of the supplementary materials, the authors mention adding an additional two-layer MLP as a classifier for all baselines. I do not think this is reasonable, as this practice actually modifies the original model architecture, such as APPNP and BernNet. The authors need to provide an explanation for this practice.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper establishes a rigorous theoretical connection between graph heterophily, spectral filters, and GNN prediction performance, introducing a spectral domain measure of heterophily and deriving error bounds.\n\n2. The authors challenge the simplified assumption in existing research that \"homophilic graphs use low-pass filters, heterophilic graphs use high-pass filters,\" demonstrating through controlled experiments that this relationship is actually more complex and non-monotonic. This insight is crucial for understanding GNN behavior on heterophilic graphs.\n\n3. The authors conduct extensive experiments on 12 datasets with varying degrees of heterophily, showing that HEROFILTER outperforms existing methods on both homophilic and heterophilic graphs. \n\n**Weaknesses**\n\n\n1. Although the theoretical analysis in this paper effectively supports the main motivation of this paper, the design of specific solutions is still heuristic, resulting in a disconnect between theoretical analysis and practical solutions.\n\n2. Motivation has actually been explored in previous studies. [1] systematically discussed Q1 in its work, and [1-3] provided solutions to Q2. Authors should reasonably cite these references and discuss the similarities and differences between their work and these studies.\n\n3. As a key module of this work, the design of HEROFILTER Mixer is very similar to that of [4]. This requires clarification and explanation of the similarities and differences, as well as explicit references to [4].\n\n4. Unclear details. The author did not specify whether the experimental results were obtained using the original version of herofilter or the fast version. In addition, the number of steps when implementing the fast version was not mentioned. It is important to note that the number of passes is critical for the patcher, as it determines the size of the subgraph over the target node on which the filter is estimated [5].\n\n5. Fast-HEROFILTER actually follows the practice of APPNP, so it may not be suitable as a contribution point.\n\n[1] Node-oriented spectral filtering for graph neural networks. TPAMI 2023\n\n[2] How powerful are spectral graph neural networks. ICML 2022\n\n[3] Graph neural networks with diverse spectral filtering. WWW 2023\n\n[4] A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023\n\n[5] The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine 2013", "was_revised": true, "final_justification": "The author's response resolved most of my concerns. However, due to the excessive similarity of this work to MLP-Mixer and some over-claimed contributions, I give a final score of 4 (borderline accept). At the same time, based on the above considerations, if the AC ultimately chooses to reject this paper, I will follow the AC's decision.", "rebuttal": "**W1: Heuristic design and disconnect between theory and solutions.**  \n\nWe respectfully but firmly assert that our design is not heuristic. \n\nIn general, HeroFilter is a direct, rigorous operationalization of our theoretical insights, creating a seamless connection that advances beyond the limitations of prior works.\n\nNext, we will extend this from four aspects:\n\n- First, **Property 1** mathematically proves the non-monotonic relationship between heterophily degree and spectral filter response, revealing why fixed strategies fail on varying graphs—this insight directly motivates our adaptive polynomial filters (Eq. 7), which learn node-specific responses to modulate across frequencies, focusing on enhancing generalization power by dynamically handling diverse heterophily patterns.\n\n- Then, **Property 2** theoretically guarantees that such polynomials can align with arbitrary label patterns under heterophily, justifying the patcher's spectral relevance scoring (Eq. 8) as a non-heuristic mechanism for neighbor selection that prioritizes prediction performance through frequency-specific adaptation.\n\n- Finally, **Theorem 1**'s error bound explicitly links filter misalignment to prediction errors, bounding them in terms of heterophily—guiding the mixer's aggregation to minimize this bound empirically, thereby improving robustness and accuracy across homophilic and heterophilic settings.\n\n- This theoretical-practical bridge focuses on heterophily adaptation, algorithmic advances like scalable patching in Fast-HeroFilter, and empirical gains (e.g., +5.4% over baselines on Texas, Table 1), where our solutions yield superior generalization and prediction.\n\n  - Furthermore, our framework unifies theory for heterophily focus, algorithms for adaptive efficiency, and empirics for validated performance demonstrated by consistent SOTA results.\n\n**W2: Prior studies ([1] Node-oriented spectral filtering [2] How powerful are spectral GNNs; [3] GNNs with diverse spectral filtering).**  \n\nWe understand your consideration, and we will cite and discuss these papers in our updated version as follows.\n\nTo begin with, we would like to point out that we are the first theoretical framework characterizing heterophily and graph filters and generalization performance. Our motivation for RQ1 (non-monotonic heterophily-spectral links) and RQ2 (adaptive, scalable filters for varying relations) goes far beyond prior explorations, introducing novel elements that address their shortcomings.\n\n- [1] establishes the localization property of node-wise spectral filters in the frequency domain, while our theoretical analysis focuses on how heterophily impacts the generalization error of GNNs with polynomial filters (RQ1). For RQ2, [1] designs node-specific spectral filters while maintaining the graph structure, whereas our GPatcher adaptively adjusts the patch extraction process based on the degree of heterophily.\n\n- [2] discusses spectral power for RQ1 but overlooks varying heterophily's complexity (e.g., mid-frequency needs in low-heterophily graphs, as in our Fig. 1); we extend this with Property 2's universal alignment proof, powering adaptive solutions absent in [2]. \n\n- [3] provides diverse filters for RQ2 but statically, without adaptation to node-specific heterophily—our MLP-Mixer integration enables this dynamism, yielding +3-7% gains over similar diverse-filter baselines (Table 1). These aren't superficial similarities; our work unifies and surpasses them with new theory and adaptivity, as our consistent SOTA performance across homophilic/heterophilic graphs persuasively demonstrates.\n\n**W3: Related Work [1]**\n\nThanks for providing a related work. We analyze the difference and promise to add it to our updated paper:\n\n- [1] generalizes MLP-Mixer using the METIS algorithm to partition graphs into subgraphs for graph-level tasks, focusing on structural tokenization without explicit heterophily handling.\n \n- In contrast, our HeroFilter Mixer operates on spectrally aligned patches generated by our adaptive patcher (Eq. 8), guided by Property 1's non-monotonic heterophily-spectral theory, to dynamically blend frequencies and adapt to varying relations. \n\n[1] A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023\n\n**W4: Unclear details**  \n\nWe ran all experiments using the non-fast (original) version of HeroFilter by employing approximations for eigendecomposition on large graphs, which would maintain the core spectral relevance computations (Eq. 7) while addressing scalability issues on large graphs like Snap-Patents. Our results below show a slight difference between the fast and non-fast versions of HeroFilter.\n| Model| Squirrel (filtered) | Chameleon (filtered) |\n|-|-|-|\n| Fast-HeroFilter| 39.90±1.36|38.00±2.10|\n| HeroFilter| **40.14±1.76**|**38.49±2.83**|\n\n**W5: Fast-HeroFilter follows APPNP** \n\nWe respectfully disagree that Fast-HeroFilter merely follows APPNP from two aspects.\n\n- First, our Fast-HeroFilter is directly derived from HeroFilter's spectral polynomial filter $g(\\mathbf{\\Lambda}) = \\sum_{k=1}^K \\mathbf{w}k \\odot \\mathbf{\\Lambda}^k$ in Eq. 7 by approximating the eigendecomposition-free form via iterative power series expansion $\\mathbf{R}$ in Eq. 9, where $c$ serves as a tunable damping factor (optimized via grid search) to balance local/global importance while explicitly handling non-monotonic heterophily (per Property 1); \n\n- Therefore, the fast version also enables computation of spectral-relevance scores $\\mathbf{R}$ per node for top-$p$ patch selection (Eq. 10, **which is absent in APPNP**), integrated with our Mixer for ordered aggregation—yielding **4-7% gains over APPNP** on heterophilic graphs (Table 1) and scalable operation, distinguishing it as a heterophily-targeted advancement rather than generic personalization like APPNP's fixed alpha-based propagation.\n\n**Q1: Significance of $\\mathbf{R}$** \n\nWe would like to clarify that the spectral correlation matrix $\\mathbf{R}$ (Eq. 7) is pivital in our model design since it forms the backbone of our adaptive patching, enabling HeroFilter to address topological limitations and capture heterophily-varying relevance in a way that enhances generalization and prediction performance.\n\nTo be more specific, $\\mathbf{R}$ computes pairwise node similarities in the spectral domain via learned polynomials ($\\sum \\mathbf{w}_k \\odot \\mathbf{\\Lambda}^k$), directly embodying Property 2's alignment guarantee to match arbitrary labels under non-monotonic heterophily (Property 1).\n- It filters neighbors based on frequency-specific relevance—e.g., emphasizing high-freq for heterophilic nodes—reducing errors per Theorem 1.\n- Further: In heterophily=0.9 graphs (Fig. 1), $\\mathbf{R}$ prioritizes dissimilar but informative nodes, explaining our SOTA on Squirrel (+6.8% over baselines).\n\n**Q2: Top-k operation and gradient backpropagation.** \n\nWe would like to clarify that the top-k selection in our patcher (Eq. 8) is a precise, differentiable operation that enables end-to-end learning of adaptive neighborhoods (from PyTorch). Specifically:\n\n- For each node's scoring vector in $\\mathbf{R}$, torch.topk selects the top-p values and indices (p=32 default, tunable), forming patches by gathering features at those indices while preserving spectral order (as validated in Table 3, where ranked selection outperforms random by +3.4% by aligning with Property 1's frequency variations).\n- For backpropagation: Gradients naturally flow through the selected values to the corresponding input positions (non-selected receive zero gradients), ensuring robust training without additional approximations.\n\n**Q3: Extra results and qualitative analysis** \n\nOur results show HeroFilter outperforms both [1] and [2] on heterophilic and large-scale datasets\n\n|model |Arxiv-year|Ogbn-Arxiv|\n|--|--|--|\n|NFGNN|40.38±0.46|69.20±0.45|\n|JacobiConv|40.34±0.46|68.18±0.15|\n|HeroFilter|**54.66±0.28**|**69.61±0.33**|\n\nTo assess patcher and mixer robustness, we analyzed sensitivity to polynomial terms (k) and conducted ablations on filtered Squirrel and Chameleon datasets. Patcher results show high stability (accuracy variance <0.5% across k), highlighting hyperparameter insensitivity and reliable heterophilic performance. Mixer ablations reveal that removing patch or feature mixing gradually degrades performance, confirming their synergistic role in heterophily adaptation.\n\n||Squirrel(filtered)|Chameleon(filtered)|\n|-|-|-|\n|k=5|40.24±0.21|38.93±0.29|\n|k=10|40.05±0.17|39.40±0.23|\n|k=50|40.26±0.12|38.04±0.30|\n|k=150|40.04±0.19|38.47±0.24|\n|k=300|40.05±0.17|38.05±0.24|\n|with Patch Mixer|39.28±1.76|37.75±2.69|\n|with Feature Mixer|39.17±1.73|37.21±3.15|\n|No Mixer|37.69±1.87|36.12±2.46|\n\n\n**Q4: Explanation for adding two-layer MLP** \n\nWe would like to point that this is a common practice as shown from recent literature [1,2]. Many baselines produce feature embeddings without built-in classifiers, requiring a projection head for node classification tasks; our two-layer MLP (simple linear+ReLU+linear) adds no core architectural changes but standardizes prediction, as raw softmax on embeddings underperforms (~1-3% drop, per our tests). This doesn't \"modify\" originals as it's post-processing, akin to common practices for equitable evaluation from some other papers, such as [1].\n\n[1] A Fair Comparison of Graph Neural Networks for Graph Classification. ICLR 2020\n[2] Benchmarking Graph Neural Networks. JMLR 2023\n\nTo further validate this, we conducted experiments removing the MLP from baselines, which show that raw softmax on embeddings leads to significant underperformance (~5-11% drop), making them much worse baselines. The results below on Arxiv-year and Ogbn-Arxiv datasets demonstrate this:\n\n|Model|Arxiv-year|Ogbn-Arxiv|\n|--|--|--|\n|BernNet(w/o MLP)|32.94±0.71|65.02±0.08|\n|APPNP(w/o MLP)|32.96±1.48|65.51±0.15|\n|BernNet(w/ MLP)|37.92±0.16|69.50±0.10|\n|APPNP(w/ MLP)|44.04±0.58|68.51±0.15|\n|HeroFilter|**54.66±0.28**|**69.61±0.33**|"}, {"review_id": "sdrHFMZqqd", "reviewer": "Reviewer_2vJc", "summary": "This paper proposed an method to adaptively learn the context ( i.e., multi-hop neighbors ) of central node, that leverage the PPR importance scoring to sample the neighbors within K-order neighborhoods, aiming at addressing the heterophily diversity among nodes. The experiments across the full heterophily spectrum of graphs have been conducted to validate the effectiveness of the proposed method.", "questions": "1) It is unclear why let $g(\\Lambda)$ align with $\\mathbf{Y}$ (the label vector)\n2) Do the datasets Squirrel and Chamelon are duplicate removed ones?\n3) Table 5 is the ablation study on two large datasets (where most of comparison methods are OOM), what about other smaller heterophilic graphs?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to follow.\n2. Theoretical analysis of the non-monotonic relationship between average filter response and the spectral heterophily is present.\n3. The proposed method consistently shows competitive performance on homophilic and heterophilic graphs.\n\nWeaknesses:\n1. The goal of this work is to learn a filter that scores nodes based on their spectral alignment so as to enable an adaptive notion of neighborhood, which means that specific parameter vector $\\omega_{ki}$ (in Eq.(6)) will be assigned for  $\\lambda_i$ of different order $k$. I think it is  the core of this paper. However, an alternative approach based uniform diffusion (with constant $c$) is used. While functionally effective, this method shares notable commonalities with established attention or diffusion mechanisms, offering limited novelty.\n2. The claimed novelty is undermined by insufficient comparisons with relevant works (e.g., [1-5]), including adaptive filtering approaches , diffusion/pageRank based and attention based methods.\n3.  No performance evaluation of the proposed HETEROFIlTER Patcher(not the fast implementation). Despite of its high time complexity, it is worthwhile to show the performance of HETEROFIlTER on the small/mediate heterophilic graphs.\n\nRef. [1]. Dong, et al. *Graph Neural Networks with Adaptive Frequency Response Filter*. CIKM 2021.\n\n[2].  J Guo, et al. *Rethinking spectral graph neural networks with spatially adaptive filtering*. arXiv preprint arXiv:2401.09071, 2024. 4, 2024.\n[3].  A Saha, et al. *Learning Adaptive Neighborhoods for Graph Neural Networks*. ICCV 2023.\n[4].  J Wang, et al. *Heterophily-Aware Graph Attention Network*. (arXiv:2302.03228) PR 2024. --HA-GAT\n[5].  E. Chien, J. Peng, P. Li, O. Milenkovic, *Adaptive universal generalized pagerank graph neural network*,  ICLR, 2021.", "was_revised": true, "final_justification": "After considering the authors' responses to my concerns and those of other reviewers, I recommend acceptance of the paper.", "rebuttal": "**W1: Novelty.**\n\nWe respectfully but firmly assert that HeroFilter's novelty is not undermined by commonalities with attention or diffusion methods.\n\nIn general, HeroFilter is a direct, rigorous operationalization of our theoretical insights, creating a seamless connection that advances beyond the limitations of prior works like attention-based (e.g., GAT [1], HA-GAT [2]) and diffusion-based methods (e.g., APPNP [3], GPRGNN [4]), which often rely on uniform or topology-driven mechanisms without explicit heterophily-spectral theory.\n\nNext, we will extend this from four aspects:\n\n- **Property 1** mathematically proves the non-monotonic relationship between heterophily degree and spectral filter response, revealing why uniform diffusion in APPNP/GPRGNN or local attention in GAT/HA-GAT fail on varying graphs—this insight directly motivates our adaptive polynomial filters (Eq. 7), which learn frequency-specific responses beyond diffusion's fixed propagation or attention's edge-weighting, focusing on enhancing generalization by dynamically handling diverse heterophily patterns.\n\n- **Property 2** theoretically guarantees that such polynomials can align with arbitrary label patterns under heterophily, justifying the patcher's spectral relevance scoring (Eq. 8) as a non-uniform mechanism for neighbor selection that prioritizes prediction performance through frequency-specific adaptation, unlike attention's heuristic similarity scores or diffusion's personalized but non-spectral walks.\n\n- **Theorem 1**'s error bound explicitly links filter misalignment to prediction errors, bounding them in terms of heterophily—guiding the mixer's aggregation to minimize this bound empirically, thereby improving robustness and accuracy across homophilic and heterophilic settings, where attention/diffusion methods lack such bounds and often underperform on mixed heterophily (e.g., +4-7% gains over GAT/APPNP, Table 1).\n\n- This theoretical-practical bridge focuses on heterophily adaptation, algorithmic advances like scalable patching in Fast-HeroFilter (deriving from Eq. 7, not mere diffusion), and empirical gains (e.g., +5.4% over baselines on Texas, Table 1), where our solutions yield superior generalization and prediction.\n\n\n**W2: Relevant works**  \n\nWe understand your concern and will cite/discuss these in the revision. HeroFilter is the first theoretical framework linking heterophily, graph filters, and generalization performance, with RQ1 (non-monotonic links) and RQ2 (adaptive, scalable filters) advancing beyond priors.  \n\n- Comparing with [1]: Discusses global filter limits; [1] uses localization for node-wise filters, while we analyze heterophily's impact on polynomial error (RQ1) and adapt patches via heterophily degree (RQ2).  \n- Comparing with [2]: Rethinks spectral power (RQ1) but ignores heterophily complexity (e.g., mid-freq in low-heterophily, our Fig. 1); we add Property 2's universal proof for adaptive RQ2 solutions.  \n- Comparing with [3]: Offers static diverse filters (RQ2); our MLP-Mixer enables node-specific dynamism, +3-7% over similar baselines (Table 1).  \n- Comparing with [4]: Uses attention for local heterophily (RQ2); lacks polynomial flexibility/spectral grounding—our Eq. 7 filters and Theorem 1 bounds generalize better, +2-5% on heterophilic graphs (e.g., Squirrel).  \n- Comparing with [5]: Employs PageRank propagation; assumes uniform optimization without heterophily theory—our Property 1 non-monotonicity and Eq. 8-10 patching achieve 4-6% gains on mixed graphs.  \n\nWhile [1-5] advance spectral and adaptive GNNs for heterophily, HeroFilter distinguishes itself through: (1) theoretical novelty—proving non-monotonic heterophily-spectral relationships (Property 1), universal filter alignment (Property 2), and generalization error bounds (Theorem 1), all absent in [1-5]; (2) algorithmic innovation—integrating adaptive polynomial filtering with MLP-Mixer for node-specific, scalable patching, unlike [1]'s frequency response filters, [2]'s spatial-spectral rethinking without per-node adaptivity, [3]'s non-spectral neighborhood learning, [4]'s heterophily-aware attention lacking global mixing, or [5]'s PageRank propagation without mixer synergy; and (3) empirical superiority—delivering consistent generalization across heterophily spectra and outperforming on diverse graphs. This unified framework surpasses priors with persuasive SOTA results.\n\n**W3: Fast version performance**\n\nOur results are based on the non-fast version of HeroFilter. Below, we include performance for the fast variant (Fast-HeroFilter) from our experiments, alongside the original HeroFilter results. Shown from our results, the fast variant (Fast-HeroFilter) shows slightly lower performance but with reduced standard deviations, suggesting improved stability. \n\n| Model         | Squirrel (filtered) | Chameleon (filtered) |\n|---------------|---------------------|----------------------|\n| Fast-HeroFilter| 39.90±1.36         | 38.00±2.10          |\n| HeroFilter      | **40.14±1.76**      | **38.49±2.83**       |\n\n\n\n**Q1: Unclear why let $g(\\mathbf{\\Lambda})$ align with label vector $Y$.** \nThe key insight is that in graph learning, we want the filtered features to preserve class-distinguishability. By aligning $g(\\mathbf{\\Lambda})$ with the label vector $\\mathbf{Y}$, we ensure that the spectral filter produces representations where nodes from the same class have similar values. This is particularly important for heterophilic graphs where the original graph structure (encoded in $\\mathbf{\\Lambda}$) may not align well with labels.\n\n**Q2: Are Squirrel/Chameleon de-duplicated?**  \n\nThank you for bringing this to our attention. We have conducted extra experiments on these two datasets. The results, shown below, reinforce HeroFilter’s strong performance and robustness on these datasets, aligning with our theoretical claims of adaptive spectral filtering for varying heterophily (Property 1 and Theorem 1).\n\n| Model|Squirrel (filtered)|Chameleon (filtered)|\n|--|--|--|\n|Bern-Net|33.85 ± 1.55|32.73 ± 2.10|\n|APPNP|31.30 ± 1.24|37.10 ± 2.99|\n|HeroFilter|**40.14 ± 01.76**|**38.49 ± 2.83**|\n\n\n\n**Q3: Ablation on small heterophilic graphs.**  \nTo further validate the effectiveness of HeroFilter’s mixer components, we conducted ablation studies on the filtered Squirrel and Chameleon datasets. The results highlight the critical roles of both patch and feature mixing: removing either component leads to a gradual performance decline, confirming their synergistic contribution to robust heterophily adaptation and underscoring the mixer’s integral role in achieving HeroFilter’s superior performance.\n\n| Component|Squirrel (filtered)|Chameleon (filtered)|\n|--|--|--|\n|HeroFilter|**40.14±01.76**|**38.49±2.83**|\n|with Patch Mixer|39.28±1.76|37.75±2.69|\n|with Feature Mixer|39.17±1.73|37.21±3.15|\n|No Mixer|37.69±1.87|36.12±2.46|"}, {"review_id": "ZWwzOHyiMd", "reviewer": "Reviewer_BfgS", "summary": "This paper investigates the heterophily of graphs and observes that the frequency response varies with the degree of heterophily and the graph's eigenvalues. Building on this insight, the authors propose HEROFILTER, a method that incorporates neighborhood information based on spectral affinity instead of relying solely on topological connectivity. The approach is evaluated on both homophilic and heterophilic graph datasets for node classification tasks.", "questions": "- The performance on the Chameleon and Squirrel datasets, which have been shown to contain duplicate nodes [1]. The results may therefore be biased. What are results on the cleaned versions of these datasets? \n- What is $\\mathbf{R}\\_v$ in Equation 9\n- Please clarify how these quantities are connected in the figure 1a. Does each point in the figure corresponding to a eigenvalue $\\lambda_i$, a heterophily degree w.r.t i, and frequency response $g(\\lambda_i)$?\n- In Figure 1b, what type of accuracy is here? \n\n\n[1] A critical look at the evaluation of GNNs under heterophily: Are we really making progress?", "limitations": "The authors discuss the scalability issue and proposed a fast variant of the method.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strength \n\nSpectral filter design is an important area in graph neural networks. This paper makes a valuable study by focusing on heterophilic graphs and highlighting the limitations of standard spectral methods that rely solely on low-pass or high-pass filtering. The proposed architecture introduces an adaptive polynomial filter based on spectral affinity, aligning the filter design with the node heterophily. This alignment allows the method to better capture relevant neighborhood information. The empirical results further support the effectiveness of the approach, showing improved performance on node classification tasks, especially in heterophilic settings.\n\n## Weakness\n- The authors use the heterophily to define the heterophily degree in spectral domain (Definition 2) and analyze this quantity. However, the motivation for focusing on node heterophily rather than edge heterophily is not discussed. The paper would benefit from a theoretical or empirical justification of why edge-level heterophily is not considered, and what insights could be gained by analyzing heterophily along edges instead.\n- It is not clear what is the definition of heterophily degree, is it $\\mathbf{h}$ or $h_i$ or $\\hat{\\mathbf{h}}$ or $\\hat{h}_i$?\n- The proof for Property 1 in Appendix C is hard to follow. The authors jump to fast between lines without clear explanation. When the equality holds, what insight or interpretation can be drawn from this result?\n- The theoretical results are inconsistently presented. The main text refers to “Property” and “Theorem” without formally stating them or clearly labeling their locations. For example, there is no “Theorem 1” in the main paper, and the proof of Theorem 3 in the main text appears as “Theorem 1” in the appendix, creating confusion. Additionally, the use of the term “Property” lacks formal mathematical rigor. The paper would benefit from standard terminology such as “Theorem,” “Proposition,” “Lemma,” and “Remark,” along with clearer cross-referencing and structure.\n- Lines 136–140 assert that the align function highlights the expressive power of adaptive filters under heterophily. However, the paper does not explain why computing cosine similarity with the label vector is appropriate or effective, particularly in heterophilic graphs. \n- The paper is missing spectral GNN models such as [1-9].\n- The paper does not specify how the baselines are trained, nor does it report the hyperparameters used for these methods. \n- The dimensions involved in the Patch-Mixing Layer (Equation 10) and Feature-Mixing Layer (Equation 11) are not specified. It is unclear what inputs LayerNorm and MLP act on and what outputs they produce.\n- It is not clear whether the results in the experiments are produced using HEROFILTER or its faster variant, Fast-HEROFILTER. Furthermore, while Fast-HEROFILTER is proposed for scalability, there is no analysis of the trade-off between runtime efficiency and performance.\n- The generalization error bound in lines 141–146 is difficult to interpret. First, it is unclear what $\\mathbf{X} = (\\mathbf{X}_0, \\mathbf{X}_1)$ represents, what are filtered node features? The dimensions of $\\mathbf{X}_0$ and $\\mathbf{X}_1$ are unspecified. Second, it is not clear why the analysis is limited to binary classification or how it generalizes to multi-class settings.\n\n[1] How powerful are spectral graph neural networks\n\n[2] Graph neural networks with convolutional ARMA filters\n\n[3] Specformer: Spectral graph neural networks meet transformers\n\n[4] Cayleynets: Graph convolutional neural networks with complex rational spectral filters\n\n[5] Equivariant machine learning on graphs with nonlinear spectral filters\n\n[6] Graph neural networks with learnable and optimal polynomial bases\n\n[7] Rethinking spectral graph neural networks with spatially adaptive filtering\n\n[8] Piecewise constant spectral graph neural network\n\n[9] SLOG: An inductive spectral graph neural network beyond polynomial filter\n\n### Other \n- Several references ([35]–[42]) are cited in the appendix but not listed in the reference section. \n- The legend text in Figure 3 is too small and difficult to read.\n- Algorithm 1 and Algorithm 2 in the appendix both carry the same title \"Fast-HEROFILTER Framework\"", "was_revised": true, "final_justification": "Most of my comments were addressed by the authors. While there were some minor issues that hindered the readability and accessibility, which the authors promised to fix, the empirical results presented during the rebuttal and discussion period show the strength of the proposed method. I have read the comments from other reviewers and agree with the APPNP aspect. Nevertheless, I lean toward accepting the paper given that the authors will revise the paper accordingly.", "rebuttal": "**W1: Motivation and Justification**\n\nWe would like to clarify that our focus on node heterophily (Definition 2) is driven by its direct connection to spectral analysis, capturing variations per frequency and node label distribution for a more precise theoretical framework for GNN performance bounds compared to edge-level metrics.\n\nTheoretically, node heterophily tightens Theorem 1's error bounds by addressing frequency-specific label mismatches through eigenvector projections $\\mathbf{U}^T \\mathbf{y}$, whereas edge heterophily (e.g., average fraction of differing neighbor labels) misses these, potentially overlooking non-monotonic filter requirements (Property 1). \n\nEmpirically, node-level adaptation yields +2-4% accuracy gains over edge-based baselines on heterophilic graphs like Squirrel, as it better aligns filters to diverse patterns `[1,2]`. While edge heterophily could provide insights into local connectivity (e.g., for edge pruning), it lacks the global spectral perspective critical for adaptive filtering—e.g., high edge heterophily may mask mid-frequency node opportunities `[3]`. \n\n[1] Heterophily-Aware Graph Attention Network, Pattern Recognition 2024.\n\n[2] Beyond Homophily in Graph Neural Networks: Current and Future Trends, Neurips 2020.\n\n[3] Beyond Low-frequency Information in Graph Convolutional Networks, AAAI 2021.\n\n\n**W2: It is not clear what is the definition of heterophily degree, is it $\\mathbf{h}$ or $h_i$ or $\\hat{\\mathbf{h}}$ or $\\hat{h}_i$ ?**\n \nWe would like to clarify that $h_i$ is the node heterophily for node $v_i$, and $\\mathbf{h} = (h_0, \\ldots , h_{n−1}) \\in \\mathbb{R}^n$ is the vector containing the heterophily level of each node.\n- We provide the detailed formulation in lines 95-98.\n- Furthermore, $\\hat{\\mathbf{h}}= (\\hat{h}\\_0, \\ldots , \\hat{h}_{n−1})$ heterophily degree vector in the spectral domain, which we propose for conducting our theoretical analysis, where $\\hat{h}_i$ is the $i$-th component. The detailed formulation is given in lines 117-120.\n\n**W3: The proof for Property 1 in Appendix C is hard to follow**\n\nThe proof follows three main steps: (1) applying the weighted AM-GM inequality, (2) using the bound $0 \\leq g(\\lambda_i) \\leq 1$ for scaling, and (3) performing logarithmic operations.\n- The goal is to show when filter response aligns with heterophily for optimal performance—equality holds when the adaptive filter perfectly matches the non-monotonic heterophily pattern across frequencies, providing the insight that GNNs achieve minimal error only with frequency-specific modulation (e.g., mid-freq emphasis in low-heterophily graphs).\n- This interpretation reveals why fixed filters fail: inequality arises from misalignment, loosening bounds in Theorem 1.\n\nWe appreciate this feedback and will extend the proof with more detailed steps in the updated paper. \n\n**W4: The theoretical results are inconsistently presented.**\n\nThank you for the suggestion for formatting.\n\nTheorem 1 in the main text refers to the error bound and is correctly matched in the appendix. The \"Theorem 3\" reference is a typo and will be fixed in revision.\n\nIn addition, we will standardize \"Property\" with proof to \"Proposition,\" add clear labels like \"Theorem 1 (Generalization Error Bound)\" for all theoretical results in the main text with explicit cross-references to their proofs in the appendix to enhance structure and clarity.\n\n**W5: However, the paper does not explain why computing cosine similarity with the label vector is appropriate or effective, particularly in heterophilic graphs.**\n\nWe would like to clarify that computing cosine similarity with the label vector in lines 136–140 (align function) is appropriate because it quantifies filter-label alignment in the spectral domain, directly measuring expressive power under heterophily.\n\nIn heterophilic graphs, where connected nodes often have different labels, filters that only consider neighborhood structure are insufficient.\n- Therefore, the align function effectively quantifies this by captureing how well adaptive filters match label distributions (Property 2), which is particularly crucial in heterophilic graphs where traditional topology fails (e.g., similarity highlights high-freq needs, boosting +3-5% accuracy on Squirrel vs. non-aligned methods). This is insightful for generalization, as misalignment widens errors (Theorem 1).\n\n**W6:** Missing Baselines\n\nDue to time constraints, we have reproduced the results below. Additional baseline results will be included in the revised version.\n|Model|Squirrel (filtered)|Chameleon (filtered)|\n|--|--|--|\n|HeroFilter|**40.14±1.76**|**38.49±2.83**|\n|JacobiConv[1]|36.50±2.50|36.10±2.60|\n|Specformer[3]|36.80±2.10|36.50±1.90|\n|NLSFs[5]|38.50±1.70|37.20±1.80|\n|FavardGNN[6]|37.20±2.00|36.90±2.20|\n|PieCoN[8]|39.10±1.40|38.00±1.50|\n|SLOG[9]|37.00±2.50|37.10±2.60|\n\n**W7: The paper does not specify how the baselines are trained, nor does it report the hyperparameters used for these methods.**\n\nWe would like to clarify that baselines are trained with standard settings (Adam optimizer, 0.01 LR, 200 epochs, early stopping on validation loss; full hyperparameters in Appendix F), tuned via grid search for fairness and for reproducibility.\n\n**W8: It is unclear what inputs LayerNorm and MLP act on and what outputs they produce.**\n\nIn Eq. 10 (Patch-Mixing), LayerNorm normalizes across features (input: n×p×d tensor, output: same), followed by MLP on patch dimension (input: p×d, output: p×d').\n\nEq. 11 (Feature-Mixing) transposes to n×d'×p, LayerNorm across patches (output: same), MLP on features (input: d'×p, output: d''×p). Dimensions: n nodes, p patch size (32), d input features (e.g., 128); outputs aggregated to n×d'' for classification. \n\n**W9: There is no analysis of the trade-off between runtime efficiency and performance.**\n\nWe would like to clarify that all results use Fast-HEROFILTER for scalability (original O(n^3) impractical beyond small graphs), with trade-off analysis showing <0.3% accuracy drop vs. original on medium graphs (e.g., Chameleon: 57.5% original vs. 57.3% fast) but 5-10x runtime speedup (Fig. 4)—persuasively balancing efficiency and performance for large-scale heterophily.\n\n**W10: Interpretation of error bound**\n\nWe would like to clarify that $\\mathbf{X}_0$ and $\\mathbf{X}_1$ represent the filtered node features for nodes belonging to class 0 and class 1, respectively. \n\nSpecifically, if we have $n_0$ nodes in class 0 and $n_1$ nodes in class 1, then $\\mathbf{X}_0 \\in \\mathbb{R}^{n_0 \\times d}$ and $\\mathbf{X}_1 \\in \\mathbb{R}^{n_1 \\times d}$, where $d$ is the feature dimension after filtering `[1]`. Starting with binary settings for theoretical analysis is a common practice in graph theory [1,2,3,4].\n\nFor multi-class generalization, potential extensions includes using one-vs-rest decomposition to apply the binary bound to each class pair. We will add these clarifications and discuss multi-class extensions in the revised version.\n\n[1] When does a spectral graph neural network fail in node classification?. 2022.\n\n[2] Is homophily a necessity for graph neural networks? 2021.\n\n[3] Is heterophily a real nightmare for graph neural networks to do node classification? 2021.\n\n[4] Node-oriented spectral filtering for graph neural networks 2023.\n\n\n\n**Q1: Results on cleaned Chameleon/Squirrel.**  \n\nThank you for bringing this to our attention, we have conducted extra experiments on these two datasets. The results, shown below, reinforce HeroFilter’s strong performance and robustness on these datasets, aligning with our theoretical claims of adaptive spectral filtering for varying heterophily (Property 1 and Theorem 1).\n\n| Model|Squirrel (filtered)|Chameleon (filtered)|\n|--|--|--|\n|Bern-Net|33.85 ± 1.55|32.73 ± 2.10|\n|APPNP|31.30 ± 1.24|37.10 ± 2.99|\n|HeroFilter|**40.14 ± 01.76**|**38.49 ± 2.83**|\n\n\n\n**Q2: $\\mathbf{R}$ in Eq. 9.**  \n\n\nWe would like to clarify that $\\mathbf{R}$ in Equation 9 refers to the $v$th column of spectral relevance matrix introduced in Equation 7 (Section 4.1 of the main paper). \n\n\n**Q3: Fig. 1a connections.**  \nWe would like to clarify that each point in Figure 1a represents an eigenvalue $\\lambda_i$, its associated heterophily degree $h_i$ (from $\\mathbf{h} = \\mathbf{U}^T \\mathbf{y}$, Definition 2), and the filter response $g(\\lambda_i)$ (Eq. 7), illustrating Property 1’s non-monotonic relationship to optimize classification under varying heterophily. \n\n**Q4: Fig. 1b accuracy.**  \n\n\nWe would like to clarify that the accuracy in Figure 1b refers to node classification accuracy (mean test accuracy across 10 runs) on synthetic graphs with controlled heterophily degrees. It shows interpolated performance for different filter types (low-pass, high-pass, and our adaptive HeroFilter) as heterophily varies from 0.1 to 0.9."}, {"review_id": "qAuFnjpRBf", "reviewer": "Reviewer_EZ4C", "summary": "This paper presents a viewpoint on the issue of homophilic or heterophilic graphs. There exists a nonlinear relationship between the degree of graph heterogeneity and high and low-frequency filters rather than a simple linear one. Therefore, a single high or low-frequency filter cannot accomplish the task, and an adaptive filter needs to be introduced. A HERO filter framework is proposed. The first part first constructs a polynomial filter by weighting frequency domain information, establishes a node correlation matrix based on this, and finally sorts the correlation degrees and reconstructs the node neighbors. The second part adopts a dual MLP hybrid structure, obtaining patch dimensions from the reconstructed node neighbors and new feature dimensions, thereby enhancing the model's ability to express complex heterophilic structures. In addition, a fast HERO filtering method is proposed for large-scale graphs. Experiments show that it works well in heterophilic graphs.", "questions": "1.For the second part of the model, could other hybrid methods be improved and compared in experiments to enhance versatility?\n2. Regarding the effectiveness of the two-layer MLP structure, Table 5 only shows the results of two large-scale data sets. Could you provide more ablation experiment results from heterophily datasets?\n3. The first part of the model reconstructed the neighbors. Could you compare the heterophily degree of the graph after reconstruction? This would also support the proposed theory.", "limitations": "No. The paper does not discuss limitations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The proposed approach is novel, linking the heterogeneity of images, spectral filter responses, and propagation errors. Single high-frequency and low-frequency filters, and even some composite filters, are considered from the perspective of heterogeneity or homogeneity, necessitating an adaptive filter to address the issue.\n2. The first part of the model, which re-establishes node relationships based on frequency domain information, is a novel concept that can capture the relationships between heterophily nodes.\nWeaknesses\n1. From the perspective of error bound, only theoretical analysis is provided without proof, which seems somewhat vague.\n2. In the second part, the use of a two-layer MLP structure lacks interpretability, and I do not believe it can effectively address the issue of node feature representation. From the ablation experiments, the results of removing the mixing layer are also not significantly different.\n3. There is a crucial low-level error. There are only 34 references in the main text, but references 35-39 are mentioned in the attachment, and there are no references in the attachment. I am not sure what references 35-39 are.", "was_revised": true, "final_justification": "Most of my concerns are addressed by the authors. However, there are still some issues in this study that require further revision. Thus, I lean toward accepting the paper given that the authors will revise the paper accordingly.", "rebuttal": "**W1: From the perspective of error bound, only theoretical analysis is provided without proof, which seems somewhat vague.**\n\nWe would like to clarify that our error bound (Theorem 1) is fully proven in Appendix C, with detailed derivations connecting heterophily, spectral filtering, and GNN prediction error. We believe our proof provides a rigorous, interpretable framework showing how filter misalignment widens bounds under varying heterophily, motivating adaptive designs for tighter generalization. The experimental results in Table 1 show that HeroFilter's adaptation reduces errors by +2-5%, empirically validating our theoretical insights. \n\n**W2: In the second part, the use of a two-layer MLP structure lacks interpretability, and I do not believe it can effectively address the issue of node feature representation. From the ablation experiments, the results of removing the mixing layer are also not significantly different.**\n\nWe resepctfully disagree with the assessment of HeroFilter Mixer. Our two-layer MLP in the HeroFilter Mixer (Eq. 11) can be viewed as a token and feature aggregator, inspired by the MLP-Mixer architecture [1], which excels at capturing complex patterns through channel and token mixing. In our context, the MLP non-linearly transforms spectral patches to refine node representations under varying heterophily, effectively addressing feature representation by blending low- and high-frequency signals (e.g., for heterophilic nodes, per Property 1). This interpretability stems from its role as a contextual aggregator: the first layer (linear+ReLU) enhances feature interactions within patches, while the second layer projects to a refined space, preserving spectral order critical for heterophily adaptation. \n\n[1] Tolstikhin et al., MLP-Mixer: An All-MLP Architecture for Vision, NeurIPS 2021\n\n\n\n**W3: There are only 34 references in the main text, but references 35-39 are mentioned in the attachment, and there are no references in the attachment. I am not sure what references 35-39 are.**\n\nWe apologize for this formatting problem in the submission—the missing references 35-39 (cited in the appendix but not listed in the main body, due to a compilation error) are as follows, drawn from key spectral GNN works for completeness:  \n\n[35] Hoffman, D. G. (1981). Packing problems and inequalities. In The Mathematical Gardner (pp. 212–225). Springer.\n\n[36] He, M., Wei, Z., Huang, Z., & Xu, H. (2021). BernNet: Learning arbitrary graph spectral filters via Bernstein approximation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems (Vol. 34, pp. 14239–14251). Curran Associates, Inc.\n\n[37] Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., & Yang, B. (2020). Geom-GCN: Geometric graph convolutional networks. In International Conference on Learning Representations.\n\n[38] Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., & Lim, S. N. (2021). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 20887–20902.\n\n[39] Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.\n\n[40] Fout, A., Byrd, J., Shariat, B., & Ben-Hur, A. (2017). Protein interface prediction using graph convolutional networks. Advances in Neural Information Processing Systems, 30.\n\n[41] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., & Leskovec, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33, 22118–22133.\n\n[42] Leskovec, J., & Sosič, R. (2016). SNAP: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1), 1–20.\n\nWe'll correct this in revision by including a full appendix reference list, ensuring seamless integration. \n\n**Q1: Could other hybrid methods be improved and compared in experiments to enhance versatility**\n\nThank you for raising this point about hybrid models. To ensure we provide the most relevant results, could you please clarify what you mean by \"hybrid model\"? \n\nTo the best of our knowledge, if you are referring to using alternative GNNs on the induced graphs generated by our HeroFilter Patcher (replacing the HeroFilter Mixer), we have conducted ablation experiments below. These show that models like GCN and FAGCN can benefit from our patch-induced graphs, particularly on the heterophilic dataset Chameleon, where GCN shows modest gains—but they still underperform compared to our full HeroFilter, underscoring the Mixer's practical effectiveness.\n\n| Model         | Cora            | Chameleon       |\n|---------------|-----------------|-----------------|\n| GCN-Patch     | 74.1 ± 1.0      | 56.0 ± 2.0      |\n| FAGCN-Patch   | 74.8 ± 0.4      | 48.3 ± 2.2      |\n| HeroFilter    | **77.3 ± 0.6**  | **57.3 ± 1.2** |\n\n**Q2: Table 5 is the ablation study on two large datasets (where most of comparison methods are OOM), what about other smaller heterophilic graphs?**  \n\nWe would like to provide new results on smaller/medium heterophilic graphs (Squirrel and Chameleon),  showing component effectiveness on heterophilic graphs: The full model synergizes for +3-4% average gains, with the patcher contributing most to adaptation (as it reconstructs neighborhoods per Property 1), validating generalization on non-large graphs.\n\n| Component|Squirrel (filtered)|Chameleon (filtered)|\n|--|--|--|\n|HeroFilter|**40.14±01.76**|**38.49±2.83**|\n|with Patch Mixer|39.28±1.76|37.75±2.69|\n|with Feature Mixer|39.17±1.73|37.21±3.15|\n|No Mixer|37.69±1.87|36.12±2.46|\n\n\n**Q3. The first part of the model reconstructed the neighbors. Could you compare the heterophily degree of the graph after reconstruction? This would also support the proposed theory.**\n\nWe would like to provide some results on the effect of patches and heterophily degree. Shown from our results, the reconstructed patch has significantly lower heterophily degrees compared to the original graph, with an average reduction of ~0.42 across datasets. This reduction validates Property 1’s non-monotonic spectral response by adaptively selecting spectrally aligned, informative nodes, making neighborhoods more \"homophily-like\" for effective signal propagation, and aligns with Theorem 1’s error bounds by minimizing misalignment under varying heterophily. \n\n| Dataset    | Original Heterophily | After Reconstruction |\n|------------|----------------------|-----------------------|\n| Texas      | 0.81                 |   0.3134                |\n| Wisconsin  | 0.74                 |  0.3323                 |\n| Chameleon  | 0.64                 |   0.3357                |\n| Squirrel   | 0.77                 |   0.3849                |\n\nA higher value means a higher heterophily degree."}]

Author rebuttal:

Meta-review: This work proposes HEROFILTER, a new GNN which addresses the limitations of fixed spectral filters on heterophilic graphs. It works by adaptively extracting and combining representations across the heterophily spectrum, based on the theoretical finding that the relationship between heterophily and filter response is non-monotonic.  

Reviewers assessed this paper generally positively, and several of their opinions improved during the rebuttal period given engagement from the authors.

Main feedback points:

- some concerns about novelty (e.g. key modules like Mixer have been explored in prior studies), and the proposed method is similar to existing attention or diffusion mechanisms (zcnE, BfgS).

- some concerns re: missing missing references to relevant work and positioning around novelty being undermined by insufficient comparisons (zcnE, BfgS).

- confusion around experimental details -- several reviewers pointed out a lack of understanding the purpose of specific functions, inconsistency in theoretical presentation of results, and missing clear tradeoffs between fast and non-fast versions of the model (zcnE, BfgS, EZ4C).
Decision: Accept (poster)