PaperlayerView exact revision on arXiv

Source-linked AI summary

Interpreting Unfairness in Graph Neural Networks via Training Node Attribution

Yushun Dong, Song Wang, Jing Ma, Ninghao Liu, Jundong Li

arXiv:2211.14383v1cs.LGcs.CY

TL;DR

GNN unfairness is difficult to interpret at the level of individual training nodes, although that understanding matters for debiasing. The paper proposes PDD and BIND to measure bias and estimate node influence; experiments support PDD, influence estimation, and a node-deletion debiasing strategy.

  • Problem

    Existing GNN work focuses on debiasing, while methods for interpreting predictions generally do not explain fairness or how individual training nodes influence model bias.

    Source: Introduction · p. 1

  • Method

    The paper proposes PDD to quantify bias in probabilistic outputs and BIND to estimate each training node’s influence without retraining.

    Source: Introduction · p. 2, Probabilistic Distribution Disparity · p. 2

  • Results

    Experiments support PDD’s consistency with traditional fairness metrics, the efficiency and effectiveness of influence estimation, and the debiasing strategy’s performance.

    Source: Conclusion · p. 7

  • Takeaways & Limitations

    The framework includes a node-deletion strategy for GNN debiasing based on estimated training-node influence.

    Source: Conclusion · p. 7

    The test-node representation bound is analyzed for GCN under stated assumptions, including equal norms, though the analysis is described as generalizable to other GNNs.

    Source: Non-I.I.D. Characterization · p. 4

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have emerged as the leading paradigm for solving graph analytical problems in various real-world applications. Nevertheless, GNNs could potentially render biased predictions towards certain demographic subgroups. Understanding how the bias in predictions arises is critical, as it guides the design of GNN debiasing mechanisms. However, most existing works overwhelmingly focus on GNN debiasing, but fall short on explaining how such bias is induced. In this paper, we study a novel problem of interpreting GNN unfairness through attributing it to the influence of training nodes. Specifically, we propose a novel strategy named Probabilistic Distribution Disparity (PDD) to measure the bias exhibited in GNNs, and develop an algorithm to efficiently estimate the influence of each training node on such bias. We verify the validity of PDD and the effectiveness of influence estimation through experiments on real-world datasets. Finally, we also demonstrate how the proposed framework could be used for debiasing GNNs. Open-source code can be found at https://github.com/yushundong/BIND.

Introduction

GNN predictions can exhibit bias toward demographic subgroups, with potentially destructive effects in high-stakes decisions. The paper addresses the gap between GNN debiasing and understanding how training nodes influence model bias.

Introduction

  • Existing GNN interpretation methods explain predictions rather than fairness, leaving the influence of individual training nodes on model bias unaddressed.Understanding that influence can help decide whether a node should be included in training and guide debiasing methods.Source: Introduction · p. 1
  • Traditional fairness metrics based on predicted labels are poorly suited to measuring a single training node’s influence, which may not change test predictions.Estimating influence by deleting a node and retraining is prohibitively expensive, while graph-neighbor dependencies further complicate analysis.Source: Introduction · pp. 1–2
  • BIND combines Probabilistic Distribution Disparity with an influence-estimation algorithm to quantify each training node’s influence on GNN model bias without retraining.The framework also characterizes dependencies between nodes through training-loss analysis.Source: Introduction · p. 2

Preliminaries

The preliminaries establish graph and model notation, then formulate unfairness interpretation as quantifying how each training node influences unfairness in a trained GNN’s test predictions.

Preliminaries

  • The preliminaries introduce notation before defining the problem of interpreting GNN unfairness through training-node influence.Source: Preliminaries · p. 2

Notations

  • The paper introduces notation for graph data, training nodes, trained GNN parameters, probabilistic predictions, labels, sensitive attributes, and computation graphs.The graph is G = {V, E, X}, and G−i denotes the graph with node vi deleted.Source: Notations · p. 2

Problem Statement

  • GNN unfairness interpretation is defined as quantifying each training node’s influence on unfairness in the model’s predictions on the test set.Source: Problem Statement · p. 2

Methodology

The methodology introduces PDD to measure model bias using probabilistic outputs, then estimates training-node influence by analyzing changes to the training objective and node dependencies. The algorithm has quadratic complexity in the number of training nodes.

Probabilistic Distribution Disparity

  • PDD measures disparity between probabilistic-output distributions across sensitive subgroups, enabling finer-grained assessment of node influence than predicted-label fairness metrics.It uses Wasserstein-1 distance, can instantiate different fairness notions, and a larger PDD indicates greater model bias.Source: Probabilistic Distribution Disparity · pp. 2–3

