Source-linked AI summary
DeBayes: a Bayesian Method for Debiasing Network Embeddings
Maarten Buyl, Tijl De Bie
TL;DR
Fairness methods have advanced in standard machine learning, but options for network embeddings remain limited. DeBayes learns embeddings using a biased prior and evaluates links with an oblivious prior; the paper reports substantially debiased embeddings and fair link predictions, with a limited AUC cost.
Problem
Fairness methods for network embedding remain limited in number and performance, despite the field’s relevance to applications such as social graphs and recommender systems.
Source: §1 · p. 1Method
DeBayes adapts Conditional Network Embedding by modeling sensitive information in a biased training prior, then using an oblivious prior for link prediction.
Source: §1 · p. 1, §4.2 · p. 5Results
DeBayes substantially debiases node embeddings in almost all cases, and link predictions score well on three high-level fairness measures with a limited prediction-AUC cost.
Source: §6 · p. 9Takeaways & Limitations
The method can incorporate multiple sensitive attributes and avoids relying on a fairness-related loss term, instead depending on how readily the prior can model sensitive information.
Source: §6 · p. 9The paper considers categorical sensitive attributes, while extending the training prior to continuous values is left for further research.
Source: §6 · p. 9
Abstract
from arXiv · showhide
As machine learning algorithms are increasingly deployed for high-impact automated decision making, ethical and increasingly also legal standards demand that they treat all individuals fairly, without discrimination based on their age, gender, race or other sensitive traits. In recent years much progress has been made on ensuring fairness and reducing bias in standard machine learning settings. Yet, for network embedding, with applications in vulnerable domains ranging from social network analysis to recommender systems, current options remain limited both in number and performance. We thus propose DeBayes: a conceptually elegant Bayesian method that is capable of learning debiased embeddings by using a biased prior. Our experiments show that these representations can then be used to perform link prediction that is significantly more fair in terms of popular metrics such as demographic parity and equalized opportunity.
1. Introduction
DeBayes adapts Conditional Network Embedding by modeling sensitive information in a biased prior, so embeddings need not encode it. It trains with that biased prior and evaluates links with an oblivious prior to reduce bias while keeping prediction accuracy high.
Motivation
- Fairness matters because removing sensitive inputs alone does not address disparate impact, and network embeddings can support recommendations that reinforce group biases.The introduction identifies friendship recommendations and book recommendations as examples of potential harms.Source: §1 · p. 1
Proposed method
- DeBayes models sensitive information as strongly as possible in the training prior, allowing the learned embeddings to omit that information.The approach adapts Conditional Network Embedding, whose prior models network structure such as node degrees or block structure.Source: §1 · p. 1
- With an oblivious prior, CNE embeddings separate liberal and conservative political blogs; with a biased prior, the prior represents this structure and no separation is required.Figure 1 depicts the 50 highest-degree blogs, grouped by leaning and sorted by degree; its heatmaps show prior probabilities and its scatterplots show embeddings.Source: §1 · p. 2, Figure 1 · p. 2
- The proposed training and evaluation strategy is intended to reduce bias while keeping link-prediction accuracy high.Training uses a biased prior; link probabilities are evaluated with an oblivious prior.Source: §1 · p. 2
- DeBayes can switch fairness on or off at evaluation by choosing the prior, model multiple sensitive attributes, and impose fairness without additional computational cost.The paper also proposes extending the idea to other areas of representation learning.Source: §1 · p. 2
2. Related Work
Related work frames fairness as an intervention in preprocessing, the learning algorithm, or postprocessing, and reviews fair-representation and fair-network-embedding methods. DeBayes differs by using a Bayesian prior rather than a fairness-related loss term.
Fairness methods
- Fairness methods intervene in preprocessing, the algorithm, or postprocessing; post-hoc correction can significantly hurt predictor accuracy.Preprocessing modifies training data, while postprocessing adjusts output probabilities to satisfy a fairness constraint.Source: §2 · pp. 2–3
Algorithmic fairness
- Algorithmic fairness methods commonly modify the loss with regularization or fairness constraints; prior Bayesian work uses latent variables to model fair dependencies.DeBayes makes comparable assumptions, treating embeddings as latent variables.Source: §2 · p. 3
Fair representation learning
- Fair representation learning seeks informative embeddings without sensitive information; approaches include fairness penalties, adversarial losses, and disentanglement.DeBayes instead avoids bias through the Bayesian objective and prior, without a manually chosen fairness-loss hyperparameter.Source: §2 · p. 3
Fair network embedding
- Fairwalk reweights neighborhoods toward under-represented groups, while Compositional Fairness Constraints trains an encoder against adversaries predicting sensitive attributes.Fairwalk adapts node2vec; Compositional Fairness Constraints is an adversarial approach.Source: §2 · p. 3
3. Fairness in Link Prediction
This section extends fairness notions usually specialized to binary classification to link prediction, addressing both representation-level obfuscation and fairness of predictions themselves.
3. Fairness in Link Prediction
- The section extends fairness notions generally specialized to binary classification to link prediction, evaluating fairness at representation and prediction levels.These notions are intended to inspire and evaluate the method’s fairness properties.Source: §3 · p. 3
3.1. Notation
- The setup considers an undirected attributed graph with one sensitive attribute per node and frames link prediction as estimating edge probabilities from node embeddings.The one-attribute case is stated to be without loss of generality for DeBayes.Source: §3.1 · p. 3
3.2. Fair Representations
- Representation bias is assessed by how accurately a classifier predicts sensitive attributes from embeddings on unseen nodes, using weighted one-versus-rest AUC.The weighting makes each sensitive-value group’s contribution proportional to its size.Source: §3.2 · pp. 3–4
- Fair embeddings alone do not guarantee fair link predictions, because CNE uses both embeddings and a prior to generate predictions.Some link-prediction algorithms may not use embeddings at all.Source: §3.2 · p. 4
3.3. High-Level Fairness Measures for Link Prediction
- Demographic parity requires equal prediction rates across sensitive-attribute pairs, while equalized opportunity requires true positive rates to be independent of those attributes.The DP deviation is the maximum absolute difference between any two prediction rates; EO compares rates for attribute-paired true edges.Source: §3.3 · p. 4
- Demographic parity may reduce prediction quality when group-specific differences reflect the ground truth rather than discrimination.The passage gives higher within-group connectivity as an example.Source: §3.3 · p. 4
- Acceptance rate parity compares rates at which links between attribute groups appear among the overall top-k% prediction scores.A link in those top scores counts as a recommendation.Source: §3.3 · p. 4
4. The DeBayes Method
DeBayes reduces the influence of sensitive attributes by modeling them in the prior while learning network embeddings. It uses a biased prior during training and an oblivious prior for link-prediction evaluation, with extensions for multiple or partially observed attributes.
4. The DeBayes Method
- DeBayes models sensitive information in the prior to generate debiased network embeddings, then uses an oblivious prior for link-prediction evaluation.The method extends CNE by using a biased prior for training and an oblivious prior during evaluation.Source: §4 · p. 5, §4.3 · p. 6
4.1. Conditional Network Embedding
- CNE uses a graph prior for structural properties and a likelihood that favors nearby embeddings for connected nodes; its pairwise probabilities also support link prediction.A maximum-entropy prior can match expected structural statistics to observed graph statistics, including node degrees.Source: §4.1 · p. 5
4.2. Training with a Biased Prior
- The biased prior matches each node’s expected neighbors within sensitive-attribute groups, allowing the embedding to focus on information not absorbed by the prior.DeBayes keeps CNE’s attribute-independent embedding conditional distribution, so the prior absorbs as much attribute-linked structure as possible.Source: §4.2 · p. 5
4.3. Evaluating with an Oblivious Prior
- For link prediction, DeBayes replaces the attribute-dependent training prior with an oblivious prior whose constraints are independent of the sensitive attribute.When node degrees are independent of the sensitive attribute, a maximum-entropy prior with attribute-independent constraints guarantees that independence.Source: §4.3 · pp. 5–6
4.4. Generalization
- DeBayes extends to multiple sensitive attributes by adding constraints for each attribute set, provided the constraints do not fully specify the graph.For graphs with unattributed nodes, such as items in recommender systems, an additional degree constraint can sum over those nodes.Source: §4.4 · p. 6
5. Experiments
Across the experiments, DeBayes reduced representation bias while keeping the link-prediction AUC decrease limited on ML-100k; on DBLP, nonlinear classification still separated continents. High-level fairness results varied across methods and measures, with DeBayes improving on its unfair configuration.
5. Experiments
- The evaluation used 10 runs with different random seeds and train/test splits; training used about 80% of edges, with the remaining 20% and an equal number of non-edges for testing.The experiments examined network-embedding bias and downstream link prediction across the two datasets.Source: §5 · p. 6
5.1. Datasets
- DBLP provided a co-authorship network with continent as the sensitive attribute, while ML-100k provided user-movie links and treated gender, age, and occupation as sensitive attributes.Africa and Antarctica were excluded from the DBLP analysis because of strong under-representation; ML-100k ages were grouped into seven categories.Source: §5.1 · p. 6
5.2. Configurations
- The experiments used DeBayes, CFC, Fairwalk, and a random predictor, tuning influential hyperparameters against link-prediction AUC; DeBayes evaluation used an oblivious prior.DeBayes was also trained with either an oblivious or biased prior; its oblivious-training and oblivious-evaluation configuration is equivalent to CNE.Source: §5.2 · pp. 6–7
5.3. Analysis of Representation Bias
- On ML-100k, DeBayes made gender, age, and occupation hard to predict for both classifiers with a limited AUC decrease; on DBLP, the nonlinear SVM still separated continents.For DBLP, logistic regression became less successful at estimating continent; the nonlinear SVM remained strong.Source: §5.3 · pp. 7–8
5.4. Analysis of High-Level Fairness
- On DBLP, DeBayes with a biased prior made predictions fairer than its oblivious-prior configuration; CFC improved fairness only with sharply dropping AUC, while Fairwalk’s effects varied by measure.Fairwalk improved DP_gender but scored worse on EO_gender and ARP_gender; DeBayes and CFC did not approach the random predictor’s high-level fairness, although fairness measures were already low without adaptations.Source: §5.4 · p. 8
5.5. Discussion
- DeBayes models sensitive connectivity in its prior and evaluates links with an oblivious prior; the discussion reports debiased, informative embeddings, while Fairwalk’s random-walk modification may leave sparse same-attribute neighborhoods unchanged.The authors note that DeBayes’s constraints scale with the number of categorical attribute values; continuous attributes would require different constraints.Source: §5.5 · pp. 8–9
6. Conclusion
DeBayes substantially debiases node embeddings in almost all cases, and its link predictions score well on three high-level fairness measures despite a limited prediction-quality cost. The conclusion identifies training-prior and evaluation-prior extensions, and possible generalization to other areas of fair machine learning.
6. Conclusion
- DeBayes substantially debiases node embeddings in almost all cases, while link predictions score well on three high-level fairness measures.The method’s prediction-quality cost is limited despite an inevitable trade-off between fairness and prediction AUC.Source: §6 · p. 9
- DeBayes supports multiple types of sensitive attributes without relying on a fairness-related loss term, instead depending on how easily the information can be modeled through a prior.Source: §6 · p. 9
- Further training-prior research could support more sensitive-attribute types, including continuous values, while evaluation priors could be adjusted for greater debiasing when degree and sensitive attributes are dependent.Source: §6 · p. 9
- The authors suggest that DeBayes principles could be generalized to other areas of fair machine learning.Source: §6 · p. 9