Learning Product Graphs Underlying Smooth Graph Signals

Abstract

Real-world data is often times associated with irregular structures that can analytically be represented as graphs. Having access to this graph, which is sometimes trivially evident from domain knowledge, provides a better representation of the data and facilitates various information processing tasks. However, in cases where the underlying graph is unavailable, it needs to be learned from the data itself for data representation, data processing and inference purposes. Existing literature on learning graphs from data has mostly considered arbitrary graphs, whereas the graphs generating real-world data tend to have additional structure that can be incorporated in the graph learning procedure. Structure-aware graph learning methods require learning fewer parameters and have the potential to reduce computational, memory and sample complexities. In light of this, the focus of this paper is to devise a method to learn structured graphs from data that are given in the form of product graphs. Product graphs arise naturally in many real-world datasets and provide an efficient and compact representation of large-scale graphs through several smaller factor graphs. To this end, first the graph learning problem is posed as a linear program, which (on average) outperforms the state-of-the-art graph learning algorithms. This formulation is of independent interest itself as it shows that graph learning is possible through a simple linear program. Afterwards, an alternating minimization-based algorithm aimed at learning various types of product graphs is proposed, and local convergence guarantees to the true solution are established for this algorithm. Finally the performance gains, reduced sample complexity, and inference capabilities of the proposed algorithm over existing methods are also validated through numerical simulations on synthetic and real datasets.

arXiv comment14 pages, 5 figures, and 2 tables; revised version of the preprint of a journal paper; revision includes restructuring of text, improved theoretical results, and additional references

References in corpus (11)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Geometric deep learning: going beyond Euclidean data
• Discrete Signal Processing on Graphs
• Kronecker Graphs: An Approach to Modeling Networks
• Signal Recovery on Graphs: Variation Minimization
• GSPBOX: A toolbox for signal processing on graphs
• Covariance Estimation in High Dimensions via Kronecker Product Expansions
• Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
• Graph topology inference based on sparsifying transform learning
• Large Scale Graph Learning from Smooth Signals
• How to learn a graph from smooth signals

Cited by in corpus (1)

• A Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression