PaperlayerView exact revision on arXiv

Source-linked AI summary

FairDrop: Biased Edge Dropout for Enhancing Fairness in Graph Representation Learning

Indro Spinelli, Simone Scardapane, Amir Hussain, Aurelio Uncini

arXiv:2104.14210v2cs.LGstat.ML

TL;DR

Sensitive-attribute homophily can worsen fairness in graph learning, while link prediction requires fairness measures adapted to graph structure. FairDrop reduces that homophily through biased edge dropout and is evaluated for link prediction and node embeddings. The reported results show improved fairness across these tasks, with a small accuracy drop for node-embedding downstream tasks.

  • Problem

    Sensitive-attribute homophily can worsen fairness in graph learning, and link prediction calls for fairness measures that account for edge-level groups.

    Source: §I · p. 2

  • Method

    FairDrop generates fairer training graphs by dropping edges between nodes with matching sensitive attributes, and the paper pairs link-prediction evaluation with dyadic fairness measures.

    Source: §IV · p. 3, §VII · p. 9

  • Results

    FairDrop improves fairness metrics on every link-prediction dataset over unbiased dropout or no dropout, while Node2Vec with FairDrop improves sensitive-attribute obfuscation with a small downstream-accuracy drop.

    Source: A. Fair link prediction · p. 7, B. Fair representation learning · p. 7

  • Takeaways & Limitations

    FairDrop’s fairness intensity is regulated by one hyperparameter, and the approach can be used with different architectures or paired with other fairness constraints.

    Source: §VII · p. 9

    A possible limitation is extending FairDrop to settings with multiple sensitive attributes present at once.

    Source: §VII · p. 9

Abstract

from arXiv · show

Graph representation learning has become a ubiquitous component in many scenarios, ranging from social network analysis to energy forecasting in smart grids. In several applications, ensuring the fairness of the node (or graph) representations with respect to some protected attributes is crucial for their correct deployment. Yet, fairness in graph deep learning remains under-explored, with few solutions available. In particular, the tendency of similar nodes to cluster on several real-world graphs (i.e., homophily) can dramatically worsen the fairness of these procedures. In this paper, we propose a novel biased edge dropout algorithm (FairDrop) to counter-act homophily and improve fairness in graph representation learning. FairDrop can be plugged in easily on many existing algorithms, is efficient, adaptable, and can be combined with other fairness-inducing solutions. After describing the general algorithm, we demonstrate its application on two benchmark tasks, specifically, as a random walk model for producing node embeddings, and to a graph convolutional network for link prediction. We prove that the proposed algorithm can successfully improve the fairness of all models up to a small or negligible drop in accuracy, and compares favourably with existing state-of-the-art solutions. In an ablation study, we demonstrate that our algorithm can flexibly interpolate between biasing towards fairness and an unbiased edge dropout. Furthermore, to better evaluate the gains, we propose a new dyadic group definition to measure the bias of a link prediction task when paired with group-based fairness metrics. In particular, we extend the metric used to measure the bias in the node embeddings to take into account the graph structure.

I. INTRODUCTION

Graph homophily on sensitive attributes can worsen unfairness in graph learning, while fairness methods for graph data remain limited. FairDrop counters this bias through biased edge dropout, alongside dyadic fairness measures for link prediction and a graph-aware representation-bias metric.

I. INTRODUCTION

  • Homophily in sensitive attributes can restrict minority users’ links to majority groups, and unfair link prediction can increase segregation between groups.The paper identifies this segregation as a filter-bubble issue.Source: §I · pp. 1–2
  • FairDrop biases edge dropout to reduce sensitive-attribute homophily, while preserving most original accuracy and allowing combination with other fairness techniques.The paper notes that unfairness can also arise from adjacency weights or node features, which FairDrop does not address on its own.Source: §I · p. 2

A. Contributions of the paper

  • The contributions include dyadic edge groups for group-fairness metrics and a representation-bias metric that accounts for graph structure.The paper also describes FairDrop as a preprocessing and data-augmentation technique with one parameter regulating fairness intensity.Source: A. Contributions of the paper · p. 2

B. Outline of the paper

  • The paper’s roadmap introduces graph and fairness preliminaries, presents FairDrop, evaluates it, and concludes with general remarks.The outline places the method in Section IV and its evaluation in Section VI.Source: B. Outline of the paper · p. 2

