arXiv:2603.05375cs.LG2026-03被引 1

用改进的随机游走计算节点相似性,更鲁棒且可解释。

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

  • 基于起点锚定的随机游走,优先访问结构相似邻居。
  • 在各类网络中表现优于Jaccard、PageRank等经典方法。
  • 适合需要可解释相似性的图分析与机器学习任务。

节点相似性估计是网络分析和基于图的机器学习中的基础任务,广泛应用于聚类、社区发现、分类和推荐。本文提出TopKGraphs方法,利用起点锚定的随机游走,通过杰卡德相似性度量结构相似的邻域,使转移偏向相似节点。不计算稳态分布,而是将游走视为随机邻域采样,生成部分节点排序,并通过鲁棒的排名聚合构建可解释的节点间亲和矩阵。该方法为节点相似性提供了一种非参数化、可解释且通用的表示,适用于网络分析与机器学习流程。我们在合成图(随机块模型、Lancichinetti-Fortunato-Radicchi基准图)、表格数据的k近邻图及高置信度蛋白质互作网络上评估了该方法。在所有场景中,TopKGraphs的表现均达到或超过标准相似性度量(如杰卡德、狄氏)、扩散方法(个性化PageRank)以及嵌入方法(Node2Vec),尤其在稀疏、噪声大或异质网络中表现出强鲁棒性。结果表明,TopKGraphs是一种连接局部相似性与复杂嵌入方法的多功能、可解释工具,有助于推动数据挖掘与网络分析应用。

原文摘要 · Abstract (English)

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.

图神经网络节点相似性随机游走可解释性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。