MIDAS: Multilinear Detection at Scale

EasyChair Preprint 237

Abstract

We focus on two classes of problems in graph mininghere: (1) finding trees and (2) anomaly detection using networkscan statistics in complex networks. These are fundamentalproblems in a broad class of applications. Most of the parallelalgorithms for such problems are either based on heuristics,which do not scale very well, or use techniques like colorcoding, which have a high memory overhead. In this paper, wedevelop a novel approach for parallelizing both these classesof problems, using an algebraic representation of subgraphsas monomials—this methodology involves detecting multilinearterms in multivariate polynomials. Our algorithms show goodscaling over a large regime, and they run on networks with closeto half a billion edges. The resulting parallel algorithm for treesis able to scale to subgraphs of size18, which has not beenshown before, and it significantly outperforms the best priorcolor coding based method (FASCIA) by more than two ordersof magnitude. Our algorithm for network scan statistics is thefirst such parallelization, and it is able to handle a broad class ofscan statistics functions (both parametric and non-parametric),with the same approach.

Keyphrases: distributed algorithms, graph algorithms, multilinear detection, parameterized complexity, subgraph detection

@booklet{EasyChair:237,
  author    = {Saliya Ekanayake and Jose Cadena and Udayanga Wickramasinghe and Anil Kumar Vullikanti},
  title     = {MIDAS: Multilinear Detection at Scale},
  doi       = {10.29007/6xgg},
  howpublished = {EasyChair Preprint 237},
  year      = {EasyChair, 2018}}