[2603.05375] Robust Node Affinities via Jaccard-Biased Random Walks and Rank Aggregation

Computer Science > Machine Learning arXiv:2603.05375 (cs) [Submitted on 5 Mar 2026] Title:Robust Node Affinities via Jaccard-Biased Random Walks and Rank Aggregation Authors:Bastian Pfeifer, Michael G. Schimek View a PDF of the paper titled Robust Node Affinities via Jaccard-Biased Random Walks and Rank Aggregation, by Bastian Pfeifer and Michael G. Schimek View PDF HTML (experimental) Abstract: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 s...