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

Ioakeim Perros; Evangelos E. Papalexakis; Haesun Park; Richard Vuduc; Xiaowei Yan; Christopher Defilippi; Walter F. Stewart; Jimeng Sun

Source-linked AI summary

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

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

arXiv:1803.05473v1Mar 14, 2018cs.LG

TL;DR

Real-valued factorization can make integer-valued event counts difficult to interpret. SUSTain instead uses integer-constrained matrix and tensor factorizations, achieving better fit or major speedups while extracting clinically meaningful EHR phenotypes.

Problem
Real-valued factors distort integer data and make counts, relative importance, and standardized score interpretations difficult to preserve.
Method
SUSTain partitions integer-constrained factorization into efficiently solvable subproblems and provides SUSTainM and SUSTainT for matrix and tensor inputs.
Results
SUSTain shows either significantly better fit or orders-of-magnitude speedups with comparable fit, including up to 425× faster performance, across synthetic and real EHR datasets.
Takeaways & Limitations
Integer scoring yields interpretable unsupervised phenotypes for EHR data, with 87% of heart-failure phenotype candidates validated as clinically meaningful by a cardiologist.
Takeaways & Limitations
The paper targets event counts; extending the approach to other integer-valued sources such as ordinal data remains future work.

Abstract

from arXiv · show

This paper presents a new method, which we call SUSTain, that extends real-valued matrix and tensor factorizations to data where values are integers. Such data are common when the values correspond to event counts or ordinal measures. The conventional approach is to treat integer data as real, and then apply real-valued factorizations. However, doing so fails to preserve important characteristics of the original data, thereby making it hard to interpret the results. Instead, our approach extracts factor values from integer datasets as scores that are constrained to take values from a small integer set. These scores are easy to interpret: a score of zero indicates no feature contribution and higher scores indicate distinct levels of feature importance. At its core, SUSTain relies on: a) a problem partitioning into integer-constrained subproblems, so that they can be optimally solved in an efficient manner; and b) organizing the order of the subproblems' solution, to promote reuse of shared intermediate results. We propose two variants, SUSTain_M and SUSTain_T, to handle both matrix and tensor inputs, respectively. We evaluate SUSTain against several state-of-the-art baselines on both synthetic and real Electronic Health Record (EHR) datasets. Comparing to those baselines, SUSTain shows either significantly better fit or orders of magnitude speedups that achieve a comparable fit (up to 425X faster). We apply SUSTain to EHR datasets to extract patient phenotypes (i.e., clinically meaningful patient clusters). Furthermore, 87% of them were validated as clinically meaningful phenotypes related to heart failure by a cardiologist.

1 Introduction

SUSTain addresses the interpretability and scalability limits of applying real-valued factorization to integer-valued event-count and ordinal data. It provides integer-constrained matrix and tensor methods that achieve strong fit or substantial speedups, while supporting clinically meaningful EHR phenotyping.

Motivation: Real-valued factors can distort integer counts, obscure relative feature importance, and require arbitrary transformations that hinder interpretation.These limitations are especially relevant when practitioners interpret standardized integer-valued scores.
Evaluation: Up to 425× faster, SUSTainM matches the most accurate baseline’s accuracy on a large Sutter patient-by-diagnoses matrix.For R = 5, it runs in approximately 3 seconds versus approximately 22 minutes for AILS.
Phenotyping: SUSTain produces scoring-based phenotypes that medical experts can interpret, and a cardiologist judged 87% clinically meaningful and related to heart failure.The case study extracted phenotypes from EHR data for heart failure patients.
Method: SUSTain decomposes integer multi-aspect data into integer scores, preserving the original integer characteristics and providing concise, interpretable factor values.The method partitions the problem into integer-constrained subproblems solved efficiently and orders updates to reuse shared intermediate results.
Method: SUSTainM and SUSTainT support matrix and tensor inputs, respectively, and are evaluated on synthetic and real healthcare datasets.The matrix and tensor variants extend the approach across both input formats.

2 Background

The background introduces notation for projections, rank-1 factorization, Khatri-Rao products, and tensors. It also identifies MTTKRP as a bottleneck in many sparse tensor algorithms.

