PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards a Unified Framework for Fair and Stable Graph Representation Learning

Chirag Agarwal, Himabindu Lakkaraju, Marinka Zitnik

arXiv:2102.13186v3cs.LG

TL;DR

GNN representations used in real-world applications need protection against discriminatory bias and instability under graph or attribute perturbations. NIFTY unifies counterfactual fairness and stability through a similarity-based objective over augmented graphs and layer-wise weight normalization, achieving substantial average improvements without sacrificing predictive performance. The framework is supported by theoretical analysis and experiments on new criminal-justice and financial-lending datasets.

  • Problem

    GNN representations used in real-world applications need protection against discriminatory bias and instability under graph or attribute perturbations.

  • Method

    NIFTY unifies counterfactual fairness and stability using a similarity-based objective over augmented graphs and layer-wise weight normalization based on the Lipschitz constant.

  • Results

    92.01% fairness improvement and 60.87% stability improvement were achieved on average across five GNNs without sacrificing predictive performance.

  • Takeaways & Limitations

    NIFTY provides a unified framework whose representations are theoretically stable and counterfactually fair, with experiments spanning criminal justice and financial lending datasets.

  • Takeaways & Limitations

    The counterfactual fairness construction changes only the sensitive attribute while keeping all other node and graph information constant.

Abstract

from arXiv · show

As the representations output by Graph Neural Networks (GNNs) are increasingly employed in real-world applications, it becomes important to ensure that these representations are fair and stable. In this work, we establish a key connection between counterfactual fairness and stability and leverage it to propose a novel framework, NIFTY (uNIfying Fairness and stabiliTY), which can be used with any GNN to learn fair and stable representations. We introduce a novel objective function that simultaneously accounts for fairness and stability and develop a layer-wise weight normalization using the Lipschitz constant to enhance neural message passing in GNNs. In doing so, we enforce fairness and stability both in the objective function as well as in the GNN architecture. Further, we show theoretically that our layer-wise weight normalization promotes counterfactual fairness and stability in the resulting representations. We introduce three new graph datasets comprising of high-stakes decisions in criminal justice and financial lending domains. Extensive experimentation with the above datasets demonstrates the efficacy of our framework.

1 INTRODUCTION

GNN representations support high-stakes applications but can inherit or amplify discriminatory bias and instability. NIFTY unifies counterfactual fairness and stability, enforcing both through its objective and architecture while improving fairness and stability without sacrificing predictive performance.

  • Motivation: GNNs increasingly support critical applications, creating a need for representations that are fair and robust to graph and attribute perturbations.Applications include protein interaction prediction, drug repurposing, crime forecasting, and recommendations.
  • Motivation: Message passing can amplify discriminatory bias because connected nodes with similar sensitive attributes tend to receive similar representations.This can make downstream predictions highly correlated with sensitive attributes.
  • Research gap: Prior work largely treated fairness and stability as separate problems, leaving their deeper connection and simultaneous achievement open.Existing examples separately promote group fairness or robustness to adversarial attacks.
  • Contribution: NIFTY connects counterfactual fairness with stability and applies the connection to any existing GNN through a joint objective and architectural enforcement.The objective maximizes similarity between original nodes and counterparts in augmented graphs created through attribute, edge, and counterfactual modifications.
  • Results: 92.01% fairness improvement and 60.87% stability improvement were achieved on average across five GNNs without sacrificing predictive performance.The evaluation uses three new datasets involving criminal justice and financial lending decisions.

2 RELATED WORK

Related work spans fairness notions, graph representation learning, and separate approaches to fairness or stability in GNNs. These strands motivate a unified treatment of fair and stable graph representations.

  • Scope: The paper positions its contribution at the intersection of fairness and stability in machine learning and GNNs.This framing connects the fairness, graph-learning, and robustness literatures.
  • Fairness: Fairness research distinguishes group fairness, individual fairness, and counterfactual fairness.These notions respectively concern treatment across groups, similar treatment for similar individuals, and invariance to sensitive-attribute changes.
  • Graph Neural Networks: GNNs learn node embeddings whose geometry reflects graph topology and node attributes through transformations that exchange information across neighboring nodes.GCNs apply local neighborhood transformations, while later methods use skip connections, adaptive node weighting, or mutual-information objectives.
  • Fairness and Stability in GNNs: Existing GNN fairness methods primarily debias embeddings with respect to sensitive attributes using adversarial learning and group-fairness regularization.The related-work discussion places these methods alongside separate research on GNN stability.

