Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction

We thank the reviewer for their helpful and specific feedback! To address your stated weaknesses and questions:

• Weakness (1), Questions (1)-(2): By theoretically and empirically uncovering preferential attachment bias and within-group unfairness issues in GCN link prediction, we lay a foundation to study these issues in other link prediction methods in the future. This will include SOTA contrastive methods for link prediction (1) and how they are affected by fairness regularization (2). Overall, this is an important and interesting direction of research.

We also include experiments for a link predictor that uses a Hadamard product and MLP score function (instead of an inner product) in Appendix G.2. We find that our theoretical analysis is still relevant to and reasonably supports the experimental results, both qualitatively and quantitatively. This could be because MLPs have an inductive bias towards learning simpler, often linear functions [1, 2], and our theoretical findings are generalizable to linear LP score functions.

• Weakness (2): Because we unveil a new form of unfairness, it is difficult for us to find comparable methods to use as baselines. While we describe methods for alleviating degree bias in the “Degree bias in GNNs” paragraph in our related work section, these methods address performance disparities for low-degree nodes. In contrast, we do not study performance issues but rather how GCN often scales node representations proportionally to the square root of their within-group degree, which affects the magnitude of their link prediction scores.

• Weakness (3): We do not use the loss as our fairness metric, but rather the fairness metric as a regularization term in our loss. We theoretically motivate and ground the fairness metric in Section 4.2, and because the metric is differentiable, we are able to directly add it to our loss function. While it is not surprising that the fairness regularization approach will minimize our metric, it is significant that our experiments show that the regularization does not severely impact link prediction performance.

• Question (3): We focus on GCN (with symmetric and random walk normalized filters) because it provides us with a reasonable setting to develop a rigorous theory of preferential attachment bias in GNN link prediction while leveraging tools from spectral graph theory. We believe that our results may be generalizable to GNN architectures that use a symmetric degree-normalized diffusion operator. Furthermore, it is not uncommon to use vanilla GCN for link prediction; for example, PyTorch Geometric (a popular graph learning library) has code examples that apply vanilla GCN to link prediction: https://github.com/pyg-team/pytorch_geometric/blob/master/examples/link_pred.py.

• Question (4): The time complexity of calculating the regularization term is $O(\sum_{b = 1}^B |S^{(b)} \cap T^{(1)}| \cdot S^{(b)} + |S^{(b)} \cap T^{(2)}| \cdot S^{(b)})$, as we have already computed the link prediction scores for the cross-entropy loss term and simply need to sum them appropriately with respect to the groups and subgroups. The time complexity of computing gradients for the regularization term should be on the same order as backpropagation for the cross-entropy loss term.

[1] Nakkiran, Preetum, et al. "Sgd on neural networks learns functions of increasing complexity." arXiv preprint arXiv:1905.11604 (2019).

[2] Valle-Perez, Guillermo, Chico Q. Camargo, and Ard A. Louis. "Deep learning generalizes because the parameter-function map is biased towards simple functions." arXiv preprint arXiv:1805.08522 (2018).

Thanks for the response from the authors.

My concerns are partially addressed, but two of my major concerns remain: (1) it is not surprising that if a term is added to the objective function, then this term will be optimized when the objective is optimized, so it seems not comprehensive to only present the fairness performance from this specific perspective; (2) There should be a comprehensive discussion about why it is impossible to adopt existing frameworks as baselines for the studied problem. For example, does any of the existing fairness-aware frameworks contribute to the optimization of the proposed fairness metric? How does the proposed fairness metric connect with other existing metrics? It would be more reasonable to avoid adopting any baseline after properly placing the proposed approach in a broader literature background about the studied problem.

We thank the reviewer for their insightful and thorough feedback! To address your concerns:

• We agree that the association between node degrees and group membership depends on group size and homophily. In our camera-ready (after working out space constraints), we will add the following text before Section 4.2:

”An association between node degrees and group membership depends on group size and homophily; in particular, when a group has many nodes and intra-links (i.e., is homophilous), there may be more nodes with a high within-group degree.”

We touch upon social group homophily in Section 4.1 using the term “social stratification” from the social science literature. In particular, the intra-link approximation error term $\sum_{l = 1}^L {L \choose l} \left\| \Xi^{(0)} \right\|^l_{op} \left\| \widehat{P} \right\|^{L - l}_{op}$ captures homophily.

• We will add a discussion of how our findings relate to Intersectionality in the “Within-group fairness” paragraph of Section 2:

”Our theoretical and empirical findings reveal that GCN link prediction can further marginalize social subgroups. This relates to the “complexity” tenet of Intersectionality, which expresses that the marginalization faced by, e.g., Black women, is non-additive and distinct from the marginalization faced by Black men and white women [1].”

• In Figure 2, the colors represent different groups. We describe the type of groups in each dataset in Section C; for example, in the LastFMAsia dataset, the groups are the home countries of users. However, we were unable to find the exact group names (e.g., Vietnam, India) from the dataset documentation.

