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

Thanks for your insightful comments and positive reception! Regarding the weaknesses:

• This is a great and interesting question! We agree that it would be beneficial to close this missing link. Via some preliminary analysis, we find that it is possible to express the inverse collision probability (i.e., express the sum of $l$-hop collision probabilities) in terms of $D_{i i}$. In particular, we can show: $\sum_{l = 0}^L \alpha_i^{(l)} = \alpha_i^{(0)} + \sum_{l = 1}^L \sum_{j \in {\cal V}} [(P^l_{rw})\_{i j}]^2 = 1 + \frac{1}{D^2\_{i i}} \sum_{l = 1}^L \sum_{j \in {\cal V}} [\sum_{k \in {\cal N(i)}} (P^{l - 1}\_{rw})\_{k j}]^2$. As before, we can see that the inverse collision probability is larger (and thus $R_{i, c’}$ is larger) when $D_{i i}$ is larger, and $\sum_{l = 1}^L \sum_{j \in {\cal V}} [\sum_{k \in {\cal N(i)}} (P^{l - 1}\_{rw})\_{k j}]^2 \in o(D_{i i}^2)$. However, because $\sum_{k \in {\cal N(i)}}$ depends on $D_{i i}$, this expression does not completely isolate the impact of $D_{i i}$ on the inverse collision probability. A similar expression can be derived for SYM by expressing: $P_{sym} = D^{\frac{1}{2}} P_{rw} D^{-\frac{1}{2}}$.

Another proof route that was considered was via the following bound: $\sum_{l = 0}^L \alpha_i^{(l)} \leq \sum_{l = 0}^\infty \alpha_i^{(l)}$, as then we can plug in the steady-state probabilities of uniform random walks on graphs. However, as $l \to \infty$, $(P^l_{rw})\_{i j} = D_{j j} / 2 |{\cal E}|$ only depends on $D_{j j}$ (not $D_{i i}$ as desired). It is also possible to upper bound the inverse collision probability as: $1 / \sum_{l = 0} \alpha_i^{(l)} \leq 1 / (\alpha_i^{(0)} + \alpha_i^{(1)}) = 1 / (1 / D_{i i} + 1)$, which is in terms of $D_{i i}$; however, we cannot use this upper bound to lower bound $R_{i, c’}$.

We will continue ideating about: (1) better bounds for the inverse collision probability in terms of $D_{i i}$, or (2) an impossibility result for a bound that isolates the effect of $D_{i i}$ on $R_{i, c’}$. This being said, our paper argues that the inverse collision probability is a more fundamental quantity that influences what the community has termed “degree bias” than degree alone, which is positively associated with the inverse collision probability.

• It would be interesting as future work to investigate the effects of nonlinearities on degree bias. Towards this, a possible option is to assume that node features are drawn from a Gaussian distribution and derive high-dimensional asymptotics for degree bias in non-linear GNNs using the Gaussian equivalence theorem, as in [1].

[1] Ben Adlam, Jeffrey Pennington Proceedings of the 37th International Conference on Machine Learning, PMLR 119:74-84, 2020.

• Thanks for catching the presentation issues. We will move the explanation of the error bars to the caption of Figure 1 and the captions of the figures in Appendix E. We will likewise remove “FAIR ATT” from the caption of Figure 2.

Regarding your questions:

1. We recommend that future work target criteria 2 and 3 (lines 291-294) first. These criteria are important because they reflect (to a large extent) inherent fairness issues with the graph filters that are popular in the graph learning community. For instance, the random walk and symmetric filters disadvantage low-degree nodes by yielding representations with high variance and low magnitude, respectively. It is valuable for the community to investigate filters that are adaptive or not restricted to the graph topology in a way that ensures that low-degree nodes are not marginalized through disparate representational distributions or poor neighborhood diversity.

2. We discuss potential leads above to bound the inverse collision probability in terms of node degree. The collision probabilities themselves are intimately related to (more global) properties of the graph; for instance, via eigendecomposition, $[(P^l_{rw})\_{i j}]^2 \leq \lambda^{2 l}$, where $\lambda < 1$ is the eigenvalue of $P_{rw}$ with the largest magnitude [2]. Then, the inverse collision probability is strictly greater than $\frac{1}{\sum_{l = 0}^L |{\cal V}| \lambda^{2 l}}$.

