PaperlayerView exact revision on arXiv

Source-linked AI summary

CrossWalk: Fairness-enhanced Node Representation Learning

Ahmad Khajehnejad, Moein Khajehnejad, Mahmoudreza Babaei, Krishna P. Gummadi, Adrian Weller, Baharan Mirzasoleiman

arXiv:2105.02725v2cs.LGcs.SIstat.ML

TL;DR

Fairness in graph algorithms has received little attention despite the potential for algorithmic decisions to affect population groups differently. CrossWalk reweights random-walk edges to encourage movement across group boundaries, and experiments report improved fairness across several graph tasks on synthetic and real networks with little performance compromise.

  • Problem

    There has been little work on enhancing fairness in graph algorithms, although their outcomes can affect population groups disproportionately.

    Source: §1 · p. 1

  • Method

    CrossWalk biases random walks across group boundaries by upweighting edges near group peripheries or connecting different groups.

    Source: §1 · p. 1

  • Results

    Across synthetic and real networks, CrossWalk improves fairness in influence maximization, node classification, and link prediction without significant compromise in total performance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The reweighting strategy applies to DeepWalk and Node2Vec representations and supports fairness evaluation across multiple graph algorithms.

    Source: §7 · p. 7

    The formulation assumes a directed network with nodes partitioned into groups.

    Source: §3 · p. 3

Abstract

from arXiv · show

The potential for machine learning systems to amplify social inequities and unfairness is receiving increasing popular and academic attention. Much recent work has focused on developing algorithmic tools to assess and mitigate such unfairness. However, there is little work on enhancing fairness in graph algorithms. Here, we develop a simple, effective and general method, CrossWalk, that enhances fairness of various graph algorithms, including influence maximization, link prediction and node classification, applied to node embeddings. CrossWalk is applicable to any random walk based node representation learning algorithm, such as DeepWalk and Node2Vec. The key idea is to bias random walks to cross group boundaries, by upweighting edges which (1) are closer to the groups' peripheries or (2) connect different groups in the network. CrossWalk pulls nodes that are near groups' peripheries towards their neighbors from other groups in the embedding space, while preserving the necessary structural properties of the graph. Extensive experiments show the effectiveness of our algorithm to enhance fairness in various graph algorithms, including influence maximization, link prediction and node classification in synthetic and real networks, with only a very small decrease in performance.

1 Introduction

CrossWalk addresses the limited work on fairness in graph algorithms by reweighting random-walk edges to encourage cross-group movement. Experiments report improved fairness across several graph algorithms on synthetic and real networks, without significant compromise in total performance.

1 Introduction

  • Despite growing attention to algorithmic fairness, little work has focused on fairness in graph algorithms.The paper points to influence maximization and node classification as examples where group disparities matter.Source: §1 · p. 1
  • CrossWalk biases random walks toward group boundaries by upweighting edges near group peripheries or connecting different groups.The resulting embeddings pull peripheral nodes toward neighbors from other groups while preserving necessary graph structure.Source: §1 · p. 1
  • Across synthetic and real networks, CrossWalk improves fairness in influence maximization, node classification, and link prediction without significant compromise in total performance.Experiments apply DeepWalk and Node2Vec to learn representations before evaluating the graph algorithms.Source: §1 · p. 2

2 Related Work

Prior work covers graph representation learning and fairness methods for individual graph tasks, while this paper positions CrossWalk as a general approach spanning multiple algorithms.

2 Related Work

  • Prior research on fairness in machine learning has paid limited attention to graph algorithms such as influence maximization, node classification, and link prediction.The paper reviews network embedding alongside fairness work in these graph tasks.Source: §2 · p. 2

Representation Learning on Graphs

  • DeepWalk and Node2Vec learn node representations from random walks, with Node2Vec balancing breadth-first and depth-first exploration.DeepWalk optimizes a Skip-gram likelihood objective over random walks; Node2Vec's search balance can preserve community structure and structural equivalence.Source: Representation Learning on Graphs · p. 2

Fair Influence Maximization

  • Fair influence maximization work includes diverse seed selection and adversarial representations, but earlier seed-diversification methods do not account for fairness.The paper uses adversarial network representation learning as a baseline.Source: Fair Influence Maximization · p. 2

Fair Node Classification

  • Prior fair-representation methods for classification use task-specific similarity, and the authors report no known fairness-enhanced graph representation method for classification.The cited approaches seek similar outcomes for individuals deemed similar under a task-specific metric.Source: Fair Node Classification · p. 2

