A generic framework for engineering graph canonization algorithms

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

140 Downloads (Pure)

Abstract

The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement paradigm, and their di erence is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas a ect the performance on di erent graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of di erent algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of di erent graph classes we investigate the e ect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of di cult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.

Original languageEnglish
Title of host publication2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
EditorsSuresh Venkatasubramanian, Rasmus Pagh
PublisherSociety for Industrial and Applied Mathematics Publications
Publication dateJan 2018
Pages139-153
ISBN (Electronic)978-1-61197-505-5
DOIs
Publication statusPublished - Jan 2018
Event20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 - New Orleans, United States
Duration: 7. Jan 20188. Jan 2018

Conference

Conference20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
CountryUnited States
CityNew Orleans
Period07/01/201808/01/2018

Fingerprint

Visualization

Cite this

Andersen, J. L., & Merkle, D. (2018). A generic framework for engineering graph canonization algorithms. In S. Venkatasubramanian, & R. Pagh (Eds.), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 (pp. 139-153). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611975055.13
Andersen, Jakob L. ; Merkle, Daniel. / A generic framework for engineering graph canonization algorithms. 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. editor / Suresh Venkatasubramanian ; Rasmus Pagh. Society for Industrial and Applied Mathematics Publications, 2018. pp. 139-153
@inproceedings{d90c037eab0e47febc67da995e3331a8,
title = "A generic framework for engineering graph canonization algorithms",
abstract = "The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement paradigm, and their di erence is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas a ect the performance on di erent graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of di erent algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of di erent graph classes we investigate the e ect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of di cult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.",
author = "Andersen, {Jakob L.} and Daniel Merkle",
year = "2018",
month = "1",
doi = "10.1137/1.9781611975055.13",
language = "English",
pages = "139--153",
editor = "Suresh Venkatasubramanian and Rasmus Pagh",
booktitle = "2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018",
publisher = "Society for Industrial and Applied Mathematics Publications",
address = "United States",

}

Andersen, JL & Merkle, D 2018, A generic framework for engineering graph canonization algorithms. in S Venkatasubramanian & R Pagh (eds), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. Society for Industrial and Applied Mathematics Publications, pp. 139-153, 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, United States, 07/01/2018. https://doi.org/10.1137/1.9781611975055.13

A generic framework for engineering graph canonization algorithms. / Andersen, Jakob L.; Merkle, Daniel.

2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. ed. / Suresh Venkatasubramanian; Rasmus Pagh. Society for Industrial and Applied Mathematics Publications, 2018. p. 139-153.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - A generic framework for engineering graph canonization algorithms

AU - Andersen, Jakob L.

AU - Merkle, Daniel

PY - 2018/1

Y1 - 2018/1

N2 - The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement paradigm, and their di erence is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas a ect the performance on di erent graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of di erent algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of di erent graph classes we investigate the e ect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of di cult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.

AB - The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement paradigm, and their di erence is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas a ect the performance on di erent graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of di erent algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of di erent graph classes we investigate the e ect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of di cult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.

U2 - 10.1137/1.9781611975055.13

DO - 10.1137/1.9781611975055.13

M3 - Article in proceedings

AN - SCOPUS:85041377067

SP - 139

EP - 153

BT - 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018

A2 - Venkatasubramanian, Suresh

A2 - Pagh, Rasmus

PB - Society for Industrial and Applied Mathematics Publications

ER -

Andersen JL, Merkle D. A generic framework for engineering graph canonization algorithms. In Venkatasubramanian S, Pagh R, editors, 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. Society for Industrial and Applied Mathematics Publications. 2018. p. 139-153 https://doi.org/10.1137/1.9781611975055.13