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

Bastian Pfeifer; Michael G. Schimek

cs.LGMar 5, 2026

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

Authors: Bastian Pfeifer, Michael G. Schimek

Organizations: Institute for Medical Informatics, Statistics and Documentation, Medical University Graz, Austria.

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 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.

Figures & tables

Figure 1: Community detection performance on synthetic stochastic block model (SBM) graphs with varying intra-community density. Boxplots show the distribution of Adjusted Rand Index (ARI) values across 50 simulations. Hierarchical clustering (Ward’s method) was applied to node affinity matrices derived from six approaches: TopKGraphs, Jaccard similarity, Dice similarity, Laplacian embedding, personalized PageRank, and Node2Vec. Synthetic graphs had three equally sized communities (ten nodes each) with fixed low inter-community connection probability (0.05) and intra-community probabilities ranging from 0.10 to 0.50.

Figure 2: Community detection performance on synthetic stochastic block model (SBM) graphs with varying inter-community density. Boxplots show the distribution of Adjusted Rand Index (ARI) values across 50 simulations. Hierarchical clustering (Ward’s method) was applied to node affinity matrices derived from six approaches: TopKGraphs, Jaccard similarity, Dice similarity, Laplacian embedding, personalized PageRank, and Node2Vec. Synthetic graphs had three equally sized communities (ten nodes each) with fixed intra-community connection probability of

0.50

and inter-community probabilities ranging from 0.01 to 0.30.

Figure 3: Community detection performance on synthetic LFR benchmark graphs. Boxplots display the distribution of Adjusted Rand Index (ARI) values over 50 simulation runs. In each iteration, an LFR benchmark graph (100 nodes, average degree 5, maximum degree 10) was generated with varying mixing parameter

\mu=[0.03,0.05,0.10,0.20,0.30]

, fixed degree exponent

\tau_{1}=2

, and fixed community size exponent

\tau_{2}=1.1

(community sizes between 5 and 50 nodes). Hierarchical clustering (Ward’s method) was applied to node-affinity matrices derived from six approaches: TopKGraphs, Jaccard similarity, Dice similarity, Laplacian embedding, personalized PageRank, and Node2Vec. Clustering performance was evaluated against the planted LFR community structure.

Panel of Figure 4 — Figure 4: Effect of random walk length and number of walks on community detection performance. Mean and standard deviation of Adjusted Rand Index (ARI) values from 50 simulation runs are displayed while subsequently increasing (a) walk length and (b) number of walks. Hierarchical clustering (Ward’s method) was applied to node-affinity representations obtained from TopKGraphs and Node2Vec. (a) LFR benchmark graphs (100 nodes, average degree 5, maximum degree 10, community sizes between 5 and 50 nodes). The mixing parameter was set to $\mu=0.05$ , with degree exponent $\tau_{1}=2$ and community size exponent $\tau_{2}=1.1$ . (b) SBM benchmark graphs with three equally sized communities (ten nodes each), fixed intra-community connection probability of $0.50$ and inter-community probabilities of $0.05$ .

Figure 5: Computational scaling of node-affinity methods on synthetic LFR graphs. Runtime (in seconds) as a function of graph size for six node-affinity approaches: TopKGraphs, Node2Vec, Jaccard similarity, Dice similarity, Laplacian embedding, and personalized PageRank. For each graph size (50–1000 nodes), an LFR benchmark graph was generated (average degree 5, maximum degree 10, mixing parameter

\mu=0.05

\tau_{1}=2

\tau_{2}=1.1

), and the computation time required to obtain the corresponding affinity matrix or embedding was recorded. The figure illustrates the computational scaling behavior of the different methods as network size increases.

Figure 6: Clustering performance on the Breast Cancer Wisconsin dataset using kNN graph representations. Bar plots show the mean clustering performance (± standard deviation over 50 runs) measured by Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), and Adjusted Mutual Information (AMI). A k-nearest neighbor (kNN) graph was constructed from standardized feature vectors (30 features), with

k\in\{5,7,10\}

