Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes Adaptive Simple Graph Convolution (ASGC), which can adapt to both homophilous and heterophilous graph structures. ASGC represents an extension of SGC to graph with heterophily, which is a novel and timely contribution.
strengths_and_weaknesses: Strengths:
- The contribution is novel. Most existing methods for simplifying Graph Neural Networks make the homophily assumption. This paper extends the use case of this line of work to heterophilous graphs, which have wide applications in cases like networks based on adjacencies of words in text
- The paper provides nice theoretical guarantees on the capability of proposed ASGC at denoising FSBM networks.

Weakness:
- More explorations regarding the potential of ASGC are needed. Based on the experimental results in Figure 3, ASGC actually performs worse than the standard SGC in a few datasets. I hope the authors can provide more justifications and analyses on why this is the case.
- I hope the paper can somehow unify the idea of ASGC and SGC, such that a model can automatically decide and apply the best feature propagation scheme based on the task of interest. I.e., the model tends to be more ASGC alike when the input graph is more heterophilous, and the model is more SGC alike when the input graph is more homophilous. This improvement to the model should make it much easier to use, as a user no longer has to decide between ASGC and SGC.
questions: Suggestions:
- Typos on Figure 3. Should be ASGC, not AGC. 

Questions:
- Could ASGC extend to graph classification tasks?
limitations: Yes.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper presents an adaptive simple graph convolution method (ASGC) for learning over heterophilous graphs. ASGC is proposed as an extension of the previously proposed simple graph convolution (SGC) to better handle graph heterophily. The authors provide a theoretical analysis of synthetic datasets to demonstrate the ineffectiveness of SGC on heterophilous graphs. Empirical comparisons with several state-of-the-art methods show some promising results of ASGC as compared with deep learning models. 
strengths_and_weaknesses: Strengths:
1. This paper is well written and easy to follow. 
2. The theoretical analysis based on stochastic block models show the limitations of SGC and the improvements of ASGC over SGC.

Weakness:
1. Technical contributions of this paper are somehow limited. In essence, I think the proposed method uses a similar "adaptive" idea as  Generalized PageRank GNN (GPR-GNN) -- which achieves adaptive smoothing over edges via learnable coefficients, thus better generalising to heterophilous graphs. It is unclear to me what advantages ASGC offers over GPR-GNN, apart from being a non deep learning model. Empirical results also show that ASGC is less effective than GPR-GNN on 3 out of 5 heterophilous graphs. 

2. The authors claim that "our work is the first to show that heterophily can be handled using just feature pre-processing". I think this is overclaimed because the authors are mainly concerned about node classification on graphs. In a general sense, how to effectively handle heterophily is indeed dependent on the learning task to be addressed. 

3. The experimental evaluation is weak. First, heterophilous graphs used in the experiments are quite small. Adding more and larger datasets would make the evaluation stronger. Second, empirically, ASGC is claimed to be competitive with recent deep learning models on heterophilous graphs. However, its performance is found to be inferior to GPR-GNN on more than half of heterophilous graphs. Third, the authors have not provided comparisons with several recent works for handling graph heterophily.



questions: 1. What is the key difference between the proposed ASGC method and Generalized PageRank GNN (GPR-GNN), except for the loss function? Why ASGC works better than GPR-GNN on some datasets, but worse on some other datasets?

2. The authors claim that they are the first to handle graph heterophily using feature pre-processing. What is the significance of pre-processing features to handle heterophily without considering any particular learning tasks? Please give more explanations.

3 Please give more explanations for the theoretical analysis provided. For example, what is the connection between the learned coefficients \beta and homophily ratio of graphs?


limitations: I think the authors have adequately addressed the limitations of their proposed method.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper introduces Adaptive SGC as an improvement of SGC to better handle heterophilous graphs. The major idea is to learn a polynomial of normalized adjacency matrix by solving a least square problem. The proposed idea is simple and scalable. Theoretical analyses under very ideal assumptions are provided. The empirical performance is competitive with recent baselines. 
strengths_and_weaknesses: Strengths:

1. The paper introduces a simple and scalable approach for graph learning in both homophilous and heterophilous settings. 

2. The paper is clearly written and easy to follow. 

3. Motivation examples and theoretical analyses are provided to justify the proposed idea. 

4. Empirical evidence supports the effectiveness of the proposed algorithm.

Weakness:

