# Learning low-rank latent mesoscale structures in networks

arXiv: https://arxiv.org/abs/2102.06984 · HTML: https://mlsanity.com/paper/2102.06984/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 97 references that are in the map.
- First posted on arXiv 13 Feb 2021.

## Builds on (most cited first, 15 of 15)

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks](https://mlsanity.com/paper/1403.3795/) (2014)
- [Online matrix factorization for Markovian data and applications to Network Dictionary Learning](https://mlsanity.com/paper/1911.01931/) (2019)
- [Motifs for processes on networks](https://mlsanity.com/paper/2007.07447/) (2020)
- [Multilayer motif analysis of brain networks](https://mlsanity.com/paper/1606.09115/) (2016)
- [Sampling random graph homomorphisms and applications to network data analysis](https://mlsanity.com/paper/1910.09483/) (2019)
- [Assembling thefacebook: Using heterogeneity to understand online social network assembly](https://mlsanity.com/paper/1503.06772/) (2015)

## Built on by (most cited first, 3 of 3)

- [Renormalized Graph Representations for Node Classification](https://mlsanity.com/paper/2306.00707/) (2023)
- [A latent linear model for nonlinear coupled oscillators on graphs](https://mlsanity.com/paper/2311.14910/) (2023)
- [Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion](https://mlsanity.com/paper/2607.06546/) (2026)

## Abstract (arXiv)

It is common to use networks to encode the architecture of interactions between entities in complex systems in the physical, biological, social, and information sciences. To study the large-scale behavior of complex systems, it is useful to examine mesoscale structures in networks as building blocks that influence such behavior. We present a new approach for describing low-rank mesoscale structures in networks, and we illustrate our approach using several synthetic network models and empirical friendship, collaboration, and protein--protein interaction (PPI) networks. We find that these networks possess a relatively small number of `latent motifs' that together can successfully approximate most subgraphs of a network at a fixed mesoscale. We use an algorithm for `network dictionary learning' (NDL), which combines a network-sampling method and nonnegative matrix factorization, to learn the latent motifs of a given network. The ability to encode a network using a set of latent motifs has a wide variety of applications to network-analysis tasks, such as comparison, denoising, and edge inference. Additionally, using a new network denoising and reconstruction (NDR) algorithm, we demonstrate how to denoise a corrupted network by using only the latent motifs that one learns directly from the corrupted network.