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

Maarten Buyl, Tijl De Bie

TL;DR

This paper introduces a generic fairness regularizer for link prediction in graphs by measuring the "distance" (KL-divergence) between a probabilistic model and its mathematically "fair" counterpart, known as an I-projection. This approach allows researchers to plug fairness into almost any graph-based machine learning model—from simple embeddings to Graph Neural Networks—while achieving a superior balance between predictive accuracy and social equity compared to existing specialized methods.

What Problem Does This Paper Address?

Graphs are the backbone of modern recommendation engines and social networks, but they are rarely neutral. Because they reflect real-world human interactions, they often encode deep-seated biases, such as homophily (the tendency to associate with similar people). When a machine learning model predicts new links based on this biased data, it risks creating "filter bubbles" or perpetuating systemic segregation—for example, recommending high-paying jobs only to certain demographic groups.

While fairness in standard classification is well-studied, fairness in link prediction is much harder. Most existing solutions are "one-trick ponies": they are designed for one specific algorithm or one specific definition of fairness. The authors identify a need for a flexible, mathematically grounded framework that works across different models and fairness criteria.

Methods

The core innovation is the use of the Fair Information Projection (I-projection) as a regularizer.

  1. Defining the "Fair" Set: The authors show that common fairness definitions, like Demographic Parity (DP) and Equalized Opportunity (EO), can be expressed as linear constraints on a probability distribution. This defines a "set of all fair models."
  2. The I-Projection: For any given biased model $h$, there is a unique "fair" distribution $h_{\mathcal{F}}$ that is closest to it in terms of information theory (specifically, KL-divergence). This is the I-projection.
  3. The Regularizer: The authors propose a new loss function: $$\mathcal{L} = \text{Accuracy Loss} + \gamma \cdot D_{KL}(h_{\mathcal{F}} || h)$$ By minimizing this, the model is forced to stay "close" to its fair version during training. The parameter $\gamma$ allows practitioners to tune the trade-off between accuracy and fairness.

  4. Generality: Because the regularizer is based on the output probabilities of the model, it is "model-agnostic." The authors demonstrate it on four diverse architectures: MaxEnt (statistical), Dot-Product (embedding-based), CNE (Conditional Network Embedding), and GAE (Graph Auto-Encoder).

Datasets

The authors evaluated their method on three real-world datasets with distinct social characteristics:

  • Polblogs: A network of US political blogs. This is a "high-bias" dataset where bloggers almost exclusively link to others with the same political leanings (Republican or Democrat).
  • ML100k (MovieLens): A bipartite graph of users and movie ratings. The sensitive attribute here is the age of the users.
  • Facebook: A social circle dataset where the sensitive attribute is gender. This dataset has much weaker inherent bias than Polblogs.

Key Insights and Ideas

  • Fairness as Information Loss: The authors frame "unfairness" as the amount of information lost when moving from a biased model to its fair idealized version. This provides a principled, information-theoretic justification for the regularizer.
  • Linearity is Key: By proving that DP and EO are linear constraints, the authors make the complex problem of "finding the fair version" computationally tractable using Lagrange multipliers.
  • Breaking the "Specific-Model" Silo: Unlike previous work that required re-engineering the internal architecture of a GNN or an embedding model, this method treats the model as a probabilistic black box, making it much easier to adopt in production.

Key Results

  • Superior Trade-offs: In experiments on the Polblogs dataset, the proposed regularizer significantly reduced demographic parity violations while maintaining higher AUC (Area Under Curve) scores than state-of-the-art baselines like DeBayes and CFC.
  • Versatility: The method successfully enforced fairness even on models it wasn't specifically "built" for. For instance, it made Graph Auto-Encoders (GAEs) fair without requiring adversarial training, which is often unstable.
  • Scalability: While computing the I-projection over all possible 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.

Limitations and Future Work

  • Computational Overhead: Even with subsampling, calculating the I-projection adds a layer of complexity to the training loop, leading to longer runtimes compared to unregularized models.
  • Transductive Nature: The current experiments focus on transductive settings (where all nodes are known at training time). Extending this to "inductive" settings—where the model must handle entirely new nodes at test time—remains an open challenge.
  • Beyond Graphs: The authors suggest that this I-projection framework could be extended to other areas of machine learning beyond relational data, potentially offering a unified theory for fairness regularization in general probabilistic modeling.

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},
}

Loading related content...

Figure