SUSTain: Scalable Unsupervised Scoring for Tensors and its Application to Phenotyping

Ioakeim Perros, Evangelos E. Papalexakis, Haesun Park, Richard W. Vuduc, Xiaowei Yan, Christopher deFilippi, Walter F. Stewart, Jimeng Sun

Introduction

In healthcare, data is inherently discrete. Electronic Health Records (EHRs) typically consist of integer counts, such as the number of times a patient received a specific diagnosis code or medication. Traditional analysis tools like Non-negative Matrix Factorization (NMF) treat these counts as continuous real numbers, leading to two primary issues: poor interpretability for clinicians (e.g., a "0.45 importance score") and information loss when results are post-hoc rounded to integers. While integer-only algorithms exist, they often fail to scale to the millions of records found in modern medical datasets.

SUSTain (Scalable Unsupervised Scoring for Tensors) addresses these challenges by factorizing large-scale integer data into easy-to-read integer scores. It provides a massive performance leap—up to 425x faster than existing integer-based methods—while producing "phenotypes" (patient clusters) that are highly clinically relevant.

Methods

SUSTain is designed for both matrices ($SUSTain_M$) and multi-dimensional tensors ($SUSTain_T$). The framework employs several key innovations:

  • Problem Partitioning: The complex integer optimization problem is decomposed into smaller, efficiently solvable sub-problems.
  • Hierarchical Updates: Utilizing an alternating update scheme inspired by Hierarchical Alternating Least Squares, SUSTain reuses intermediate calculations. This significantly reduces the computational burden of the Matricized Tensor Times Khatri-Rao Product (MTTKRP), the primary bottleneck in tensor factorization.
  • Scaling via $\Lambda$ Matrix: A diagonal matrix $\Lambda$ absorbs data scaling, allowing the feature matrices to remain constrained within a user-defined integer range (e.g., 0 to 5).

Experimental Evaluation

The researchers evaluated SUSTain using synthetic benchmarks and two massive real-world healthcare datasets:

  • Sutter Health (PAMF): EHR data for patients aged 50–80 focused on heart failure, including a 260k-patient matrix and a 3D tensor for medications.
  • CMS (Medicare): A synthetic dataset from the Centers for Medicare & Medicaid Services containing three years of claims to test scalability.

Key Results and Insights

SUSTain demonstrates that discrete constraints can be a computational advantage rather than a hindrance. By optimizing for integers from the start, SUSTain achieves up to 16% better fit than "Scale-and-Round" heuristics, which often destroy model accuracy.

SUSTain achieves up to 425x speedup over existing integer-based methods like AILS while maintaining high fit.

Performance and Scalability

Compared to AILS, the previous state-of-the-art for integer factorization, SUSTain is up to 425x faster. The algorithm exhibits linear scalability with respect to the number of patients, processing nearly a million records in seconds per iteration.

Clinical Relevance

In a heart failure case study, a cardiologist validated 87% of the phenotypes discovered by SUSTain as clinically meaningful. The integer-constrained output (e.g., scores from 0-5) mimics the risk scores used in daily medical practice, making the results immediately interpretable.

An example of a clinician-friendly phenotype (Hyperlipidemia) generated by SUSTain, using simple integer scores.

Conclusion

SUSTain provides a scalable and interpretable solution for analyzing discrete medical data. While currently optimized for non-negative counts, future work may extend the framework to ordinal data or incorporate explicit sparsity constraints. By bridging the gap between integer accuracy and computational efficiency, SUSTain offers a powerful tool for automated clinical phenotyping.

Summary updated

BibTeX
@inproceedings{perros2018sustain,
  author = {Ioakeim Perros and Evangelos E. Papalexakis and Haesun Park and Richard W. Vuduc and Xiaowei Yan and Christopher deFilippi and Walter F. Stewart and Jimeng Sun},
  title = {{SUSTain: Scalable Unsupervised Scoring for Tensors and its Application to Phenotyping}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2018},
  doi = {10.1145/3219819.3219999},
}
Figure