PaperlayerView exact revision on arXiv

Source-linked AI summary

Fairness in Graph Mining: A Survey

Yushun Dong, Jing Ma, Song Wang, Chen Chen, Jundong Li

arXiv:2204.09888v3cs.LGcs.CY

TL;DR

Graph mining lacks fairness considerations, while graph-specific fairness notions and techniques remain difficult to organize. This survey develops a taxonomy and systematically reviews fairness-promoting techniques and benchmark datasets, offering a structured foundation for research in fair graph mining.

  • Problem

    Graph mining lacks fairness considerations, and inconsistent graph-specific fairness notions impede systematic progress toward fair algorithms.

  • Method

    The survey proposes a five-group fairness taxonomy, reviews six groups of fairness-promoting techniques, and summarizes widely used benchmark graph datasets.

  • Results

    The survey systematically organizes fairness notions, techniques, and datasets across fair graph mining research.

  • Takeaways & Limitations

    The survey provides a structured reference for understanding fairness notions and techniques and for supporting future advances in fair graph mining.

  • Takeaways & Limitations

    Fairness-promoting strategies can degrade downstream utility, making the trade-off between fairness and utility an important research challenge.

Abstract

from arXiv · show

Graph mining algorithms have been playing a significant role in myriad fields over the years. However, despite their promising performance on various graph analytical tasks, most of these algorithms lack fairness considerations. As a consequence, they could lead to discrimination towards certain populations when exploited in human-centered applications. Recently, algorithmic fairness has been extensively studied in graph-based applications. In contrast to algorithmic fairness on independent and identically distributed (i.i.d.) data, fairness in graph mining has exclusive backgrounds, taxonomies, and fulfilling techniques. In this survey, we provide a comprehensive and up-to-date introduction of existing literature under the context of fair graph mining. Specifically, we propose a novel taxonomy of fairness notions on graphs, which sheds light on their connections and differences. We further present an organized summary of existing techniques that promote fairness in graph mining. Finally, we summarize the widely used datasets in this emerging research field and provide insights on current research challenges and open questions, aiming at encouraging cross-breeding ideas and further advances.

1 INTRODUCTION

Graph mining advances across many applications but often overlook fairness, potentially producing discriminatory outcomes in human-centered settings. This survey organizes fairness notions, techniques, resources, and open challenges to support fair graph mining research.

  • Most graph mining algorithms lack fairness considerations and may discriminate against populations in human-centered applications such as job recommendation.Examples include recommending fewer job opportunities to people of a certain gender or underrepresented ethnic group.
  • Fairness in graph mining is non-trivial because i.i.d.-data fairness notions may not reflect bias exhibited by relationships in graphs.The introduction identifies formulating proper fairness criteria as a central challenge.
  • The survey proposes a taxonomy covering five fairness groups: group, individual, counterfactual, degree-related, and application-specific fairness.Definitions and common quantitative metrics are presented for each group.
  • The survey reviews six technique groups for promoting fairness in graph mining algorithms and summarizes representative formulations under different fairness notions.It aims to clarify mappings between fairness notions and fairness-fulfilling techniques.
  • The survey compiles algorithms and benchmark datasets, identifies current limitations and pressing challenges, and discusses open research questions for further advances.These resources are intended to facilitate development of new fair graph mining approaches.

2 NOTATIONS AND PRELIMINARIES

This section defines the paper’s notation conventions and establishes that individuals are represented as graph nodes by default, while allowing discussion of other scenarios.

  • Notations: The paper defines notation conventions for matrices, vectors, sets, matrix entries, and transposes used throughout the survey.Matrices and vectors use bold uppercase and lowercase letters, sets use calligraphic letters, A_i,j denotes a matrix entry, and A⊤ denotes transpose.
  • Preliminaries: Individuals are represented as nodes in a graph by default, although the survey also considers other scenarios.Additional clarifications for these scenarios are provided elsewhere in the paper.

3 FAIRNESS NOTIONS IN GRAPH MINING

