License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.28
URN: urn:nbn:de:0030-drops-89631
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8963/
Kaski, Petteri ;
Lauri, Juho ;
Thejaswi, Suhas
Engineering Motif Search for Large Motifs
Abstract
Given a vertex-colored graph H and a multiset M of colors as input, the graph motif problem asks us to decide whether H has a connected induced subgraph whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit randomized algorithms based on constrained multilinear sieving over GF(2^b) that run in time O(2^kk^2m {M({2^b})}) and with a false-negative probability of at most k/2^{b-1} for a connected m-edge input and a motif of size k. On modern CPU microarchitectures such algorithms have practical edge-linear scalability to inputs with billions of edges for small motif sizes, as demonstrated by Björklund, Kaski, Kowalik, and Lauri [ALENEX'15]. This scalability to large graphs prompts the dual question whether it is possible to scale to large motif sizes.
We present a vertex-localized variant of the constrained multilinear sieve that enables us to obtain, in time O(2^kk^2m{M({2^b})}) and for every vertex simultaneously, whether the vertex participates in at least one match with the motif, with a per-vertex probability of at most k/2^{b-1} for a false negative. Furthermore, the algorithm is easily vector-parallelizable for up to 2^k threads, and parallelizable for up to 2^kn threads, where n is the number of vertices in H. Here {M({2^b})} is the time complexity to multiply in GF(2^b).
We demonstrate with an open-source implementation that our variant of constrained multilinear sieving can be engineered for vector-parallel microarchitectures to yield hardware utilization that is bound by the available memory bandwidth.
Our main engineering contributions are (a) a version of the recurrence for tightly labeled arborescences that can be executed as a sequence of memory-and-arithmetic coalescent parallel workloads on multiple GPUs, and (b) a bit-sliced low-level implementation for arithmetic in characteristic 2 to support (a).
BibTeX - Entry
@InProceedings{kaski_et_al:LIPIcs:2018:8963,
author = {Petteri Kaski and Juho Lauri and Suhas Thejaswi},
title = {{Engineering Motif Search for Large Motifs}},
booktitle = {17th International Symposium on Experimental Algorithms (SEA 2018)},
pages = {28:1--28:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-070-5},
ISSN = {1868-8969},
year = {2018},
volume = {103},
editor = {Gianlorenzo D'Angelo},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8963},
URN = {urn:nbn:de:0030-drops-89631},
doi = {10.4230/LIPIcs.SEA.2018.28},
annote = {Keywords: algorithm engineering, constrained multilinear sieving, graph motif problem, multi-GPU, vector-parallel, vertex-localization}
}
|
Keywords: |
|
algorithm engineering, constrained multilinear sieving, graph motif problem, multi-GPU, vector-parallel, vertex-localization |
|
Collection: |
|
17th International Symposium on Experimental Algorithms (SEA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
19.06.2018 |