II. RELATED WORKS

  • Prior approaches use adversarial constraints, learn fair adjacency, model sensitive priors, or rebalance walks; counterfactual augmentation requires a specified causal model,.The paper places these methods in a literature where most bias approaches address i.i.d. data rather than graph-structured data.Source: §II · p. 2

III. PRELIMINARIES

The preliminaries define a graph with node features and sensitive attributes, then frame link prediction as predicting whether two nodes are connected. They describe both end-to-end GNNs and unsupervised node embeddings as graph-learning routes.

A. Graph representation learning

  • The setup uses an undirected, unweighted graph whose nodes may have feature vectors and categorical sensitive attributes, represented through an adjacency matrix.The adjacency matrix supports operators that define communication across the graph.Source: A. Graph representation learning · pp. 2–3
  • Link prediction asks whether two nodes are likely to have a link, combining node features and graph structure through end-to-end optimization when features are available.The preliminaries also introduce the normalized graph Laplacian as a graph operator.Source: A. Graph representation learning · p. 3
  • An alternative first learns node embeddings without supervision, then uses them for downstream link prediction; the proposed framework applies to both this route and GNNs.Unsupervised embeddings can be reused across downstream tasks.Source: A. Graph representation learning · p. 3

B. Fairness measures in i.i.d. data

The section introduces group fairness for binary prediction and two common criteria: demographic parity and equalized odds. It notes that these i.i.d.-data definitions cannot be applied directly to graph-structured data.

B. Fairness measures in i.i.d. data

  • Group fairness concerns whether predictions disproportionately benefit or harm groups defined by sensitive attributes, but these definitions do not directly fit graph-structured data.Source: B. Fairness measures in i.i.d. data · p. 3
  • Demographic parity requires equal positive-outcome likelihood across sensitive groups, while equalized odds requires equal true-positive and false-positive rates.The section assumes binary sensitive attributes for simplicity and notes that the definitions extend to multiple categories.Source: B. Fairness measures in i.i.d. data · p. 3
  • The section measures departures from ideal fairness using group disparities, including differences in selection rates and discrepancies in true- and false-positive rates.Equalized-odds difference takes the largest discrepancy between the true-positive-rate and false-positive-rate differences across groups.Source: B. Fairness measures in i.i.d. data · p. 3

IV. PROPOSED BIASED EDGE DROPOUT TO ENHANCE FAIRNESS

FairDrop generates a fairer random adjacency matrix during training by reducing connections between nodes with matching sensitive attributes. Its pipeline builds and randomizes a homophily mask, then drops edges according to that mask.

IV. PROPOSED BIASED EDGE DROPOUT TO ENHANCE FAIRNESS

  • At each training epoch, FairDrop generates a random copy of the adjacency matrix that reduces connections between nodes sharing sensitive attributes.Source: §IV · p. 3
  • The three steps are to compute a sensitive-attribute homophily mask, perturb it with biased randomness, and remove edges according to the perturbed mask.Figure 1 depicts the mask, randomized response, and resulting graph in that order.Source: §IV · p. 3, Figure 1 · p. 4
  • Training on multiple fairness-enforcing adjacency copies is conjectured to increase input randomness and diversity, framing FairDrop as fairness-biased data augmentation.The paper compares this interpretation with noise-based data augmentation through standard dropout.Source: §IV · p. 3

A. Sensitive attribute homophily mask

The section encodes sensitive-attribute heterophily in an adjacency mask, then randomizes that mask to create a fairness-biased version for use in FairDrop.

A. Sensitive attribute homophily mask

  • The adjacency matrix M records heterogeneous connections between sensitive attributes, with m_ij = 1 marking an edge between nodes with different attribute values.The method identifies these heterogeneous connections as the type to promote when improving graph fairness.Source: A. Sensitive attribute homophily mask · p. 4

B. Randomized response

  • At δ = 0 randomized response always returns random answers, while δ = 1/2 yields clean data without privacy protection.These settings mark the endpoints of its privacy–data-utility trade-off.Source: B. Randomized response · p. 4
  • Randomized response takes the sensitive-attribute homophily mask as input and produces a randomized version for the FairDrop pipeline.The passage describes randomized response for binary questions: a coin determines whether respondents answer truthfully or at random.Source: B. Randomized response · p. 4