Node Influence on Model Bias Estimation

  • For node vi, down-weighting changes its own loss and the losses of training nodes in its computation graph affected through message passing.The parameter ϵ controls the down-weighting scale from 0 to 1/m.Source: Node Influence on Model Bias Estimation · p. 3, Figure 1 · p. 4
  • The method estimates the PDD change from a node’s down-weighting using a first-order approximation, then relates that change to deleting the node.Theorem 2 equates the estimated value change with the PDD change when the GNN is trained on G−i, avoiding retraining.Source: Node Influence on Model Bias Estimation · p. 4

Non-I.I.D. Characterization

  • The dependency characterization compares losses of other training nodes in vi’s computation graph on G and on G−i.The method argues that training-node dependencies should be retained because they affect model parameters, while test-node representation changes are bounded and decay with distance.Source: Non-I.I.D. Characterization · p. 4
  • The test-node representation bound is derived for the prevalent GCN model under stated assumptions, including equal norms for node representations.The analysis says it can be generalized to other GNNs.Source: Non-I.I.D. Characterization · p. 4

Complexity Analysis

  • Algorithm 1 has time complexity O(mr̄t), which is quadratic in the number of training nodes when r̄ ≤ m.Here t is the number of model parameters and r̄ is the average number of training nodes in a training node’s computation graph.Source: Complexity Analysis · p. 5

Experiments

The experiments assess BIND’s efficiency, influence-estimation accuracy, and use for GNN debiasing across four real-world node-classification datasets. They report substantial speedups, strong estimated-to-actual influence correlations, and competitive fairness results without an obvious utility decrease.

Experimental Setup

  • Experiments use node classification on Income, Recidivism, Pokec-z, and Pokec-n, mainly with GCN, and evaluate efficiency, influence-estimation correlation, fairness, and accuracy.The baselines are FairGNN, NIFTY, and EDITS.Source: Experimental Setup · p. 5, Experiments · p. 5

Efficiency of Node Influence Estimation

Effectiveness of Node Influence Estimation

  • Estimated ΔΓSP and ΔΓEO have Pearson correlations over 0.9 with actual values across all four datasets.The evaluation selects non-overlapping computation graphs for node sets; exact linear correlation is described as almost impossible with the first-order Taylor expansion.Source: Figure 3 · p. 6, Effectiveness of Node Influence… · p. 6
  • Disabling non-i.i.d. characterization decreases estimated-to-actual ΔΓ correlation, including on other datasets for both statistical parity and equal opportunity.The Income comparison sets the non-i.i.d. term in Eq. 4 to 0.Source: Effectiveness of Node Influence… · p. 6
  • PDD values match traditional fairness metrics ΔSP and ΔEO, supporting PDD as an indicator of fairness levels measured by those metrics.The comparison uses values collected during GNN retraining.Source: Effectiveness of Node Influence… · p. 6

Debiasing via Harmful Nodes Deletion

  • BIND achieves competitive results on both ΔSP and ΔEO versus baselines, with no obvious decrease in model utility.The deletion strategy combines statistical parity and equal opportunity with λ = 0.5 and tests budgets of 1% and 10% of training nodes.Source: Debiasing via Harmful Nodes Deletion · p. 6

Related Work

Prior work studies GNN architectures, algorithmic fairness, debiasing, and model interpretation. This paper distinguishes its focus on attributing model bias to training nodes rather than explaining test predictions or assigning training-sample weights.

Graph Neural Networks

  • GNN research includes spectral graph-filter approaches and spatial message-passing approaches that aggregate information from neighboring nodes.The passage describes these as two broad GNN categories.Source: Related Work · p. 6

Algorithmic Fairness

  • Existing training-sample reweighting methods mitigate bias, but leave unclear how much each sample influences exhibited bias; this work instead analyzes training-node influence and non-IID dependencies.The cited reweighting methods are described as mostly developed under an IID assumption.Source: Related Work · p. 7

Interpretation of Deep Learning Models

  • Prior GNN interpretation work focuses on test-set utility, whereas this work attributes model bias to the training set.The distinction is framed as interpreting bias rather than utility and training-set influence rather than test-set predictions.Source: Related Work · p. 7

Conclusion

The paper studies training-node influence on bias in trained GNNs, proposing PDD and BIND to quantify and estimate that influence. Experiments support the metric, estimation approach, and node-deletion debiasing strategy, while interpretation on other graph-learning tasks remains future work.