[2] Lovasz, L. M. Random walks on graphs: A survey. 2001.

3. We will definitely detail the main limitations of our paper in the conclusion of the camera-ready version.

Thanks for your thoughtful feedback and questions! Regarding the weaknesses and your questions:

• Our findings do extend to heterophilic graphs. For example, in Lines 220-222, we explain that high-degree nodes in heterophilic networks do not have more negative L-hop prediction homogeneity levels due to higher local heterophily, hence we do not necessarily observe better performance for them; we empirically validate that there is a lack of degree bias for the heterophilic datasets Chameleon and Squirrel in Figure 5. Furthermore, in lines 693-696, we explain that models do not learn more rapidly for high-degree nodes under heterophily (Figures 11-12) because the “features of nodes in the neighborhoods of high-degree nodes and training nodes are dissimilar.” None of our theoretical analysis assumes homophilic networks. We will clarify any parts of the paper that suggest that our theoretical analysis does not encompass heterophilic networks.

• We agree that it is valuable to study the possibility of expanding our findings to heterogeneous graphs. For example, in our literature survey, we cover works that establish the issue of degree bias for knowledge graph predictions and embeddings (e.g., [4, 38]). Furthermore, we state in Section K, “it remains to identify the shortcomings of our theoretical findings for heterogeneous and directed networks.” Our theoretical analysis is general and covers diverse message passing GNNs, and can be extended to heterogeneous networks if messages aggregated from different edge types are subsequently linearly combined. In this setting, $R_{i, c’}$ can be computed as the sum of the prediction homogeneity quantities $(\sum_{l = 0}^L \beta_{i, c’}^{(l)})^2$ for each edge type divided by the sum of the collision probability quantities $\sum_{j \in {\cal V}} [(P_{rw}^l)_{i j}]^2$ for each edge type.

[4] Stephen Bonner, Ufuk Kirik, Ola Engkvist, Jian Tang, and Ian P Barrett. Implications of topological imbalance for representation learning on biomedical knowledge graphs. Briefings in Bioinformatics, 23(5):bbac279, 07 2022.

[38] Harry Shomer, Wei Jin, Wentao Wang, and Jiliang Tang. Toward degree bias in embedding based knowledge graph completion. In Proceedings of the ACM Web Conference 2023, WWW ’23, page 705–715, New York, NY, USA, 2023. Association for Computing Machinery.

Thanks for your feedback and the helpful resources! Regarding the weaknesses, we will definitely include and discuss the recommended references on homophily in our paper:

[1] provides a complementary perspective on the possible performance issues of GNNs that arise from degree disparities in graphs (e.g., low-degree nodes induce oversmoothing in homophilic graphs, while high-degree nodes induce oversmoothing in heterophilic networks). Oversmoothing is related to prediction homogeneity $(\sum_{l = 0}^L \beta_{i, c’}^{(l)})^2$ (line 149); for homophilic networks, as the number of layers in a GNN increases (i.e., as oversmoothing occurs), $(\sum_{l = 0}^L \beta_{i, c’}^{(l)})^2$ gets closer to 0 (i.e., does not increase $R_{i, c’}$), thereby not inducing as much degree bias. In contrast, our theoretical analysis demonstrates that degree bias occurs without oversmoothing and is amplified by high local homophily (lines 170-171).

[2] connects node distinguishability to node degree and homophily by analyzing the intra-class vs. inter-class embedding distance. We discuss similar quantities in lines 175-189 and lines 208-226, and will integrate connections to [2] in these discussions. However, with the exception of Section 3.5, [2] considers the CSBM-H model in its theoretical analysis, which has pitfalls (as we discuss in lines 79-83). Moreover, unlike our work, [2] does not explicitly link the misclassification error of a node to its degree in a more general data and model setting.

[3] analyzes the effect of heterophily on GNNs via class separability, which it characterizes through neighborhood distributions and average node degree. Like with [1] and [2], we will discuss connections between prediction homogeneity, homophily, and separability. Notably, similar to [2], [3] only considers the HSBM model in its theoretical analysis.

