Flexible graph matching and graph edit distance using answer set programming

Sheung Chi Chan; James Cheney

doi:10.1007/978-3-030-39197-3_2

Flexible graph matching and graph edit distance using answer set programming

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Practical Aspects of Declarative Languages
Subtitle of host publication	22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings
Editors	Ekaterina Komendantskaya, Yanhong Annie Liu
Publisher	Springer-Verlag
Pages	20-36
Number of pages	22
ISBN (Electronic)	978-3-030-39197-3
ISBN (Print)	978-3-030-39196-6
DOIs	https://doi.org/10.1007/978-3-030-39197-3_2
Publication status	Published - 14 Jan 2020
Event	22nd Symposium on Practical Aspects of Declarative Languages - New Orleans, United States Duration: 20 Jan 2020 → 21 Jan 2020 Conference number: 22 https://popl20.sigplan.org/home/PADL-2020

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Publisher	Springer, Cham
Volume	12007
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd Symposium on Practical Aspects of Declarative Languages
Abbreviated title	PADL 2020
Country/Territory	United States
City	New Orleans
Period	20/01/20 → 21/01/20
Internet address	https://popl20.sigplan.org/home/PADL-2020

Keywords

cs.LO

Access to Document

10.1007/978-3-030-39197-3_2Licence: All Rights Reserved

1911.11584v1Accepted author manuscript, 498 KB

https://link.springer.com/chapter/10.1007/978-3-030-39197-3_2Licence: All Rights Reserved

Turing Fellowship
Cheney, J.
UK-based charities
1/09/18 → 31/08/20
Project: Research
Skye-A programming language bridging theory and practice for scientific data curation
Cheney, J.
EU government bodies
1/09/16 → 31/08/22
Project: Research
A Diagnostics Approach to Persistent Threat Detection (ADAPT)
Cheney, J.
Non-EU other
26/06/15 → 30/06/19
Project: Research

Cite this

Chan, S. C., & Cheney, J. (2020). Flexible graph matching and graph edit distance using answer set programming. In E. Komendantskaya, & Y. A. Liu (Eds.), Practical Aspects of Declarative Languages : 22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings (pp. 20-36). (Lecture Notes in Computer Science (LNCS); Vol. 12007). Springer-Verlag. https://doi.org/10.1007/978-3-030-39197-3_2

Chan, Sheung Chi ; Cheney, James. / Flexible graph matching and graph edit distance using answer set programming. Practical Aspects of Declarative Languages : 22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings. editor / Ekaterina Komendantskaya ; Yanhong Annie Liu. Springer-Verlag, 2020. pp. 20-36 (Lecture Notes in Computer Science (LNCS)).

@inproceedings{49fc7651e406480a97e210149520dd58,

title = "Flexible graph matching and graph edit distance using answer set programming",

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. ",

keywords = "cs.LO",

author = "Chan, {Sheung Chi} and James Cheney",

note = "To appear, PADL 2020; 22nd Symposium on Practical Aspects of Declarative Languages, PADL 2020 ; Conference date: 20-01-2020 Through 21-01-2020",

year = "2020",

month = jan,

day = "14",

doi = "10.1007/978-3-030-39197-3_2",

language = "English",

isbn = "978-3-030-39196-6",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer-Verlag",

pages = "20--36",

editor = "Ekaterina Komendantskaya and Liu, {Yanhong Annie }",

booktitle = "Practical Aspects of Declarative Languages",

url = "https://popl20.sigplan.org/home/PADL-2020",

}

Chan, SC & Cheney, J 2020, Flexible graph matching and graph edit distance using answer set programming. in E Komendantskaya & YA Liu (eds), Practical Aspects of Declarative Languages : 22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 12007, Springer-Verlag, pp. 20-36, 22nd Symposium on Practical Aspects of Declarative Languages, New Orleans, Louisiana, United States, 20/01/20. https://doi.org/10.1007/978-3-030-39197-3_2

Flexible graph matching and graph edit distance using answer set programming. / Chan, Sheung Chi; Cheney, James.

Practical Aspects of Declarative Languages : 22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings. ed. / Ekaterina Komendantskaya; Yanhong Annie Liu. Springer-Verlag, 2020. p. 20-36 (Lecture Notes in Computer Science (LNCS); Vol. 12007).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Flexible graph matching and graph edit distance using answer set programming

AU - Chan, Sheung Chi

AU - Cheney, James

N1 - Conference code: 22

PY - 2020/1/14

Y1 - 2020/1/14

N2 - 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.

AB - 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.

KW - cs.LO

U2 - 10.1007/978-3-030-39197-3_2

DO - 10.1007/978-3-030-39197-3_2

M3 - Conference contribution

SN - 978-3-030-39196-6

T3 - Lecture Notes in Computer Science (LNCS)

SP - 20

EP - 36

BT - Practical Aspects of Declarative Languages

A2 - Komendantskaya, Ekaterina

A2 - Liu, Yanhong Annie

PB - Springer-Verlag

T2 - 22nd Symposium on Practical Aspects of Declarative Languages

Y2 - 20 January 2020 through 21 January 2020

ER -

Chan SC, Cheney J. Flexible graph matching and graph edit distance using answer set programming. In Komendantskaya E, Liu YA, editors, Practical Aspects of Declarative Languages : 22nd International Symposium, PADL 2020, New Orleans, LA, USA, January 20–21, 2020, Proceedings. Springer-Verlag. 2020. p. 20-36. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-030-39197-3_2

Flexible graph matching and graph edit distance using answer set programming

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Projects

Turing Fellowship

Skye-A programming language bridging theory and practice for scientific data curation

A Diagnostics Approach to Persistent Threat Detection (ADAPT)

Cite this