Clustering multilayer graphs with missing nodes

Guillaume Braun, Hemant Tyagi, Christophe Biernacki
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2260-2268, 2021.

Abstract

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 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 several real datasets, thus highlighting the promising behaviour of our methods in various realistic settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-braun21a, title = { Clustering multilayer graphs with missing nodes }, author = {Braun, Guillaume and Tyagi, Hemant and Biernacki, Christophe}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2260--2268}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/braun21a/braun21a.pdf}, url = {https://proceedings.mlr.press/v130/braun21a.html}, abstract = { 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 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 several real datasets, thus highlighting the promising behaviour of our methods in various realistic settings. } }
Endnote
%0 Conference Paper %T Clustering multilayer graphs with missing nodes %A Guillaume Braun %A Hemant Tyagi %A Christophe Biernacki %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-braun21a %I PMLR %P 2260--2268 %U https://proceedings.mlr.press/v130/braun21a.html %V 130 %X 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 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 several real datasets, thus highlighting the promising behaviour of our methods in various realistic settings.
APA
Braun, G., Tyagi, H. & Biernacki, C.. (2021). Clustering multilayer graphs with missing nodes . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2260-2268 Available from https://proceedings.mlr.press/v130/braun21a.html.

Related Material