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

• URL: http://arxiv.org/abs/2309.17417v2
• Date: Tue, 4 Jun 2024 23:47:06 GMT
• Title: Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction
• Authors: Arjun Subramonian, Levent Sagun, Yizhou Sun,
• Abstract summary: We study how degree bias in networks affects Graph Convolutional Network (GCN) link prediction. GCNs with a symmetric normalized graph filter have a within-group preferential attachment bias. We propose a new within-group fairness metric, which quantifies disparities in link prediction scores within social groups.
• Score: 44.00932300499947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural network (GNN) link prediction is increasingly deployed in citation, collaboration, and online social networks to recommend academic literature, collaborators, and friends. While prior research has investigated the dyadic fairness of GNN link prediction, the within-group (e.g., queer women) fairness and "rich get richer" dynamics of link prediction remain underexplored. However, these aspects have significant consequences for degree and power imbalances in networks. In this paper, we shed light on how degree bias in networks affects Graph Convolutional Network (GCN) link prediction. In particular, we theoretically uncover that GCNs with a symmetric normalized graph filter have a within-group preferential attachment bias. We validate our theoretical analysis on real-world citation, collaboration, and online social networks. We further bridge GCN's preferential attachment bias with unfairness in link prediction and propose a new within-group fairness metric. This metric quantifies disparities in link prediction scores within social groups, towards combating the amplification of degree and power disparities. Finally, we propose a simple training-time strategy to alleviate within-group unfairness, and we show that it is effective on citation, social, and credit networks.

Related papers

• Towards Fair Graph Representation Learning in Social Networks [20.823461673845756]
  We introduce constraints for fair representation learning based on three principles: sufficiency, independence, and separation. We theoretically demonstrate that our EAGNN method can effectively achieve group fairness.
  arXiv  Detail & Related papers  (2024-10-15T10:57:02Z)
• Promoting Fairness in Link Prediction with Graph Enhancement [6.477859104817626]
  Link prediction is a crucial task in network analysis, but it has been shown to be prone to biased predictions. We study the fair link prediction problem, which aims to ensure that the predicted link probability is independent of the sensitive attributes of the connected nodes. We propose FairLink, a method that learns a fairness-enhanced graph to bypass the need for debiasing during the link predictor's training.
  arXiv  Detail & Related papers  (2024-09-13T09:18:29Z)
• Uncertainty in Graph Neural Networks: A Survey [50.63474656037679]
  Graph Neural Networks (GNNs) have been extensively used in various real-world applications. However, the predictive uncertainty of GNNs stemming from diverse sources can lead to unstable and erroneous predictions. This survey aims to provide a comprehensive overview of the GNNs from the perspective of uncertainty.
  arXiv  Detail & Related papers  (2024-03-11T21:54:52Z)
• Adversarial Attacks on Fairness of Graph Neural Networks [63.155299388146176]
  Fairness-aware graph neural networks (GNNs) have gained a surge of attention as they can reduce the bias of predictions on any demographic group. Although these methods greatly improve the algorithmic fairness of GNNs, the fairness can be easily corrupted by carefully designed adversarial attacks.
  arXiv  Detail & Related papers  (2023-10-20T21:19:54Z)
• Information Flow in Graph Neural Networks: A Clinical Triage Use Case [49.86931948849343]
  Graph Neural Networks (GNNs) have gained popularity in healthcare and other domains due to their ability to process multi-modal and multi-relational graphs. We investigate how the flow of embedding information within GNNs affects the prediction of links in Knowledge Graphs (KGs) Our results demonstrate that incorporating domain knowledge into the GNN connectivity leads to better performance than using the same connectivity as the KG or allowing unconstrained embedding propagation.
  arXiv  Detail & Related papers  (2023-09-12T09:18:12Z)
• BScNets: Block Simplicial Complex Neural Networks [79.81654213581977]
  Simplicial neural networks (SNN) have recently emerged as the newest direction in graph learning. We present Block Simplicial Complex Neural Networks (BScNets) model for link prediction. BScNets outperforms state-of-the-art models by a significant margin while maintaining low costs.
  arXiv  Detail & Related papers  (2021-12-13T17:35:54Z)
• wsGAT: Weighted and Signed Graph Attention Networks for Link Prediction [0.0]
  Graph Neural Networks (GNNs) have been widely used to learn representations on graphs and tackle many real-world problems. We propose wsGAT, an extension of the Graph Attention Network (GAT) layers, to handle graphs with signed and weighted links. Our results show that models with wsGAT layers outperform the ones with GCNII and SGCN layers, and that there is no loss in performance when signed weights are predicted.
  arXiv  Detail & Related papers  (2021-09-21T12:07:51Z)
• Harnessing the Power of Ego Network Layers for Link Prediction in Online Social Networks [0.734084539365505]
  Predictions are typically based on unsupervised or supervised learning. We argue that richer information about personal social structure of individuals might lead to better predictions. We show that social-awareness generally provides significant improvements in the prediction performance.
  arXiv  Detail & Related papers  (2021-09-19T18:49:10Z)
• Adversarial Robustness of Probabilistic Network Embedding for Link Prediction [24.335469995826244]
  We study adversarial robustness of Conditional Network Embedding (CNE) for link prediction. We measure the sensitivity of the link predictions of the model to small adversarial perturbations of the network. Our approach allows one to identify the links and non-links in the network that are most vulnerable to such perturbations.
  arXiv  Detail & Related papers  (2021-07-05T11:07:35Z)
• Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction [69.1473775184952]
  We introduce a realistic problem of few-shot out-of-graph link prediction. We tackle this problem with a novel transductive meta-learning framework. We validate our model on multiple benchmark datasets for knowledge graph completion and drug-drug interaction prediction.
  arXiv  Detail & Related papers  (2020-06-11T17:42:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.