Fair Link Prediction

  • FairWalk modifies random walks for fair link prediction but can fail when most nodes lie more than one hop from group peripheries; CrossWalk targets broader graph-algorithm use.The paper contrasts task-specific fairness methods with its general approach across influence maximization, link prediction, and node classification.Source: Fair Link Prediction · pp. 2–3

3 Problem Formulation

The formulation considers a directed, group-partitioned graph and modifies its edge weights for random-walk-based representations. The objective is to reduce disparity in algorithm performance across groups.

3 Problem Formulation

  • The formulation assumes a directed graph whose nodes are partitioned into groups, with edge weights and immediate neighborhoods defined for each node.DeepWalk and Node2Vec are cited as representation-learning methods that use random walks to preserve higher-order proximity.Source: §3 · p. 3
  • A random walk is a sequence of vertices connected by graph edges, with each next node generated according to a transition distribution.For weighted networks, normalized edge weights can serve as transition probabilities.Source: §3 · p. 3
  • The method maps original edge weights to modified weights for random-walk embeddings, aiming for lower disparity between group-level and whole-graph algorithm performance.The formulation defines Q as whole-graph performance and Q_i as performance for group i; examples include infected-node and correctly labeled or detected fractions.Source: §3 · p. 3

4 Our Method: CrossWalk

CrossWalk biases random walks toward group boundaries and other groups by reweighting edges according to node proximity and group membership. Its reweighting pulls embeddings across groups while preserving existing graph edges, and differs from FairWalk by also steering walks from within-group nodes toward group peripheries.

Bias towards Group Boundaries

  • CrossWalk reweights edges near group peripheries and edges connecting different groups to steer walks toward boundaries and across groups.The proximity m(v) estimates how often other-group nodes are visited in truncated walks; nodes with larger proximity receive greater weight.Source: §4 · p. 3, Bias towards Group Boundaries · pp. 3–4, Figure 1 · p. 4

Bias towards Other Groups

  • For same-group and cross-group outlinks, CrossWalk scales weights by m(u)^p and allocates total transition weight 1 − α and α/|R_v|, respectively.The parameter p controls bias toward boundary nodes, while α controls the probability of crossing to other groups.Source: Bias towards Other Groups · p. 4

CrossWalk Enhances Fairness

  • Reweighted walks spend more time at group boundaries, pulling nearby cross-group embeddings together while retaining the graph’s existing edges.For networks where most nodes are more than one hop from a boundary, larger p favors walks toward other groups; with more intergroup connections, larger α is recommended.Source: CrossWalk Enhances Fairness · p. 4

CrossWalk vs FairWalk

  • Unlike FairWalk, CrossWalk reweights within-group edges toward peripheries, so walks from interior nodes can reach other groups sooner, including via a group’s sole gateway.Its tunable α also maintains a constant 1 − α probability of staying within the same group, unlike FairWalk’s boundary-node allocation.Source: CrossWalk vs FairWalk · p. 5

5 Applications

This section applies CrossWalk-learned embeddings to influence maximization, node classification, and link prediction. It describes task-specific workflows and connects cross-group embedding proximity with reduced disparity across groups.

5 Applications

  • CrossWalk embeddings support influence maximization, node classification, and link prediction as applications of the reweighting strategy.The section also refers to an Independent Cascade influence-maximization application in the supplementary material.Source: §5 · p. 5
  • For influence maximization, the method selects centrally located embedding-space nodes as seeds using k-medoids clustering.The selected seeds’ spread is simulated on the original, unreweighted graph under the Independent Cascade model.Source: §5 · p. 5

Node Classification

  • For node classification, Label Propagation uses a k-nearest graph; for link prediction, logistic regression classifies edges using elementwise-squared differences between endpoint embeddings.The link-prediction evaluation holds out 10% of existing edges as positive test data and uses an equal number of non-existing edges as negatives.Source: Node Classification · pp. 5–6
  • Cross-group nodes or edges become closer in the embedding space, which the paper links to shared labels across groups and reduced disparity in test accuracy.For influence maximization, centrally located nodes can be closer to multiple groups and spread information more effectively among them.Source: Node Classification · p. 6

6 Experiments

Experiments compare CrossWalk with fairness and performance baselines on real and synthetic networks, applying the learned representations to influence maximization, node classification, and link prediction. Across these tasks, CrossWalk reduces disparity, with reported trade-offs varying by dataset and task.

