Connecting the Dots: Identifying Network Structure via Graph Signal Processing

Abstract

Network topology inference is a prominent problem in Network Science. Most graph signal processing (GSP) efforts to date assume that the underlying network is known, and then analyze how the graph's algebraic and spectral characteristics impact the properties of the graph signals of interest. Such an assumption is often untenable beyond applications dealing with e.g., directly observable social and infrastructure networks; and typically adopted graph construction schemes are largely informal, distinctly lacking an element of validation. This tutorial offers an overview of graph learning methods developed to bridge the aforementioned gap, by using information available from graph signals to infer the underlying graph topology. Fairly mature statistical approaches are surveyed first, where correlation analysis takes center stage along with its connections to covariance selection and high-dimensional regression for learning Gaussian graphical models. Recent GSP-based network inference frameworks are also described, which postulate that the network exists as a latent underlying structure, and that observations are generated as a result of a network process defined in such a graph. A number of arguably more nascent topics are also briefly outlined, including inference of dynamic networks, nonlinear models of pairwise interaction, as well as extensions to directed graphs and their relation to causal inference. All in all, this paper introduces readers to challenges and opportunities for signal processing research in emerging topic areas at the crossroads of modeling, prediction, and control of complex behavior arising in networked systems that evolve over time.

References in corpus (17)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• 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
• Sampling of graph signals with successive local aggregations
• Stationary signal processing on graphs
• Stationary Graph Processes and Spectral Estimation
• Graph Frequency Analysis of Brain Signals
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Causal Network Inference via Group Sparse Regularization
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks
• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• Learning Laplacian Matrix in Smooth Graph Signal Representations
• Inference of High-dimensional Autoregressive Generalized Linear Models
• Network Inference via the Time-Varying Graphical Lasso
• Structure and Dynamics of Information Pathways in Online Media

Cited by in corpus (65)

• 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
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Differentiable Graph Module (DGM) for Graph Convolutional Networks
• Feature Graph Learning for 3D Point Cloud Denoising
• Hypergraph Spectral Analysis and Processing in 3D Point Cloud
• Network Inference from Consensus Dynamics with Unknown Parameters
• Blind identification of stochastic block models from dynamical observations
• Joint Inference of Multiple Graphs from Matrix Polynomials
• Multi-way Graph Signal Processing on Tensors: Integrative analysis of irregular geometries
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Exact Blind Community Detection from Signals on Multiple Graphs
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Blind Inference of Eigenvector Centrality Rankings
• Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
• Graph Signal Reconstruction Techniques for IoT Air Pollution Monitoring Platforms
• Joint Network Topology Inference in the Presence of Hidden Nodes
• Joint Network Topology Inference via a Shared Graphon Model
• A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
• Estimate the spectrum of affine dynamical systems from partial observations of a single trajectory data
• Sampling Theory of Jointly Bandlimited Time-vertex Graph Signals
• Multiple Kernel Representation Learning on Networks
• An Unbiased Symmetric Matrix Estimator for Topology Inference under Partial Observability
• Graph Learning for Spatiotemporal Signals with Long- and Short-Term Characterization
• Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty
• Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications
• Consensus-Based Distributed Computation of Link-Based Network Metrics
• Signal processing on simplicial complexes
• Understanding Concepts in Graph Signal Processing for Neurophysiological Signal Analysis
• Learning Quadratic Games on Networks
• Blind Graph Matching Using Graph Signals
• Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes
• Network Diffusions via Neural Mean-Field Dynamics
• Signal Processing on Directed Graphs
• Point Cloud Segmentation based on Hypergraph Spectral Clustering
• Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach
• Graph learning under spectral sparsity constraints
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation
• Robust Graph Learning Under Wasserstein Uncertainty
• Topology Inference for Network Systems with Unknown Inputs
• Mask Combination of Multi-layer Graphs for Global Structure Inference
• Network Clustering Via Kernel-ARMA Modeling and the Grassmannian The Brain-Network Case
• Identifying First-order Lowpass Graph Signals using Perron Frobenius Theorem
• Laplacian Constrained Precision Matrix Estimation: Existence and High Dimensional Consistency
• Learning Parametrised Graph Shift Operators
• Graph Signal Processing over a Probability Space of Shift Operators
• Brain-Network Clustering via Kernel-ARMA Modeling and the Grassmannian
• Time-varying Graph Learning Under Structured Temporal Priors
• Topology Inference over Networks with Nonlinear Coupling
• Online Graph Learning in Dynamic Environments
• Inference on the structure of gene regulatory networks
• Joint Network Topology Inference via Structured Fusion Regularization
• Time-Vertex Machine Learning for Optimal Sensor Placement in Temporal Graph Signals: Applications in Structural Health Monitoring
• 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
• Signal processing with a distribution of graph operators
• Graphs for deep learning representations
• Estimating Network Processes via Blind Identification of Multiple Graph Filters
• Time-Varying Graph Learning with Constraints on Graph Temporal Variation
• Graph-Time Spectral Analysis for Atrial Fibrillation
• Estimating Centrality Blindly from Low-pass Filtered Graph Signals
• Recursive Network Estimation From Binary-Valued Observation Data