Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis

Abstract

This paper treats a blind detection problem to identify the central nodes in a graph from filtered graph signals. Unlike prior works which impose strong restrictions on the data model, we only require the underlying graph filter to satisfy a low pass property with a generic low-rank excitation model. We treat two cases depending on the low pass graph filter's strength. When the graph filter is strong low pass, i.e., it has a frequency response that drops sharply at the high frequencies, we show that the principal component analysis (PCA) method detects central nodes with high accuracy. For general low pass graph filter, we show that the graph signals can be described by a structured factor model featuring the product between a low-rank plus sparse factor and an unstructured factor. We propose a two-stage decomposition algorithm to learn the structured factor model via a judicious combination of the non-negative matrix factorization and robust PCA algorithms. We analyze the identifiability conditions for the model which lead to accurate central nodes detection. Numerical experiments on synthetic and real data are provided to support our findings. We demonstrate significant performance gains over prior works.

References in corpus (14)

• Discrete Signal Processing on Graphs
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
• Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
• A User Guide to Low-Pass Graph Signal Processing and its Applications
• A variational approach to stable principal component pursuit
• Community detection in networks without observing edges
• Blind identification of stochastic block models from dynamical observations
• Exact Blind Community Detection from Signals on Multiple Graphs
• Blind Inference of Eigenvector Centrality Rankings
• Hybrid Inexact BCD for Coupled Structured Matrix Factorization in Hyperspectral Super-Resolution

Cited by in corpus (4)

• Robust Graph Filter Identification and Graph Denoising from Signal Observations
• Blind Graph Matching Using Graph Signals
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation
• Learning Graph Filters for Structure-Function Coupling based Hub Node Identification