FaRS: A High-Performance Automorphism-Aware Algorithm for Graph Similarity Matching

Abstract

Role-based similarity search, predicated on the topological structure of graphs, is a highly effective and widely applicable technique for various real-world information extraction applications. Although the prominent rolebased similarity algorithm, RoleSim, successfully provides the automorphic (role) equivalence of similarity between pairs of nodes, it does not effectively differentiate nodes that exhibit exact automorphic equivalence but differ in terms of structural equivalence within a given graph. This limitation arises from disregarding most adjacency similarity information between pairs of nodes during the RoleSim computation. To address this research gap, we propose a novel single-source role similarity search algorithm, named FaRS, which employs the top Γ maximum similarity matching technique to capture more information from the classes of neighboring nodes, ensuring both automorphic equivalence and structural equivalence of role similarity. Furthermore, we establi sh the convergence of FaRS and demonstrate its adherence to various axioms, including uniqueness, symmetry, boundedness, and triangular inequality. Additionally, we introduce the Opt FaRS algorithm, which optimizes the computation of FaRS through two acceleration components: path extraction tracking and precomputation (P-speedup and Out-speedup approach). Experimental results on real datasets demonstrate that FaRS and Opt FaRS outperform baseline algorithms in terms of both accuracy and efficiency.