Luca Pantea

MSc Student in Artificial Intelligence   University Logo   University of Amsterdam

Fairness-Enhanced Representational Learning | Luca Pantea

Fairness-Enhanced Representational Learning

February 25, 2024

The work was accepted for the 2022 Machine Learning Reproducibility Challenge and published in ReScience C journal and was awarded a $10,000 grant from Kaggle. Paper links: OpenReview | Kaggle | GitHub

Header Image

Recently, alongside Andrei, I ventured into the realm of fairness in machine learning by getting our hands dirty with reproducing “CrossWalk: Fairness-enhanced Node Representation Learning.” (paper link). The potential for machine learning systems to amplify social inequities and unfairness is receiving increasing popular and academic attention. However, there is little work enhancing fairness in graph algorithms. Even less in reproducing these algorithms, and verifying their claims…

Our starting point was the CrossWalk repository that the original authors were kind enough to share. Step $0$ to $1$ was done. However, $1$ to $n$ was a whole different story. The lack of documentation and some missing logic meant we had to roll up our sleeves and re-code from scratch. We packaged all our hard work into a neat Python package, so anyone could easily replicate the results and join in on the fun (here’s the repo link).

This is what we managed to do in a month’s time:

Quite a bit :) let’s dive into it.

The Original Model’s Inner workings

CrossWalk is a re-weighting method that is used to bias random walk-based algorithms towards visiting multiple groups, which in turn enhances fairness. This is mainly done by re-weighting the probabilities associated with the graph edges as follows:

The mathematical formulas that describe the re-weightings from points 1 and 2 are the following:

\[\begin{equation} w_{vu}^{'} = \begin{cases} w_{vu}(1-\alpha) \times \frac{m(u)^p}{\sum\limits_{z \in N_v} w_{vz}m(z)^p} & \text{if } u \in N(v), l_v = l_u \\ w_{vu}\alpha \times \frac{m(u)^p}{|R_{v}| \times \sum\limits_{z \in N_{v}^c} w_{vz}m(z)^p} & \text{if } u \in N(v), l_v \neq l_u = c.\end{cases} \end{equation}\]

where $w_{vu}$ is the initial weight of the edge $(u,v)$, $\alpha$ and $p$ are hyperparameters, $R_{v}$ the set of groups in the neighbourhood of $v$, $l_{x}$ the group that node $x$ is part of, and $m(z)$ is the proximity of a node as described in the original paper.

Cool 🎉. However, upon further in-depth study, we realised that this re-weighting caused some subtle, yet impactful issues.

In a nutshell, this re-weighting mechanism caused the random walks to travel back and forth between edges localted at group peripherals, esentially getting stuck in a loop. This is because the re-weighting mechanism is not self-avoiding, meaning that the random walks can visit the same edge multiple times. This is a problem because the random walks are supposed to be unbiased, and the re-weighting mechanism biases these trajectories in an undesirable way.

Through sampling and visually analyzing trajectories, we explored CrossWalk’s mechanics. The image at the beginning the page compares edge weights and a trajectory between a random walk algorithm without and with CrossWalk’s re-weighting. Lighter edges indicate higher edge weights, different node colors represent distinct groups, and a bolded blue line traces a sampled random walk trajectory. CrossWalk on the right visits fewer new nodes compared to the un-reweighted algorithm on the left, as the re-weighting mechanism leads the random walk into a repetitive loop, revisiting the same edges.

As a result, the structural properties of the graph are not fully utilized, leading to decreased representation quality.

Our Enhancement!

We propose a solution based on Self‐Avoiding Walks which steers the random walks towards avoiding previously visited edges by using a discounting function, parameterized by $\gamma$:

\[\begin{equation} P(u_i = u \lvert u_{i-1} = v) = \left\{ \begin{array}{ll} \pi_{uv} \cdot \gamma^{c(u,v)} & \quad \text{if} \ (u, v) \in E \\ 0 & \quad \text{otherwise} \end{array} \right. \end{equation}\]

Where $c(u, \ v)$ stores the number of times the walk has traversed the edge between node $u$ and $v$. As $\gamma \in [0, \ 1]$, if $\gamma \rightarrow 1$, the behaviour is similar to CrossWalk, while $\gamma \rightarrow 0$ stimulates the random walk to avoid already visited edges. $\pi_{uv}$ represents probability of selecting the edge $(u, \ v)$, weighted by the modifed edge weights of CrossWalk, as expressed above. We call this method SoftWalk.

Our implementation uses a HashMap initialized per random walk for storing the counts of the previously visited edges, which has a worst-case time and space complexity of $\mathcal{O}(K)$, where $K$ represents the preset random walk length. Thus, our proposed method scales with $K$, which supports scalability, as $K$ $«$ $\lvert E\lvert$, where $E$ is the set of graph edges for a given graph.

Our Results and a Bit of Discussion

The results indicate that the proposed extension consistently outperforms the original implementation of CrossWalk on the two reproducible tasks - Link Prediction and Node Classification. Softwalk not only achieves better accuracy and influence percentage but additionally minimizes the disparity (thus maximizing fairness) for each task. Check our paper to see the numbers and plots!


Our contributions suffer from three main drawbacks. First, due to time constraints, we were unable to resolve the outstanding issues regarding link predictions, yet we were able to obtain results that follow the same trends for the other tasks. Second, the re-implementation of the original base significantly decelerated the reproduction process. And finally, the proposed approach is independent of the underlying graph characteristics, which encourages future work in the direction of estimating $\gamma$ via a non-linear function approximation (i.e. neural network-based approaches).

If you made it this far, I hope you enjoyed the read and learned something new! If you have any questions, feel free to reach out to me on Twitter or LinkedIn. I’d love to hear your thoughts! 😊