Online tensor methods for learning latent variable models

Furong Huang, U. N. Niranjan, Mohammad Umar Hakeem, Animashree AnandkumarJMLR 2015 · OpenReview

TL;DR

This paper introduces a novel online tensor decomposition method for learning latent variable models, specifically for community detection in social networks and topic modeling in text. By leveraging stochastic gradient descent and avoiding explicit tensor formation, their approach achieves significant speedups (orders of magnitude) and competitive accuracy compared to existing methods, making it highly scalable for large datasets.

What Problem Does This Paper Address?

Traditional methods for learning latent variable models, like Expectation-Maximization (EM) and Variational Bayes, often lack theoretical guarantees and can be computationally expensive. Tensor-based methods offer a more principled approach, but batch implementations can be slow. The authors address the challenge of efficiently implementing these powerful tensor-based methods for large-scale, real-world problems like identifying communities in massive social networks or discovering hidden topics in vast document collections. They aim to bridge the gap between theoretical tensor methods and practical, scalable applications.

Methods

The core of this work is an online tensor decomposition approach using stochastic gradient descent (SGD). Instead of forming large, explicit tensors (which is computationally prohibitive for big data), they cleverly optimize multilinear operations within the SGD framework. This allows them to work with implicit tensor representations.

Key methodological contributions include:

  • Stochastic Gradient Descent for Tensor Decomposition: This is a departure from previous batch-based tensor methods, enabling online updates and better scalability.
  • Implicit Tensor Operations: They avoid forming the full tensor, instead manipulating neighborhood vectors and using efficient matrix/vector operations.
  • GPU and CPU Implementations: They provide optimized implementations for both platforms. The GPU version leverages SIMD parallelism for speed, while the CPU version uses sparse matrix computations for large, sparse datasets.
  • Dimensionality Reduction and Whitening: A crucial preprocessing step involves whitening the data using second-order moments to reduce dimensionality from O(n³) to O(k³), where k is the number of latent variables (communities/topics), significantly improving computational efficiency.
  • Randomized SVD and QR: For efficient whitening, they employ randomized low-rank approximation techniques like tall-thin SVD and QR factorizations, particularly useful for large matrices.

Datasets

The authors evaluate their method on several real-world datasets:

  • Community Detection:
    • Facebook
    • Yelp
    • DBLP
  • Topic Modeling:
    • New York Times corpus (from UCI bag-of-words dataset)

The paper does not introduce new benchmark datasets but rather applies their method to existing, well-known datasets to demonstrate its effectiveness.

Key Insights and Ideas

  • Online Tensor Methods are Scalable: The most significant insight is that tensor decomposition, often perceived as computationally intensive, can be made highly scalable and efficient through online (stochastic) methods and clever implicit operations.
  • Avoiding Explicit Tensor Formation is Key: The ability to perform tensor operations without explicitly constructing the tensor is a critical enabler for handling large datasets.
  • GPU Parallelism for Speed: For dense or moderately sized problems, GPU implementations offer substantial speedups due to their inherent parallelism.
  • Sparse CPU for Massive Networks: For extremely large and sparse networks, a well-optimized CPU implementation using sparse matrix techniques remains highly competitive and memory-efficient.
  • Unified Framework: The tensor formulation naturally handles both community detection and topic modeling, highlighting the generality of the approach.
  • P-value Testing for Validation: The introduction of a p-value based error score provides a more robust way to validate community detection results, especially when ground truth is available, and is less prone to underestimating errors compared to traditional metrics like NMI.

Key Results

  • Speedup: The proposed method achieves several orders of magnitude speedup in execution time compared to state-of-the-art variational methods for community detection. For example, on the DBLP dataset, their method runs in about two minutes, whereas a variational method might take much longer.
  • Accuracy: The method demonstrates good accuracy on various datasets for both community detection and topic modeling, often matching or exceeding state-of-the-art results. For instance, on synthetic datasets, errors are around 8%-14%.
  • Scalability: The GPU implementation is shown to scale well with the number of communities (k), and the CPU implementation handles large sparse graphs efficiently. The method is demonstrated to be scalable to datasets with millions of nodes.
  • Facebook Dataset: For a concentration parameter $\alpha_0=100$, the recovery ratio improves with larger $\alpha_0$, while the error score remains relatively stable.
  • Yelp Dataset: The method successfully recovers business categories and attributes, even in a bipartite graph setting where other methods might fail.

Limitations and Future Work

  • Parameter Tuning: While the p-value testing helps in avoiding explicit tuning of the number of communities, other parameters (like the regularization parameter $\theta$ in the loss function) might still require some tuning.
  • Homophily Assumption: The synthetic experiments assume a diagonal-dominated community connectivity matrix (homophily), though the method is noted to be flexible for general directed social ties.
  • Future Work: The authors suggest extending the framework to multi-graphs and hypergraphs, exploring cloud-based systems for even larger datasets, and investigating efficient partitioning and communication strategies for distributed systems. Combining their approach with other community detection methods for further speedup is also mentioned.

Summary updated

Abstract

We introduce an online tensor decomposition based approach for two latent variable modeling problems namely, (1) community detection, in which we learn the latent communities that the social actors in social networks belong to, and (2) topic modeling, in which we infer hidden topics of text articles. We consider decomposition of moment tensors using stochastic gradient descent. We conduct optimization of multilinear operations in SGD and avoid directly forming the tensors, to save computational and storage costs. We present optimized algorithm in two platforms. Our GPU-based implementation exploits the parallelism of SIMD architectures to allow for maximum speed-up by a careful optimization of storage and data transfer, whereas our CPU-based implementation uses efficient sparse matrix computations and is suitable for large sparse data sets. For the community detection problem, we demonstrate accuracy and computational efficiency on Facebook, Yelp and DBLP data sets, and for the topic modeling problem, we also demonstrate good performance on the New York Times data set. We compare our results to the state-of-the-art algorithms such as the variational method, and report a gain of accuracy and a gain of several orders of magnitude in the execution time.
BibTeX
@article{huang2015online,
  author = {Furong Huang and U. N. Niranjan and Mohammad Umar Hakeem and Animashree Anandkumar},
  title = {{Online tensor methods for learning latent variable models}},
  journal = {J. Mach. Learn. Res.},
  year = {2015},
  url = {https://openreview.net/forum?id=BPCMvaka9ZL},
}
Figure