. Hierarchical clustering (Ward’s method) was applied to node-affinity matrices derived from TopKGraphs, Jaccard similarity, Dice similarity, personalized PageRank, and Node2Vec embeddings. Performance was evaluated against the ground-truth diagnostic labels (malignant vs. benign).

Figure 7: Node-affinity evaluation on the CORA citation network. Performance was assessed on randomly sampled connected subgraphs (100 nodes) from the largest connected component of the CORA citation network over 50 runs. Node-affinity matrices were computed using TopKGraphs, Node2Vec, Jaccard similarity, Dice similarity, and personalized PageRank. Left: k-nearest neighbor (kNN) classification performance measured by Balanced Accuracy for

k\in\{5,7,10\}

, using distances derived from each affinity representation. Boxplots summarize variability across runs. Right: Community detection performance obtained via hierarchical clustering (Ward’s method) applied to each affinity matrix. Bars show mean ± standard error for Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), and Adjusted Mutual Information (AMI), evaluated against the ground-truth paper subject classes.

Figure 8: Node-affinity evaluation on the human protein–protein interaction (PPI) network. Performance was assessed on randomly sampled connected subgraphs (100 nodes) from the largest connected component of a high-confidence STRING PPI network (combined score greater than 990), restricted to genes with curated disease annotations from DisGeNET. Small disease categories (

<20

genes) and overly dominant classes (e.g., prostate cancer) were removed to obtain balanced disease communities. Results are aggregated over 50 runs. Node-affinity matrices were computed using TopKGraphs, Node2Vec, Jaccard similarity, Dice similarity, and personalized PageRank. Left: k-nearest neighbor (kNN) classification performance measured by Balanced Accuracy for

k\in\{5,7,10\}

Graph Representation Learning

Graph representation learning develops methods for encoding nodes, edges, and whole graphs for prediction, comparison, and transfer.

See all 305 papers

Random Wavelet Features for Graph Kernel Machines
Feb 17, 2026Valentin de Bassompierre, Jean-Charles Delvenne, Laurent JacquesGraph Representation Learning Graph Embedding
INMA/ICTEAM, UCLouvain, Belgium
PreGress: Ranking-Native Pre-training and Prompting for Graph Node Ranking
Aug 10, 2026Lujie Ban, Jiasheng shi, Yingli Zhou +5Learning to Rank Prompt Tuning
School of Data Science, The Chinese University of Hong Kong, Shenzhen, China · GTS, Huawei Technologies Co., Ltd., China
Diffusion enabled Optimal Transport distances for graph matching
Jul 7, 2026Iman Seyedi, Francesco ArchettiGraph Matching Wasserstein Distance
Department of Computer Science Systems and Communication, University of Milano-Bi- cocca, 20126 Milan, Italy

Feb 17, 2026J/K move · Enter open · S save

Random Wavelet Features for Graph Kernel Machines

Valentin de Bassompierre, Jean-Charles Delvenne, Laurent Jacques

INMA/ICTEAM, UCLouvain, Belgium

Graph Representation Learning Graph Embedding Spectral Graph Embedding Kernel Methods Random Feature Methods

Open paper AskPDF arXiv

Node embeddings map graph vertices into low-dimensional Euclidean spaces while preserving structural information. They are central to tasks such as node classification, link prediction, and signal reconstruction. A key goal is to design node embeddings whose dot products capture meaningful notions of node similarity induced by the graph. Graph kernels offer a principled way to define such similarities, but their direct computation is often prohibitive for large networks. Inspired by random feature methods for kernel approximation in Euclidean spaces, we introduce randomized spectral node embeddings whose dot products estimate a low-rank approximation of any specific graph kernel. We provide theoretical and empirical results showing that our embeddings achieve more accurate kernel approximations than existing methods, particularly for spectrally localized kernels. These results demonstrate the effectiveness of randomized spectral constructions for scalable and principled graph representation learning.

Abstract

Graph Representation Learning

Explore similar work

Random Wavelet Features for Graph Kernel Machines

PreGress: Ranking-Native Pre-training and Prompting for Graph Node Ranking

Diffusion enabled Optimal Transport distances for graph matching