Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks

Summary

The authors consider the problem of degree bias for node classification using graph neural networks (GNNs). Much prior work has shown that GNNs tend to be much more accurate for nodes with higher degree than for lower degree. The authors survey 38 papers that pose hypotheses, sometimes contradictory, for why this degree bias exists. In this paper, the authors provide theoretical analyses on linearized versions of message-passing GNNs using random walk (RW) and symmetric (SYM) graph filters. Their bounds yield some insights on the origins of degree bias at both test time and training time and provide evidence to support some hypotheses from prior work but not others. Finally, they run experiments using the RW, SYM, and graph attention (ATT) filters on a variety of data sets, confirming their theoretical results. They conclude by providing some criteria that mitigation strategies for degree bias should target.

Strengths

- Provides a very general theoretical analysis on the misclassification probabilities of nodes using message-passing GNNs with RW and SYM graph filters. - Empirical results support predictions from theoretical results. - Theoretical and empirical results yield insights as to what types of mitigation strategies for degree bias may be most effective. - Thoroughly explores hypotheses for degree bias in the existing literature and connects the theoretical results in this paper to provide evidence for some hypotheses and against others. - Excellent use of hyperlinks to guide reader back and forth between portions of the supplement, figures, and body text. I really enjoyed reading this paper and would likely have found it much more frustrating if I had to navigate back and forth manually. - Addresses a topic of great interest to the NeurIPS community, as illustrated by the large body of recent work on the topic.

Weaknesses

- Theorem 2 bounds the squared inverse coefficient of variation $R_{i,c^′}$ based on the inverse collision probability $1/\sum_{l=0} \alpha_i^{(l)}$. There is no relationship or bound on the inverse collision probability as a function of node degree beyond a single layer, with the authors providing only empirical results. Thus, the theoretical results are not "end to end", with this one link between misclassification probability and node degree missing. - Analysis is for linearized versions of GNNs and not the GNNs themselves. Minor presentation issues: - Error bars in Figure 1 and similar figures in Appendix E are not explained in the figure caption. I see that they are explained later in the beginning of Section 3. I suggest adding (or moving) the description to the figure caption. - Figure 2: Caption lists FAIR ATT, but those plots are not shown.

Questions

1. Of the four target criteria you present in Section 6, is there any ordering or predicted importance that you would recommend future work to target? 2. I noted the lack of a relationship between inverse collision probability and node degree as a weakness. Do you have any potential leads on whether it would be possible to bound this based on other quantities in the graph? This would allow your theoretical results to potentially be "end to end".

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

4

Limitations

Limitations are discussed in the supplementary material. The paper would be strengthened if a short summary of the main limitations (maybe 2 or 3 lines) could be added to the conclusion.

Summary

The paper provides a comprehensive analysis of the origins of degree bias in message-passing GNNs, proving that high-degree test nodes have a lower probability of misclassification, regardless of how GNNs are trained. They surveyed 38 papers on degree bias and found that existing hypotheses are often not rigorously validated and can be contradictory. They also show that some GNNs may adjust their loss on low-degree nodes more slowly during training, but with sufficient training epochs, these models can achieve their maximum possible training accuracy. The theoretical findings are validated on eight real-world networks, and a roadmap to alleviate degree bias is proposed.

Strengths

+This paper explores the important issue of the origins of degree bias in Graph Neural Networks (GNNs). +The authors conduct a comprehensive survey on degree bias, carefully identifying and validating existing hypotheses while pointing out those that are contradictory or lack validation. +The study examines the effects of different graph filters and analyzes degree bias separately during both test time and training time. +The paper provides a thorough theoretical analysis and supports its claims with empirical studies on eight datasets.

Weaknesses

-It appears that the findings in this paper are limited to homophilous graphs, as the results do not extend to heterophilic graphs, according to the paper's analysis. -The current analysis is based on graphs with a single edge type. Can these findings be expanded to heterogeneous graphs, where the edges can have different types? It could be worth studying to explore this possibility.

Questions

Please address the questions regarding weaknesses.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes

Summary

The paper explores the causes and characteristics of degree bias in graph neural networks (GNNs), particularly in node classification tasks. It contributes to the field by providing a rigorous theoretical analysis supported by empirical evidence across multiple datasets, revealing that degree bias is influenced by factors such as homophily and diversity of neighbors. The study also proposes a structured approach to mitigate this bias, enhancing the fairness and effectiveness of GNN applications in social and recommendation systems.

Strengths

originality: medium quality: good clarity: good significance: medium

Weaknesses