3 PRELIMINARIES

The preliminaries define graph notation, augmented graphs, GNN representations, counterfactual fairness, and Lipschitz stability. These definitions establish the objects and invariances targeted by NIFTY.

  • Notation: A graph G=(V,E,X) contains nodes, edges, and node attributes, while each node’s combined information includes its attributes and incident-edge vector.The augmented graph G′ perturbs attributes and/or edges and includes corresponding nodes.
  • GNN representations: A K-layer GNN produces intermediate representations h^k_u, with z_u denoting the final-layer representation for node u.The same node in the augmented graph has representation ˜z_u.
  • GNN representations: Message-passing GNNs recursively exchange, aggregate, and transform embeddings through message, aggregation, and update operators.These operators are applied across K layers to obtain final node representations.
  • Fairness and stability: Counterfactual fairness requires an encoder’s representation to remain independent of a node’s sensitive attribute.The counterfactual node ˜u_s flips the sensitive attribute while keeping everything else constant.
  • Fairness and stability: Lipschitz stability requires small perturbations to attributes or incident edges to avoid drastic changes in the resulting representation.The Lipschitz constant L bounds representation change relative to the change in node information.

4 OUR FRAMEWORK NIFTY

NIFTY jointly enforces fairness and stability through a Siamese, triplet-based objective and Lipschitz-normalized GNN architecture. It creates counterfactual and noisy graph views, aligns their embeddings, and bounds representation changes under perturbations.

  • NIFTY infuses fairness and stability into both the training objective and the architecture of an underlying GNN.
  • Objective function: The objective maximizes agreement between embeddings from the original graph and counterfactual or noisy views using a Siamese framework.
  • Graph augmentation: NIFTY generates augmented views through non-sensitive attribute perturbations, sensitive-attribute counterfactuals, and edge dropping.
  • Objective function: A predictor transforms representations, while cosine-distance matching with stopgrad prevents gradients from propagating through the counterpart representation.
  • Objective function: The overall objective combines downstream binary cross-entropy classification loss with the triplet-based loss, controlled by regularization coefficient λ.
  • Architecture: Lipschitz normalization of layer weights bounds embedding differences between original and perturbed inputs and connects stability with counterfactual fairness.

5 THEORETICAL ANALYSIS OF NIFTY

The theoretical analysis establishes stability and bounds representation unfairness under Lipschitz-continuous activations and normalized weights. It also shows that counterfactually fair NIFTY representations yield counterfactually fair downstream classifiers.

  • The analysis proves that NIFTY representations are stable, provides an upper bound on representation unfairness, and establishes counterfactual fairness for downstream classifiers.
  • Stability theorem: The stability theorem assumes a Lipschitz-continuous activation function and concludes that NIFTY representations are stable.
  • Stability proof: NIFTY’s encoder is a composition of layer-wise Lipschitz message-passing functions, whose combined constant is the product of their individual constants.
  • Stability proof: For p = 2, the encoder’s Lipschitz constant equals the product of the weight matrices’ largest singular values, motivating spectral normalization at each layer.
  • Counterfactual fairness theorem: The counterfactual fairness theorem considers a binary sensitive attribute whose value is flipped while all other node information remains constant.
  • Downstream classifier: If NIFTY representations satisfy counterfactual fairness, a downstream classifier using those representations also satisfies counterfactual fairness.

6 EXPERIMENTS

Experiments evaluate NIFTY across three graph datasets, five GNN backbones, fairness and stability metrics, predictive performance, regularization, and component ablations. Across these evaluations, NIFTY improves fairness and stability while preserving predictive performance, with both its objective and architecture contributing.

  • Datasets and experimental setup: Experiments compare five GNN methods across three graph datasets using predictive, fairness, and stability measures.The evaluation includes AUROC and F1-score, counterfactual unfairness and instability, and group-fairness metrics ∆SP and ∆EO.
  • Results: NIFTY-enhanced GNNs learn fairer and more stable embeddings than their unmodified counterparts across all datasets and backbones.Figure 2 reports this comparison for five GNNs across the three datasets.
  • Results: 60.87% average stability improvement and 92.01% average fairness improvement occur without sacrificing predictive performance.Predictive preservation is assessed using AUROC and F1-scores.
  • Results: NIFTY outperforms FairGCN and RobustGCN by 62.07% and 57.26%, respectively, on four fairness and stability metrics.Table 1 averages performance across five independent runs and notes that FairGCN cannot assess counterfactual fairness.
  • Results: Across datasets, NIFTY achieves 43.56% lower ∆SP and 34.70% lower ∆EO, while also improving both metrics over baseline methods.Compared with baselines, ∆SP is 36.05% lower and ∆EO is 29.71% lower.
  • Trade-offs and ablation: Increasing λ lowers fairness and stability error rates but eventually reduces predictive performance; both NIFTY’s objective and Lipschitz normalization are necessary for jointly fair and stable embeddings.At λ = 0.1, unfairness improves by 94.29%; the ablation reports a 90.7% fairness improvement for NIFTY-GCN over vanilla GCN.