The section proposes a five-group taxonomy of fairness notions in graph mining and organizes the corresponding fairness metrics. It covers group-fairness criteria for prediction, clustering, and influence, as well as counterfactual fairness on graphs.

  • Taxonomy: The survey organizes graph-mining fairness notions into five groups and introduces their corresponding metrics.This taxonomy is presented in Fig. 2.
  • Group Fairness: Demographic parity requires equal prediction or connection rates across sensitive subgroups, with extensions to multi-class, link-prediction, and continuous sensitive features.For continuous sensitive features, Generalized Demographic Parity quantifies fairness using a discrepancy measure, where smaller values indicate higher fairness.
  • Group Fairness: Equality of odds requires equal true-positive and false-positive rates across sensitive subgroups, whereas equality of opportunity requires equal positive prediction rates among individuals with positive ground-truth labels.Equality of opportunity is associated with avoiding disadvantaged predictions for qualified individuals and is commonly measured by the difference in positive prediction rates.
  • Clustering and Influence Fairness: Fairness in graph clustering requires sensitive subgroups to be proportionally represented within each cluster, while maxmin fairness seeks to maximize the minimum subgroup influence.The balance score is a common clustering fairness metric, whereas Umin quantifies maxmin fairness but may reduce total-population influence.
  • Counterfactual Fairness: Counterfactual fairness on graphs evaluates whether predictions change when sensitive feature values or assignments are altered while other features remain fixed.Common measures include the percentage of nodes whose predicted labels change and the average prediction discrepancy across counterfactual assignments.

4 TECHNIQUES FOR IMPROVING FAIRNESS

The survey organizes fairness-improving graph-mining techniques into six categories: regularization, constraints, rebalancing, adversarial learning, edge rewiring, and orthogonal projection. It explains how these methods promote application-agnostic and application-specific fairness, including through output, topology, counterfactual, and popularity-based regularization.

  • Technique taxonomy: The taxonomy comprises optimization with regularization, optimization with constraints, rebalancing, adversarial learning, edge rewiring, and orthogonal projection.The categories are summarized in Fig. 3.
  • Optimization with regularization: Regularization adds a fairness term to the utility objective, with λ controlling its influence, and can exploit graph relational information beyond i.i.d. debiasing.The pipeline steers optimization toward regions with higher fairness.
  • Optimization with regularization: Regularization promotes group fairness through output-based parity or opportunity terms and topology-based penalties that equalize propagated feature averages across sensitive subgroups.Topology-based regularization is also used in link prediction.
  • Optimization with regularization: Other regularizers target individual, counterfactual, and popularity fairness by aligning similar nodes, factual and counterfactual embeddings, or predicted relevance with item popularity.Wasserstein distance can improve group and individual fairness, while popularity regularization reduces the advantage of popular items.
  • Rebalancing: Rebalancing promotes fairness by balancing node appearances across sensitive groups in random walks and increasing low-degree nodes’ access to labeled neighborhood information.Fairwalk balances minority and majority appearances, while pseudo labels improve labeled-node exposure for low-degree nodes.
  • Orthogonal projection: Orthogonal projection removes correlation between potentially biased node features and topological embeddings, but guarantees only this decorrelation.The cited passage presents this as a limitation of the technique.

5 RESEARCH CHALLENGES

Current fair graph mining research faces open challenges in defining comprehensive fairness notions, simultaneously promoting multiple fairness types, and balancing fairness with model utility. These challenges motivate further study of bias, discrimination, and fairness–utility trade-offs in real-world graph applications.

  • Formulating Fairness Notions: Fairness notions remain incomplete because graph-mining discrimination can take diverse forms across real-world applications.Future work should formulate additional fairness notions to capture biases that depend on application needs.
  • Fulfilling Multiple Types of Fairness: Promoting multiple fairness types simultaneously is urgent but non-trivial because improving one type may degrade others.Group fairness and individual fairness can sometimes be promoted together, but their joint optimization remains challenging.
  • Balancing Model Utility and Algorithmic Fairness: Fairness-aware algorithms often sacrifice utility, making the trade-off between algorithmic fairness and prediction accuracy a critical research problem.Regularization can move solutions away from the utility-optimal unregularized solution, while adversarial learning may remove useful information from embeddings or predictions.

6 CONCLUSION

Graph mining has achieved major real-world success, but its lack of fairness considerations raises concerns about discrimination in predictions and decisions. This survey organizes efforts to define, measure, and promote fairness through a novel taxonomy of fairness notions.

  • 6 CONCLUSION: The survey proposes a novel taxonomy of fairness notions in graph mining research amid growing concerns that graph algorithms may discriminate in real-world predictions and decisions.It situates this contribution within broader efforts to define, measure, and promote fairness in graph mining.