Some degree-related papers should be included and discussed in this paper, for example: [1] takes a unified view to explain the over-smoothing and heterophily problems simultaneously by profiling nodes with two metrics: the relative degree of a node (compared to its neighbors) and the node-level heterophily. [2] investigates how does node degree, homophily and class variance influence the node distinguishability. [3] finds that the effectiveness of graph convolution operations in enhancing separability is determined by the Euclidean distance of the neighborhood distributions and the square root of the average node degree. Furthermore, they find that topological noise negatively affects separability by effectively lowering the average node degree. [4] observes that the prediction accuracy of high-degree nodes is usually significantly lower under heterophily and the hypothesis that "nodes with higher degrees are naturally favored by GNNs" no longer holds. In fact, the degree-wise bias is more sensitive, but not necessarily beneficial, to high-degree nodes with regard to varying graph conditions. [1] Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In2022 IEEE International Conference on Data Mining (ICDM) 2022 Nov 28 (pp. 1287-1292). IEEE. [2] When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability. Advances in Neural Information Processing Systems. 2024 Feb 13;36. [3] Understanding Heterophily for Graph Neural Networks. In Forty-first International Conference on Machine Learning. [4] Liao N, Liu H, Zhu Z, Luo S, Lakshmanan LV. Benchmarking Spectral Graph Neural Networks: A Comprehensive Study on Effectiveness and Efficiency. arXiv preprint arXiv:2406.09675. 2024 Jun 14.

Questions

1. How does homophily relate to degree bias? I expect some conclusions in this paper but cannot find them. 2. The "expected similarity of the neighborhoods" in section 5 is very similar to the similarity matrix defined in [5] 3. The criteria proposed in section 6 should be verified in real-world datasets. [5] Revisiting heterophily for graph neural networks. Advances in neural information processing systems. 2022 Dec 6;35:1362-75.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

the authors adequately addressed the limitations

Summary

Given the wide-adoption of GNN-based node classification and the potential risk of degree-related bias, this paper systematically reviews the degree-bias paper in previous literature and proposes a theoretical framework to analyze the degree-related bias. Several insightful observations have been drawn with empirical verification.

Strengths

(1) A systematic investigation of a long-standing yet not addressed research problem, degree bias. Comprehensive summary of previous works on this has been presented (2) The degree-related bias is urgently related to social benefit.

Weaknesses

(1) Some experimental results are not supportive of some claims. (2) Some theoretical analyses lack intuitive justification from a graph topology perspective, e.g., the connection with network homophily/heterophily.

Questions

(1) Since the degree bias focused on here is node classification, would it be better to note this special case somewhere in the paper, or at least for the title, would it be better to reword and limit the task scope to node classification? Is there any insight or potential thought on degree-related bias in link prediction and graph classification (here the degree would correspond to graph density)? (2) In Figure 5, when looking at the Squirrel and Chameleon datasets, there is no significant difference in high-degree and low-degree test loss, is there a specific reason for their difference from the other datasets? (3) Maybe it is a typo, but in the Equation at the bottom of page 4, if we unify different layers' weight transformation matrices as of dimension $\mathbb{R}^{d^0\times C}$, would it cause some dimension mismatch during matrix multiplication? Why does every layer of convolution consider the project from space $\mathbb{R}^{d^0}$ to $\mathbb{R}^{C}$? Moreover, it might be better to add back the Equation number. (4) It is not so clear about "the diversity of neighborhoods" until the formal definition in Line 168. It might be better to provide some concise illustrations to help readers understand the diversity of neighbors when it was mentioned for the very first time. (5) Based on Theorem 2, in addition to decreasing the negative $\sum_{l=0}^{L}\beta_{i, c'}^{(l)}$ so that $R_{i, c'}$ could increase, could we also increase the positive $\sum_{l=0}^{L}\beta_{i, c'}^{(l)}$ so that $R_{i, c'}$ could increase? Are these two scenarios corresponding to some graph local structure? Based on my understanding, as $\beta_{i, c'}^{(l)}$ measures of the local subgraph difference between class $c'$ and class $c$, it really boils down to the local homophily and local heterophily, if the value is pretty small, then it might correspond to a very small $\beta$, which might correspond to a equal contribution between class c and c' and hence the subgraph is really like a mixture between nodes from these two classes and hence cannot work very well. To sum up this point, my thinking is that it would be better to provide some intuition for some theoretical findings from a topology perspective. (6) It might be interesting to add some analysis when a distribution shift happens. (7) For the training loss visualization in Figure 2, it is really hard to see the difference of low/high-degree nodes for RW and ATT.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper addressed all limitations with the following exceptions: The paper mainly studies degree-related bias for node classification. There are some other tasks such as link prediction and graph classification worth similar analysis as well.

Thank you for your response!

Despite most of the concerns have been addressed, I still have follow-up questions: (1) **In the random walk filter case, link prediction scores between low-degree nodes will suffer from higher variance because low-degree node representations have higher variance. Hence, Theorem 1 suggests that predictions for links between low-degree nodes will have a higher misclassification error.**, there is some other work proving that local clustering coefficient of nodes decreases as node degree increases and since LCC is very related to node link prediction performance, I am not sure whether this intuition is right or not. (2) **Could you please elaborate on which experimental results are “not supportive of claims?” We would like to address or clarify any potential mismatches between our theoretical analysis and experiments.** In Figure 6 middle row, I didn't see the training loss decrease more rapidly for SYM on low-degree nodes as claimed in the main paper.