Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work, by redefining GCN’s depth d as a trainable parameter continuously adjustable within positive infinity and negative infinity, a simple and powerful GCN model RED-GCN is proposed to retain the simplicity of GCN and meanwhile automatically search for the optimal d without the prior knowledge regarding whether the input graph is homophilic or heterophilic.
strength_and_weaknesses: Strength: The problem is interesting and usefull for GCN designing.
Weaknesses: The motivation and the physical meaning of the negative depth value are not clear. When the depth of GCN is negative, what dose it mean?
clarity,_quality,_novelty_and_reproducibility: The problem is interesting and the proposed method is novel. But the physical meaning of negative results is not clear.
summary_of_the_review: The problem is interesting and the proposed method is novel. But the physical meaning of negative results is not clear.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel graph convolutional network to address the over-smoothing and heterophily issue. The proposed model is equipped with a trainable depth parameter $d$ and a selection of the spectrum of the graph signal. Based on such modeling, this paper discovers a connection between negative GCN depth and graph heterophily. The experimental results on 11 graph datasets show the proposed model outperforms baseline methods.
strength_and_weaknesses: Strengths,

S1: This paper models the depth of GCN as a trainable parameter by eigen decomposition.

S2: Experiments validate the effectiveness of the trainable depth, especially negative depth for disassortative graphs.

Weaknesses,

W1: Adaptive and continuous depth is not new for GCN, e.g., in Graph Neural Diffusion (GRAND).

W2: Negative depth may not be a correct choice, which loses most of the topology information.

W3: This paper does not analyze the expressive power of the proposed model. 


clarity,_quality,_novelty_and_reproducibility: This paper is well-written and well-organized. It is easy to follow the proposed ideas and technological details.
The novelty of this paper is incremental because spectrum decomposition is not new for graph analysis.  
Although the proposed model achieved better performance than baselines in experiments, it is not clear what and how new information/patterns are captured by the model.
summary_of_the_review: I recommend a weak reject for this paper because of its limited novelty and the lack of analysis of expressive power.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors define GCN’s depth as a trainable continuous parameter within (−∞,+∞) and propose RED-GCN which can automatically search for the optimal depth without the prior knowledge regarding whether the input graph is homophilic or heterophilic.
strength_and_weaknesses: ## Strength
The idea of setting the depth as trainable continuous value and the concept of eigengraph are interesting.

## Weaknesses
1. The writing needs to be improved.
2. Some experiments and comparisons are missing.


## Questions and Comments

1. “Apparently, high frequency eigenvectors and their corresponding eigengraphs have advantage on capturing graph heterophily” This is not apparent, need more explanation.

2. “High frequency eigengraphs should accordingly take larger.  weights when modeling heterophilic graphs, while low frequency ones should carry larger weights when dealing with homophilic graphs.” This is similar as [5]. 

3. Equation (7) is actually lazy random walk affinity matrix and see [5] for the generalized lazy random walk matrix.

4. Red-GCN is essentially a linear model without any non-linearity?

5. The reported results of FAGCN, GPRGNN and H2GCN in table 2 are not the same as the results in the original papers and not consistent with my personal experience.

6. Some missing comparisons, e.g. ACM-GCN [1], LINKX [2], BernNet [3] and GloGNN [4].

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

[2] 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

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

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

[5] 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: quality: medium
clarity: mediem
originality of the work: medium
Reproducibility: NA
summary_of_the_review: This is a borderline paper and if the authors can address my concerns satisfactorily, I will consider raise my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of investigating the depth of GNN. The authors propose a novel and interesting method to extend the depth of GNNs from a positive integer to a real value. It is claimed that negative depth enables high-pass frequency filtering functionality for graph heterophily while positive value enables low-pass filter and is to model homophily. Experimental studies have been conducted on both homophilous and heterophilous graphs and the results show that the proposed method can achieve comparable or better performance in both types of graphs compared to baselines.
strength_and_weaknesses: Strength:
- Both problems of GNN depth and adaptive GNN for modeling homophily and heterophily are interesting and important. 
- The proposed method to extend positive integer depth to real value is novel.
- The experimental results of the method demonstrate the effectiveness of the proposed method compared to previous baselines.

Weakness:
- The claims are based on empirical results and theoretical analysis is not provided.
- Experimental results demonstrate the effectiveness of the proposed method, it is also important to show the efficiency of the method, e..g, presenting the complexity or comparing running time.
- More insights can be provided to better show the correlations between homophily/heterophily and positive/negative depth, for example, analyzing the learn representations rather than just reporting the overall classification accuracy in the downstream task.
- The size of the benchmark dataset is relatively small to show the ability of generalization. I suggest conducting experiments on larger datasets such as OGB.
- In the experimental studies, some representative methods can be compared including (1) GAT, as an attention method, and (2) some recent work on adaptive GNN for modeling homophily and heterophily, for instance, GBK-GNN [1].


[1] GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily
clarity,_quality,_novelty_and_reproducibility: Clarity: overall the paper is well-organized but some parts are hard to follow, e.g., how to learn the depth d is not introduced very clearly.

Quality: the work is of average quality.

Novelty: The proposed method to extend the depth of GNNs from the positive integers to real values is novel.

Reproducibility: it should be possible to implement the method and reproduce the results from the description given in the paper.
summary_of_the_review: This paper studies an interesting and important problem. Overall this paper is well-organized. Experiments from different aspects have been conducted. Although experimental studies can be further improved by providing more insight into investigations and comparing the proposed method to more representative methods, the method is novel from the methodological perspective and effective from the experimental perspective. Thus, I will recommend a weak acceptance of the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: __Summary.__ The authors generalize the depth of the GCN to a continuous (real) value d, which is trainable and adjustable. To justify this approach, the authors show through an eigen decomposition of the symmetrically normalized graph Laplacian, a correlation between graph homophily/heterophily and the eigenvector frequencies. This analysis allows them to introduce the notion of eigengraph – a weighted graph with potentially negative edges: the normalized adjacency matrix can in fact be written as a linear combination of such eigengraphs, where the coefficients determine the ability of GCN to capture homophilic/heterophilic signals. This eigengraph analysis of the convolution leads the authors to consider its extension to arbitrary depths. The authors then show through a set of experiments that heterophilic graphs are usually associated with low (or even negative) diffusion depths.

__Summary of the reviews.__  Overall, the reviewers’ feedback for this submission was tepid at best. The contribution does not seem extremely novel (continuous depth was already introduced by GRAND, but the possible negativity of the depth is new to this submission). One of the issues brought forward by the reviewers was the difficulty in scaling up these methods, solved to some extent in the paper by arbitrarily selected the K lowest and K highest eigenvalues. The authors’ experiments lack in showing the applicability of their method to large scale graphs. The main issue with the evaluation of the method is that it is performed on real life graphs, which are necessarily noisy and imperfect. To really verify their claims, the reviewers would have preferred the authors to evaluate their methods on synthetic datasets (eg Stochastic Block Models), where the degree of homophily and heterophily can be controlled much more accurately. __For this reason, we recommend a rejection.__
justification_for_why_not_higher_score: The reviewers suggested during the meeting that this paper could benefit in using synthetic experiments to substantiate their claims.
Decision: Reject