1. Despite the motivation example and theoretical analyses, the intuition and motivation of the proposed filter learning via lease square approximation are still unclear. There is a lack of discussion about the insight of projecting the feature onto the column space of the Krylov matrix.

2. The motivation example and theoretical analyses are provided under ideal assumptions. For instance, the adjacent matrix is the expected adjacent matrix that precisely reflects the membership information of each node. It is unclear how the sampled setting impacts the current theoretical results.

3. The theoretical analysis removes the raw feature in the least square approximation. But the impact of raw feature and coefficient regularization are never studied in the experiments. 

4. It is unclear why ASGC would achieve similar performance as using the raw feature. A shallow discussion is provided in Section 3 but it is not sufficient. A further discussion about when and why the proposed method fails will also be helpful to understand its limitation.

5. The performance improvements over recent baselines are not stable and are sometimes worse.
questions: Please respond to the comments mentioned in the weakness.

In addition to that, could you please compare the advantages and disadvantages of the proposed filter learning and existing filter learning such as ChebNet and GPR-GNN in terms of accuracy regardless of efficiency？
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper study the extension of SGC for heterophily settings. More specifically, it is known that SGC work for the homophilous setting where nodes that have similar labels are connected by an edge, however, SGC performs poorly on heterophily graph where nodes with different labels are connected by an edge.
The authors consider an multi-hop SGC as $\mathbf{H} = \sum_{i=0}^K \beta_i \mathbf{S}^i \mathbf{X},~\mathbf{S}=\mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$.
To overcome the performance degradation issue for applying SGC on heterophily graphs, the authors propose an adaptive SGC method that learns the combination coefficient $\beta_i$ (as shown in Eq. 4).
strengths_and_weaknesses: **Originality**

Both the method and the analysis in this paper sound novel and interesting to me.

**Quality + Significance**

I have doubts about the correctness of the adaptive SGC method in Eq. 4. Please refer to the Question section.

If I misunderstood the method in Eq. 4 and the author could correct me, then the contribution is significant. Otherwise, the authors might need to double-check their experiment results because according to my understanding, Eq. 4 should lead to a degenerated solution ...

 
**Clarity**  

The paper is easy to follow and the intuition is quite clear.
questions: **Won't Eq. 4 with regularization lead to a degenerated solution?**

For example, I can write the Eq. 4 as
$$
\min_{\boldsymbol{\beta}} f(\boldsymbol{\beta}) = \sum_{i=1}^K \\| \beta_i (\mathbf{S}^i \mathbf{x} - \mathbf{x})\\|_2^2 + \mathbf{I}\\{i=0\\} R^2 \beta_0^2,
$$ 
where $S^0 = \mathbf{I}_N$ by using the authors' notation. 
Taking gradient to each $\beta_i, i\in \{ 0,\ldots, K\}$ and set to zero, we have
$$
\frac{\partial f(\boldsymbol{\beta})}{\partial \beta_i} = 2\beta_i (\mathbf{S}^i \mathbf{x} - \mathbf{x}) (\mathbf{S}^i \mathbf{x} - \mathbf{x}) + \mathbf{I}\\{i=0\\} 2R^2 \beta_0 = 0
$$

Then, the closed form solution still has $\beta_0 \neq 0$ but $\beta_i = 0, i=1,\ldots,K$, which is the degenerated solution ...
in other words, the optimal $\boldsymbol{\beta}$ gives us linear NN.
limitations: No
review_title: null

Meta-review: metareview: This paper proposes a new feature smoothing graph learning algorithm handling heterophilous graphs. The proposed idea is an adaptive node feature smoothing technique which essentially uses a regularized least square to find a weighted sum of the Krylov matrix columns (smoothed features at different orders) as an approximation of the original features. Careful theoretical and empirical analyses are carried out on a stochastic block model with 2 communities. These analyses, although in a rather restrictive setting, provide valuable insights.

Most reviewers appreciated the novelty of the idea and appreciated the theoretical and empirical insights on the 2-cluster SBM setting. The benefit over previous method (SGC) on heterophilous graphs are well established. These feature-smoothing methods are generally interesting and important; they can better reveal the mechanism of graph learning and potentially improve efficiency and representation learning. Using non-deep Most technical concerns (formulation, evaluation, baselines, datasets) are addressed and clarified during rebuttal and discussion period. The theoretical results, although restricted to a relatively limited setting, provide a good intuition of how the idea works and help build good heuristics in real world setting. This is valuable and will benefit NeurIPS audience. 

confidence: Certain
Decision: Accept