Notation: Euclidean projection selects the point in a set C closest to x0 under Euclidean distance.The notation is written as ΠC(x0).
Factorization: A rank-1 matrix is expressed as the outer product of two non-zero vectors, while a rank-1 d-order tensor uses d non-zero vectors.The tensor definition generalizes the matrix case across multiple modes.
Notation: The Khatri-Rao product is the column-wise matching Kronecker product of two matrices.For U and V, it forms a matrix by taking the Kronecker product of corresponding columns.
Tensor concepts: A tensor is a multidimensional array whose order counts its dimensions; fibers and slices fix all but one or two modes, respectively.Matrices are identified as second-order tensors.
Tensor computation: MTTKRP is described as the bottleneck operation in many sparse tensor algorithms.

3 The SUSTain framework

SUSTain factorizes integer-valued matrices and tensors while constraining factor entries to small integer sets. It solves alternating integer-constrained subproblems and orders updates to reuse shared intermediate results.

Framework variants: SUSTain provides SUSTainM for matrix inputs and SUSTainT for high-order tensor inputs.The tensor formulation extends the matrix method and can be viewed as a constrained CP tensor model.
Integer-constrained model: Integer-constrained factors use Zτ = {0, 1, ..., τ}, while λ values absorb scaling for each rank-1 component.The integer sets can vary across factor matrices and may also allow negative integers, although the presented formulation uses nonnegative bounded factors.
Alternating updates: SUSTain isolates each rank-1 component and solves its factor updates through integer-constrained least-squares subproblems.The derivation treats the residual associated with the k-th component as fixed, then obtains updates for λ(k) and the corresponding factor column.
Alternating updates: The Optimal Scaling Lemma reduces bounded integer updates to projection of unconstrained solutions onto the constraint set.For Cartesian-product constraints, projection is performed coordinate by coordinate.
Efficient implementation: SUSTain reuses shared intermediate results by updating λ(k) and its factor column successively within the same iteration.The update order limits additional computation to adjusting the contribution of the k-th component.
Efficient implementation: For sparse matrix input, one iteration costs 4R(nnz(X) + (M + N)R) flops.The stated complexity accounts for sparse matrix-factor products and Gram-matrix computations.
Phenotyping interpretation: In EHR phenotyping, integer patient memberships represent phenotype frequency levels, feature factors represent feature frequency levels, and λ values indicate encounter-count scaling.Higher λ(r) values are expected to describe more persistent medical conditions with more associated encounters.

4.1 Setup

The evaluation compares SUSTain and integer-factorization baselines on synthetic and healthcare datasets across accuracy–time trade-offs and scalability settings. Fit measures the proportion of input data explained by the reconstructed model.

Datasets: The study evaluates matrix and tensor methods on synthetic and real healthcare datasets.The datasets include EHR-derived matrix and tensor inputs, including diagnoses, medications, and procedures.
Baselines: Round projects nonnegative matrix or tensor factorization outputs onto Zτ after factorization.In the matrix case, the baseline uses NMF; in the tensor case, it uses nonnegative CP-ALS.
Baselines: Scale-and-round scales factor columns so their maxima reach the upper bound τ before rounding.The absorbed scaling is placed into λ, further reducing values that would otherwise be zeroed out.
Baseline limitation: The tensor AILS extension failed from out-of-memory errors when materializing the Khatri–Rao product, requiring approximately 3 Terabytes for one Sutter configuration.The reported example uses Sutter data with R = 5.
Evaluation protocol: The evaluation compares execution time and fit across target ranks R = {5, 10, 20, 40}.Fit is defined as 1 − ||X − X̂||²_F and represents the proportion of data explained by the model.
Evaluation protocol: SUSTain and AILS receive the same initialization when directly compared.For accuracy–time evaluation, each method is evaluated with several initialization schemes and the highest-fit scheme is selected.
Evaluation protocol: Scalability experiments use random-and-sampling initialization but exclude initialization time.This setting focuses the comparison on scalability behavior rather than startup cost.

4.2 Matrix case experiments

SUSTainM delivers comparable or better fit than matrix baselines while substantially reducing runtime across Sutter and CMS datasets. Its speed advantage reaches 425×, and it remains fast as patient counts grow.

