Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: **Summary**
The paper proposed a method ALT to convert any graph neural network to be effective for non-homophily graphs. The key idea is to use two backbone GNNs and an additional MLP to shift (or adapt) the frequency response function of the diffusion filter. The authors also propose a more complicated version of ALT which compute a weight of edges with an additional GNN. The resulting model is optimized with a bi-level optimization method on both the train and valid vertices. ALT shows good empirical performance, especially on non-homophily graphs and on top of the classical GNNs.
strength_and_weaknesses: **Good Empirical Results**
The authors performed a very comprehensive study on a wide range of datasets. The authors also compared against a wide range of baselines. Overall the improvement is quite significant. Also, the authors conducted a detailed ablation study of ALT-local. That highlight the importance of frequency modulator.

**Well Motivated/Explained Architecture Design**
The ALT design is well motivated by the combination of two filters with complementary characteristics. The edge reweighting is well motivated by the need to switch from global filter to local filter. The augmentation GNN is also well motivated by the discriminative argument to use a high pass filter.

**Issue with Experiments**
One complain I have is that the bi-level optimization explicitly use the validation vertices to train the augmentation. This makes the empirical comparison unfair for the baselines. My suggestion would be to split part of the training nodes for training the backbone and augmentation separately.
clarity,_quality,_novelty_and_reproducibility: **Clarity**
Writing is very easy to follow.

**Quality**
Good.

**Novelty**
Good.

**Reproducibility**
Should be reproducible.
summary_of_the_review: Borderline accept, would be stronger if issue with experiments fixed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a general framework ALT to deal with the heterophily problem in GNNs. The main idea is to design multiple GNNs or MLP with different graph filters and it finally merges their predictions regardless of the GNN backbones. A local version is also developed for further improvement. 
strength_and_weaknesses: # Strength:

1. The paper is well-written and easy to follow.

2. The proposed idea can be used as a general framework to potentially improve any GNN models.

3. The motivation of ALT-Global is clear and valid.

# Weakness:

1. The novelty of the proposed idea is limited. The idea of combining graph signals from different graph filters is implicitly encoded in polynomial filters of graph signals, and this is a well-studied problem in the literature. For instance, in the analysis of ALT-Global (Section 3.2), the paper assumes the GA-MLP architecture: $H=C~MLP(X)$ and all three MLPs share the same parameters. Then the proposed ALT essentially reduces to a specific case of GPRGNN [1] whose polynomial filter is even more flexible and adaptive. 

2. The proposed framework might be able to improve some classic GNN backbones (such as GCN, SGC, and APPNP) that intrinsically adopt low-pass filters and therefore can not handle heterophilic data. However, it is unclear how the proposed idea improves stronger approaches such as GPRGNN [1] and other approaches with high-frequency filters. 

3. In the ablation study (Table 3), even for GCN, the ALT-Glocal variant only improves the performance very marginally. I suspect that ALT-Global can not improve the performance of GPRGNN, APPNP, or GCNII. The paper only presents the ablation study on GCN, but more results are needed to clarify this concern.

4. The local adaptive method proposed in Section 3.4 is heuristic and ad-hoc. The training procedure in Section 3.5 seems to be computationally expensive but there is no discussion on the running time and training cost. 

5. There is a lack of comparison with other local adaptive approaches which also adaptively adjust the edge weight as in ALT-Local. For instance, graph attention networks [2] adjust the weight by attention scores; ElasticGNN [3] models the locally adaptive smoothness over the graph by graph trend filtering; DAGNN [4] adjusts the feature combination from different propagation layers by attention scores; More discussion and comparison will be helpful to justify the advantages of the proposed idea. Overall, it will be beneficial to show how the proposed idea improves state-of-art algorithms instead of old algorithms.

[1] Adaptive Universal Generalized PageRank Graph Neural Network, ICLR 2021

[2] Graph Attention Networks, ICLR 2018

[3] Elastic Graph Neural Networks, ICML 2021

[4] Towards Deeper Graph Neural Networks, KDD 2020



clarity,_quality,_novelty_and_reproducibility: The paper is clearly written but the novelty is limited.
summary_of_the_review: The paper proposes a general framework ALT to deal with the heterophily problem in GNNs. The main idea is to design multiple GNNs or MLP with different graph filters and it finally merges their predictions regardless of the GNN backbones. The novelty is limited compared with existing approaches, and it is unclear how it advances the state-of-art algorithms. Moreover, a local version is developed for further improvement but the proposed method is quite heuristic without clear justification and running time analysis.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors ALT to handle graphs with either low or high homophily by decomposing a given graph into two components, extracting complementary graph signals from these two components, and adaptively merge the graph signals for node classification. 
strength_and_weaknesses: ## Strength
The frequency analysis is somehow interesting.

## Weaknesses
1. The writing needs to be improved.
2. The idea is not novel.


## Questions and Comments

1. “our core idea is to adaptively combine signals from two filters with the complementary filter characteristics. For example, if a low-pass filter GNN is given, it should be adaptively combined with another high-pass filter.” Combining low-pass filter and high-pass filter adaptively is exactly the same as [3] and as the author mentioned, “equip GNNs with an adaptive filter” is not a new idea.

2. The authors show that “The filter characteristic of the proposed ALT-global (Eq. 1d) is adaptive…”. How does the learned filter compared with GPRGNN and BernNet?

3. “applies a global filter to every node, which could lead to suboptimal performance.” Any evidence to this claim?

4. The ALT-LOCAL is very similar to FB-GAT, which combines low-pass filter, high-pass filter and learnable edge weights adaptively.

