PaperlayerView exact revision on arXiv

Source-linked AI summary

EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks

Yushun Dong, Ninghao Liu, Brian Jalaian, Jundong Li

arXiv:2108.05233v2cs.LG

TL;DR

GNN debiasing methods are often specific to particular models, motivating a model-agnostic alternative that debiases attributed-network inputs. The paper defines metrics for attribute and structural bias and introduces EDITS to mitigate them before GNN processing. Experiments report effective bias mitigation with little utility sacrifice across cases.

  • Problem

    Existing GNN debiasing approaches are tailored to specific models, while debiasing attributed-network inputs before GNN processing has not been studied.

  • Method

    EDITS defines attribute and structural bias metrics and debiases attributed networks before they are fed into any GNN.

  • Results

    EDITS achieves desirable bias mitigation with little utility sacrifice across cases compared with GNNs using the original network.

  • Takeaways & Limitations

    Debiasing the attributed network provides a model-agnostic way to mitigate bias in the outcomes of different GNNs.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have shown superior performance in analyzing attributed networks in various web-based applications such as social recommendation and web search. Nevertheless, in high-stake decision-making scenarios such as online fraud detection, there is an increasing societal concern that GNNs could make discriminatory decisions towards certain demographic groups. Despite recent explorations on fair GNNs, these works are tailored for a specific GNN model. However, myriads of GNN variants have been proposed for different applications, and it is costly to fine-tune existing debiasing algorithms for each specific GNN architecture. Different from existing works that debias GNN models, we aim to debias the input attributed network to achieve fairer GNNs through feeding GNNs with less biased data. Specifically, we propose novel definitions and metrics to measure the bias in an attributed network, which leads to the optimization objective to mitigate bias. We then develop a framework EDITS to mitigate the bias in attributed networks while maintaining the performance of GNNs in downstream tasks. EDITS works in a model-agnostic manner, i.e., it is independent of any specific GNN. Experiments demonstrate the validity of the proposed bias metrics and the superiority of EDITS on both bias mitigation and utility maintenance. Open-source implementation: https://github.com/yushundong/EDITS.

1 INTRODUCTION

GNNs can make biased decisions, while existing debiasing methods are tied to specific models and tasks. The paper instead targets bias in attributed-network inputs through model-agnostic metrics and the EDITS framework.

  • Existing GNN debiasing approaches are tailored to specific models and downstream tasks, making adaptation to different GNN variants costly.
  • The paper identifies data bias modeling, multi-modality debiasing, and model-agnostic debiasing as three central challenges.
  • EDITS models attribute and structural bias, then mitigates bias in attributed networks before they are fed into GNNs.
  • The framework is designed to produce less biased attributed networks for any GNN rather than optimize a specific GNN outcome.
  • Experiments on synthetic and real-world datasets evaluate the validity of the proposed metrics and the effectiveness of EDITS.

2 PRELIMINARY ANALYSIS

Bias can enter GNN information propagation through either node attributes or network structure. The analysis motivates separate modality-specific bias measures and debiasing processes before GNN training.

  • Node attributes and network structure are two data modalities that can introduce bias during GNN information propagation.
  • The analysis models attribute bias using differences between demographic groups’ attribute distributions.
  • Structural bias is modeled through differences in demographic groups’ attribute distributions after information propagation.
  • At least two debiasing processes are needed to target attributes and network structure separately.
  • If group attribute distributions are less biased before and after propagation, learned node representations tend to be less distinguishable between groups.

3 MODELING DATA BIAS FOR GNNS

The paper models two sources of attributed-network bias: differences in original attribute distributions and differences introduced or amplified by information propagation. It quantifies both with Wasserstein-based metrics and formulates model-agnostic network debiasing.

  • Attribute Bias: Attribute bias exists when attribute-value distributions differ between demographic groups.
  • Structural Bias: Structural bias exists when propagated attribute distributions differ between demographic groups at any attribute dimension.
  • Bias Metrics: The attribute-bias metric averages Wasserstein-1 distances between groups across normalized attribute dimensions.
  • Bias Metrics: The structural-bias metric similarly compares group distributions after several rounds of propagation using aggregated reachability.
  • Debiasing Objective: The debiasing problem reduces both metrics to produce a less biased attributed network independently of any specific GNN.