Sutter PAMF dataset: 425× faster than AILS for R = 5 on Sutter while achieving the same accuracy.For R = 40, SUSTainM is at least 60× faster; for R = {10, 20}, it is 98× and 110× faster.
Sutter PAMF dataset: Up to 16% higher fit than the scale-and-round heuristic on Sutter at comparable running times.For R = 5, random initialization also produced higher fit and faster execution than scale-and-round initialization.
CMS dataset: At least an order of magnitude faster than AILS on CMS while achieving the same accuracy, reaching 38× faster for R = 20.SUSTainM also achieves up to 14% higher fit than scale-and-rounding heuristics at comparable execution time.
CMS scalability: Approximately 3 seconds per iteration on CMS with about 985 thousand patients for R = 10.The runtime measurement concerns a single iteration of the matrix method.

4.3 Tensor case experiments

SUSTainT improves fit over scale-and-round heuristics on tensor inputs and scales with increasing patient counts. The tensor extension of AILS does not scale for the evaluated datasets and target ranks.

Accuracy-time trade-off: Up to 9% and 12% higher fit than scale-and-rounding on the Sutter PAMF and CMS tensor datasets, respectively.The comparison spans target ranks R = {5, 10, 20, 40}.
Scaling: Linear scale-up with increasing patient counts for SUSTainT on CMS tensor data.The tensor evaluation fixes the target rank at R = 10 for the scaling experiment.
Heart-failure case study: ≈8.6% increase in fit over a sparsity-matched Nonnegative CP-ALS model for the heart-failure case study at R = 15.The result is reported for the HF case study.

4.4 Case study on Phenotyping HF patients

SUSTainT was applied to an incident heart-failure cohort to discover reproducible phenotypes from a patient-by-diagnosis-by-medication tensor. The selected phenotypes were sparse, fit the data accurately, and were largely judged clinically meaningful by a cardiologist.

Cohort and data selection: 3,497 × 396 × 367 tensor captured 70,531 clinical encounters and 92,662 non-zero elements from incident heart-failure cases.The tensor combined medication orders and indications with encounter diagnoses from 12 months before and after diagnosis.
Choosing the number of phenotypes: R = 15 phenotypes were selected using a stability-driven criterion over target ranks from 5 through 20.Twenty initial points were used for SUSTainT, and the highest-fit solution was chosen at the selected rank.
Phenotype discovery: The phenotype table reports feature scores as relative frequencies within each phenotype and distinguishes medication features from diagnosis features.A cardiologist validated examples corresponding to guideline-based HFrEF management and hypertensive patient groups.
Concise and accurate solutions: SUSTainT achieved an ≈8.6% fit increase over a sparsified real-valued NN CP-ALS model at the same sparsity level.Feature factors retained top-k elements per column, while patient factors retained top-k elements per row.
Phenotype discovery: 13 out of 15 phenotype candidates were annotated as clinically meaningful phenotypes related to heart failure.The annotations included phenotypes involving reduced LVEF, hypertension, atrial fibrillation, depression, diabetes, aging-related comorbidities, and prior pulmonary embolism.

5 Related Work

Related work includes discrete factorization methods based on integer least squares and ternary matrix decomposition. The paper reports that the integer matrix factorization approach is much slower than SUSTain at the same accuracy.

Discrete factorization-based approaches: Dong et al.’s Integer Matrix Factorization framework solves Integer Least Squares subproblems but is orders of magnitude slower than SUSTain at the same accuracy.The comparison concerns the experimentally evaluated matrix-factorization approach.
Discrete factorization-based approaches: Kolda and O’Leary’s Semidiscrete Matrix Decomposition uses ternary factors with values {−1, 0, 1}.The passage describes its demonstrated success for compression before discussing limitations of direct application.

6 Conclusions

The conclusion attributes SUSTain’s performance on native integer data to optimal, efficient integer-constrained subproblems and update ordering that reuses shared intermediate results. It reports better fit or major speedups at comparable fit, while identifying ordinal data as future scope.

Contributions: SUSTain partitions integer-constrained subproblems for optimal efficient solution and orders alternating updates to reuse shared intermediate results.These two design choices are presented as the sources of its accuracy and scalability on native integer data.
Future work: The paper targets event counts, while extensions to other integer-valued sources such as ordinal values remain future work.Ordinal values are identified as another real-world source of integer data.