Ring Based Approximation of Graph Edit Distance

被引:7
作者
Blumenthal, David B. [1 ]
Bougleux, Sebastien [2 ]
Gamper, Johann [1 ]
Brun, Luc [2 ]
机构
[1] Free Univ Bozen Bolzano, Fac Comp Sci, Bolzano, Italy
[2] Normandie Univ, UNICAEN, ENSICAEN, CNRS,GREYC, Caen, France
来源
STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2018 | 2018年 / 11004卷
关键词
Graph edit distance; Graph matching; Upper bounds; SEARCH;
D O I
10.1007/978-3-319-97785-0_28
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The graph edit distance (GED) is a flexible graph dissimilarity measure widely used within the structural pattern recognition field. A widely used paradigm for approximating GED is to define local structures rooted at the nodes of the input graphs and use these structures to transform the problem of computing GED into a linear sum assignment problem with error correction (LSAPE). In the literature, different local structures such as incident edges, walks of fixed length, and induced subgraphs of fixed radius have been proposed. In this paper, we propose to use rings as local structure, which are defined as collections of nodes and edges at fixed distances from the root node. We empirically show that this allows us to quickly compute a tight approximation of GED.
引用
收藏
页码:293 / 303
页数:11
相关论文
共 50 条
  • [21] Efficient approximate approach for graph edit distance problem
    Dabah, Adel
    Chegrane, Ibrahim
    Yahiaoui, Said
    PATTERN RECOGNITION LETTERS, 2021, 151 : 310 - 316
  • [22] On the exact computation of the graph edit distance
    Blumenthal, David B.
    Gamper, Johann
    PATTERN RECOGNITION LETTERS, 2020, 134 : 46 - 57
  • [23] A Hausdorff Heuristic for Efficient Computation of Graph Edit Distance
    Fischer, Andreas
    Plamondon, Rejean
    Savaria, Yvon
    Riesen, Kaspar
    Bunke, Horst
    STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, 2014, 8621 : 83 - 92
  • [24] Suboptimal Graph Edit Distance Based on Sorted Local Assignments
    Riesen, Kaspar
    Ferrer, Miquel
    Bunke, Horst
    MULTIPLE CLASSIFIER SYSTEMS (MCS 2015), 2015, 9132 : 147 - 156
  • [25] Graph node matching for edit distance
    Moscatelli, Aldo
    Piquenot, Jason
    Berar, Maxime
    Heroux, Pierre
    Adam, Sebastien
    PATTERN RECOGNITION LETTERS, 2024, 184 : 14 - 20
  • [26] Graph edit distance: Restrictions to be a metric
    Serratosa, Francesc
    PATTERN RECOGNITION, 2019, 90 : 250 - 256
  • [27] Ligand-Based Virtual Screening Based on the Graph Edit Distance
    Rica, Elena
    Alvarez, Susana
    Serratosa, Francesc
    INTERNATIONAL JOURNAL OF MOLECULAR SCIENCES, 2021, 22 (23)
  • [28] HMM-based graph edit distance for image indexing
    Xiao, Bing
    Gao, Xinbo
    Tao, Dacheng
    Li, Xuelong
    INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY, 2008, 18 (2-3) : 209 - 218
  • [29] Learning edit cost estimation models for graph edit distance
    Cortes, Xavier
    Conte, Donatello
    Cardot, Hubert
    PATTERN RECOGNITION LETTERS, 2019, 125 : 256 - 263
  • [30] Learning graph edit distance by graph neural networks
    Riba, Pau
    Fischer, Andreas
    Llados, Josep
    Fornes, Alicia
    PATTERN RECOGNITION, 2021, 120