• We adopt the class labels for each dataset as the social group labels. This design choice is reasonable, as in all the datasets, the classes naturally correspond to socially-relevant groupings of the nodes, or proxies thereof (e.g., in the LastFMAsia dataset, the classes are the home countries of users). We will add the following discussion of homophily in Section 5:

”Because we adopt the class labels for each dataset as the social group labels, the social groups are largely homophilic. This aligns with our assumptions when interpreting Theorems 4.3 and 4.4 that social groups are stratified in networks.”

[1] Collins, Patricia Hill, and Sirma Bilge. Intersectionality. John Wiley & Sons, 2020.

We thank the reviewer for their detailed and valuable feedback! To address your concerns and questions:

• W2: Could you please elaborate on which aspects of the initial motivation can be clarified? (e.g., specific lines). We greatly appreciate your help in making our motivation clear and accessible to readers.

• W3, Q3: Thank you for bringing [1, 2] to our attention; we will add these papers to the “Degree bias in GNNs” paragraph in our related work section. However, these works touch upon different forms of degree bias (i.e., sampling and performance bias) than the type of degree bias we uncover: GCNs often scale node representations proportionally to the square root of their within-group degree, which affects the magnitude of their link prediction scores.

• Q1: We did not observe that the relative error is smaller for lower values of the ratio. We add plots demonstrating this in Appendix I (Figure 11).

Furthermore, $\Phi_r$ link prediction scores are not associated with either $\widehat{D}_{i i}$, $\widehat{D}_{j j}$, or the product thereof. We add plots demonstrating this in Section I (Figure 12).

There are intimate connections between our result and the steady-state probabilities of the classic RW. The stationary probabilities of classic RW are the same regardless of the starting node. This is why $\Phi_r$ produces similar representations for all the nodes in each group, regardless of the degree of the node (with a larger number of layers, $\Phi_r$ would oversmooth all the representations to the same vector). Hence, $\Phi_r$ link prediction scores do not have a degree dependence, theoretically or empirically.

• Q2: In Figure 1, we treat the disciplines as groups and gender as subgroups; in particular, we are concerned about GCN link prediction further marginalizing the subgroup of women within the group of CS researchers.

We agree that fixing the number of recommendations per individual is a possible solution, but doing this with utility in mind requires identifying a utility-maximizing subset of link predictions. As our theoretical and empirical results reveal, GCN link prediction scores are often inherently proportional to the geometric mean of the degrees of the incident nodes, which can make them a poor indicator of prediction confidence. From a calibration perspective, GCN naturally makes overconfident predictions for links between high-degree nodes.

In Eq. (5), the power takes precedence over the subscripting.

[1] Kojaku, Sadamori, Jisung Yoon, Isabel Constantino, and Yong-Yeol Ahn. "Residual2Vec: Debiasing graph embedding with random graphs." Advances in Neural Information Processing Systems 34 (2021): 24150-24163.

