Compositional Fairness Constraints for Graph Embeddings

In plain words

Graph embeddings turn every node, such as a user or a movie, into a list of numbers that a recommender or link predictor can use. These numbers can quietly carry information such as a user's gender or age, even when nobody asked for it. The paper asks how to stop that: a user might want recommendations that do not depend on their gender, and another user might only ask to ignore their age.

The method trains a small "filter" for each sensitive attribute. Each filter is pushed, through a training game, to remove whatever a separate guessing network could use to recover that attribute. Because the filters are separate, they can be applied in any combination when a recommendation is made, so one user can ask for age-blindness and another for age- and gender-blindness, without retraining. The authors test this on a knowledge graph, a movie-rating dataset and a Reddit user-community graph. They report that the attributes become hard to guess, at the cost of a modest drop in prediction accuracy.

TL;DR

• Adds one adversarial filter per sensitive attribute to graph node embeddings; a discriminator per attribute tries to recover that attribute from the filtered embedding §4.2.
• At inference a subset S of attributes is chosen and the filters for S are combined into the embedding; the paper reports this also works for subsets not seen in training §5.2.
• Attribute classifiers retrained on the frozen embeddings reach roughly majority-classifier level on MovieLens-1M, and the paper calls the attributes nearly impossible to predict on MovieLens-1M and Reddit. Edge error rises about 10% relative on those two datasets (author-reported) §5.2.
• The Freebase result is weaker: the synthetic attributes cannot be removed without a large accuracy loss, and the mean rank rises from 285 to 542 §5.2 tab. 3.
• Use it if you need per-request invariance to a small set of attributes. Check the paper-vs-code differences before you reimplement: the composition rule, the margin, the norm and the negative count all differ §5 paper_trans_e.py.

Problem

Node embeddings learned for link prediction or recommendation can encode sensitive attributes. Enforcing a fairness constraint on each individual edge score is intractable, because a graph has millions of candidate edges §4.1. The paper assumes the score depends on a user only through that user's embedding, so it is enough to make the embedding independent of the attribute §4.1 eq. 3 eq. 4. Prior fairness work mostly handles one attribute at a time, while social graphs may have many attributes, and the set of attributes a user wants enforced is not fixed in advance §1 §4.1.

Method

Setting §3. The graph has typed nodes and typed relations. A scoring function s ranks true edges above sampled negative edges. Training uses a per-edge loss summed over a batch of edges, with negatives drawn by corrupting an edge eq. 1 eq. 2. The fairness setting assumes that one node type has K categorical sensitive attributes, and that nodes have no other attributes §3.

Invariance target §4.1. For a set S of attributes, the target is that the embedding carries zero mutual information with each attribute in S, for every node eq. 5. The paper argues this implies demographic parity between groups on the scores, if scores are thresholded §4.1.

Compositional encoder §4.2. Each attribute k gets a filter f_k: R^d to R^d. For a set S, the composed embedding is the average of the filtered base embeddings over S eq. 6. During training a fresh S is sampled for each minibatch, as K independent Bernoulli draws with probability 0.5 per attribute §4.2. Note that the paper's equation averages over S, but the code sums (see Paper vs code).

Adversarial loss §4.2. Each attribute k gets a discriminator D_k that predicts a_k from the composed embedding. The per-edge loss is the edge loss plus lambda times the sum, over active attributes, of the log-probability that D_k assigns to the observed attribute value eq. 7. Training alternates T minibatch updates of the encoder and filters on this loss, and T' minibatch updates of the discriminators on the negated loss, with the other side fixed. The paper does not give T or T' §4.2. The appendix says the discriminator is updated 5 times per encoder step app. A.

Theory §4.2. A theorem states that, if the discriminators reach their optimum and lambda goes to infinity, the mutual information between the embedding and the attribute goes to zero at the equilibrium. The paper notes that trivial solutions, such as a constant encoder, also satisfy this, so a finite lambda trades edge accuracy against invariance §4.2.

Instantiations §5.1.

• Freebase15k-237: a TransD encoder whose head and tail embeddings depend on the relation eq. 8. The score is the negative distance between the transformed head, the relation vector and the transformed tail, with an unnumbered norm in the paper's display §5.1. The loss is a max-margin hinge with one negative eq. 9. The three sensitive attributes are the three most common entity-type labels §5.1.
• MovieLens-1M: an embedding-lookup encoder for users and movies. Ratings are relation types, and the score is a log-likelihood built from relation matrices that combine two learned bases §5.1. The sensitive attributes are age, gender and occupation §5.1.
• Reddit: an embedding-lookup encoder with a dot-product score and the same max-margin loss eq. 9. The sensitive attributes are whether a user commented in each of 10 chosen subreddits §5.1.

TransD encoding §5.1 eq. 8:

\mathrm{enc}(u, \langle u, r, v\rangle) = (\mathbf{r}_p \mathbf{u}_p^\top + \mathbf{I})\,\mathbf{u} eq. 8

Training step, reconstructed from §4.2 and the FB script. The paper has no algorithm box. The code's order of updates is shown in paper_trans_e.py.

