Computing the Graph Edit Distance Using Dominant Sets

被引：0
|
作者：
Rebagliati, Nicola [1 ]
Sole-Ribalta, Albert [2 ]
Pelillo, Marcello [1 ]
Serratosa, Francesc [2 ]
机构：
[1] Univ Ca Foscari Venezia, Venice, Italy
[2] Univ Rovira & Virgili, Tarragona, Spain
来源：
2012 21ST INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION (ICPR 2012) | 2012年
关键词：
RECOGNITION;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We present a new approach to compute the graph edit distance between two attributed graphs which is based on a formal connection between the graph edit distance problem and that of finding a dominant set in an auxiliary edge-weighted "association" graph. Experiments performed on various data sets show that with the proposed approach we are able to improve on state-of-the-art algorithms.
引用
收藏
页码：1080 / 1083
页数：4
相关论文
共 50 条
  • [1] Computing graph edit distance on quantum devices
    Incudini, Massimiliano
    Tarocco, Fabio
    Mengoni, Riccardo
    Di Pierro, Alessandra
    Mandarino, Antonio
    QUANTUM MACHINE INTELLIGENCE, 2022, 4 (02)
  • [2] Efficient Parallel Computing of Graph Edit Distance
    Wang, Ran
    Fang, Yixiang
    Feng, Xing
    2019 IEEE 35TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING WORKSHOPS (ICDEW 2019), 2019, : 233 - 240
  • [3] Computing graph edit distance on quantum devices
    Massimiliano Incudini
    Fabio Tarocco
    Riccardo Mengoni
    Alessandra Di Pierro
    Antonio Mandarino
    Quantum Machine Intelligence, 2022, 4
  • [4] Computing Graph Edit Distance via Neural Graph Matching
    Piao, Chengzhi
    Xu, Tingyang
    Sun, Xiangguo
    Rong, Yu
    Zhao, Kangfei
    Cheng, Hong
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2023, 16 (08): : 1817 - 1829
  • [5] Bipartite graph matching for computing the edit distance of graphs
    Riesen, Kaspar
    Neuhaus, Michel
    Bunke, Horst
    GRAPH-BASED REPRESENTATIONS IN PATTERN RECOGNITION, PROCEEDINGS, 2007, 4538 : 1 - +
  • [6] Graph Edit Distance or Graph Edit Pseudo-Distance?
    Serratosa, Francesc
    Cortes, Xavier
    Moreno, Carlos-Francisco
    STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2016, 2016, 10029 : 530 - 540
  • [7] Approximating Graph Edit Distance Using GNCCP
    Gauzere, Benoit
    Bougleux, Sebastien
    Brun, Luc
    STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2016, 2016, 10029 : 496 - 506
  • [8] Graph Similarity Using Tree Edit Distance
    Dwivedi, Shri Prakash
    Srivastava, Vishal
    Gupta, Umesh
    STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2022, 2022, 13813 : 233 - 241
  • [9] PyGTED: Python']Python Application for Computing Graph Traversal Edit Distance
    Boroojeny, Ali Ebrahimpour
    Shrestha, Akash
    Sharifi-zarchi, Ali
    Gallagher, Suzanne Renick
    Sahinalp, Suleyman Cenk
    Chitsaz, Hamidreza
    JOURNAL OF COMPUTATIONAL BIOLOGY, 2020, 27 (03) : 436 - 439
  • [10] A survey of graph edit distance
    Xinbo Gao
    Bing Xiao
    Dacheng Tao
    Xuelong Li
    Pattern Analysis and Applications, 2010, 13 : 113 - 129
12345