[2] Harry Shomer, Wei Jin, Wentao Wang, and Jiliang Tang. 2023. Toward Degree Bias in Embedding-Based Knowledge Graph Completion. In Proceedings of the ACM Web Conference 2023 (WWW '23). Association for Computing Machinery, New York, NY, USA, 705–715. https://doi.org/10.1145/3543507.3583544

We thank the reviewer for their thoughtful feedback! To address your concerns:

• We agree that the independence of path activation probabilities may not always hold true in the real world. However, we verify that this assumption is plausible via our extensive experiments on real-world datasets to validate our theoretical analysis (Section 5.1). This assumption also aligns with findings that deep neural networks have an inductive bias towards learning simpler, often linear functions [1, 2]. Furthermore, a variant of our assumption (where $\rho(i) = \rho$ is constant for all nodes) has been used in the literature to simplify theoretical analysis (e.g., [3, 4]); our assumption may be more realistic than this variant, as it captures that the probability of paths activating can differ across nodes (e.g., due to differences in features, neighborhood structure).

• Thanks for highlighting works [5, 6, 7] on link prediction using GNNs. To address these, we will add the following text to the end of Section 3 in our camera-ready (once we work out space constraints):

"In recent years, researchers have proposed methods to improve the expressivity of node representations for link prediction by capturing subgraph information [5, 6, 7]. Our theoretical findings remain relevant to methods that ultimately use a GCN to predict links (e.g., [6, 7]), as we do not make assumptions about the features passed to the GCN (i.e., they could be distance encodings, SEAL node embeddings, etc.) Studying the fairness of more expressive link prediction methods is an interesting direction for future research."

We also include experiments for a link predictor that uses a Hadamard product and MLP score function (instead of an inner product) in Appendix G.2. We find that our theoretical analysis is still relevant to and reasonably supports the experimental results, both qualitatively and quantitatively. This could be because MLPs have an inductive bias towards learning simpler, often linear functions [1, 2], and our theoretical findings are generalizable to linear LP score functions.

[1] Nakkiran, Preetum, et al. "Sgd on neural networks learns functions of increasing complexity." arXiv preprint arXiv:1905.11604 (2019).

[2] Valle-Perez, Guillermo, Chico Q. Camargo, and Ard A. Louis. "Deep learning generalizes because the parameter-function map is biased towards simple functions." arXiv preprint arXiv:1805.08522 (2018).

[3] Xu, Keyulu, et al. "Representation learning on graphs with jumping knowledge networks." International conference on machine learning. PMLR, 2018.

[4] Tang, Xianfeng, et al. "Investigating and mitigating degree-related biases in graph convoltuional networks." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[5] Graph Neural Networks for Link Prediction with Subgraph Sketching, ICLR 2023

[6] Link Prediction Based on Graph Neural Networks, NeurIPS 2018

[7] Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning, NeurIPS 2020

Dear Authors,

I am checking your paper and have several questions, which can hopefully get your further clarification.

Motivation I read the abstract, introduction, and related work several times, but failed to find a concrete motivation. Based on my understanding, the motivation comes from the challenges of the research question and drawbacks of existing solutions. I am eager to know which challenges this paper targets to solve and how difficult they are, and why the existing solutions cannot be adapted to solve these challenges, or why the targeted gap is important. Here I am asking for the motivation, rather than the research question or solutions. Please do not repeat some sentences like the last part of the first paragraph in related work, which does not help with this concern.

PA What is preferential attachment? Could you provide a formal definition or equation? Further, what is the new type of unfairness in this paper? Any formal definition or equation?

Metric What metrics are used for evaluating the unfairness?

Look forward to hearing from the authors. Thank you.

Kind Regards,

AC

We thank the area chair for their questions and are happy to provide clarification. We begin by explaining preferential attachment, before elaborating on our motivation and how we define unfairness.

PA: Preferential attachment describes the propensity of links to form with high-degree nodes (https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_prediction.preferential_attachment.html). Network scientists have studied for decades how links in real-world networks exhibit preferential attachment. For example, in the iterative Barabasi-Albert model of network formation, each new node $s$ forms links with existing nodes $t$ with probability proportional to the degree of $t$, i.e., $Pr((s, t) \in {\cal E}) \propto deg(t)$. In the context of our paper, preferential attachment describes how a GCN (with an inner product score function) often predicts links between nodes $i, j$ with score $\propto \sqrt{deg(i) \cdot deg(j)}$ (Eq. 7).

Motivation: A wealth of literature in network science and the social sciences has examined the preferential attachment properties of real-world networks and how these properties contribute to unfair (non-neural) algorithms. For example, [1] finds that Instagram accounts run by men have a significantly higher following than those run by women due to gender discrimination; this degree disparity is only amplified by link recommendation algorithms that suggest accounts to follow (i.e., recommending accounts with higher degree to follow, which makes the rich get richer), revealing that these algorithms have a preferential attachment bias. Moreover, many papers outside graph learning have discussed the intersectional unfairness of machine learning.

However, despite the increasing real-world deployment of graph neural networks (GNNs) for link prediction, their unfairness has not been studied from the perspectives of preferential attachment and intersections of social groups. Our paper fills this gap by providing thorough theoretical and empirical evidence that GCNs (an extremely popular GNN architecture with 28843 citations) have a preferential attachment bias when predicting links between nodes in the same social group. This finding is nontrivial and as GCNs leverage a combination of features and local structural context to make link predictions.

This research question is challenging from a technical perspective, as it requires uncovering properties of short random walks on graphs (since most GNNs are shallow) with social aspects in mind; in contrast, most random walk results in the literature concern random walks at convergence. This is further an important research question because GNNs with a preferential attachment bias can amplify degree disparities, which translates to increased discrimination and disparities in social influence among nodes.

As we uncover this new form of unfairness, there are no existing solutions to this unfairness in the literature. We propose a training-time regularization-based fairness method that alleviates this unfairness without greatly sacrificing the test AUC of link prediction. While we describe methods for alleviating degree bias in the “Degree bias in GNNs” paragraph in our Related Work section, these methods address degraded performance for low-degree nodes, not preferential attachment bias. We do not study performance issues but rather how GCN scales node representations proportionally to the square root of their within-group degree, which affects the magnitude of their link prediction scores.

In summary, we augment the field’s understanding of degree biases beyond performance disparities across nodes. We further lay a foundation to study preferential attachment biases and within-group unfairness in GNN link prediction, which is a critical direction of research.

Unfairness and Metric: We formally define our new type of unfairness via our unfairness metric in Eq. 9. This metric quantifies disparities in how a GNN allocates link prediction scores between social subgroups (i.e., are links with nodes in one subgroup predicted at a higher rate than links with nodes in the other subgroup?). Our metric is motivated by how GNN link predictions (e.g., in recommender systems) influence real-world link formation, which has consequences for degree and power disparities.

We use Eq. 9 to evaluate unfairness. We cannot simply adopt common fairness metrics like node-wise equal opportunity or dyadic fairness, as they do not capture the new type of unfairness that we uncover.

Please let us know if we can answer any additional questions.

[1] Stoica, Ana-Andreea, Christopher Riederer, and Augustin Chaintreau. "Algorithmic glass ceiling in social networks: The effects of social recommendations on network diversity." Proceedings of the 2018 World Wide Web Conference. 2018.