C. Fair edge dropout

FairDrop forms random adjacency copies that preferentially remove same-attribute connections, then uses these copies to train models or generate node embeddings.

C. Fair edge dropout

  • The resulting A_fair is a random copy of the original adjacency matrix, with dropout biased toward removing connections between nodes sharing a sensitive attribute.The reduction in unfair homophily is intended to appear in the learned embeddings or model predictions.Source: C. Fair edge dropout · p. 4
  • The parameter δ ranges from unbiased edge dropout at δ = 0 to removing all unfair edges and keeping all fair ones at its maximum.Increasing δ incrementally promotes fair connections; FairDrop adds almost no cost over standard edge dropout.Source: C. Fair edge dropout · p. 4
  • For multiple sensitive attributes, FairDrop can build a fair adjacency matrix for each attribute and alternate them during training.Source: C. Fair edge dropout · p. 4

D. Deployment

  • FairDrop acts as fairness-biased data augmentation, generating random fair copies and allowing combination with other fairness constraints.The paper considers end-to-end link prediction and link prediction after learning node embeddings.Source: D. Deployment · pp. 4–5
  • For embedding learning, FairDrop is paired with Node2Vec, generating a fairness-enforcing graph version for each batch of random walks.For end-to-end training, a different fair random copy is used each epoch with models such as GCN, GAT, or AP-GCN.Source: D. Deployment · p. 5

V. PROPOSED FAIRNESS METRICS FOR GRAPH REPRESENTATION LEARNING

The section adapts group fairness criteria to link prediction by defining dyadic groups over edges, including a proposed group dyadic criterion alongside existing alternatives.

A. Fairness for link prediction

  • Link prediction needs dyadic fairness because each edge joins two sensitive attributes, and the paper proposes group dyadic-level protection alongside existing mixed and subgroup criteria.Dyadic groups map node-level sensitive groups to edge-level groups so group fairness criteria can be applied to links.Source: A. Fairness for link prediction · p. 5, §V · p. 5
  • Mixed dyadic grouping places edges between nodes with the same sensitive attribute in an intra-group and all other edges in an inter-group.The paper notes this definition is common in recommender systems, where intra-group edges are associated with filter bubbles.Source: A. Fairness for link prediction · p. 5
  • Group dyadic grouping maps dyadic groups one-to-one to node-level groups, assigning each link twice so both endpoint groups are represented.Each assignment depends on one endpoint's sensitive attribute, regardless of the other endpoint's value.Source: A. Fairness for link prediction · p. 5
  • Sub-group dyadic fairness treats each possible connection between sensitive groups, including within-group connections, as a separate subgroup.The paper extends demographic parity and the other Section III-B metrics to the dyadic groups; Figure 2 visualizes the definitions and Figure 3 shows their Citeseer composition.Source: A. Fairness for link prediction · p. 5

B. Fairness for node embeddings

Representation bias measures how well sensitive attributes can be predicted from learned representations, and the paper extends this measure to link embeddings.

B. Fairness for node embeddings

  • A node embedding is considered fair when a classifier predicting the sensitive attribute performs at the level of a random classifier; representation bias is measured with balanced accuracy.The score is associated with the node embeddings Z.Source: B. Fairness for node embeddings · p. 5
  • For link embeddings, the method concatenates source and destination node embeddings and treats sensitive-attribute prediction as a multi-label task.The paper conjectures that information about the relation between nodes makes this classification task harder to score well on.Source: B. Fairness for node embeddings · p. 5
  • The link representation-bias score is the mean of balanced accuracies for the source-node and destination-node sensitive-attribute labels.Balanced accuracy may be unsuitable when groups are strongly under-represented; the authors say an unbalanced version can avoid underestimating hypothetical perfect accuracy for such a group.Source: B. Fairness for node embeddings · p. 6

VI. EVALUATION

Across link prediction and node-embedding evaluations, FairDrop improves fairness-related outcomes while retaining strong task performance. The evaluation also compares its training costs with FairAdj and DeBayes.

