Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focused on improving graph neural networks from homophily and over-smoothing issues by introducing a diverse message passing (DMP) framework. Experiments on 9 public datasets with a variety of homophily scores were provided to validate the effectiveness of the proposed method. 
main_review: Pros:
-	Following previous works [8], the motivation of this work is clearly presented.  How the proposed method connects to existing GNN methods has been elaborated in both spatial and spectral domains. 
-	While the proposed implementation is simple and straightforward, some theoretical analyses (Theorem 4 and 5, though with some key typos) have been provided to demonstrate the benefits of DMP over the uniform message passing. 
-	Extensive experimental results have been provided in terms of different homophily graphs and model components. Plus, experiments on heterogenous graphs and deep GNNs have also been conducted. 

Cons:
-	The technical contribution of this work is limited since the proposed method mainly follows the framework provided in [8] and adopts a similar implementation way to compute “attentions” over attributes as in [18,22,23]. 
-	Some claims are over-emphasized as the proposed method is clearly built on top of several theoretical frameworks [6-8, 28]. To name a few, “existing spectral GNNs are just equivalent to a degeneration of diverse message passing”, “diverse message passing may break the ceiling of spectral GNNs”, etc.
-	The proposed method might be ad hoc to the datasets with low homophily rates. 
limitations_and_societal_impact: Suffice.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a diverse message passing framework (DMP) to generalize a classic uniform message passing framework and also suggests strategies preventing over-smoothing issues.
main_review: ================================================================= 

[Main Strengths] 

This paper's main strength is that the motivations of the work are well described (as shown in SEction 3.1) and evaluations across various homophily rate datasets (see Table1) are well designed. 

================================================================= 

[Main Weaknesses] 

The paper's main weakness is the somewhat limited merits of the theoretical analysis shown in Section 3.4. In particular, the potential benefits of the contribution of Theorem 5 toward preventing an over-smoothing issue are not clear to me.

================================================================= 
limitations_and_societal_impact: The authors did not provide the “limitations and social impact” of this work in the paper.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors extend network homophily rate to attribute homophily rate by taking attribute as weak label and design diverse message passing (DMP) framework to specifiy each attribute propagation weight along each edge. The authors show that DMP can prevent  over-smoothing and handle network with heterophily.

main_review: Strength:

1. Although DMP looks like a simple extension of GAT, I think to form uniform and diverse message passing into an optimization problem is interesting.
2. The visualization looks good.

Weakness&Advice:

1. Line 74, “ddimensions” —> “dimensions”

2. In equation (3), is it possible to get a zero denominator? Do you assume all elements $x_{vf}$ are positive?

3. In equation (4)(6), DMP looks like a channel-wise GAT with attention values in (-1,1). The contribution and novelty in section 3.2 are limited.

4. In theorem 5, should add $f=1.\dots, F$

5. Line 213-216, “different form Uniform Message Passing, which directly generates a F-components partition, Diverse Message Passing generates F groups 2-components partitions as candidates and then the  classifier in semi-supervised task determines how to combine them to form the final F-components partition.” For shallow GNNs, why generating  F groups of 2-components partitions is better than generating one F-components partition on semi-supervised learning. Need more explanation.

6. The dimension of $X$ is $N\times F$ and F is number of partitions you use in section 3.4. What is the relation between the two $F$ or do I miss something? $F$ is an assumption or a restriction for theorem 4?

7. Making correction of theorem 5 in supplementary material seems not to be allowed.

8. Should add a comparison with GPRGNN, which is a new model to solve heterophily problem.

9. Standard deviation should be provided in table 2&3.

10. There are two strategies proposed to reduce the number of learnable parameters. So what is the running speed of the current models and how they compare with the existing methods?

11. How well does DMP on solving over-smoothing compared to the existing models.

limitations_and_societal_impact: Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper extends the node-level network homophily based on the node label to attribute-level one by considering each attribute as a weak label. Then, it observes that different attributes have diverse attribute homophily rates. To alleviate the issue of existing uniform message passing on capturing this diverse attribute homophily rates, this paper proposes diverse message passing, where different attributes are assigned different propagation weights, and two implementations. Finally, it theoretically investigates the ability of diverse message passing on overcoming over-smoothing by analyzing the roles of the uniform and diverse propagation weights. 
main_review: The extension from network homophily rate to attribute homophily rate makes sense since node attributes can be seen as the weak label to represent the node compared to the node label. It is interesting to separately consider the homophily rate of each attribute and propose diverse propagation weights for different attributes. By comparing the proposed two implementation strategies and the interpretation from the spectral perspective, the two strategies can be regarded as a compromise between the expressive power and the overfitting issue. Thus, I think the proposed diverse message passing is effective in capturing the diverse homophily rate of different attributes. Therefore, this paper is technically sound.

Besides, the theoretical contribution of this paper is significant. Different from previous works, which often consider the over smoothing issue is caused by the over propagation, this paper shows that the over smoothing issue is actually induced by the uniform propagation. The theorems show an interesting finding that the propagation weight learning is equivalent to graph partition, and connect the graph partition and over smoothing issue. Thus, the theoretical analysis provides a new perspective to understand the over smoothing issue. 

The experimental evaluation is sufficient. It demonstrates the superior performance on networks with heterophily and heterogeneous information networks and the ability on preventing the over-smoothing issues.  

Although I think this paper is interesting and novel, there are also some concerns. 
1.	Why the performance improvements on networks with heterophily are more significant than those on networks with homophily?
2.	The explanation of why multiple graph partition just below theorem 5 is hard to understand. It is better to reorganize this paragraph.
3.	The description of the data in Figure 1 is not very clear in the appendix.
The performance of the proposed DMP can’t outperform some SOTA methods designed for heterogeneous such as MAGNN.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper proposes a message passing scheme for graph neural networks(GNNs) derived from homophily.  The problem is clearly motivated. The distinctness of the work is brought vis-a-vis GNN models has been elaborated in both spatial and spectral domains. One of the reviewers appreciated the theoretical insights which help in understand the shortcomings of existing literature. However the main concern seems to be that comparisons of the State of the art need to be improved.

Decision: Accept (Poster)