SPARTan: Scalable PARAFAC2 for Large & Sparse Data

Ioakeim Perros, Evangelos E. Papalexakis, Fei Wang, Richard Vuduc, Elizabeth Searles, Michael Thompson, Jimeng Sun

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

Abstract

In exploratory tensor mining, a common problem is how to analyze a set of variables across a set of subjects whose observations do not align naturally. For example, when modeling medical features across a set of patients, the number and duration of treatments may vary widely in time, meaning there is no meaningful way to align their clinical records across time points for analysis purposes. To handle such data, the state-of-the-art tensor model is the so-called PARAFAC2, which yields interpretable and robust output and can naturally handle sparse data. However, its main limitation up to now has been the lack of eficient algorithms that can handle large-scale datasets. In this work, we fill this gap by developing a scalable method to compute the PARAFAC2 decomposition of large and sparse datasets, called SPARTan. Our method exploits special structure within PARAFAC2, leading to a novel algorithmic reformulation that is both faster (in absolute time) and more memory-eficient than prior work. We evaluate SPARTan on both synthetic and real datasets, showing 22 × performance gains over the best previous implementation and also handling larger problem instances for which the baseline fails. Furthermore, we are able to apply SPARTan to the mining of temporally-evolving phenotypes on data taken from real and medically complex pediatric patients. The clinical meaningfulness of the phenotypes identifed in this process, as well as their temporal evolution over time for several patients, have been endorsed by clinical experts.

Original languageEnglish (US)
Title of host publicationKDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery
Pages376-384
Number of pages9
ISBN (Electronic)9781450348874
DOIs
StatePublished - Aug 13 2017
Externally publishedYes
Event23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017 - Halifax, Canada
Duration: Aug 13 2017Aug 17 2017

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
VolumePart F129685

Other

Other23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2017
CountryCanada
CityHalifax
Period8/13/178/17/17

Keywords

  • PARAFAC2
  • Phenotyping
  • Sparse tensor factorization
  • Unsuper-vised learning

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'SPARTan: Scalable PARAFAC2 for Large & Sparse Data'. Together they form a unique fingerprint.

Cite this