[4] observes that GNN performance is lower for high-degree nodes under heterophily. We likewise observe this in Figure 5 for Chameleon and Squirrel (which are heterophilic networks), and we will connect this observation to [4]. Moreover, our theoretical analysis explains why degree bias is not observed for heterophilic graphs; in lines 220-222, we explain that high-degree nodes in heterophilic networks do not have lower $l$-hop prediction homogeneity levels due to higher local heterophily, hence we do not necessarily observe better performance for them compared to low-degree nodes. We would additionally like to note that [4] was released on 4 Jun 2024, which was after the NeurIPS submission deadline on 22 May 2024.

Regarding your questions:

1. We make connections between homophily and degree bias in the paper. For example:

• Lines 170-171: We show that to amplify degree bias, we need to make $R_{i, c’}$ larger, for which it is sufficient to make the prediction homogeneity $\sum_{l = 0}^L \beta_{i, c’}^{(l)}$ more negative, “e.g., when most nodes in the $l$-hop neighborhood of $i$ are predicted to belong to class $c$.” This can occur when node $i$ has high local homophily.
• Lines 175-179: Our proof of Theorem 2 shows that, in expectation, $\overline{RW}$ “produces similar representations for low and high-degree nodes with similar L-hop neighborhood homophily levels.” However, low-degree nodes have a higher representation variance (due to a lower inverse collision probability), which can amplify degree bias. This entails that factors beyond homophily (e.g., diversity of neighbors) induce degree bias.
• Lines 208-214, 222-226: Our proof of Theorem 3 likewise shows that for SYM, homophily alone does not induce degree bias.
• Lines 220-222: We explain that high-degree nodes in heterophilic networks do not have lower $l$-hop prediction homogeneity levels due to higher local heterophily, hence we do not necessarily observe better performance for them.
• Lines 693-696: We explain that models do not learn more rapidly for high-degree nodes under heterophily (Figures 11-12) because the “features of nodes in the neighborhoods of high-degree nodes and training nodes are dissimilar.”

2. The similarity matrix defined by [5] is post-aggregation, while our matrix is pre-aggregation. Moreover, our similarity matrix is an interpretable quantity that naturally arose during our theoretical analysis. We are happy to cite [5].

3. We perform extensive validation of the criteria in Section 6 on 8 real-world datasets:

• Figure 3 and the plots in Section G show strong positive associations between inverse collision probability and degree for the RW, SYM, and ATT filters, and Figure 1 and the plots in Section E show strong negative associations between degree and test loss for the homophilic datasets. Hence, we validate that there is a negative association between inverse collision probability and test loss.

• The lack of degree bias observed in Figure 5 for Chameleon and Squirrel (which are heterophilic networks), compared to Figure 1 and the other plots in Section E, confirms our theoretical finding that under heterophily, the prediction homogeneity for high-degree nodes is closer to 0, so high-degree nodes do not necessarily experience better performance.

• Figures 2, 6-10 empirically confirm our theoretical finding that disparities in the expectation and variance of node representations are responsible for performance disparities. Figures 11-12 suggest that smaller distributional differences among representations (due to heterophily) can alleviate degree bias.

• Figure 2 and the plots in Section F empirically validate the training discrepancies between low and high-degree nodes that we theoretically analyze in Section 5.

Thanks for your comments and thorough questions! Regarding your questions:

(1) We will make the scope of the paper clearer by indicating in the title, introduction section, and limitations section that we focus on node classification. Our findings readily lend insight into the origins of degree bias in link prediction. For example, if one uses node representations and an inner-product decoder to predict links between nodes, our results (lines 208-226) indicate that:

• 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.
• In the symmetric filter case, the link prediction scores between high-degree nodes will be over-calibrated (i.e., disproportionately large) because high-degree node representations have a larger magnitude (i.e., approximately proportional to the square root of their degree). Hence, our proof of Theorem 3 suggests that over-optimistic and possibly inaccurate links will be predicted between high-degree nodes. More research is required to understand the implications of our findings for degree bias in the context of graph classification; such research likely has rich connections to the literature on spectral expressive power [1].

