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

Feb 17, 2026

Random Wavelet Features for Graph Kernel Machines

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.

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

Ask PDF

Aug 10, 2026

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

Node ranking is a fundamental problem in graph information retrieval, measuring the relative importance of nodes and supporting a wide range of applications such as influence analysis, recommendation, and graph-based retrieval augmented generation. However, exact computation of graph-based ranking measures is often computationally prohibitive at scale. Existing GNN-based ranking methods provide scalable approximations, but they are typically tailored to individual ranking criteria and require retraining for each downstream task, which limits their transferability and efficiency. Recent graph pre-training approaches aim to enable knowledge transfer across tasks, yet their learning objectives are largely misaligned with node ranking, resulting in suboptimal adaptability to ranking-oriented applications. To address these limitations, we propose PreGress, the first ranking-native pre-training and prompting framework for supporting a wide range of node ranking tasks. PreGress performs multi-task pre-training using our carefully designed objectives, including degree centrality prediction and attribute reconstruction, to jointly capture structural and attribute information. To support heterogeneous ranking criteria, we design lightweight, task-specific prompt modules that adapt a frozen ranking backbone to downstream tasks without full retraining. Experiments on six public graphs and two real-world query-to-item benchmarks---Yelp2018 and MovieLens-100K---together with a controlled five-criterion graph-access study demonstrate strong ranking quality with low task-specific state overhead.

Lujie Ban, Jiasheng shi, Yingli Zhou +5

School of Data Science, The Chinese University of Hong Kong, Shenzhen, China · GTS, Huawei Technologies Co., Ltd., China

Learning to Rank Prompt Tuning Graph Foundation Models

Ask PDF

Jul 7, 2026

Diffusion enabled Optimal Transport distances for graph matching

This paper introduces Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), a novel method for graph comparison that unifies node features and structural connectivity through optimal transport. While traditional Gromov-Wasserstein and semi-relaxed variants (srGW, srFGW) capture graph structure, they often struggle with sparse, noisy, or partially observed graphs. Inspired by Graph Diffusion Distance, which posits graphs are similar if they enable similar information transmission patterns, DsrFGW incorporates diffusion processes allowing information propagation across nodes, capturing local and global structural patterns while reducing sensitivity to noise or missing edges. An extensive evaluation on 36 synthetic pairwise graph matching tasks (easy, medium, hard) demonstrates consistent superiority over srFGW, achieving accuracy improvements of 0-20 percentage points and dramatic Adjusted Rand Index (ARI) gains: in medium-difficulty scenarios, srFGW often achieves negative ARI (worse than random) while DsrFGW offers better performance in terms of both internal and external clustering quality measures (i.e., Adjusted Rank Index and Accuracy with respect to the true underlying clusters, respectively). Even under severe noise, DsrFGW improves clustering quality in 92% of the synthetic tasks with optimal diffusion scales adapting to problem difficulty, establishing DsrFGW as a robust framework for graph comparison under structural uncertainty.

Iman Seyedi, Francesco Archetti

Department of Computer Science Systems and Communication, University of Milano-Bi- cocca, 20126 Milan, Italy

Graph Matching Wasserstein Distance

Ask PDF

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