Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?

Summary

This paper investigates the effectiveness of GNNs on nodes with different structural patterns in real-world graphs and proposes a new method to identify the reasons for performance disparities. The authors found that GNNs tend to perform well on homophilic nodes within homophilic graphs, but struggle with the opposite node set, and they provide insights into the performance disparities by analyzing aggregated feature distance and homophily ratio difference between training and testing nodes.

Strengths

This paper provides both empirical and theoretical evidence to support its findings. It conducts rigorous analyses and derives a non-i.i.d. PAC-Bayesian generalization bound for GNNs, which adds credibility to the research. The authors substantiate their findings with controllable synthetic experiments and real-world datasets, further strengthening the quality of the paper.

Weaknesses

1. Writing needs to improve. 2. Some explanation needs more elaboration.

Questions

1. Line 49-50, “while heterophilic graphs exhibit an opposite phenomenon with homophilic nodes in the majority and heterophilic ones in the minority.” Check this definition of heterophilic graphs. 2. Line 55-56, “ Such differences may lead to performance disparity between nodes in majority and minority patterns.” If you randomly sample training and test data, the distribution of the majority and minority patterns should be the same for training and test nodes. Thus, the disparity shown in this example is not valid in practice. 3. “Consequently, the performance disparity can be overwhelmed by such gap which renders the effect from structural patterns.” I don’t understand this sentence. Please elaborate the reason why you use GLNN here. 4. Are the observations in Figure 3 also hold on other benchmark datasets? 5. Line 170, why both homophilic and heterophilic patterns have p>q? In your definition, nodes from the subgroup but different classes have the same (p,q)? 6. Line 179-181, check the English. 7. “This proposition suggests that aggregation results in a distance gap between different patterns within the same class.” I cannot see how this proposition suggests the distance gap. Please elaborate it. 8. In Lemma 1, are nodes u,v from the same class? Why do you want to examine “discrepancy between nodes and with the same aggregated feature but different structural patterns.”? How does this relates to the proposed claim about majority and minority nodes?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Yes

Summary

This paper focuses on the performance disparity on homophily and heterophily nodes in node-level classification tasks. It claims that although GNNs have good performance on both pure homophily and pure heterophily graphs, GNNs cannot perform well when dealing with graphs with both these two types of nodes. The paper then analyses the reason for different impact on majority and minority nodes and illustrates the aggregation function's contribution on this. It delves into the theoretical analysis, deriving a non-i.i.d PAC-Bayesian generalization bound based on the Subgroup Generalization bound of Deterministic Classifier. The theoretical analysis indicates that test nodes with larger aggregated feature distances and homophily ratio differences from training nodes experience performance degradation. The practical implications of the findings are demonstrated on real-world datasets.

Strengths

- The paper provides sufficient real-world experiments to show how the homophily ratio and the feature distance influence the GNN’s aggregation and the actual performance on both homophilic and heterophilic datasets. This could sever as a foundation for future GNN architecture design. - The paper performs the theoretical analysis that reveals potential reasons for the performance disparity. The findings are supported by experimental results. - The paper is well structured with good clarity in presentation.

Weaknesses

- The paper identifies the problem of performance disparity but does not provide a solution to address it. - The classification of nodes into homophily and heterophily classes using a hard threshold is a simple and ideal setting. This setting may fail to capture the complexity and nuances that may exist in real-world scenarios. Do the conclusions/findings still hold if we directly use the continuous homophily ratio rather than thresholding it?

Questions

See the weaknesses section.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

NA

Summary

This paper provides a rigorous analysis of the effect of structural disparity on the performance of GNNs. The proposed CSBM-S model and the application of PAC-Bayes analysis, among others, show the different effects of aggregation on the performance of nodes with different structural disparity. The analysis further indicate subgroup generalization bound for GNN and elucidate the effectiveness of deeper GNNs.

Strengths

1. The problem considered in this paper is extremely important. I agree with the authors that real-world graphs can’t be easily classified as homophilic or heterophilic. Therefore, analyzing how structural disparity influences the performance is essential to GNN design. 2. It is well backed up by theoretical analysis and examples. The authors show several nice analysis methods, including CSBM-S model and subgroup generalization bound for GNNs. 3. Extensive experiment enables the conclusions presented in this paper to be convincing

Weaknesses

1. The conclusions hold in this paper share the same promise that the aggregation operation is neighbourhood averaging, which may not generalize to a broad range of GCNs models 2. The writing could be improved in terms of tone and phrases. There are also some grammar and spelling errors

Questions

There are two assumptions that nodes from different subgroup share the same distribution and similar degree distribution. How does the conclusions are still valid without the above assumptions as stated in the supplementary material.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

This work tries to understand the effectiveness of GNNs w.r.t different structural disparities within a graph. Previous studies have focussed on GNN's effectiveness on overall graphs, but here the authors try to understand GNN's effectiveness w.r.t structural patterns such as homophilic and heterophilic nodes to provide deeper insight into GNN's performance. Contributions include understanding why the performance of GNNs is rather good on homophilic nodes in homophilic graphs and heterophilic nodes in heterophilic graphs, but not on the opposite set. Specifically, how aggregated feature distances and homophily ratio differences in mixed graphs impact the GNN performance. Authors also present experimental results on how deeper GNNs perform better on minority node subgroups while also proposing a new data split strategy to where majority nodes are selected for train/validation and minority nodes for test.

Strengths

GNN performance studies on datasets across difference structural subgroups is a crucial metric to understand the overall performance of the model. Quantitive understanding of the effect of aggregation and homophily ratio difference w.r.t train nodes is a significant metric to compare different GNN architectures. This provides new evaluation strategies for future GNN studies. The effect of new data splitting strategy is again a significant contribution and is useful to evaluate the overall GNN performance.

Weaknesses

The work by itself is strong and would have been even stronger if presented with more understanding of the effectiveness of Deeper GNNs on doing comparatively well on minority nodes.

Questions

1. Is there a way to prove deeper GNNs improved discriminative ability on minority nodes? 2. Are there any additional factors other than aggregation and homophily ratio difference that you thought about?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

None

Thank you for the response

The rebuttal has addressed my concerns. I will keep the current rating.

A gentle remind to reviewer itvA

Dear reviewer itvA Thanks for your review. Your time and efforts in evaluating our work are appreciated greatly. Could we kindly know if the responses have addressed your concerns and if further explanations or clarifications are needed? Thanks.

Thanks for your rebuttal

The authors addressed most of my concerns. In general, I find this paper interesting. I will raise my score to 5.