VI. EVALUATION

  • Each evaluation experiment uses 10 random seeds and 80/20 train-test splits, reports averages with standard deviations, and fixes δ at 0.25.Source: §VI · p. 6

A. Fair link prediction

  • Link-prediction experiments compare two-layer GCN and GAT models on Citeseer, Cora-ML, and PubMed, measuring accuracy, AUC, demographic parity difference, and equality of odds difference.The comparison includes original adjacency, unbiased edge dropout, FairDrop, and both configurations of FairAdj.Source: A. Fair link prediction · pp. 6–7
  • FairDrop improves link-prediction fairness on every dataset over unbiased or no dropout, with superior task performance and results close to or sometimes better than FairAdj.On Cora, FairAdj takes 16 seconds at T2=5 and 41 seconds at T2=20, versus 2 seconds for FairDrop.Source: A. Fair link prediction · p. 7
  • Sub-group dyadic metrics remain especially difficult to minimize on Cora, where every evaluated algorithm produces very unfair predictions; improvement is left to future work.The authors associate this difficulty with Cora’s high sensitive-attribute cardinality and dominant intra-group connections.Source: A. Fair link prediction · p. 7

B. Fair representation learning

  • Representation-bias experiments compare FairDrop with DeBayes and FairWalk on DBLP and FB using logistic regression, neural-network, and random-forest classifiers with cross-validated hyperparameters.The DBLP data excludes authors from Africa and Antarctica because they are under-represented.Source: B. Fair representation learning · p. 7
  • FairDrop improves sensitive-attribute obfuscation in Node2Vec embeddings, with its largest gain in Node RB and robustness across downstream classifiers, at a small accuracy drop.For Link RB, FairDrop performs on par with DeBayes when comparing how often each achieves the best score; FairWalk offers less protection but higher accuracy.Source: B. Fair representation learning · p. 7
  • On DBLP, Node2Vec with FairDrop takes 50 seconds versus DeBayes’s average 33 minutes; FairWalk adds almost 80 seconds to build walks and 200 seconds to train.The paper attributes FairWalk’s additional walk-construction work to evaluating each node’s neighborhood during the random walk.Source: B. Fair representation learning · p. 7

C. Ablation

The ablation shows a fairness–performance trade-off that depends on the dropout-bias parameter δ. Moderate bias can improve fairness without reducing AUC, while stronger bias can substantially reduce it.

C. Ablation

  • For δ ∈(0.2, 0.3), the end-to-end link prediction task has better or equal AUC paired with a fairness improvement.Above a certain δ, AUC drops substantially.Source: C. Ablation · p. 7
  • On FB, downstream link prediction AUC grows as representation biases decrease with higher δ.Figure 4 visualizes the trade-off between representation biases and downstream link prediction performance.Source: C. Ablation · p. 7, Figure 4 · p. 9
  • Small datasets and 2-hop aggregation are proposed as potential causes of the issue associated with strongly biased dropout.The passage connects these factors to the substantial AUC drop at higher δ.Source: C. Ablation · pp. 7, 9

VII. CONCLUSION

FairDrop uses biased edge dropout to target sensitive-attribute homophily, with one parameter controlling the fairness constraint. The conclusion also presents dyadic fairness metrics and notes boundaries and future directions for the approach.

VII. CONCLUSION

  • FairDrop is a flexible biased edge dropout method tested for unsupervised node embedding generation and link prediction.A single hyperparameter ranges from maximum fairness to unbiased edge dropout; the approach can be paired with different architectures and other fairness constraints.Source: §VII · p. 9
  • The paper adapts group fairness metrics to edge-defined dyadic groups and extends representation-bias evaluation to account for graph structure.It proposes a dyadic group closer to groups defined by sensitive attributes and plans further metric development for strong attribute imbalance.Source: §VII · p. 9
  • Extending FairDrop to multiple sensitive attributes is a possible limitation; alternating their masks may be sub-optimal.The authors propose mask alternation to guide biased dropout in this setting.Source: §VII · p. 9
  • Future work may combine perturbation-aware algorithms with fairness constraints for more selective edge sampling.The conclusion notes that edge connections do not all have equal importance, while randomness remains fundamental to FairDrop.Source: §VII · p. 9

Related papers

Loading 2104.14210v2…