7 CONCLUSIONS & FUTURE WORK

NIFTY unifies fairness and stability through a connection between counterfactual fairness and stability, modifying existing GNNs at both architectural and objective-function levels. The framework improves fairness and stability on criminal-justice and financial-lending graph datasets while preserving predictive performance.

  • NIFTY modifies existing GNNs through a two-level strategy combining architectural changes with objective-function changes.The framework is designed to learn representations satisfying both fairness and stability.
  • Theoretical analysis shows that NIFTY-learned representations are counterfactually fair and stable.
  • Experiments on new criminal-justice and financial-lending graph datasets show improved counterfactual fairness, group fairness, and stability without sacrificing predictive performance.
  • Future work includes extending NIFTY to edges and subgraphs and to downstream tasks such as link prediction and graph classification.

A PROPOSITION 1 AND ITS PROOF

If NIFTY representations are counterfactually fair, a downstream classifier using those representations is also counterfactually fair. The proof uses the Markov chain from node attributes through representations to predictions and mutual-information inequalities.

  • A downstream classifier using a counterfactually fair NIFTY representation also satisfies counterfactual fairness.
  • The proof models the pipeline as the Markov chain x_u → z_u → ŷ_u.
  • Counterfactual fairness is defined by independence between the sensitive attribute s and representation z_u, expressed as I(s; z_u) = 0.
  • Because 0 ≤ I(s; ŷ_u) ≤ I(s; z_u), zero mutual information for the representation implies zero mutual information for the prediction.

B DATASET DETAILS

The paper constructs three graph datasets for fairness- and stability-aware node classification: German credit, recidivism, and credit default. Each graph connects individuals using attribute similarity, with sensitive attributes relevant to fairness evaluation.

  • German Credit Graph: The German credit graph contains 1,000 clients labeled as good or bad credit risks, with attributes including gender and loan amount.
  • For these datasets, graph edges are constructed using Minkowski distance as the attribute-similarity measure.
  • Recidivism Graph: The recidivism graph contains 18,876 defendants released on bail, with criminal records, demographic attributes, and other details collected from US state courts between 1990 and 2009.
  • Recidivism Graph: Race is used as the protected attribute in the recidivism graph because fair predictions should be independent of the defendant’s race.
  • Credit Defaulter Graph: The credit defaulter graph contains 30,000 individuals, and the task is predicting whether an applicant will default on an upcoming credit-card payment.

C ARCHITECTURE AND HYPERPARAMETER SELECTION

The experiments use a GNN-based encoder, projection head, predictor, and downstream classifier, with fixed perturbation and optimization settings. Figure 4 examines how self-supervised regularization affects predictive, stability, and fairness metrics across three graphs.

  • Architecture: The framework architecture includes an encoder, a projection head, a predictor, and a downstream classifier.
  • Encoder: The encoder can use an MLP or GNN variant; experiments use a single-layer GNN with hidden dimensionality 16 and a two-layer MLP projection head.
  • Predictor and classifier: The predictor is a single-layer MLP with hidden dimensionality 16, while the downstream classifier is a single fully connected layer with sigmoid activation.
  • Hyperparameters: Experiments perturb feature dimensions with probability p_n = 0.1 and drop edges with probability p_e = 0.001.
  • Hyperparameters: Training uses Adam with learning rate 1 × 10^-3, weight decay 1 × 10^-5, and 1000 epochs.
  • Regularization analysis: Figure 4 varies the regularization coefficient and tracks AUROC, F1-score, stability, and fairness for NIFTY-GIN on three graph datasets.
Loading 2102.13186v3…