Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint

Abstract

The problem of graph learning concerns the construction of an explicit topological structure revealing the relationship between nodes representing data entities, which plays an increasingly important role in the success of many graph-based representations and algorithms in the field of machine learning and graph signal processing. In this paper, we propose a novel graph learning framework that incorporates the node-side and observation-side information, and in particular the covariates that help to explain the dependency structures in graph signals. To this end, we consider graph signals as functions in the reproducing kernel Hilbert space associated with a Kronecker product kernel, and integrate functional learning with smoothness-promoting graph learning to learn a graph representing the relationship between nodes. The functional learning increases the robustness of graph learning against missing and incomplete information in the graph signals. In addition, we develop a novel graph-based regularisation method which, when combined with the Kronecker product kernel, enables our model to capture both the dependency explained by the graph and the dependency due to graph signals observed under different but related circumstances, e.g. different points in time. The latter means the graph signals are free from the i.i.d. assumptions required by the classical graph learning models. Experiments on both synthetic and real-world data show that our methods outperform the state-of-the-art models in learning a meaningful graph topology from graph signals, in particular under heavy noise, missing values, and multiple dependency.

arXiv comment13 pages, with extra 3-page appendices

References in corpus (20)

• A Comprehensive Survey on Graph Neural Networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Neural Architecture Search with Reinforcement Learning
• Geometric deep learning: going beyond Euclidean data
• Discrete Signal Processing on Graphs
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• Neural Relational Inference for Interacting Systems
• Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• Learning Discrete Structures for Graph Neural Networks
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks
• Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
• Iterative Thresholding Algorithm for Sparse Inverse Covariance Estimation
• Large sample analysis of the median heuristic
• Large Scale Graph Learning from Smooth Signals
• Deep Iterative and Adaptive Learning for Graph Neural Networks
• Graph Learning for Spatiotemporal Signals with Long- and Short-Term Characterization

Cited by in corpus (3)

• Reconstruction of Time-varying Graph Signals via Sobolev Smoothness
• Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model
• Clustering as Approximation by Constrained Projectors: Theory and Guarantees