Flexible graph matching and graph edit distance using answer set programming

Sheung Chi Chan, James Cheney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The graph isomorphism, subgraph isomorphism, and graph edit distance problems are combinatorial problems with many applications. Heuristic exact and approximate algorithms for each of these problems have been developed for different kinds of graphs: directed, undirected, labeled, etc. However, additional work is often needed to adapt such algorithms to different classes of graphs, for example to accommodate both labels and property annotations on nodes and edges. In this paper, we propose an approach based on answer set programming. We show how each of these problems can be defined for a general class of property graphs with directed edges, and labels and key-value properties annotating both nodes and edges. We evaluate this approach on a variety of synthetic and realistic graphs, demonstrating that it is feasible as a rapid prototyping approach.
Original languageEnglish
Title of host publicationPractical Aspects of Declarative Languages
Subtitle of host publication22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings
EditorsEkaterina Komendantskaya, Yanhong Annie Liu
PublisherSpringer-Verlag
Pages20-36
Number of pages22
ISBN (Electronic)978-3-030-39197-3
ISBN (Print)978-3-030-39196-6
DOIs
Publication statusPublished - 14 Jan 2020
Event22nd Symposium on Practical Aspects of Declarative Languages - New Orleans, United States
Duration: 20 Jan 202021 Jan 2020
Conference number: 22
https://popl20.sigplan.org/home/PADL-2020

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer, Cham
Volume12007
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd Symposium on Practical Aspects of Declarative Languages
Abbreviated titlePADL 2020
CountryUnited States
CityNew Orleans
Period20/01/2021/01/20
Internet address

Keywords

  • cs.LO

Fingerprint Dive into the research topics of 'Flexible graph matching and graph edit distance using answer set programming'. Together they form a unique fingerprint.

Cite this