APPENDIX A TECHNIQUES COMPARISON UNDER SAME FAIR- · NESS NOTIONS · A.1 Group Fairness

The surveyed literature uses multiple techniques to achieve group fairness in graph mining. These techniques fulfill group fairness through different mechanisms.

  • A.1 Group Fairness: Group fairness is addressed through regularization, constraints, rebalancing, adversarial learning, edge rewiring, and orthogonal projection.
  • A.1 Group Fairness: Regularization-based optimization and adversarial learning directly enforce fairness-aware objectives during graph mining optimization.
  • A.1 Group Fairness: The surveyed techniques differ in how they fulfill group fairness.

A.2 Individual Fairness

Individual fairness in graph mining can be promoted through regularization, constraints, or edge rewiring, which respectively penalize bias, define fair feasible sets, or directly modify graph edges.

  • A.2 Individual Fairness: Regularization-based optimization promotes individual fairness by penalizing exhibited bias under a specified fairness notion.
  • A.2 Individual Fairness: Constraint-based optimization promotes individual fairness by first defining a feasible set considered fair according to a specified fairness notion.
  • A.2 Individual Fairness: Edge rewiring promotes individual fairness by directly modifying the graph’s edges.

A.3 Fairness in Recommender Systems

Fairness in recommender systems is pursued through optimization with regularization, rebalancing, and edge rewiring. These techniques penalize exhibited unfairness or adjust input data to balance the appearance rates of instances across groups.

  • The surveyed literature adopts regularization, rebalancing, and edge rewiring to promote fairness in recommender systems.
  • Regularization penalizes exhibited unfairness during optimization, while rebalancing generally adjusts input data to balance instance appearance rates across groups.

A.4 Fairness in Knowledge Graphs

Fairness in knowledge graphs can be promoted through regularization-based optimization or adversarial learning, which share a fairness-aware optimization objective but formulate it differently.

  • A.4 Fairness in Knowledge Graphs: Regularization-based optimization and adversarial learning are two approaches for enforcing fairness in knowledge graphs.Both approaches target fairness during optimization of the graph mining algorithm.
  • A.4 Fairness in Knowledge Graphs: Both approaches incorporate a fairness-aware objective function into graph mining optimization.
  • A.4 Fairness in Knowledge Graphs: Regularization requires mathematically formulating the fairness goal according to fairness notions, whereas adversarial learning formulates it through performance.

APPENDIX B EFFECTIVENESS OF THE SURVEYED TECHNIQUES

The surveyed techniques show varied effectiveness across fairness and utility objectives, with performance depending on datasets, models, application scenarios, and assumptions. Adversarial learning, edge rewiring, and orthogonal projection can improve fairness, but each has documented limitations.

  • Rebalancing: Rebalancing is widely effective for fairness but can produce large fairness variances, lower competitiveness, and stronger dependence on application scenarios.The strategy is primarily tailored to specific application settings, which limits generality.
  • Adversarial Learning: Adversarial learning effectively improves fairness, but balancing prediction utility and fairness can be difficult, and utility may be clearly jeopardized.The surveyed results support higher fairness levels while documenting utility trade-offs.
  • Edge Rewiring: Edge rewiring can stably improve prediction fairness while maintaining utility, yet may be less competitive than baselines in some cases.Its limited exploration is partly attributed to the difficulty of optimizing binary edge-rewiring solutions with gradient-based methods.
  • Orthogonal Projection: Orthogonal projection can achieve high fairness, but existing studies mostly assume linear relationships between sensitive attributes and predictions.The fairness impact of nonlinear dependencies remains under-explored.

APPENDIX C ONLINE RESOURCES

The appendix provides benchmark datasets organized into four network categories and directs researchers to PyGDebias for fairness-aware graph mining implementations and performance leaderboards.

  • Benchmark Datasets: Benchmark datasets are grouped into social, recommendation-based, academic, and other network categories.These categories are summarized in Table 3.
  • Popular Algorithms: PyGDebias is an open-source library for comparing and selecting graph mining algorithms with fairness considerations.The library facilitates the usage of different fairness-aware algorithms.
  • Online Resources: The PyGDebias repository provides benchmark datasets, fairness-aware graph mining implementations, and performance leaderboards across fairness notions.The resources are available at https://github.com/yushundong/PyGDebias.
Loading 2204.09888v3…