# Clustering multilayer graphs with missing nodes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 4 Mar 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [Spectral and matrix factorization methods for consistent community detection in multi-layer networks](https://mlsanity.com/paper/1704.07353/) (2017)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [One-Pass Incomplete Multi-view Clustering](https://mlsanity.com/paper/1903.00637/) (2019)
- [High-dimensional principal component analysis with heterogeneous missingness](https://mlsanity.com/paper/1906.12125/) (2019)
- [k-POD: A Method for k-Means Clustering of Missing Data](https://mlsanity.com/paper/1411.7013/) (2014)
- [Spectral clustering in the dynamic stochastic block model](https://mlsanity.com/paper/1705.01204/) (2017)
- [Spectral Clustering for Multiple Sparse Networks: I](https://mlsanity.com/paper/1805.10594/) (2018)
- [General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers](https://mlsanity.com/paper/2004.03480/) (2020)
- [Four lectures on probabilistic methods for data science](https://mlsanity.com/paper/1612.06661/) (2016)

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

- [Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization](https://mlsanity.com/paper/2205.00626/) (2022)
- [Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection](https://mlsanity.com/paper/2610.01361/) (2026)

## Abstract (arXiv)

Relationship between agents can be conveniently represented by graphs. When these relationships have different modalities, they are better modelled by multilayer graphs where each layer is associated with one modality. Such graphs arise naturally in many contexts including biological and social networks. Clustering is a fundamental problem in network analysis where the goal is to regroup nodes with similar connectivity profiles. In the past decade, various clustering methods have been extended from the unilayer setting to multilayer graphs in order to incorporate the information provided by each layer. While most existing works assume - rather restrictively - that all layers share the same set of nodes, we propose a new framework that allows for layers to be defined on different sets of nodes. In particular, the nodes not recorded in a layer are treated as missing. Within this paradigm, we investigate several generalizations of well-known clustering methods in the complete setting to the incomplete one and prove some consistency results under the Multi-Layer Stochastic Block Model assumption. Our theoretical results are complemented by thorough numerical comparisons between our proposed algorithms on synthetic data, and also on real datasets, thus highlighting the promising behaviour of our methods in various settings.