Community Detection from Low-Rank Excitations of a Graph Filter

Hoi-To Wai, Santiago Segarra, Asuman E. Ozdaglar, Anna Scaglione, Ali JadbabaieICASSP 2018 · OpenReview

Abstract

Traditional community detection methods rely on explicit knowledge of a network's topology, typically represented by an adjacency matrix. However, in many real-world scenarios, the underlying graph structure is latent, and only signals observed at the nodes are available. This paper presents a framework for "blind" community detection, demonstrating that community structures can be recovered directly from the covariance of observed signals, even when those signals are driven by low-rank excitations. By leveraging Graph Signal Processing (GSP) principles, the proposed methods bypass the computationally intensive step of full graph reconstruction, offering a robust solution for data-scarce environments.

Introduction

In network science, identifying communities—clusters of nodes with dense internal connections—is a fundamental task. Standard approaches assume the graph's edges are known. When the graph is hidden, researchers typically employ a two-step pipeline: first, inferring the graph structure from nodal observations (graph learning), and second, applying community detection algorithms to the inferred graph.

This two-step process often falters when data is "low-rank." For instance, if a signal (such as an opinion or a virus) originates from only a few sources, the resulting observations do not provide enough information to reconstruct every individual edge of the network. This paper addresses this gap by proposing a direct approach that identifies communities without ever explicitly reconstructing the network's adjacency matrix.

Methodology

Graph Signal Processing Framework

The authors model observed signals as the output of an unknown "graph filter." In this model, an input excitation (the source of the signal) is smoothed by a filter that depends on the underlying graph's Laplacian or adjacency matrix. The resulting observed signals reflect the connectivity of the graph, particularly its community structure, if the filter exhibits "low-pass" characteristics.

Proposed Algorithms

The paper introduces two primary algorithms for blind detection:

  1. BlindCD (Blind Community Detection): This algorithm operates by calculating the sample covariance matrix of the observed signals. It then performs spectral clustering—specifically K-means on the top eigenvectors of the covariance matrix. The theoretical justification is that the covariance matrix serves as a "sketch" of the graph's spectral properties, preserving the subspace associated with the community structure.
  2. Boosted BlindCD: This variant is applicable when the latent excitations (the source inputs) are known or can be estimated. It utilizes a low-rank plus sparse matrix decomposition to refine the signal. By removing constant-level frequency responses, it effectively "sharpens" the low-pass filter, making the boundaries between communities more distinct and improving clustering accuracy.

Experimental Evaluation

Synthetic Benchmarks

The methods were tested using the Stochastic Block Model (SBM), a standard generative model for graphs with community structures. The results indicated that while traditional two-step methods require "full-rank" excitations to succeed, BlindCD remains effective even with very few observations. Interestingly, while the accuracy of graph reconstruction improves with higher rank, the ability to detect communities reaches a plateau much earlier, suggesting that community detection is a fundamentally easier task than full graph recovery.

Real-World Applications

  • US Senate Rollcall Records: The researchers analyzed voting patterns from the 110th Congress. By treating states as nodes and votes as signals, the algorithm successfully grouped states into politically coherent clusters. Notably, it correctly identified the political alignment of states like Maine (which had two Republican senators at the time) with other conservative-leaning states based purely on signal covariance.
  • Social Networks: The algorithms were validated on Zachary’s Karate Club and the Facebook (ReedCollege) dataset. In both cases, the blind approach recovered the known community structures with high fidelity, comparable to methods that have full access to the network edges.

Key Insights

Covariance as a Topological Sketch

A central finding of this research is that the covariance of signals observed over a graph contains a compressed version of the graph’s topology. This "sketch" is sufficient for identifying macro-scale features like communities, even if it is insufficient for micro-scale features like individual edge weights.

The Role of Low-Pass Filtering

The success of blind detection is contingent on the network process being "low-pass." This means the process must promote similarity between neighbors (e.g., consensus building, heat diffusion, or social influence). In such processes, the signal's energy is concentrated in the lower end of the graph spectrum, which aligns with the eigenvectors that define community membership.

Conclusion and Future Work

This work demonstrates that community detection is possible even when the underlying network is entirely unknown and the available data is limited. By shifting the focus from graph reconstruction to direct subspace estimation, the authors provide a more efficient path for analyzing networked data.

Future research directions include extending the framework to directed graphs and developing automated methods to estimate the number of communities ($K$) without prior knowledge. Additionally, investigating the performance of these methods under "high-pass" signal regimes—where neighbors are encouraged to be dissimilar—remains an open challenge.

Summary updated

Abstract

This paper considers the problem of inferring the topology of a graph from noisy outputs of an unknown graph filter excited by low-rank signals. Limited by this low-rank structure, we focus on solving the community detection problem, whose aim is to partition the node set of the unknown graph into subsets with high edge densities. We propose to detect the communities by applying spectral clustering on the low-rank output covariance matrix. To analyze the performance, we show that the low-rank covariance yields a sketch of the eigenvectors of the unknown graph. Importantly, we provide theoretical bounds on the error introduced by this sketching procedure based on spectral features of the graph filter involved. Finally, our theoretical findings are validated via numerical experiments.
BibTeX
@inproceedings{wai2018community,
  author = {Hoi-To Wai and Santiago Segarra and Asuman E. Ozdaglar and Anna Scaglione and Ali Jadbabaie},
  title = {{Community Detection from Low-Rank Excitations of a Graph Filter}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  url = {https://openreview.net/forum?id=aPz75BSb4xL},
}
Figure