The KL-Divergence between a Graph Model and its Fair I-Projection as a Fairness Regularizer

Maarten Buyl, Tijl De Bie

Introduction

Relational data, represented as graphs, underpins critical systems from social networks to recommendation engines. However, these graphs often mirror societal biases, such as homophily—the tendency for similar individuals to connect. When probabilistic models like Graph Neural Networks (GNNs) or graph embeddings are trained on this data, they risk amplifying these biases, leading to unfair outcomes in link prediction. While fairness in traditional classification is well-documented, achieving fairness in link prediction remains a significant challenge due to the complex dependencies inherent in graph structures.

The Need for a Generic Framework

Existing approaches to fair graph modeling are often "one-trick ponies," designed for specific algorithms or narrow definitions of fairness. This lack of generality hinders the adoption of fairness constraints across the diverse landscape of graph-based machine learning. There is a clear need for a mathematically grounded, model-agnostic framework that can enforce various fairness criteria without requiring a complete redesign of the underlying architecture.

Methodology: The Fair I-Projection

The authors propose a novel approach using the Fair Information Projection (I-projection) as a fairness regularizer. This method treats fairness through the lens of information theory.

1. Defining the Fair Set

The first step involves defining a set of "fair" models, $\mathcal{F}$. The authors demonstrate that common fairness definitions, such as Demographic Parity (DP) and Equalized Opportunity (EO), can be formulated as linear constraints on the probability distribution of links. This allows the set of fair models to be represented as a convex polytope in the space of all possible distributions.

2. The I-Projection and KL-Divergence

For any biased model $h$, there exists a unique distribution $h_{\mathcal{F}}$ within the fair set $\mathcal{F}$ that is "closest" to $h$ in terms of information content. This distribution is the I-projection. The "distance" is measured using the Kullback-Leibler (KL) divergence, $D_{KL}(h_{\mathcal{F}} || h)$.

3. The Fairness Regularizer

The proposed fairness regularizer integrates this distance into the model's training objective. The total loss function becomes: $$\mathcal{L} = \text{Accuracy Loss} + \gamma \cdot D_{KL}(h_{\mathcal{F}} || h)$$ By minimizing this loss, the model is incentivized to remain as close as possible to its fair counterpart. The parameter $\gamma$ serves as a hyperparameter that allows practitioners to navigate the trade-off between predictive accuracy and social equity.

Experimental Evaluation

The framework's versatility was tested across four distinct architectures: MaxEnt (statistical), Dot-Product (embedding-based), Conditional Network Embedding (CNE), and Graph Auto-Encoders (GAE). These models were evaluated on three real-world datasets with varying levels of inherent bias:

  • Polblogs: A highly polarized network of US political blogs where homophily is extreme.
  • ML100k (MovieLens): A bipartite user-movie graph where age is the sensitive attribute.
  • Facebook: A social circle dataset where gender is the sensitive attribute.

Key Insights and Results

  • Model Agnosticism: Because the regularizer operates on the output probabilities, it can be applied to virtually any probabilistic graph model without modifying its internal structure. This was demonstrated by successfully making GAEs fair without the instability of adversarial training.
  • Superior Trade-offs: In experiments on the Polblogs dataset, the proposed regularizer achieved a superior balance between Demographic Parity and AUC compared to specialized baselines like DeBayes and CFC.
  • Scalability: Although computing the I-projection over all node pairs is $O(n^2)$, the authors found that subsampling vertex pairs during training provides a highly accurate approximation, allowing the method to scale to larger graphs.

Conclusion and Future Work

This research provides a unified, information-theoretic framework for fairness in graph modeling. By framing fairness as a distance to an I-projection, the authors offer a tool that is both mathematically rigorous and practically flexible. While the current work focuses on transductive settings, future research could extend this framework to inductive scenarios, where models must generalize fairness to previously unseen nodes at test time.

Summary updated

Abstract

Learning and reasoning over graphs is increasingly done by means of probabilistic models, e.g. exponential random graph models, graph embedding models, and graph neural networks. When graphs are modeling relations between people, however, they will inevitably reflect biases, prejudices, and other forms of inequity and inequality. An important challenge is thus to design accurate graph modeling approaches while guaranteeing fairness according to the specific notion of fairness that the problem requires. Yet, past work on the topic remains scarce, is limited to debiasing specific graph modeling methods, and often aims to ensure fairness in an indirect manner. We propose a generic approach applicable to most probabilistic graph modeling approaches. Specifically, we first define the class of fair graph models corresponding to a chosen set of fairness criteria. Given this, we propose a fairness regularizer defined as the KL-divergence between the graph model and its I-projection onto the set of fair models. We demonstrate that using this fairness regularizer in combination with existing graph modeling approaches efficiently trades-off fairness with accuracy, whereas the state-of-the-art models can only make this trade-off for the fairness criterion that they were specifically designed for.
BibTeX
@inproceedings{buyl2021kl,
  author = {Maarten Buyl and Tijl De Bie},
  title = {{The KL-Divergence between a Graph Model and its Fair I-Projection as a Fairness Regularizer}},
  booktitle = {ECML/PKDD},
  year = {2021},
  url = {https://openreview.net/forum?id=TdrMZWoMIv1},
}
Figure