6 Experiments

  • Experiments use DeepWalk and FairWalk baselines on two real and two synthetic datasets, with k-medoids seed selection and greedy and adversarial baselines for influence maximization.The real datasets are Rice-Facebook and a Twitter subset; the influence experiments compare embedding-based seed selection with greedy selection.Source: §6 · p. 6, Influence Maximization · p. 6

Influence Maximization

  • CrossWalk reduces influence disparity more than FairWalk and adversarial embedding with little loss in total influence on Rice-Facebook and the 2-group synthetic network; on Twitter, it also improves total influence.On Twitter, FairWalk increases disparity compared with DeepWalk.Source: Figure 4 · p. 7, Influence Maximization · p. 7
  • On Rice-Facebook with Node2Vec, CrossWalk outperforms FairWalk in reducing influence disparity.The comparison uses CrossWalk with α = 0.5, p = 4 and FairWalk with p = 0.5, q = 0.5.Source: Figure 5 · p. 7, Influence Maximization · p. 7
  • For Label Propagation with k = 7 on Rice-Facebook, CrossWalk reduces node-classification disparity compared with FairWalk.The reported accuracy and disparity average 200 runs.Source: Figure 6 · p. 7, Influence Maximization · p. 7

Link Prediction

  • For link prediction, CrossWalk reduces disparity compared with FairWalk, with a slight decrease in accuracy.The evaluation averages five runs and samples equal numbers of positive and negative test links for each connection type.Source: Figure 7 · p. 7, Link Prediction · p. 7

7 Conclusion

CrossWalk reweights graph edges to improve fairness in graph algorithms applied to random-walk node embeddings. The paper applies the strategy with DeepWalk and Node2Vec across three tasks and reports effectiveness on synthetic and real networks.

7 Conclusion

  • CrossWalk enhances fairness in graph algorithms that use random-walk-based node embeddings.The method upweights edges near group peripheries or connecting different groups.Source: §7 · p. 7
  • The reweighting strategy is applied with DeepWalk and Node2Vec to influence maximization, node classification, and link prediction.Source: §7 · p. 7
  • Experiments on synthetic and real networks confirm CrossWalk’s effectiveness for enhancing fairness across these graph algorithms.Source: §7 · p. 7

A Classical Influence Maximization

Classical influence maximization selects a set of seeds to maximize information spread. The section describes how edge reweighting changes influence under the Independent Cascade model and how results are evaluated.

A Classical Influence Maximization

  • Influence maximization chooses k seed nodes to maximize expected spread; under the Independent Cascade model, the utility is monotone submodular and greedy selection has a logarithmic approximation guarantee.The utility counts expected individuals infected at the end of diffusion.Source: A Classical Influence Maximization · pp. 7–8
  • Reweighting increases activation chances for peripheral nodes and cross-group spread from boundary nodes, encouraging greedy selection of seeds that can reach other groups.The passage connects this mechanism to reduced disparity in the number of influenced individuals across groups.Source: A Classical Influence Maximization · p. 8
  • The greedy algorithm simulates Independent Cascade diffusion with transmission probabilities scaled by the reweighting weights, but evaluates the selected seeds on the original graph.Source: A Classical Influence Maximization · p. 8

B Effect of Bias parameters α and p

CrossWalk’s influence fairness gains depend on the network and bias parameters: larger p values improve fairness in the tested setting, while networks with more inter-group connections call for larger α.

C Code and Data

The paper provides its experiment code and datasets in an anonymous repository, with instructions for regenerating figures and running task-specific code.

  • Source code and experimental datasets are available in the paper’s anonymous GitHub repository.The datasets are in its “data” directory.Source: C Code and Data · p. 8
  • Section 6 figures can be regenerated with notebooks, while Figure 3 uses code in the “tsne” directory.Source: C Code and Data · p. 8
  • The “deepwalk” directory generates embeddings, and separate influence-maximization, classifier, and link-prediction directories contain task code.Dataset files and embeddings must be placed in the appropriate subdirectories before running the code.Source: C Code and Data · p. 8
  • Figures 8–9 cover reweighting’s greedy IC effect on Rice-Facebook and α,p fairness comparisons of DeepWalk versus CrossWalk embeddings on synthetic graphs.The plotted y-axis is the averaged difference in influenced fractions between groups across k=1–40 seeds.Source: Figure 8 · p. 9, Figure 9 · p. 9, C Code and Data · p. 9

Related papers

Loading 2105.02725v2…