Memory-efficient query-driven community detection with application to complex disease associations

Steve Harenberg, Ramona G. Seay, Stephen Ranshous, Kanchana Padmanabhan, Jitendra K. Harlalka, Eric R. Schendel, Michael P. O'Brien, Rada Y. Chirkova, William Hendrix, Alok N. Choudhary, Vipin Kumar, Murali Doraiswamy, Nagiza F. Samatova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Community detection in real-world graphs presents a number of challenges. First, even if the number of detected communities grows linearly with the graph size, it becomes impossible to manually inspect each community for value added to the application knowledge base. Mining for communities with query nodes as knowledge priors could allow for filtering out irrelevant information and for enriching end-users knowledge associated with the problem of interest, such as discovery of genes functionally associated with the Alzheimer's (AD) biomarker genes. Second, the data-intensive nature of community enumeration challenges current approaches that often assume that the input graph and the detected communities fit in memory. As computer systems scale, DRAM memory sizes are not expected to increase linearly, while technologies such as SSD memories have the potential to provide much higher capacities at a lower power-cost point, and have a much lower latency than disks. Out-of-core algorithms and/or databaseinspired indexing could provide an opportunity for different design optimizations for query-driven community detection algorithms tuned for emerging architectures. Therefore, this work addresses the need for query-driven and memory-efficient community detection. Using maximal cliques as the community definition, due to their high signalto-noise ratio, we propose and systematically compare two contrasting methods: indexed-based and out-of-core. Both methods improve peak memory efficiency as much as 1000X compared to the state-of-the-art. However, the index-based method, which also has a 10-to-100-fold run time reduction, outperforms the out-of-core algorithm in most cases. The achieved scalability enables the discovery of diseases that are known to be or likely associated with Alzheimer's when the genome-scale network is mined with AD biomarker genes as knowledge priors.

Original languageEnglish (US)
Title of host publicationSIAM International Conference on Data Mining 2014, SDM 2014
EditorsPang Ning-Tan, Arindam Banerjee, Srinivasan Parthasarathy, Zoran Obradovic, Chandrika Kamath, Mohammed Zaki
PublisherSociety for Industrial and Applied Mathematics Publications
Pages1010-1018
Number of pages9
ISBN (Electronic)9781510811515
DOIs
StatePublished - 2014
Event14th SIAM International Conference on Data Mining, SDM 2014 - Philadelphia, United States
Duration: Apr 24 2014Apr 26 2014

Publication series

NameSIAM International Conference on Data Mining 2014, SDM 2014
Volume2

Other

Other14th SIAM International Conference on Data Mining, SDM 2014
CountryUnited States
CityPhiladelphia
Period4/24/144/26/14

Bibliographical note

Funding Information:
This work was supported in part by the DOE SDAVI Institute and the U.S. National Science Foundation (Expeditions in Computing and EAGER programs).

Fingerprint Dive into the research topics of 'Memory-efficient query-driven community detection with application to complex disease associations'. Together they form a unique fingerprint.

Cite this