Graph Edit Distance in the Exact Context

被引：2

作者：

Darwiche, Mostafa ^{[1
,2
]}

Raveaux, Romain ^{[1
]}

Conte, Donatello ^{[1
]}

T'Kindt, Vincent ^{[2
]}

机构：

[1] Univ Tours, LIFAT EA6300, 64 Ave Jean Portalis, F-37200 Tours, France

[2] Univ Tours, LIFAT EA6300, ROOT ERL CNRS 7002, 64 Ave Jean Portalis, F-37200 Tours, France

来源：

STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2018 | 2018年 / 11004卷

关键词：

Graph Edit Distance; Graph Matching; Mixed Integer Linear Program; LINEAR-PROGRAMMING FORMULATION; ASSIGNMENT; ALGORITHMS;

D O I：

10.1007/978-3-319-97785-0_29

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents a new Mixed Integer Linear Program (MILP) formulation for the Graph Edit Distance (GED) problem. The contribution is an exact method that solves the GED problem for attributed graphs. It has an advantage over the best existing one when dealing with the case of dense of graphs, because all its constraints are independent from the number of edges in the graphs. The experiments have shown the efficiency of the new formulation in the exact context.

引用

页码：304 / 314

页数：11

共 15 条

[1]

Abu-Aisheh Zeina, 2015, Graph-Based Representations in Pattern Recognition. 10th IAPR-TC-15 International Workshop, GbRPR 2015. Proceedings: LNCS 9069, P138, DOI 10.1007/978-3-319-18224-7_14

[2]

[Anonymous], 2015, 4 INT C PATT REC APP

[3] Graph edit distance as a quadratic assignment problem [J].

Bougleux, Sebastien ;

Brun, Luc ;

Carletti, Vincenzo ;

Foggia, Pasquale ;

Gauzere, Benoit ;

Vento, Mario .

PATTERN RECOGNITION LETTERS, 2017, 87 :38-46

[4] On a relation between graph edit distance and maximum common subgraph [J].

Bunke, H .

PATTERN RECOGNITION LETTERS, 1997, 18 (08) :689-694

[5] A local branching heuristic for solving a Graph Edit Distance Problem [J].

Darwiche, Mostafa ;

Conte, Donatello ;

Raveaux, Romain ;

T'Kindt, Vincent .

COMPUTERS & OPERATIONS RESEARCH, 2019, 106 :225-235

[6] Improving bipartite graph matching by assessing the assignment confidence [J].

Ferrer, Miquel ;

Serratosa, Francesc ;

Riesen, Kaspar .

PATTERN RECOGNITION LETTERS, 2015, 65 :29-36

[7] A Graph Repository for Learning Error-Tolerant Graph Matching [J].

Francisco Moreno-Garcia, Carlos ;

Cortes, Xavier ;

Serratosa, Francesc .

STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2016, 2016, 10029 :519-529

[8] A binary linear programming formulation of the graph edit distance [J].

Justice, Derek ;

Hero, Alfred .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2006, 28 (08) :1200-1214

[9] New binary linear programming formulation to compute the graph edit distance [J].

Lerouge, Julien ;

Abu-Aisheh, Zeina ;

Raveaux, Romain ;

Heroux, Pierre ;

Adam, Sebastien .

PATTERN RECOGNITION, 2017, 72 :254-265

[10] ALGORITHMS FOR THE ASSIGNMENT AND TRANSPORTATION PROBLEMS [J].

MUNKRES, J .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1957, 5 (01) :32-38

← 1 2 →