Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition

Abstract

We introduce a unified framework, formulated as general latent space models, to study complex higher-order network interactions among multiple entities. Our framework covers several popular models in recent network analysis literature, including mixture multi-layer latent space model and hypergraph latent space model. We formulate the relationship between the latent positions and the observed data via a generalized multilinear kernel as the link function. While our model enjoys decent generality, its maximum likelihood parameter estimation is also convenient via a generalized tensor decomposition procedure. We propose a novel algorithm using projected gradient descent on Grassmannians. We also develop original theoretical guarantees for our algorithm. First, we show its linear convergence under mild conditions. Second, we establish finite-sample statistical error rates of latent position estimation, determined by the signal strength, degrees of freedom and the smoothness of link function, for both general and specific latent space models. We demonstrate the effectiveness of our method on synthetic data. We also showcase the merit of our method on two real-world datasets that are conventionally described by different specific models in producing meaningful and interpretable parameter estimations and accurate link prediction. Supplementary materials for this article are available online.

KEYWORDS:

• Hypergraph networks
• Latent space model
• Multi-layer networks
• Network modeling
• Tensor decomposition

Supplementary Materials

Supplement to “Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition”: The material includes more simulation results, technical lemmas and detailed proofs of the theoretical results in the main article. (supp.pdf, pdf file)

Codes: The material includes the R codes and data needed to reproduce empirical results in this article. Please see README in the zip file for more information. (codes.zip, zip archive)

Disclosure Statement

The authors report there are no competing interests to declare.

Acknowledgments

The authors would like to thank the Associate Editor and reviewers for careful reading, insightful comments and constructive suggestions to help improve the quality of the article.

Notes

1 Google Scholar reports $\sim 5.8$ million results to the search query “network analysis”.

2 More specifically, the rank $\mathbf{r}$-HOSVD on a m-way tensor $\mathbf{H}$ is conducted by extracting the top-r_j left singular vectors of the matrices ${\mathcal{M}}_j(\mathbf{H})$ for $j\in [m]$, where $\mathbf{r}=(r_1,\dots ,r_m)$.

Additional information

Funding

Lyu and Xia’s research is supported in part by Hong Kong RGC Grant GRF 16303320 and GRF 16300121.