Community Inference From Partially Observed Graph Signals: Algorithms and Analysis

This paper considers community inference methods for finding communities on a graph. We treat the setting where the edges are not fully observed. Instead, inference is based on partially observed filtered graph signals where observations from some nodes are missing. Under this setup, we treat two related tasks: $\mathsf{A}$) blind inference which recovers the inherited communities on the sub-graph; $\mathsf{B}$) semi-blind inference which recovers communities on the full graph with additional partial topology information. For task $\mathsf{A}$, we suggest a spectral method which analyzes the principal components of the data covariance matrix. We prove that it succeeds in finding the ‘true’ communities if the graph filter is low-pass and the nodes are uniformly sampled. For task $\mathsf{B}$, we propose a method using spectral interpolation with a Nyström extension. The latter approach is proven to succeed in finding the ‘true’ communities for modular graphs and low-pass graph filters. Numerical experiments on synthetic and real data corroborate our results.

I. Introduction

An Overarching goal of data science is to infer information about complex systems from data. When dealing with network data where signals are observed on nodes (cf. graph signals), the underlying system can be described by a latent graph [2] such as the social graph of individuals embedded in opinion data, or the stock market graph of businesses embedded in daily return records. Among others, a problem of practical interest is to infer or detect communities of nodes from these graphs. Communities are subsets of nodes with dense connections. Learning them provides a macroscopic representation of the graph topology [3]. The community information is useful, for example, in designing marketing strategies to maximize sales of a product in social networks [4], or to classify nodes with similar functionalities in biological networks [5].