# One compositional adversarial step for a batch of positive edges  [§4.2]
# Input:  positive edges (B, 3) as (head, relation, tail); attributes (B, K)
# Output: updated encoder, filters f_k and discriminators D_k

def training_step(edges, attributes):
    # Sample the invariance set S: each attribute kept with prob. 0.5  [§4.2]
    mask = bernoulli(p=0.5, size=K)                  # (K,) values in {0, 1}
    active = [k for k in range(K) if mask[k] == 1]
    # Base embeddings of the head and tail nodes  [§5.1] [eq. 8]
    raw_head, raw_tail = encoder(edges)              # (B, d) each
    # Compose filtered embeddings for S  [eq. 6]
    # The paper divides by |S|; the code sums (see Paper vs code)
    if no attribute is active:
        head, tail = raw_head, raw_tail              # code: no filtering
    else:
        head = sum(filters[k](raw_head) for k in active)   # (B, d)
        tail = sum(filters[k](raw_tail) for k in active)   # (B, d)
    # Edge loss plus adversarial term  [eq. 7] [eq. 9]
    edge_term = margin_loss(head, tail, negatives)
    adv_term = sum(log_prob(D[k](head), attributes[:, k]) for k in active)
    loss_encoder = edge_term + lam * adv_term
    update(encoder and filters, minimise loss_encoder)
    # Discriminator steps on detached embeddings  [app. A]
    # [code: paper_trans_e.py#L771-L785]
    for step in range(D_steps):                      # 5 in the appendix
        for k in active:
            loss_D = cross_entropy(D[k](head.detach()), attributes[:, k])
            update(D[k], minimise loss_D)

The head and tail composition is the same operation in the code: both are passed through the same active filters paper_trans_e.py paper_trans_e.py.

Hyperparameters

Values are as the paper and the official code state them. "Not stated" means neither gives it.

Results

Author-reported. Setup: MovieLens-1M and Reddit use embedding-lookup encoders; Freebase15k-237 uses TransD; baselines are lambda = 0 and a non-compositional adversary that trains one encoder and one adversary per attribute §5. Hardware is not stated.

Dataset statistics tab. 1:

Attribute prediction on MovieLens-1M tab. 2. Gender is scored by AUC; age and occupation by micro-averaged F1. Lower is better for invariance:

Edge prediction on MovieLens-1M: RMSE rises from 0.865 without the adversary to 1.01 with the compositional adversary §5.2 fig. 2. The paper describes this as roughly a 10% relative error increase on MovieLens and Reddit §5.2.

Attribute prediction on Freebase15k-237 tab. 3. Binary attributes scored by AUC:

On Freebase the paper says it was not possible to remove the sensitive information without a significant loss on the main task §5.2.

Reddit, held-out attribute combinations, with the number of sensitive attributes in the combination set tab. 4 app. E. The paper describes these as no statistically significant degradation; no test is reported:

Other results, from text and figures only:

• Held-out combinations on Reddit: AUC drop of 0.025 relative to seen combinations §5.2 fig. 4.
• Reddit: the compositional adversary removes less attribute information than the non-compositional one, and loses a little edge accuracy §5.2 fig. 3 fig. 4.
• MovieLens: the compositional adversary removes more attribute information than per-attribute adversaries §5.2.
• Prediction bias (average gap in predicted rating between attribute values, per movie) drops sharply with adversarial training; numbers are only in the figure §5.2 fig. 7.
• The lambda trade-off on MovieLens is shown as AUC and RMSE curves against lambda fig. 5 fig. 6.

Paper vs code

Official code: joeybose/Flexible-Fairness-Constraints, cloned at commit ea5eadb603368ee2d16d95ad1f781305d9eb71b1. The paper links it §5.1. The first author owns the repository. The repository has no LICENSE file, so its code is cited by path and line only. The README sample commands are cited only where they set a value that differs from the paper.