[1] Balcilar, Muhammet, et al. "Analyzing the expressive power of graph neural networks in a spectral perspective." 2021.

(2) The reason that we do not observe degree bias for Chameleon and Squirrel is because unlike the other datasets, these datasets are heterophilic. We intentionally include these datasets to draw contrast to the other, homophilic datasets and validate our theory. For example, in lines 220-222, we explain that high-degree nodes in heterophilic networks do not have more negative $l$-hop prediction homogeneity levels due to higher local heterophily levels; hence, we do not necessarily observe better performance for them compared to low-degree nodes.

(3) We will ensure that equation numbers are visible for all equations. The weight transformation matrices should all be of dimension $d_0 \times C$; there is not a dimension mismatch issue. This is because we consider linearized versions of message-passing GNNs. In particular, in the equation between lines 132 and 133, if we set each $\sigma^{(l)}$ to be identity and recursively expand the matrix multiplications, we end up with the expression: $Z^{(L)} = \sum_{l = 0}^L P_{rw}^l X W^{(l)}$, where $W^{(l)}$ is the sum of all the weight terms in the expansion that correspond to $P_{rw}^l$; for simplicity, we collapse each sum of weight terms into a single weight matrix. Because each $W^{(l)}$ maps the input features $P_{rw}^l X \in \mathbb{R}^{n \times d_0}$ to the outputs $Z^{(l)} \in \mathbb{R}^{n \times C}$, they must all be of size $d_0 \times C$. It makes sense to have a different weight matrix for each $P_{rw}^l X$, as we may need to extract different information from features aggregated from neighborhoods at different hops.

(4) This is great feedback. We will include a figure at the beginning of the paper that visually illustrates the concepts of prediction homogeneity and collision probability, and their connections to homophily and diversity.

(5) In Theorem 2 (lines 118-119), we assume that $\mathbb{E} [Z_{i, c’}^{(L)} - Z_{i, c}^{(L)}] < 0$ (i.e., the model generalizes in expectation); this is necessary to make a mathematically rigorous statement about degree bias via tail bounds. Thus, we cannot make $\sum_{l = 0}^L \beta_{i, c’}^{l)}$ more positive to increase $R_{i, c’}$, as this would violate the assumption of our theorem. However, intuitively, it also would not make sense that RW and SYM reduce the misclassification error for a node by predicting its neighbors to be of a different class, since message passing smooths the representations of adjacent nodes.

Furthermore, per lines 153-154, “$\beta_{i, c’}^{(l)}$ measures the expected prediction score for nodes j, weighted by their probability of being reached by a length-l random walk starting from i.” Because $\beta_{i, c’}^{(l)}$ depends on the distribution of random walks from $i$, it is intimately related to local graph structure. Indeed, $\beta_{i, c’}^{(l)}$ can be interpreted as a “local subgraph difference” and is highly influenced by the local homophily of $i$ (as we say in lines 170-174). However, $\beta_{i, c’}^{(l)}$ is also influenced by the presence of $l$-hop neighbors contained in the training set, as the model is more likely to correctly classify these nodes by a large margin (lines 172-173); hence, $\beta_{i, c’}^{(l)}$ does not only boil down to local homophily. When revising our paper, we will include and expand on these clarifications on the similarities and differences between $\beta_{i, c’}^{(l)}$ and local homophily, to provide better intuition from a topological perspective.

(6) We can add some analysis for distribution shifts. For example, our results in Section 4 can be built upon to show that shifts in local homophily from train to test time reduce test-time prediction performance, which can bring $\beta_{i, c’}^{(l)}$ closer to 0; this can increase $R_{i, c’}$, thereby not inducing as much degree bias.

(7) We will make the training loss visualizations in Figure 2 larger. The primary takeaway from this figure is that, in the case of RW and ATT, the training loss curves for low and high-degree nodes (including error bars) overlap during the first ~20 epochs of training; however, for SYM, the loss curve for high-degree nodes descends more rapidly than the curve for low-degree nodes.

Regarding the weaknesses:

(1) 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.

(2) Please see (5) above.