Making Multi-Axis Gaussian Graphical Models Scalable to Millions of Samples and Features
This work addresses the problem of analyzing large-scale datasets for researchers in fields like genomics, though it is incremental as it improves scalability while maintaining accuracy and flexibility.
The paper tackles the scalability limitations of multi-axis Gaussian graphical models, which previously had O(n^3) runtime and O(n^2) space complexity, by introducing a method with O(n^2) runtime and O(n) space complexity, enabling application to datasets with up to 1,000,000 cells.
Gaussian graphical models can be used to extract conditional dependencies between the features of the dataset. This is often done by making an independence assumption about the samples, but this assumption is rarely satisfied in reality. However, state-of-the-art approaches that avoid this assumption are not scalable, with $O(n^3)$ runtime and $O(n^2)$ space complexity. In this paper, we introduce a method that has $O(n^2)$ runtime and $O(n)$ space complexity, without assuming independence. We validate our model on both synthetic and real-world datasets, showing that our method's accuracy is comparable to that of prior work We demonstrate that our approach can be used on unprecedentedly large datasets, such as a real-world 1,000,000-cell scRNA-seq dataset; this was impossible with previous approaches. Our method maintains the flexibility of prior work, such as the ability to handle multi-modal tensor-variate datasets and the ability to work with data of arbitrary marginal distributions. An additional advantage of our method is that, unlike prior work, our hyperparameters are easily interpretable.