• Composition rule. Paper: average over S eq. 6. Code: sum over active filters, with no division by |S| paper_trans_e.py paper_trans_e.py. The same sum appears in the MovieLens and Reddit encoders model.py.
• Empty S. Paper: not defined. Code: uses the raw embedding when no filter is active paper_trans_e.py.
• Negatives, FB15k-237. Paper: 20 negatives per positive app. B; also a single negative sample in the loss §5.1 eq. 9. Code: one corrupted negative per positive, with the head or tail replaced for each half of the batch paper_trans_e.py.
• Margin. Paper: 1 eq. 9. Code default: 3 for FB and MovieLens, 1 for Reddit paper_trans_e.py main_movielens.py main_reddit.py. The README FB sample command does not set a margin, so 3 applies.
• Norm. Paper: L2 norm in the TransD score §5.1. Code default: p = 1, i.e. L1 paper_trans_e.py. The README sample commands do not change it.
• Optimizer. Paper: Adam with default parameters app. A. Code: AMSGrad, betas (0.5, 0.99) for the FB adversarial optimizer paper_trans_e.py; the MovieLens default mode adam uses betas (0.9, 0.999) with AMSGrad paper_trans_e.py main_movielens.py.
• Lambda. Paper: 1000 in all experiments app. A. README MovieLens sample command: 10 README.md. Code defaults: 0.1 for FB paper_trans_e.py, 1 for MovieLens and Reddit main_movielens.py main_reddit.py. The README FB and Reddit commands set 1000.
• Discriminator steps, MovieLens. Paper: 5 app. A. Code default: 10 main_movielens.py. The README MovieLens command does not override it.
• MovieLens encoder. Paper: embedding lookup with a log-likelihood score §5.1. Code default: TransE main_movielens.py. The README MovieLens command sets --use_gcmc=True, which switches to a graph-convolution encoder with a shared bilinear decoder main_movielens.py. The paper does not mention a graph-convolution encoder for MovieLens.
• MovieLens dropout. Paper: 0.3 app. C. Code: 0.3 is hard-coded in the discriminators model.py. The --dropout_p argument (default 0.2) is defined but never read main_movielens.py.
• Held-out Reddit combinations. Paper: 10% of user nodes held out app. D; in the experiments, 10% of combinations held out §5.2. Code: 10% of sensitive-attribute combinations, and only when --held_out_comp is set main_reddit.py. The README Reddit command does not set it. Which setting produced Table 4 is not stated.
• Filters. Paper: MLP with leaky ReLU between layers app. A. Code: two linear layers with BatchNorm on the output model.py. The BatchNorm is not described in the paper.
• Discriminator loss. Paper: sum over all attribute values a of log D(z, a) eq. 7. Code: the binary cross-entropy of the observed value for each active discriminator; the encoder term is minus this, so the sign matches paper_trans_e.py.
• Negative filtering. Paper: not mentioned. Code: sampled negatives that appear in the training set get zero weight in the margin loss, on by default for FB and MovieLens and off for Reddit paper_trans_e.py paper_trans_e.py main_reddit.py.
• Sensitive subreddits. Paper: sampled from the top 100 after excluding the top 5 §5.1. Code: sampled from a window of 101 nodes after skipping 5, filtering out user nodes main_reddit.py. The window is slightly larger than the paper's description.
• Not checked: the Reddit scoring function and loss; the MovieLens batch-norm after the embedding lookup app. C; the lambda and discriminator-step settings used for each table.

Pitfalls

• Composition scale. The paper's average keeps the embedding scale fixed as |S| changes, while the code's sum grows with |S|. A margin loss and an L1 norm are scale-sensitive, so picking one or the other changes results. Choose deliberately and test with subsets of different sizes. This is an inference from the code, not a paper claim.
• Empty invariance set. With K = 3, the empty set occurs in 1 of 8 masks. The paper leaves this undefined. The code uses the raw embedding, so the empty set enforces no invariance.
• Adversarial term. Equation 7 sums over all attribute values with no indicator for the observed one. Implement it as the log-probability of the observed value, as the code does, or the term is not the intended one.
• Lambda sensitivity. The theory needs lambda to go to infinity, but that gives trivial solutions. The paper's setting of 1000 is far from the code default of 0.1 and the README MovieLens setting of 10. Expect results to depend on this value.
• Discriminator update. The code runs all discriminator steps on one detached embedding batch paper_trans_e.py, so the discriminator sees the same batch five times per encoder step. This is a choice the paper does not describe.
• Evaluation protocol. Invariance is measured by training a fresh classifier of the discriminator's capacity on the frozen embedding §5.2 app. A. A weaker fresh classifier would overstate invariance, so keep capacity matched.
• Freebase is a poor fairness test. The attributes come from entity-type labels, which the authors note are probably relevant to the main task §5.2. The paper attributes the large accuracy loss there to this cause, so Freebase does not test the method alone.
• Generalisation claim. The Reddit held-out table shows a drop from 0.569 to 0.519 as the attribute count rises, and the paper calls this no significant degradation without a test app. E tab. 4.
• Hidden cost. Each filter and discriminator is a full MLP, and the discriminators are updated several times per step. Memory and time grow with K. The paper gives no timing.
• Environment. The README pins PyTorch 1.0 and requires Comet ML for logging README.md. The scripts call .cuda() unconditionally, for example in the discriminator and in corruption sampling paper_trans_e.py paper_trans_e.py paper_trans_e.py, so a GPU is required.
• Reproduction gap. The README MovieLens and Reddit commands differ from the paper's stated values (lambda, MovieLens encoder). Reproduce from the paper's settings and check against the README commands, not the other way round.

Lineage

• Builds on: adversarial fairness for representations, Edwards et al. (2015), cited in §1 and §5; the transfer-and-fairness work of Madras et al. (2018), cited in §2 and §6; the TransD encoder of Ji et al. (2015) §5.1; the GAN-style argument of Goodfellow et al. (2014) for §4.2; and the log-likelihood score of Berg et al. (2017) for MovieLens §5.1. The paper does not give arXiv ids for these works.
• Compared against: the same model with lambda = 0, and a non-compositional adversary that trains one encoder and one adversary per attribute §5.
• Superseded by: not stated.