Title | ||
---|---|---|
Scalable Graph Isomorphism: Combining Pairwise Color Refinement And Backtracking Via Compressed Candidate Space |
Abstract | ||
---|---|---|
Graph isomorphism is a core problem in graph analysis of various application domains. Given two graphs, the graph isomorphism problem is to determine whether there exists an isomorphism between them. As real-world graphs are getting bigger and bigger, applications demand practically fast algorithms that can run on large-scale graphs. However, existing approaches such as graph canonization and subgraph isomorphism show limited performances on large-scale graphs either in time or space. In this paper, we propose a new approach to graph isomorphism, which is the framework of pairwise color refinement and efficient backtracking. The main features of our approach are: (1) pairwise color refinement and binary cell mapping (2) compressed CS (candidate space), and (3) partial failing set, which together lead to a much faster and scalable algorithm for graph isomorphism. Extensive experiments with real-world datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of running time. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/ICDE51399.2021.00122 | 2021 IEEE 37TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2021) |
DocType | ISSN | Citations |
Conference | 1084-4627 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Geonmo Gu | 1 | 10 | 2.15 |
Yehyun Nam | 2 | 0 | 0.34 |
Kunsoo Park | 3 | 1396 | 171.00 |
Zvi Galil | 4 | 3634 | 1426.98 |
Giuseppe F. Italiano | 5 | 0 | 0.34 |
Wook-Shin Han | 6 | 805 | 57.85 |