4 MITIGATING DATA BIAS FOR GNNS

EDITS jointly debiases node attributes and network structure before GNN training, using Wasserstein-based objectives and alternating gradient-based optimization. Its design preserves information and sparsity while producing a model-agnostic debiased network.

  • Framework Overview: EDITS alternates optimization of attribute debiasing, structural debiasing, and Wasserstein distance approximation modules.
  • Framework Overview: Attribute debiasing learns a function that transforms the attribute matrix, while structural debiasing optimizes a modified adjacency matrix initialized from the original.
  • Objective Function: The objective minimizes Wasserstein distance between joint propagated-attribute distributions for the two sensitive groups across attribute dimensions.
  • Objective Function: Kantorovich-Rubinstein duality converts the intractable Wasserstein objective into a tractable gradient-based optimization problem.
  • Optimization Design: The method uses a single-layer neural network to approximate each Wasserstein critic, linear attribute reweighting, and regularization toward original information and structure.
  • Optimization Design: Training uses SGD for the Wasserstein function and PGD with clipping for debiasing parameters and adjacency optimization, followed by attribute masking and edge binarization.

5 EXPERIMENTAL EVALUATIONS

Experiments evaluate EDITS across real-world and synthetic datasets, GNN variants, bias metrics, utility, and comparisons with model-specific debiasing baselines. EDITS generally reduces attributed-network and downstream bias while preserving utility and improving the utility–bias balance.

  • Experimental Settings: Experiments use six real-world and two synthetic datasets, with node classification evaluated using GCN, GraphSAGE, and GIN.The real-world datasets include social-network and credit-related tasks with sensitive attributes such as region and gender.
  • Bias Mitigation: EDITS reduces attribute and structural bias in attributed networks compared with vanilla inputs.Table 1 reports attribute and structural bias comparisons between original and EDITS-debiased networks, where lower values are better.
  • Downstream Performance: EDITS mitigates downstream bias with little utility sacrifice across different GNN backbones.Comparisons use ΔSP and ΔEO for GNNs trained on EDITS-debiased versus original networks.
  • Comparison with Other Debiasing Models: EDITS achieves comparable utility to baselines while providing similar or better bias mitigation.The comparison evaluates AUC and ΔSP, with similar conclusions reported for GNNs beyond the illustrated GCN setting.
  • Ablation Study: Ablation results show that attribute debiasing reduces attribute bias, while both modules can reduce structural bias and downstream ΔSP.Structural debiasing alone maintains comparable AUC and outperforms attribute-only debiasing for bias mitigation across the four selected datasets.

6 RELATED WORK

Related work covers group and individual fairness in machine learning and bias mitigation methods for graph mining. Existing approaches include processing-stage constraints, modified random walks, and representation-based adversarial methods.

  • Fairness in Machine Learning: Group fairness targets nondiscriminatory outcomes across demographic groups, whereas individual fairness emphasizes treating similar individuals similarly.Individual fairness may use expert-provided similarity scores and consistency as an evaluation metric.
  • Bias Mitigation in Graph Mining: Graph-mining debiasing methods modify algorithms or representations, including random-walk adjustments and adversarial learning.Adversarial approaches seek representations that are not distinguishable by sensitive attributes, while other methods impose prediction consistency constraints.

7 CONCLUSION

The paper proposes debiasing attributed networks rather than individual GNN models to address model-specific adaptation costs. EDITS defines attribute and structural bias metrics and aims to mitigate bias while maintaining model utility.

  • Conclusion: Existing GNN debiasing methods are tailored to specific models, making adaptation to different GNNs costly.The paper instead targets the attributed network input rather than each downstream GNN.
  • Conclusion: EDITS performs model-agnostic attributed-network debiasing using metrics for attribute and structural bias.The framework is based on analyzing bias across different data modalities in the network.
  • Conclusion: Experiments demonstrate bias mitigation and maintenance of model utility with EDITS.The conclusion reports these outcomes without restricting them to a single GNN architecture.

A.1 Datasets Statistics

The appendix provides detailed statistics for three real-world datasets: German Credit, Recidivism, and Credit Defaulter.

  • Datasets Statistics: Table 3 contains detailed statistics for German Credit, Recidivism, and Credit Defaulter.

