Title: Blind Community Detection from Low-rank Excitations of a Graph Filter,
Abstract: This paper considers a novel framework to detect communities in a graph from
the observation of signals at its nodes. We model the observed signals as noisy
outputs of an unknown network process -- represented as a graph filter -- that
is excited by a set of low-rank inputs. Rather than learning the precise
parameters of the graph itself, the proposed method retrieves the community
structure directly; Furthermore, as in blind system identification methods, it
does not require knowledge of the system excitation. The paper shows that
communities can be detected by applying spectral clustering to the low-rank
output covariance matrix obtained from the graph signals. The performance
analysis indicates that the community detection accuracy depends on the
spectral properties of the graph filter considered. Furthermore, we show that
the accuracy can be improved via a low-rank matrix decomposition method when
the excitation signals are known. Numerical experiments demonstrate that our
approach is effective for analyzing network data from diffusion, consumers, and
social dynamics.