Conclusion

  • PDD can be instantiated with different fairness notions to quantify node influence on model bias.BIND is proposed for efficient estimation of each training node’s influence.Source: Conclusion · p. 7
  • Experiments verify PDD’s consistency with traditional fairness metrics and the efficiency and effectiveness of influence estimation.Source: Conclusion · p. 7
  • Experiments also verify the performance of a strategy that uses influence estimates for GNN debiasing through node deletion.Source: Conclusion · p. 7
  • Interpreting unfairness in other graph-learning tasks is left for future work.Source: Conclusion · p. 7

Supplementary Discussion

PDD extends to multi-class sensitive attributes and predicted labels by averaging Wasserstein-1 distances between probabilistic prediction distributions across sensitive-subgroup pairs. The paper also describes efficient estimation methods and limits its focus to unfairness in node classification.

Generalized PDD Instantiations

  • For multi-class sensitive attributes and labels, generalized PDD averages Wasserstein-1 distances between probabilistic prediction distributions across sensitive-subgroup pairs.The variable of interest is the probabilistic prediction, and the subgroup pairs are drawn from all possible sensitive-attribute values.Source: Supplementary Discussion · p. 10

Efficient Estimation of Wasserstein Distance

  • The method uses an adopted algorithm to estimate Wasserstein-1 distance and its derivatives with respect to the GNN parameters.This addresses both distance intractability and the difficulty of computing parameter derivatives.Source: Supplementary Discussion · p. 10

Efficient Estimation of Hessian Matrix Inverse

  • A linear-time approach estimates the product of the Hessian inverse and an arbitrary vector, reducing the cost of the Hessian-inverse operation.The vector has the same dimension as the columns of the Hessian matrix.Source: Supplementary Discussion · p. 10

Limitations & Negative Impacts

  • The paper studies unfairness in node classification and leaves unfairness in other graph analytical tasks for future work.The authors report no obvious negative impacts at this time.Source: Supplementary Discussion · p. 10

Experiments

Across four real-world datasets, estimated influence values for both ΔΓSP and ΔΓEO match actual values; supplementary tests also examine transfer to GIN and the effect of shuffling node estimates. The experiments use specified dataset splits and implementation settings.

Implementation Details

  • The four datasets use binary node-classification labels, balanced-label validation and test sets of 25% each, and training samples capped at 50% or 500 nodes per class, whichever is smaller.The datasets are Income, Recidivism, Pokec-z, and Pokec-n.Source: Implementation Details · p. 11
  • Experiments use three seeds and train GNNs for 1,000 epochs with learning rate 1e-3, hidden dimension 16, and dropout 0.5.The Hessian-inverse estimation iteration count is selected from {10, 50, 100, 500, 1000, 5000}.Source: Implementation Details · p. 12

Supplementary Experiments

  • Estimated node influence on bias follows a long-tail distribution, with only a small number of nodes having large positive or negative influence.Similar patterns are reported on other datasets.Source: Figure 5 · p. 11, Supplementary Experiments · p. 12
  • Estimated ΔΓSP and ΔΓEO show a satisfying match with actual values across the four adopted datasets.Figure 7 presents the ΔΓSP and ΔΓEO comparisons across those datasets.Source: Supplementary Experiments · p. 12
  • A GIN model on Income also shows a satisfying match between estimated and actual ΔΓSP, supporting generalization beyond GCN.The comparison is shown in Figure 6a.Source: Supplementary Experiments · p. 12, Figure 6 · p. 12
  • Randomly shuffling estimated ΔΓSP values for training nodes lowers Pearson correlation against actual values compared with Figure 7.The authors report that this decrease further corroborates the estimation algorithm's effectiveness.Source: Supplementary Experiments · p. 12, Figure 6 · p. 12

Proofs

The proofs connect node influence estimates to changes in PDD under node removal and characterize when influences over a node set can be summed. The derivations also use graph-structure and representation assumptions in their bounds.

Corollary 1

  • The derivative of Γ with respect to the node down-weighting parameter is connected to model-parameter change through the chain rule.The proof assumes Γ is differentiable with respect to W and uses the first-order simplification that drops o(ϵ) terms.Source: Proofs · pp. 13–14

Theorem 2

  • Theorem 2 equates ΔΓ for a training node with the change in Γ when the model is trained on the graph with that node removed.This is the proof basis for relating the influence estimate to a node-deletion effect.Source: Proofs · p. 14

Theorem 3 and Proposition 1

  • For a training-node set whose members' computation graphs do not overlap, the summed influence scores correspond to a linear sum of the associated loss terms.The proposition's derivation assumes equal norms for all node representations; its proof uses GCN as an exemplar and says it generalizes by choosing edge weights.Source: Proofs · pp. 14–15

Related papers

Loading 2211.14383v1…