# Robust Node Affinities via Jaccard-Biased Random Walks and Rank Aggregation

arXiv: https://arxiv.org/abs/2603.05375 · HTML: https://mlsanity.com/paper/2603.05375/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 5 Mar 2026.

## Builds on (most cited first, 9 of 9)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [RAW-GNN: RAndom Walk Aggregation based Graph Neural Network](https://mlsanity.com/paper/2206.13953/) (2022)
- [Transforming PageRank into an Infinite-Depth Graph Neural Network](https://mlsanity.com/paper/2207.00684/) (2022)
- [Parea: multi-view ensemble clustering for cancer subtype discovery](https://mlsanity.com/paper/2209.15399/) (2022)
- [Drug-disease networks and drug repurposing](https://mlsanity.com/paper/2510.19948/) (2025)

## Built on by (most cited first, 1 of 1)

- [Contrastive Representation Learning of Longitudinal Disease Trajectories on Temporal Graphs](https://mlsanity.com/paper/2607.25609/) (2026)

## Abstract (arXiv)

Estimating node similarity is a fundamental task in network analysis and graph-based machine learning, with applications in clustering, community detection, classification, and recommendation. We propose TopKGraphs, a method based on start-node-anchored random walks that bias transitions toward nodes with structurally similar neighborhoods, measured via Jaccard similarity. Rather than computing stationary distributions, walks are treated as stochastic neighborhood samplers, producing partial node rankings that are aggregated using robust rank aggregation to construct interpretable node-to-node affinity matrices. TopKGraphs provides a non-parametric, interpretable, and general-purpose representation of node similarity that can be applied in both network analysis and machine learning workflows. We evaluate the method on synthetic graphs (stochastic block models, Lancichinetti-Fortunato-Radicchi benchmark graphs), k-nearest-neighbor graphs from tabular datasets, and a curated high-confidence protein-protein interaction network. Across all scenarios, TopKGraphs achieves competitive or superior performance compared to standard similarity measures (Jaccard, Dice), a diffusion-based method (personalized PageRank), and an embedding-based approach (Node2Vec), demonstrating robustness in sparse, noisy, or heterogeneous networks. These results suggest that TopKGraphs is a versatile and interpretable tool for bridging simple local similarity measures with more complex embedding-based approaches, facilitating both data mining and network analysis applications.