5. It is invalid to use validation label in the training process.

5. Some recent works find some empirical and theoretical  evidence that heterophily is not always harmful and homophily is not always necessary for GNNs [1,2,3]. How.does this work align with the previous works.

6. Some missing comparison, e.g. LINKX [4], BernNet [5], ACM-GCN [3] and GloGNN[6].

[1] Zhu J, Yan Y, Zhao L, et al. Beyond homophily in graph neural networks: Current limitations and effective designs[J]. Advances in Neural Information Processing Systems, 2020, 33: 7793-7804.

[2] Ma Y, Liu X, Shah N, et al. Is homophily a necessity for graph neural networks?[J]. arXiv preprint arXiv:2106.06134, 2021.

[3] Luan S, Hua C, Lu Q, et al. Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?[J]. arXiv preprint arXiv:2109.05641, 2021.

[4] Lim D, Hohne F, Li X, et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods[J]. Advances in Neural Information Processing Systems, 2021, 34: 20887-20902

[5]  He M, Wei Z, Xu H. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation[J]. Advances in Neural Information Processing Systems, 2021, 34: 14239-14251.

[6] Li X, Zhu R, Cheng Y, et al. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily[J]. arXiv preprint arXiv:2205.07308, 2022.

[7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank
graph neural network. In International Conference on Learning Representations, 2021.

[8] Luan S, Zhao M, Hua C, et al. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks[J]. arXiv preprint arXiv:2008.08844, 2020.


clarity,_quality,_novelty_and_reproducibility: Clarity: medium
Quality: medium
Novelty: low
Reproducibility: NA
summary_of_the_review: Although some theoretical analysis is interesting, this paper lacks novelty and strong experimental support. Thus, I don't think it is ready to be published.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Main concern. How to accommodate GNNs to deal naturally with heterophily and provide a theoretical analysis (from signal processing perspective). The core idea is to transform/combine low-pass filter into/with high-pass, for instance. There are two learnable parameters: w and \eta whose values lead to low-pass or high-pass filters (adaptive filters): 

The above conditions are sufficient and in fact, there are many other combinations of w and η that can produce low-pass/high-pass filters 
As stated in the proof of Lemma 1. I found this idea very interesting, in particular the distinction between GLOBAL and LOCAL filtering. In particular, the insight of how GLOBAL filtering degrades the performance in a heterophilic scenario is useful. 

Related work is analyzed and the contribution evolves from FAGCN which explicitly mixes high-frequency and low-frequency signals. ALT generalizes this idea to the ‘mixture of complementary filters’; thus, even though the backbone GNN’s convolution kernel is unknown 

Results are very challenging since for heterophilic graphs, the proposed approach ALT increases the performance and for homophilic case, it preserves it or even improves it. The ablation study is very useful to understand the contribution of the local filter. 

Notes. Please, clarify that the frequency profile is basically the function phi applied on the spectrum (e.g phi = exp() when we apply a heat kernel) under the spectral theorem: phi(A) = U*phi(lambda)*U^T.


strength_and_weaknesses: * Strengths: results are very challenging and 
* Weaknesses: the underlying theory could be clarified more clearly for the nonexperts in spectral graph theory.
clarity,_quality,_novelty_and_reproducibility: * Clarity in the spectral stuff could be improved but in general it is well written. 
* Novelty. Seems that is not incremental wrt FAGCN but I am open to discuss it. 
* No code released yet but experimental protocol specified. 
summary_of_the_review: The paper provides nice results regarding how to minimally modify existing GNNs to deal with heterophilic graphs. The theory could be better explained but the paper is in general readable and direct.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a method, ALT, that allows any GNN model to be used as a component within a heterophily-aware approach. The approach combines signals in a learnable way from two complementary filters, in order to obtain an adaptive filter; they further develop a locally adaptive approach utilizing a structure-learning based augmenter. 

In general, reviewers find the paper well-written and well-motivated. However, they raise a number of key issues:

- Novelty and discussion of related work: reviewers noted that the novelty is relatively limited considering that there are a number of existing approaches also based on combining graph signals. The related work mentions a number of such methods (e.g. ACM-GNN, FAGCN, GBK), but is quite brief, making it hard to understand the relationships between the current work and these (other than FAGCN in section 3.4). In addition, while the paper notes that only one structure learning solution for heterophily exists (WRGAT), it still leaves the question of how the proposed structure learning approach compares to this and other structure learning approaches.

- Efficiency: the paper does not compare its efficiency with existing approaches; while understandable in that efficiency is not the main contribution and focus of this paper (as the authors state in the rebuttal), I find that since the goal of the paper is to be combined with a broad range of existing GNNs, efficiency still a factor in whether this can practically be done, particularly if there are large differences in efficiency. Particularly, the structure learning / bilevel optimization inclusions are relatively large modifications whose influence on computational cost could (potentially) be larger.

- A few other issues were raised that were satisfactorily addressed by the authors during the rebuttal, particularly the use of validation set data in the bilevel optimization process, and baselines such as ACMII-GCN and LINKX. I thank the authors for their efforts in addressing the concerns and improving the paper.

In the end, reviewers and AC agree that while the work is promising, due to the first two issues, the work is not yet ready for publication at ICLR. The reviews offer a number of helpful suggestions for improvement, so I encourage the authors to continue improving the paper based on the reviews for future submissions.
justification_for_why_not_higher_score: The main consideration was the issue of novelty and discussion of related work, but the lack of efficiency results was also a significant consideration, as discussed in my review.
Decision: Reject