January 01, 2018

Engineering Motif Search for Large Graphs

  • Andreas Björklund
  • Lauri J.
  • Petteri Kaski
  • Suhas Thejaswi

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^k k^2 m 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^k k^2 m 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). On a single NVIDIA Tesla P100 Accelerator (NVIDIA GP100 GPU with 3584 cores at 1189 MHz), our implementation achieves, at peak, an empirical global memory bandwidth of up to half a terabyte per second, essentially matching the peak empirical transfer bandwidth for ondevice memory. Furthermore, we obtain simultaneously an arithmetic bandwidth of over 300 billion GF(2^8)-multiplications per second. For example, with b = 8 we can find all vertices that participate in at least one match with a motif of size k = 10 on a one-million-vertex 20-regular graph (m = 10000000) in less than four seconds. With k = 20 and m = 1000000, we run in less than 25 minutes. When scaled up to a four-P100-card configuration (14336 cores), we obtain a three-tofour-fold speed-up, with up to two terabytes per second of empirical memory bandwidth and over 1.2 trillion GF(2^8)-multiplications per second when executing the sieve.

View Original Article

Recent Publications

January 01, 2019

Friendly, appealing or both? Characterising user experience in sponsored search landing pages

  • Bron M.
  • Chute M.
  • Evans H.
  • Lalmas M.
  • Redi M.
  • Silvestri F.

© 2017 International World Wide Web Conference Committee (IW3C2), published under Creative Commons CC BY 4.0 License. Many of today's websites have recognised the importance of mobile friendly pages to keep users engaged and to provide a satisfying user experience. However, next to the experience provided by the sites themselves, ...

January 01, 2019

Analyzing uber's ride-sharing economy

  • Aiello L.
  • Djuric N.
  • Grbovic M.
  • Kooti F.
  • Lerman K.
  • Radosavljevic V.

© 2017 International World Wide Web Conference Committee (IW3C2), published under Creative Commons CC BY 4.0 License. Uber is a popular ride-sharing application that matches people who need a ride (or riders) with drivers who are willing to provide it using their personal vehicles. Despite its growing popularity, there exist ...

January 01, 2019

The paradigm-shift of social spambots: Evidence, theories, and tools for the arms race

  • Cresci S.
  • Petrocchi M.
  • Pietro R.
  • Spognardi A.
  • Tesconi M.

© 2017 International World Wide Web Conference Committee (IW3C2), published under Creative Commons CC BY 4.0 License. Recent studies in social media spam and automation provide anecdotal argumentation of the rise of a new generation of spambots, so-called social spambots. Here, for the first time, we extensively study this novel ...