Robust Network Topology Inference and Processing of Graph Signals

Abstract

The abundance of large and heterogeneous systems is rendering contemporary data more pervasive, intricate, and with a non-regular structure. With classical techniques facing troubles to deal with the irregular (non-Euclidean) domain where the signals are defined, a popular approach at the heart of graph signal processing (GSP) is to: (i) represent the underlying support via a graph and (ii) exploit the topology of this graph to process the signals at hand. In addition to the irregular structure of the signals, another critical limitation is that the observed data is prone to the presence of perturbations, which, in the context of GSP, may affect not only the observed signals but also the topology of the supporting graph. Ignoring the presence of perturbations, along with the couplings between the errors in the signal and the errors in their support, can drastically hinder estimation performance. While many GSP works have looked at the presence of perturbations in the signals, much fewer have looked at the presence of perturbations in the graph, and almost none at their joint effect. While this is not surprising (GSP is a relatively new field), we expect this to change in the upcoming years. Motivated by the previous discussion, the goal of this thesis is to advance toward a robust GSP paradigm where the algorithms are carefully designed to incorporate the influence of perturbations in the graph signals, the graph support, and both. To do so, we consider different types of perturbations, evaluate their disruptive impact on fundamental GSP tasks, and design robust algorithms to address them. The first part of the thesis addresses the presence of perturbations in the graph signals, which typically lead to more tractable problems. When the observed signals are corrupted by additive noise, we introduce two untrained nonlinear graph neural network architectures to remove the noise from the observations, develop theoretical guarantees for their denoising capabilities in a simple setup, and provide empirical evidence in more general scenarios. Each of the architectures incorporates the information encoded by the graph in a different manner: one relying on graph convolutions, and the other employing graph upsampling operators based on hierarchical clustering. Intuitively, each architecture implements a different prior over the targeted signals. Then, we move on to a setting where perturbations appear in the form of missing values. In this case, we assume that the original signal is a diffused sparse graph signal, interpret the missing values as samples gathered through a successive aggregation sample scheme, and study the recovery (interpolation) of the original signal. Depending on the particular application, the goal is to use the local observations to recover the diffused signal or (the location and values of) the seeds. Different sampling configurations are investigated, including those of known and unknown locations of the sources as well as that of the diffusing filter being unknown. The second part of the thesis deals with perturbations in the topology of the graph, which give rise to more challenging formulations. In this sense, we propose a novel approach for handling perturbations in the links of the graph and apply it to the problem of robust graph filter (GF) identification from input-output observations. Different from existing works, we formulate a non-convex optimization problem that operates in the vertex domain and jointly performs GF identification and graph denoising, and hence, on top of learning the desired GF, an estimate of the graph is obtained as a byproduct. To handle the resulting bi-convex problem, we design an algorithm that blends techniques from alternating optimization and majorization minimization, showing its convergence to a stationary point. Then, moving on to the last type of perturbation, we investigate the problem of learning a graph from nodal observations for setups where only a subset of the nodes are observed, with the others remaining unobserved or hidden. Our schemes assume the number of observed nodes is considerably larger than the number of hidden nodes, and build on recent GSP models to relate the signals and the underlying graph. Specifically, we go beyond classical correlation and partial correlation approaches and assume that the signals are stationary in the sought graph, and moreover, we propose a joint network topology inference framework where several related graphs are estimated together. The underlying idea is to exploit the similarity of the different graphs to enhance the quality of the estimation. Since the resulting problems are illconditioned and non-convex, the block matrix structure of the proposed formulations is leveraged and suitable convex-regularized relaxations are presented. Although the methodology and focus of this thesis are more theoretical (defining an estimation problem, stating the considered assumptions, obtaining the estimates as solutions to rigorously formulated optimization problems, designing computationally efficient provably convergent algorithms and, whenever possible, characterizing the performance of those), the experimental results will also play an important role. To that end, we evaluate the performance of our algorithms over synthetic and real-world datasets and compare their results with state-of-the-art alternatives. These experiments reflect the impact of ignoring the presence of perturbations, show the strengths and weaknesses of the proposed methods, demonstrate that in a number of settings our methods outperform current alternatives, and assess the applicability of our schemes to real-world problems.