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

Overview

• This paper explores how the degree bias in networks affects Graph Convolutional Network (GCN) link prediction.
• The researchers uncover that GCNs with a symmetric normalized graph filter have a within-group preferential attachment bias, which can lead to unfairness in link prediction.
• They propose a new within-group fairness metric and a training-time strategy to alleviate this unfairness in citation, social, and credit networks.

Plain English Explanation

Graph neural networks (GNNs) are increasingly used in various applications like recommending academic papers, suggesting collaborators, and finding friends on social networks. Prior research has looked at fairness in GNN link prediction at the individual level, but the fairness within social groups (e.g., queer women) and the "rich get richer" dynamics have not been well explored.

This is important because these factors can contribute to imbalances in network power and influence. In this paper, the researchers shed light on how the inherent bias towards high-degree nodes in networks affects GCN, a type of GNN, and its link prediction performance.

They show that GCNs with a particular graph filter have a built-in preference for connecting to nodes with many existing connections. This can amplify the differences in the number of connections (degrees) between social groups, leading to unfairness.

To address this, the researchers propose a new metric to quantify the unfairness within social groups. They also develop a simple training technique to reduce this unfairness, which they demonstrate is effective on citation, social, and credit networks.

Technical Explanation

The researchers theoretically analyze Graph Convolutional Networks (GCNs) with a symmetric normalized graph filter and show that they exhibit a within-group preferential attachment bias. This means that GCNs tend to create more links between nodes that already have many connections, exacerbating power imbalances in the network.

To validate their theoretical findings, the researchers conduct experiments on real-world citation, collaboration, and online social networks. They find that the degree bias in these networks does indeed lead to unfairness in GCN link prediction, with certain social groups being disadvantaged.

To address this issue, the researchers propose a new within-group fairness metric that quantifies the disparities in link prediction scores within social groups. This metric can be used to evaluate and improve the fairness of GCN link prediction.

The researchers also introduce a simple training-time strategy to alleviate the within-group unfairness in GCN link prediction. This strategy is shown to be effective in improving fairness on the citation, social, and credit networks studied.

Critical Analysis

The researchers provide a comprehensive theoretical and empirical analysis of the degree bias in GCN link prediction and its implications for fairness. However, the paper does not explore the potential causes of this bias in depth, such as the role of the graph convolutional filter or the properties of the input networks.

Additionally, while the proposed fairness metric and training-time strategy are promising, their effectiveness may be limited to the specific networks and social group definitions used in the experiments. Further research is needed to understand the generalizability of these approaches and their performance on a wider range of networks and group definitions.

The paper also does not discuss the potential trade-offs between fairness and other desirable properties of link prediction, such as accuracy or efficiency. Exploring these trade-offs could provide valuable insights for practitioners seeking to balance these competing objectives.

Conclusion

This paper provides important theoretical and empirical insights into the degree bias in GCN link prediction and its consequences for fairness within social groups. The researchers' findings highlight the need to consider group-level fairness in addition to individual-level fairness when deploying GNNs in real-world applications.

The proposed fairness metric and training-time strategy offer promising approaches to mitigate these biases, but further research is needed to fully understand their limitations and applicability. As GNNs become increasingly ubiquitous, addressing these fairness concerns will be crucial for ensuring that these powerful models benefit all members of society equitably.