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