Learning graphs from data: A signal representation perspective

Abstract

The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this tutorial overview, we survey solutions to the problem of graph learning, including classical viewpoints from statistics and physics, and more recent approaches that adopt a graph signal processing (GSP) perspective. We further emphasize the conceptual similarities and differences between classical and GSP-based graph inference methods, and highlight the potential advantage of the latter in a number of theoretical and practical scenarios. We conclude with several open issues and challenges that are keys to the design of future signal processing and machine learning algorithms for learning graphs from data.

arXiv commentcorrected several imprecise statements in previous versions of the manuscript as well as in the article of the same title in the May 2019 issue of IEEE Signal Processing Magazine (vol. 36, no. 3, pp. 44-63, May 2019)

References in corpus (25)

• Community detection in graphs
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Epidemic processes in complex networks
• High-dimensional graphs and variable selection with the Lasso
• Discrete Signal Processing on Graphs
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• On the Convexity of Latent Social Network Inference
• Causal Network Inference via Group Sparse Regularization
• On the Graph Fourier Transform for Directed Graphs
• Learning parametric dictionaries for graph signals
• Blind Identification of Graph Filters
• Irregularity-Aware Graph Fourier Transforms
• A Directed Graph Fourier Transform with Spread Frequency Components
• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• Tracking Switched Dynamic Network Topologies from Information Cascades
• Nonlinear Structural Vector Autoregressive Models for Inferring Effective Brain Network Connectivity
• Graph Learning from Data under Structural and Laplacian Constraints
• A unified framework for harmonic analysis of functions on directed graphs and changing data
• Active Learning of Multiple Source Multiple Destination Topologies
• Trace Complexity of Network Inference
• Reconstructing a Graph from Path Traces
• Joint Estimation of Low-Rank Components and Connectivity Graph in High-Dimensional Graph Signals: Application to Brain Imaging

Cited by in corpus (83)

• Graph Representation Learning: A Survey
• Topological Signal Processing over Simplicial Complexes
• Graph signal processing for machine learning: A review and new perspectives
• Graph Signal Processing: History, Development, Impact, and Outlook
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Feature Graph Learning for 3D Point Cloud Denoising
• Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
• Grid-Graph Signal Processing (Grid-GSP): A Graph Signal Processing Framework for the Power Grid
• Deep Unsupervised Learning of 3D Point Clouds via Graph Topology Inference and Filtering
• Reconstruction of Time-varying Graph Signals via Sobolev Smoothness
• GOT: An Optimal Transport framework for Graph comparison
• Generalized Sampling on Graphs With Subspace and Smoothness Priors
• Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)
• Network Inference from Consensus Dynamics with Unknown Parameters
• Graph Signal Sampling Under Stochastic Priors
• Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction
• Joint Inference of Multiple Graphs from Matrix Polynomials
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Semi-supervised Superpixel-based Multi-Feature Graph Learning for Hyperspectral Image Data
• Heterogeneous Interaction Modeling With Reduced Accumulated Error for Multi-Agent Trajectory Prediction
• Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
• Graph Signal Reconstruction Techniques for IoT Air Pollution Monitoring Platforms
• Sparse Graph Learning Under Laplacian-Related Constraints
• Temporal Graph Signal Decomposition
• Node-Centric Graph Learning from Data for Brain State Identification
• Explainability and Graph Learning from Social Interactions
• Joint Network Topology Inference via a Shared Graphon Model
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
• A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks
• Residual Neural Networks for the Prediction of Planetary Collision Outcomes
• An Unbiased Symmetric Matrix Estimator for Topology Inference under Partial Observability
• Graph Learning for Spatiotemporal Signals with Long- and Short-Term Characterization
• Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications
• Reconstructing supply networks
• Online Graph Learning from Social Interactions
• Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty
• GRASPEL: Graph Spectral Learning at Scale
• Understanding Concepts in Graph Signal Processing for Neurophysiological Signal Analysis
• Signal processing on simplicial complexes
• Sampling and Recovery of Graph Signals based on Graph Neural Networks
• COPT: Coordinated Optimal Transport for Graph Sketching
• Supervised Linear Regression for Graph Learning from Graph Signals
• Graph Neural Lasso for Dynamic Network Regression
• Learning Quadratic Games on Networks
• SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements
• Network Diffusions via Neural Mean-Field Dynamics
• The Mathematical Foundations of Manifold Learning
• Point Cloud Segmentation based on Hypergraph Spectral Clustering
• Learning hidden influences in large-scale dynamical social networks: A data-driven sparsity-based approach
• Deep Importance Sampling based on Regression for Model Inversion and Emulation
• Identification of LFT Structured Descriptor Systems with Slow and Non-uniform Sampling
• Community-Level Anomaly Detection for Anti-Money Laundering
• Skeleton-based Hand-Gesture Recognition with Lightweight Graph Convolutional Networks
• Extending the Davis-Kahan theorem for comparing eigenvectors of two symmetric matrices I: Theory
• Robust Graph Learning Under Wasserstein Uncertainty
• Graph learning under spectral sparsity constraints
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation
• Identifying First-order Lowpass Graph Signals using Perron Frobenius Theorem
• Graph Signal Processing over a Probability Space of Shift Operators
• Clustering-aware Graph Construction: A Joint Learning Perspective
• Learning Networked Exponential Families with Network Lasso
• Laplacian Constrained Precision Matrix Estimation: Existence and High Dimensional Consistency
• Topology Inference for Network Systems with Unknown Inputs
• Online Graph Topology Learning from Matrix-valued Time Series
• Fast Structured Orthogonal Dictionary Learning using Householder Reflections
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
• Latent Network Embedding via Adversarial Auto-encoders
• Mask Combination of Multi-layer Graphs for Global Structure Inference
• SGL: Spectral Graph Learning from Measurements
• Signal processing with a distribution of graph operators
• Online Graph Learning in Dynamic Environments
• Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition
• Joint Network Topology Inference via Structured Fusion Regularization
• Signed Graph Learning with Hidden Nodes
• Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals
• Influence Estimation and Maximization via Neural Mean-Field Dynamics
• Stationarity of Time-Series on Graph via Bivariate Translation Invariance
• Time-Varying Graph Learning with Constraints on Graph Temporal Variation
• Time-varying Graph Learning Under Structured Temporal Priors
• Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications
• Estimating Centrality Blindly from Low-pass Filtered Graph Signals
• Recursive Prediction of Graph Signals with Incoming Nodes