HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations

W1: From the perspective of error bound, only theoretical analysis is provided without proof, which seems somewhat vague.

We 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.

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.

We 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.

[1] Tolstikhin et al., MLP-Mixer: An All-MLP Architecture for Vision, NeurIPS 2021

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.

We 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:

[35] Hoffman, D. G. (1981). Packing problems and inequalities. In The Mathematical Gardner (pp. 212–225). Springer.

[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.

[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.

[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.

[39] Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.

[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.

[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.

[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.

We'll correct this in revision by including a full appendix reference list, ensuring seamless integration.

Q1: Could other hybrid methods be improved and compared in experiments to enhance versatility

Thank 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"?

To 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.

Q2: Table 5 is the ablation study on two large datasets (where most of comparison methods are OOM), what about other smaller heterophilic graphs?

We 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.

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.

We 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.

A higher value means a higher heterophily degree.

W1: Motivation and Justification

We 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.

Theoretically, 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).

Empirically, 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].

[1] Heterophily-Aware Graph Attention Network, Pattern Recognition 2024.

[2] Beyond Homophily in Graph Neural Networks: Current and Future Trends, Neurips 2020.

[3] Beyond Low-frequency Information in Graph Convolutional Networks, AAAI 2021.

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$ ?

We 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.

• We provide the detailed formulation in lines 95-98.
• 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.

W3: The proof for Property 1 in Appendix C is hard to follow

The 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.

• 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).
• This interpretation reveals why fixed filters fail: inequality arises from misalignment, loosening bounds in Theorem 1.

We appreciate this feedback and will extend the proof with more detailed steps in the updated paper.

W4: The theoretical results are inconsistently presented.

Thank you for the suggestion for formatting.

Theorem 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.

In 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.

W5: However, the paper does not explain why computing cosine similarity with the label vector is appropriate or effective, particularly in heterophilic graphs.

We 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.

In heterophilic graphs, where connected nodes often have different labels, filters that only consider neighborhood structure are insufficient.

• 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).

W6: Missing Baselines

Due to time constraints, we have reproduced the results below. Additional baseline results will be included in the revised version.

W7: The paper does not specify how the baselines are trained, nor does it report the hyperparameters used for these methods.

We 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.

W8: It is unclear what inputs LayerNorm and MLP act on and what outputs they produce.

In 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').

Eq. 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.

W9: There is no analysis of the trade-off between runtime efficiency and performance.

We 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.

W10: Interpretation of error bound

We 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.

Specifically, 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].

For 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.

[1] When does a spectral graph neural network fail in node classification?. 2022.

[2] Is homophily a necessity for graph neural networks? 2021.

[3] Is heterophily a real nightmare for graph neural networks to do node classification? 2021.

[4] Node-oriented spectral filtering for graph neural networks 2023.

Q1: Results on cleaned Chameleon/Squirrel.

Thank 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).

Q2: $\mathbf{R}$ in Eq. 9.

We 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).

Q3: Fig. 1a connections.
We 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.

Q4: Fig. 1b accuracy.

We 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.

I would like to thank the authors for their rebuttal. I have read the response and the comments from other reviewers. Some of my concerns were addressed, for instance, those regarding the motivation behind node heterophily and the empirical support on filtered datasets. However, I still find a gap between the authors’ intentions and what is currently presented in the paper, as well as what they plan to revise. For example, I asked for a definition of the heterophily degree, which plays a central role in the paper. The authors referred to lines 117–120 for the detailed formulation, but those lines define only the spectral heterophily vector. It became clear only after the rebuttal that the term heterophily degree actually refers to a heterophily degree "vector". It remains unclear how the authors plan to revise the paper to reflect this clarification. Similarly, in response to my question about the hyperparameters used for the baselines, the authors stated that standard settings were used (Adam optimizer, learning rate of 0.01, 200 epochs, early stopping on validation loss) and that full hyperparameter details are provided in Appendix F. However, Appendix F does not include the full hyperparameter settings for the competing methods, it is "Scalability and Parameter Sensitivity Analysis". I am not sure whether and where the authors intend to address this point in the revision. Additionally, I believe the paper would benefit from a more detailed discussion of the trade-off between runtime efficiency and performance, and a clear section for the used notation. Also, my comments on the other section were not addressed, including 1) Several references ([35]–[42]) are cited in the appendix but not listed in the reference section, 2) The legend text in Figure 3 is too small and difficult to read. 3) Algorithm 1 and Algorithm 2 in the appendix both carry the same title "Fast-HEROFILTER Framework”, and the difference between the two should be highlighted. While these are detailed issues, they impact the clarity and accessibility of the paper.

Q5: Several references ([35]–[42]) are cited in the appendix but not listed in the reference section.

A5: We apologize for this formatting problem in the submission. The missing references 35-42 (cited in the appendix but not listed due to a compilation error) are as follows:

[35] Hoffman, D. G. (1981). Packing problems and inequalities. In The Mathematical Gardner (pp. 212–225). Springer.

[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.

[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.

[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.

[39] Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.

[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.

[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.

[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.

We'll correct this in revision by including a full appendix reference list, ensuring seamless integration.

Q6: The legend text in Figure 3 is too small and difficult to read.

A6: Thank you for pointing this out. We will increase the font size in the revised version. Currently, Figure 3 in the appendix shows 12 plots arranged as 4 per row. We will reorganize this to 3 plots per row to provide more space for larger, more readable legends.

Q7: Algorithm 1 and Algorithm 2 in the appendix both carry the same title "Fast-HEROFILTER Framework”, and the difference between the two should be highlighted.

A7: Thank you for pointing this out. We will revise the titles in the appendix to clearly distinguish between the two: Algorithm 1 will be retitled "HeroFilter Framework" (standard version), and Algorithm 2 will remain "Fast-HeroFilter Framework" (efficient variant). To further emphasize the difference, we will add a brief explanatory note or inline description underscoring that the key subtlety lies in the computation of the spectral relevance score. Specifically, Algorithm 2 employs optimized approximations for faster processing while maintaining comparable accuracy.

Again, we sincerely thank reviewer BfgS for your detailed comments. Your valuable feedback has helped us produce a better, clearer, and more accessible manuscript.

W1: Novelty.

We respectfully but firmly assert that HeroFilter's novelty is not undermined by commonalities with attention or diffusion methods.

In 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.

Next, we will extend this from four aspects:

• 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.

• 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.

• 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).

• 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.

W2: Relevant works

We 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.

• 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).
• 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.
• Comparing with [3]: Offers static diverse filters (RQ2); our MLP-Mixer enables node-specific dynamism, +3-7% over similar baselines (Table 1).
• 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).
• 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.

While [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.

W3: Fast version performance

Our 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.

Q1: Unclear why let $g(\mathbf{\Lambda})$ align with label vector $Y$. The 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.

Q2: Are Squirrel/Chameleon de-duplicated?

Thank 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).

Q3: Ablation on small heterophilic graphs.
To 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.

W1: Heuristic design and disconnect between theory and solutions.

We respectfully but firmly assert that our design is not heuristic.

In general, HeroFilter is a direct, rigorous operationalization of our theoretical insights, creating a seamless connection that advances beyond the limitations of prior works.

Next, we will extend this from four aspects:

• 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.

• 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.

• 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.

• 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.

  • Furthermore, our framework unifies theory for heterophily focus, algorithms for adaptive efficiency, and empirics for validated performance demonstrated by consistent SOTA results.

W2: Prior studies ([1] Node-oriented spectral filtering [2] How powerful are spectral GNNs; [3] GNNs with diverse spectral filtering).

We understand your consideration, and we will cite and discuss these papers in our updated version as follows.

To 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.

• [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.

• [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].

• [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.

W3: Related Work [1]

Thanks for providing a related work. We analyze the difference and promise to add it to our updated paper:

• [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.

• 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.

[1] A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023

W4: Unclear details

We 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.

W5: Fast-HeroFilter follows APPNP

We respectfully disagree that Fast-HeroFilter merely follows APPNP from two aspects.

• 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);

• 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.

Q1: Significance of $\mathbf{R}$

We 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.

To 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).

• It filters neighbors based on frequency-specific relevance—e.g., emphasizing high-freq for heterophilic nodes—reducing errors per Theorem 1.
• Further: In heterophily=0.9 graphs (Fig. 1), $\mathbf{R}$ prioritizes dissimilar but informative nodes, explaining our SOTA on Squirrel (+6.8% over baselines).

Q2: Top-k operation and gradient backpropagation.

We 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:

• 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).
• 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.

Q3: Extra results and qualitative analysis

Our results show HeroFilter outperforms both [1] and [2] on heterophilic and large-scale datasets

To 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.

Q4: Explanation for adding two-layer MLP

We 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].

[1] A Fair Comparison of Graph Neural Networks for Graph Classification. ICLR 2020 [2] Benchmarking Graph Neural Networks. JMLR 2023

To 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:

Dear Reviewer Yps2,

Thanks 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.

Best,

Authors