Source-linked AI summary
Compositional Fairness Constraints for Graph Embeddings
Avishek Joey Bose, William L. Hamilton
TL;DR
Graph embeddings are useful for recommendation and relational prediction but do not natively accommodate invariance to sensitive attributes. The paper introduces composable adversarial filters that support different attribute combinations, including unseen combinations at inference. Experiments report favorable sensitive-information removal and a roughly 10% edge-prediction error increase on realistic recommendation datasets.
Problem
Existing graph-embedding techniques do not address fairness constraints requiring representations to be invariant to sensitive attributes.
Method
The framework trains adversarial filters for individual sensitive attributes and composes them to generate embeddings invariant to selected attribute combinations.
Results
Across experiments, the compositional approach removed sensitive information favorably compared with individually trained adversaries, while realistic recommendation datasets incurred roughly a 10% relative edge-prediction error increase.
Takeaways & Limitations
The compositional adversary accommodates unseen combinations of fairness constraints without explicitly training on those combinations.
Takeaways & Limitations
The work considers only one adversarial loss and does not explicitly model subgroup-level fairness.
Abstract
from arXiv · showhide
Learning high-quality node embeddings is a key building block for machine learning models that operate on graph data, such as social networks and recommender systems. However, existing graph embedding techniques are unable to cope with fairness constraints, e.g., ensuring that the learned representations do not correlate with certain attributes, such as age or gender. Here, we introduce an adversarial framework to enforce fairness constraints on graph embeddings. Our approach is compositional---meaning that it can flexibly accommodate different combinations of fairness constraints during inference. For instance, in the context of social recommendations, our framework would allow one user to request that their recommendations are invariant to both their age and gender, while also allowing another user to request invariance to just their age. Experiments on standard knowledge graph and recommender system benchmarks highlight the utility of our proposed framework.
1. Introduction
The paper targets fairness and privacy constraints for graph embeddings, where existing graph-embedding methods do not address invariance to sensitive attributes. It introduces an adversarial, compositional framework that supports multiple attribute combinations, including combinations unseen during training.
- Graph embeddings support link prediction and recommender systems but may expose sensitive information such as race, age, or gender.
- Existing fairness techniques had not addressed graph embeddings, whose relational data are non-i.i.d. and non-Euclidean.
- Social graph applications may require invariance to many sensitive attributes, potentially including individual edges.
- The framework learns adversarial filters for individual attributes and composes them to enforce different combinations of invariance constraints.
- The compositional strategy can generate invariant embeddings for combinations not seen during training.
2. Related Work
Related work spans graph embeddings and algorithmic fairness. This paper combines these areas by studying fairness and invariance constraints for learned graph representations.
- Graph embeddings have roots in sociograms and latent-variable models and are now widely studied in machine learning and data mining.
- Graph embeddings support node classification, relation prediction, and clustering; this work focuses on relation prediction.
- Relation prediction also underlies recommender systems and knowledge-base completion.
- Fairness research seeks predictions that are balanced or invariant with respect to sensitive variables such as age or gender.
- The paper addresses fairness in graph embeddings, extending fairness concerns beyond the settings emphasized by prior work.
3. Preliminaries
The paper models heterogeneous, multi-relational graphs and learns embeddings that score observed and unobserved relations. Fairness is formulated as preventing embeddings from encoding categorical sensitive attributes.
- The graph consists of directed triples ⟨u, r, v⟩ with typed nodes and relation types subject to node-type constraints.
- Relation prediction learns a scoring function from observed training edges and negative edges absent from the graph.
- The ideal scoring function assigns every true edge a higher score than every negative edge.
- An embedding encoder maps each node v to a vector z_v, and a score function uses two node embeddings and a relation type to estimate edge likelihood.
- The fairness setup assigns K categorical sensitive attributes to nodes of one designated type and assumes no other node or edge features for simplicity.
- The central fairness challenge is ensuring that learned node embeddings are not biased with respect to those sensitive attributes.
4. Invariant Graph Embeddings
The method defines fairness as representational invariance, then uses compositional filters and adversarial discriminators to enforce user-selected attribute constraints. Its theory and design expose a performance–invariance tradeoff and a scope boundary around subgroup fairness.
- 4.1. Pragmatic Fairness as Invariance: Representational invariance makes edge predictions independent of sensitive attributes when the score depends on a node only through its embedding.
- 4.1. Pragmatic Fairness as Invariance: The formulation allows different nodes or users to request different subsets of sensitive-attribute invariance constraints.
- 4.1. Pragmatic Fairness as Invariance: The representational-invariance condition does not necessarily imply subgroup fairness on the joint distribution.
- 4.2. Model Definition: For each sensitive attribute, a filter removes its information; composing selected filtered embeddings produces an embedding invariant to a chosen set S.
- 4.2. Model Definition: Random binary masks select attribute subsets during training, encouraging generalization to unseen combinations at inference.
- 4.2. Model Definition: Attribute-specific discriminators adversarially predict sensitive attributes from embeddings, while λ controls the regularization strength.
- 4.2. Model Definition: As λ approaches infinity, the theory gives zero mutual information under capacity and optimization assumptions, but finite λ trades edge-prediction performance against invariance.
5. Experiments
Experiments evaluate compositional fairness on three graph datasets, measuring invariance, edge-prediction accuracy, compositionality, and generalization to unseen sensitive-attribute combinations. The approach generally trades a roughly 10% relative edge-prediction error increase for near-complete sensitive-information removal, while results vary by dataset.
- Setup and Datasets: Experiments use Freebase15k-237, MovieLens-1M, and Reddit to evaluate invariant graph embeddings on knowledge-base completion and recommendation edge-prediction tasks.The setup jointly trains the main model with adversaries and uses a newly trained classifier to test sensitive-attribute predictability.
- Setup and Datasets: The evaluation compares unconstrained models, separately trained attribute-specific adversaries, and the compositional adversarial approach.The unconstrained baseline uses λ = 0, while the non-compositional baseline trains distinct encoders and adversaries for each sensitive attribute.
- Invariance-Accuracy Tradeoff: On MovieLens-1M and Reddit, near-complete sensitive-information removal incurs a roughly 10% relative error increase on edge-prediction tasks.For MovieLens, compositional adversarial regularization increases RMSE from 0.865 to 1.01, while sensitive-attribute classification reaches majority-vote performance.
- Invariance-Accuracy Tradeoff: Freebase15k-237 cannot completely remove synthetic sensitive information without a significant decrease in accuracy on the original edge-prediction task.The sensitive attributes derive from entity-type annotations that are presumably relevant to relation prediction, illustrating a limitation of removing sensitive information.
- Impact of Compositionality: The compositional approach outperforms individually trained adversaries on MovieLens-1M and synthetic Freebase15k-237 for removing sensitive information, but performs worse on Reddit.On Reddit, compositionality also causes a small drop in the main edge-prediction performance.
- Invariance on Unseen Combinations: On Reddit, holding out 10% of sensitive-attribute combinations produces only a 0.025 performance drop, demonstrating generalization to unseen combinations.Reddit contains 10 sensitive attributes, compared with 3 for the other two datasets; appendix results extend the analysis to 50 attributes.
6. Discussion and Conclusion
The framework supports user-driven fairness constraints over large sets of sensitive attributes, including combinations unseen during training. The authors identify limited adversarial-loss coverage and potential bias in real-world fairness preferences as important limitations and future-work directions.
- Discussion and Conclusion: The compositional adversary accommodates unseen combinations of fairness constraints without explicitly training on them.This is presented as relevant to user-driven settings requiring optional enforcement of many invariance constraints.
- Discussion and Conclusion: The study considers only one type of adversarial loss, leaving alternatives such as other adversarial variations and non-adversarial regularizers for future work.The authors also note that subgroup-level fairness was not explicitly modeled.
- Discussion and Conclusion: Real-world deployment may be affected by biased user preferences over fairness attributes, potentially creating new demographic inequalities.The experiments used randomly sampled attribute sets, whereas production requests would come from users whose preferences may themselves be biased.
A. Implementation Details
The implementation uses MLP-based discriminators and adversarial filters with Adam optimization and matched discriminator and sensitive-attribute-classifier capacity.
- A. Implementation Details: Discriminators and adversarial filters are implemented as multi-layer perceptrons with leaky ReLU nonlinearities.The passage specifies Adam optimization with default parameters and λ = 1000 unless otherwise stated.
- A. Implementation Details: The discriminator and subsequent sensitive attribute classifier share the same architecture and capacity for fair comparison.
- A. Implementation Details: The experiments use λ = 1000 for all datasets unless otherwise specified.
B. FB15k-237 Details
The FB15k-237 setup trains TransD embeddings with randomly sampled negative triplets and separately specifies training durations and MLP depths for the model components.
- B. FB15k-237 Details: Negative triplets are generated by randomly sampling either a head or tail entity, using 20 negatives for each positive triplet.
- B. FB15k-237 Details: TransD is trained for 100 epochs with embedding dimension 20, selected using cross-validation.
- B. FB15k-237 Details: Sensitive attribute classifiers are trained for 50 epochs, while discriminators and adversarial filters use MLPs with 4, 4, and 2 layers, respectively.
C. MovieLens1M
The MovieLens1M configuration uses deep regularized sensitive-attribute networks, an unchanged adversarial filter, and BatchNorm in the main model.
- C. MovieLens1M: MovieLens1M uses 9-layer MLP discriminators and sensitive attribute classifiers with dropout probability p = 0.3 between layers.
- C. MovieLens1M: The adversarial filter remains unchanged from the FB15k-237 configuration.
- C. MovieLens1M: The main model uses BatchNorm after embedding lookup with embedding dimensionality 30 because regularization was crucial to performance.
D. Reddit
The Reddit experiments use negative triplet sampling with balanced negative-to-positive ratios and inherit several model components from MovieLens1M. User nodes carry sensitive attributes, while training uses edge and held-out-node splits.
- Negative triplets are generated by sampling head or tail entities, with equal numbers of negative and positive examples.
- The discriminator, sensitive attribute classifier, and attribute filters use the same architectures as in MovieLens1M.
- Table 4 reports average AUC values across top-k sensitive attributes for held-out Reddit test combinations.
- The model uses 50-dimensional embeddings, and sensitive-attribute losses apply only to user nodes.
- Training uses 90% of edges, with 10% reserved for testing, while 10% of user nodes are held out to test compositional generalizability.
E. Additional Results on Reddit
Additional Reddit results examine held-out test performance across different numbers of sensitive attributes. Across 20, 30, 40, and 50 attributes, invariance and task accuracy show no statistically significant degradation.
- The held-out Reddit results evaluate combinations of 20, 30, 40, and 50 sensitive attributes.
- No statistically significant degradation is observed in invariance performance as the number of sensitive attributes increases.
- No statistically significant degradation is observed in task accuracy across the tested sensitive-attribute counts.