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

Fan Wang, Weiren Yu, Hai Wang, Victor Chang

Research output: Chapter in Book/Published conference outputConference publication

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.
Original languageEnglish
Title of host publicationProceedings of the 9th International Conference on Complexity, Future Information Systems and Risk, COMPLEXIS 2024
EditorsAli Emrouznejad, Luigi Fortuna, Victor Chang
PublisherSciTePress
Pages17-29
Number of pages13
ISBN (Electronic)9789897586989
DOIs
Publication statusPublished - Apr 2024

Publication series

NameInternational Conference on Complexity, Future Information Systems and Risk, COMPLEXIS - Proceedings
ISSN (Electronic)2184-5034

Bibliographical note

Publisher Copyright:
Copyright © 2024 by SCITEPRESS - Science and Technology Publications, Lda.

Keywords

  • Link Analysis
  • Similarity Search
  • Web Search

Cite this