Image Processing and Analysis with Graphs

13

Graph Edit Distance—Theory, Algorithms, and Applications

Miquel Ferrer

Instiut de Robòtica i Informàtica Industrial

Universitat Politècnica de Catalunya - CSIC

Barcelona, Spain

Email: [e-mail]

Horst Bunke

NICTA, Victoria Research Laboratory

The University of Melbourne, Parkville

Victoria, Australia

Email: [e-mail]

CONTENTS

13.1  Introduction

13.2  Definitions and Graph Matching

13.2.1  Exact Graph Matching

13.2.1.1  Graph Similarity Measures Based on the MACS and the MICS

13.2.2  Error-Tolerant Graph Matching

13.2.3  Graph Edit Distance

13.3  Theoretical Aspects of GED

13.3.1  Edit Costs

13.3.1.1  Conditions on Edit Costs

13.3.1.2  Example of Edit Costs

13.3.2  Automatic Learning of Edit Costs

13.3.2.1  Learning Probabilistic ...