Kaski, Petteri ;
Lauri, Juho ;
Thejaswi, Suhas
Engineering Motif Search for Large Motifs
Abstract
Given a vertexcolored 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 NPcomplete 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 falsenegative probability of at most k/2^{b1} for a connected medge input and a motif of size k. On modern CPU microarchitectures such algorithms have practical edgelinear 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 vertexlocalized 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 pervertex probability of at most k/2^{b1} for a false negative. Furthermore, the algorithm is easily vectorparallelizable 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 opensource implementation that our variant of constrained multilinear sieving can be engineered for vectorparallel 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 memoryandarithmetic coalescent parallel workloads on multiple GPUs, and (b) a bitsliced lowlevel 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:128:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770705},
ISSN = {18688969},
year = {2018},
volume = {103},
editor = {Gianlorenzo D'Angelo},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8963},
URN = {urn:nbn:de:0030drops89631},
doi = {10.4230/LIPIcs.SEA.2018.28},
annote = {Keywords: algorithm engineering, constrained multilinear sieving, graph motif problem, multiGPU, vectorparallel, vertexlocalization}
}
19.06.2018
Keywords: 

algorithm engineering, constrained multilinear sieving, graph motif problem, multiGPU, vectorparallel, vertexlocalization 
Seminar: 

17th International Symposium on Experimental Algorithms (SEA 2018)

Issue date: 

2018 
Date of publication: 

19.06.2018 