# Role Similarity Metric Based on Spanning Rooted Forest

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 60 references that are in the map.
- First posted on arXiv 15 Oct 2021.

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

- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [RiWalk: Fast Structural Node Embedding via Role Identification](https://mlsanity.com/paper/1910.06541/) (2019)
- [Panther: Fast Top-k Similarity Search in Large Networks](https://mlsanity.com/paper/1504.02577/) (2015)
- [Measure of Node Similarity in Multilayer Networks](https://mlsanity.com/paper/1606.00715/) (2016)
- [ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs](https://mlsanity.com/paper/1709.06955/) (2017)
- [New Approximation Algorithms for Forest Closeness Centrality -- for Individual Vertices and Vertex Groups](https://mlsanity.com/paper/2101.06192/) (2021)

## Abstract (arXiv)

As a fundamental issue in network analysis, structural node similarity has received much attention in academia and is adopted in a wide range of applications. Among these proposed structural node similarity measures, role similarity stands out because of satisfying several axiomatic properties including automorphism conformation. Existing role similarity metrics cannot handle top-k queries on large real-world networks due to the high time and space cost. In this paper, we propose a new role similarity metric, namely textsfForestSim. We prove that textsfForestSim is an admissible role similarity metric and devise the corresponding top-k similarity search algorithm, namely textsfForestSimSearch, which is able to process a top-k query in O(k) time once the precomputation is finished. Moreover, we speed up the precomputation by using a fast approximate algorithm to compute the diagonal entries of the forest matrix, which reduces the time and space complexity of the precomputation to O(ε-2mlog5nlogfrac1ε) and O(mlog3n), respectively. Finally, we conduct extensive experiments on 26 real-world networks. The results show that textsfForestSim works efficiently on million-scale networks and achieves comparable performance to the state-of-art methods.