.png){kind=icon}
Return
Efficient graph edit distance computation using isomorphic vertices
.png){kind=icon}
PRE
AI
DOI：10.1016/j.patrec.2023.03.002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we study the problem of graph edit distance (GED) computation. We empirically observe that real graph data contain many isomorphic substructures, which incur redundant computation. Based on this observation, we aim at reducing the cost of GED computation by avoiding redundant computation caused by isomorphic substructures. To detect isomorphic substructures, we precisely define a notion of vertex isomorphism and propose a dynamic programming algorithm that identifies isomorphic vertices in a graph. By taking advantage of isomorphic vertices, we develop an efficient GED computation algorithm. In experiments, we show that isomorphic vertices are effectively used in reducing the search space of GED computation, and as a result our approach improves the performance of GED computation.(c) 2023 Elsevier B.V. All rights reserved.
Keywords:
Graph similarity
Graph edit distance
Vertex isomorphism
Search space reduction
Journal
IF:
3.3
Papers:
8.0K
Citations:
1.6W
Organization
Cited Papers
ShareSaveShareSaveMapping landscape connectivity as a driver of species richness under tectonic and climatic forcing
OAAI
OAAIShareSaveHGED: A Hybrid Search Algorithm for Efficient Parallel Graph Edit Distance Computation.png)
IEEE ACCESSOAAI
IEEE ACCESSIF3.6
OAAIShareSaveShareSaveShareSave
View more