A.2 Algorithm

Algorithm 1 initializes the attributed network and iteratively optimizes EDITS to produce debiased adjacency and attribute matrices. The procedure updates model weights and both data modalities, then applies masking and binarization before returning the debiased network.

  • Post-processing: The algorithm returns the debiased adjacency matrix ˜A and attribute matrix ˜X for downstream use.These are the two outputs specified by the procedure.
  • Initialization and optimization: EDITS initializes the adjacency matrix and optimization variables before entering an epoch-limited iterative procedure.The algorithm sets ˜A ← A and Θ ← I, then repeats updates while epoch ≤ epoch_max.
  • Initialization and optimization: Each iteration computes L1, updates f by SGD, clips its weights, and updates Θ by PGD to obtain ˜X = XΘ.The weight clipping threshold is c.
  • Post-processing: After optimization, EDITS masks the z smallest diagonal entries of Θ and binarizes ˜A using threshold r.The resulting matrices are returned as the debiased adjacency and attribute matrices.

A.3 Theoretical Analysis

The theoretical analysis interprets GNN propagation as graph filtering and connects attribute bias with structural bias. Under specified propagation parameters, the filter attenuates higher-frequency components more than lower-frequency components.

  • Theoretical setup: The analysis focuses on structural bias because zero Wasserstein distance between group attribute distributions removes distinguishing information for attribute bias.The attribute-bias case is treated as straightforward, while structural bias receives the main theoretical analysis.
  • Propagation as graph filtering: Theorem 1 states that multiplying X by M_H is equivalent to low-pass filtering when α = 1/λ_max and all β_i > 0.Here λ_max is the largest eigenvalue of the normalized Laplacian.
  • Propagation as graph filtering: The propagation matrix M_H has a frequency response composed of H low-pass filters because each response decreases monotonically with λ_i.Higher-frequency graph-signal components are weakened more than lower-frequency components.
  • Propagation as graph filtering: In the structural-bias metric, the graph signal being filtered is the attribute matrix X.This identifies the signal whose frequency components are affected by propagation.
  • Bias connection: Corollary 1 establishes that attribute bias in an attributed network’s low-frequency components is equivalent to structural bias.This corollary connects the two proposed bias notions through the filtering interpretation.
  • Bias connection: EDITS therefore targets the full graph-signal spectrum while learning frequencies and bases that further mitigate bias in lower-frequency components.The interpretation follows from jointly optimizing the network structure and attributes.

A.4 Implementation Details

The implementation evaluates EDITS on real-world and synthetic settings, including ternary sensitive attributes, using specified optimization settings and comparisons of fairness, utility, and parameter sensitivity. The experiments examine whether EDITS balances bias mitigation with predictive utility.

  • Implementation settings: EDITS uses PyTorch and RMSprop, with 100 training epochs for Recidivism and 500 for other datasets.Its learning rate is 3 × 10^-3 below epoch 400 and 1 × 10^-3 afterward.
  • Implementation settings: The GNN evaluations use 1,000 Adam-training epochs with learning rate 1 × 10^-3, dropout 0.05, and 16 hidden channels.These settings are reported for training the downstream GNNs.
  • Non-binary sensitive attributes: The non-binary extension generates a synthetic attributed network with at least three sensitive-attribute groups and evaluates pairwise group comparisons.The ternary sensitive attribute is represented by s ∈ {0, 1, 2}.
  • Non-binary sensitive attributes: Figure 5 compares ΔSP and ΔEO between vanilla and EDITS using GCN for ternary sensitive attributes.The figure is designed to compare fairness changes across the two conditions.
  • Non-binary sensitive attributes: Table 5 compares fairness and utility between the original and debiased synthetic networks, with b_attr and b_stru reported at scale ×10^-3.Best values are marked in bold.
  • Non-binary sensitive attributes: The reported ternary-attribute results indicate that EDITS balances fairness and utility for GNN predictions relative to the vanilla input.This conclusion is stated for the synthetic-network comparison.
  • Parameter sensitivity: The parameter study varies μ1 and μ3, which control preservation of original attribute information and graph-structure information, respectively.The study is conducted on the German dataset, with similar observations reported for other datasets.
Loading 2108.05233v2…