A. Natali
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
11 records found
1
This paper addresses graph topology identification for applications where the underlying structure of systems like brain and social networks is not directly observable. Traditional approaches based on signal matching and spectral templates have limitations, particularly in handling scale issues and sparsity assumptions. We introduce a novel covariance matching methodology that efficiently reconstructs the graph topology using observable data. For the structural equation model (SEM) using an undirected graph, we demonstrate that our method can converge to the correct result under relatively soft conditions. Furthermore, we extend our methodology to polynomial models and any known distribution of latent variables, broadening its applicability and utility in diverse graph-based systems.
...
This paper addresses graph topology identification for applications where the underlying structure of systems like brain and social networks is not directly observable. Traditional approaches based on signal matching and spectral templates have limitations, particularly in handling scale issues and sparsity assumptions. We introduce a novel covariance matching methodology that efficiently reconstructs the graph topology using observable data. For the structural equation model (SEM) using an undirected graph, we demonstrate that our method can converge to the correct result under relatively soft conditions. Furthermore, we extend our methodology to polynomial models and any known distribution of latent variables, broadening its applicability and utility in diverse graph-based systems.
In this paper, we present a novel convolution theorem which encompasses the well known convolution theorem in (graph) signal processing as well as the one related to time-varying filters. Specifically, we show how a node-wise convolution for signals supported on a graph can be expressed as another node-wise convolution in a frequency domain graph, different from the original graph. This is achieved through a parameterization of the filter coefficients following a basis expansion model. After showing how the presented theorem is consistent with the already existing body of literature, we discuss its implications in terms of non-stationarity. Finally, we propose a data-driven algorithm based on subspace fitting to learn the frequency domain graph, which is then corroborated by experimental results on synthetic and real data.
...
In this paper, we present a novel convolution theorem which encompasses the well known convolution theorem in (graph) signal processing as well as the one related to time-varying filters. Specifically, we show how a node-wise convolution for signals supported on a graph can be expressed as another node-wise convolution in a frequency domain graph, different from the original graph. This is achieved through a parameterization of the filter coefficients following a basis expansion model. After showing how the presented theorem is consistent with the already existing body of literature, we discuss its implications in terms of non-stationarity. Finally, we propose a data-driven algorithm based on subspace fitting to learn the frequency domain graph, which is then corroborated by experimental results on synthetic and real data.
Signal processing and optimization on graphs
Learning time-varying structures and generalizing convolution principles
Graph signal processing is a field that focuses on extracting valuable information from data collected in networks, such as social, transportation, and brain networks. This doctoral thesis makes significant contributions to two important aspects of graph signal processing: network topology identification and the convolution theorem. The thesis begins by introducing the fundamental concepts of signal processing, such as shifting, convolution, and filtering, in the discrete-time domain. It then extends these concepts to a graph-based context, where classical discrete-time signal processing can be seen as a special case of graph signal processing. The thesis then presents novel theories and algorithms in three main areas. Specifically:
(1) Graph Topology and Filter Estimation: It proposes an algorithmic approach to jointly learn the graph structure and filter coefficients from input-output graph-based data. The method addresses the non-convexity of the problem using an alternating-minimization scheme, ensuring global convergence.
(2) Time-Varying Graph Topology Inference: A new framework based on time-varying convex optimization tools is introduced for inferring time-varying network structures from graph-based data. This framework offers flexibility to users in balancing execution speed and algorithm accuracy through tunable parameters.
(3) Generalizing the Convolution Theorem: A generalization of the convolution theorem that encompasses both the graph convolution theorem and the one related to time-varying filters is introduced. This generalization has implications for (non-) stationarity and spectral analysis of signals and enables the casting of a graph learning problem to infer a potential graph structure for the frequency domain.
In summary, this thesis significantly contributes to advancing graph signal processing by addressing fundamental challenges and introducing innovative methodologies. It holds the potential to inspire further innovation in the field and deepen our understanding of complex network dynamics.
...
(1) Graph Topology and Filter Estimation: It proposes an algorithmic approach to jointly learn the graph structure and filter coefficients from input-output graph-based data. The method addresses the non-convexity of the problem using an alternating-minimization scheme, ensuring global convergence.
(2) Time-Varying Graph Topology Inference: A new framework based on time-varying convex optimization tools is introduced for inferring time-varying network structures from graph-based data. This framework offers flexibility to users in balancing execution speed and algorithm accuracy through tunable parameters.
(3) Generalizing the Convolution Theorem: A generalization of the convolution theorem that encompasses both the graph convolution theorem and the one related to time-varying filters is introduced. This generalization has implications for (non-) stationarity and spectral analysis of signals and enables the casting of a graph learning problem to infer a potential graph structure for the frequency domain.
In summary, this thesis significantly contributes to advancing graph signal processing by addressing fundamental challenges and introducing innovative methodologies. It holds the potential to inspire further innovation in the field and deepen our understanding of complex network dynamics.
...
Graph signal processing is a field that focuses on extracting valuable information from data collected in networks, such as social, transportation, and brain networks. This doctoral thesis makes significant contributions to two important aspects of graph signal processing: network topology identification and the convolution theorem. The thesis begins by introducing the fundamental concepts of signal processing, such as shifting, convolution, and filtering, in the discrete-time domain. It then extends these concepts to a graph-based context, where classical discrete-time signal processing can be seen as a special case of graph signal processing. The thesis then presents novel theories and algorithms in three main areas. Specifically:
(1) Graph Topology and Filter Estimation: It proposes an algorithmic approach to jointly learn the graph structure and filter coefficients from input-output graph-based data. The method addresses the non-convexity of the problem using an alternating-minimization scheme, ensuring global convergence.
(2) Time-Varying Graph Topology Inference: A new framework based on time-varying convex optimization tools is introduced for inferring time-varying network structures from graph-based data. This framework offers flexibility to users in balancing execution speed and algorithm accuracy through tunable parameters.
(3) Generalizing the Convolution Theorem: A generalization of the convolution theorem that encompasses both the graph convolution theorem and the one related to time-varying filters is introduced. This generalization has implications for (non-) stationarity and spectral analysis of signals and enables the casting of a graph learning problem to infer a potential graph structure for the frequency domain.
In summary, this thesis significantly contributes to advancing graph signal processing by addressing fundamental challenges and introducing innovative methodologies. It holds the potential to inspire further innovation in the field and deepen our understanding of complex network dynamics.
(1) Graph Topology and Filter Estimation: It proposes an algorithmic approach to jointly learn the graph structure and filter coefficients from input-output graph-based data. The method addresses the non-convexity of the problem using an alternating-minimization scheme, ensuring global convergence.
(2) Time-Varying Graph Topology Inference: A new framework based on time-varying convex optimization tools is introduced for inferring time-varying network structures from graph-based data. This framework offers flexibility to users in balancing execution speed and algorithm accuracy through tunable parameters.
(3) Generalizing the Convolution Theorem: A generalization of the convolution theorem that encompasses both the graph convolution theorem and the one related to time-varying filters is introduced. This generalization has implications for (non-) stationarity and spectral analysis of signals and enables the casting of a graph learning problem to infer a potential graph structure for the frequency domain.
In summary, this thesis significantly contributes to advancing graph signal processing by addressing fundamental challenges and introducing innovative methodologies. It holds the potential to inspire further innovation in the field and deepen our understanding of complex network dynamics.
Forecasting time series on graphs is a fundamental problem in graph signal processing. When each entity of the network carries a vector of values for each time stamp instead of a scalar one, existing approaches resort to the use of product graphs to combine this multidimensional information, at the expense of creating a larger graph. In this paper, we show the limitations of such approaches, and propose extensions to tackle them. Then, we propose a recursive multiple-input multiple-output graph filter which encompasses many already existing models in the literature while being more flexible. Numerical simulations on a real world data set show the effectiveness of the proposed models.
...
Forecasting time series on graphs is a fundamental problem in graph signal processing. When each entity of the network carries a vector of values for each time stamp instead of a scalar one, existing approaches resort to the use of product graphs to combine this multidimensional information, at the expense of creating a larger graph. In this paper, we show the limitations of such approaches, and propose extensions to tackle them. Then, we propose a recursive multiple-input multiple-output graph filter which encompasses many already existing models in the literature while being more flexible. Numerical simulations on a real world data set show the effectiveness of the proposed models.
Fitting a polynomial to observed data is an ubiquitous task in many signal processing and machine learning tasks, such as interpolation and prediction. In that context, input and output pairs are available and the goal is to find the coefficients of the polynomial. However, in many applications, the input may be partially known or not known at all, rendering conventional regression approaches not applicable. In this paper, we formally state the (potentially partial) blind regression problem, illustrate some of its theoretical properties, and propose an algorithmic approach to solve it. As a case-study, we apply our methods to a jitter-correction problem and corroborate its performance.
...
Fitting a polynomial to observed data is an ubiquitous task in many signal processing and machine learning tasks, such as interpolation and prediction. In that context, input and output pairs are available and the goal is to find the coefficients of the polynomial. However, in many applications, the input may be partially known or not known at all, rendering conventional regression approaches not applicable. In this paper, we formally state the (potentially partial) blind regression problem, illustrate some of its theoretical properties, and propose an algorithmic approach to solve it. As a case-study, we apply our methods to a jitter-correction problem and corroborate its performance.
This work proposes an algorithmic framework to learn time-varying graphs from online data. The generality offered by the framework renders it model-independent, i.e., it can be theoretically analyzed in its abstract formulation and then instantiated under a variety of model-dependent graph learning problems. This is possible by phrasing (time-varying) graph learning as a composite optimization problem, where different functions regulate different desiderata, e.g., data fidelity, sparsity or smoothness. Instrumental for the findings is recognizing that the dependence of the majority (if not all) data-driven graph learning algorithms on the data is exerted through the empirical covariance matrix, representing a sufficient statistic for the estimation problem. Its user-defined recursive update enables the framework to work in non-stationary environments, while iterative algorithms building on novel time-varying optimization tools explicitly take into account the temporal dynamics, speeding up convergence and implicitly including a temporal-regularization of the solution. We specialize the framework to three well-known graph learning models, namely, the Gaussian graphical model (GGM), the structural equation model (SEM), and the smoothness-based model (SBM), where we also introduce ad-hoc vectorization schemes for structured matrices (symmetric, hollows, etc.) which are crucial to perform correct gradient computations, other than enabling to work in low-dimensional vector spaces and hence easing storage requirements. After discussing the theoretical guarantees of the proposed framework, we corroborate it with extensive numerical tests in synthetic and real data.
...
This work proposes an algorithmic framework to learn time-varying graphs from online data. The generality offered by the framework renders it model-independent, i.e., it can be theoretically analyzed in its abstract formulation and then instantiated under a variety of model-dependent graph learning problems. This is possible by phrasing (time-varying) graph learning as a composite optimization problem, where different functions regulate different desiderata, e.g., data fidelity, sparsity or smoothness. Instrumental for the findings is recognizing that the dependence of the majority (if not all) data-driven graph learning algorithms on the data is exerted through the empirical covariance matrix, representing a sufficient statistic for the estimation problem. Its user-defined recursive update enables the framework to work in non-stationary environments, while iterative algorithms building on novel time-varying optimization tools explicitly take into account the temporal dynamics, speeding up convergence and implicitly including a temporal-regularization of the solution. We specialize the framework to three well-known graph learning models, namely, the Gaussian graphical model (GGM), the structural equation model (SEM), and the smoothness-based model (SBM), where we also introduce ad-hoc vectorization schemes for structured matrices (symmetric, hollows, etc.) which are crucial to perform correct gradient computations, other than enabling to work in low-dimensional vector spaces and hence easing storage requirements. After discussing the theoretical guarantees of the proposed framework, we corroborate it with extensive numerical tests in synthetic and real data.
This paper focuses on the field of graph signal processing (GSP) and studies the node-varying graph filter (NV-GF) which has been proposed as a way to broaden the applicability of the classical graph filter (C-GF). In particular, we state and prove a new convolution theorem for a NV-GF which extends both the one for a C-GF and the one for a time-varying filter. The theorem relies on the definition of a so-called dual graph which characterizes the support of the frequency domain. The dual graph concept has been studied only very recently and many versions exist, yet the proposed convolution theorem is independent of the particular version. More interestingly, using non-stationary graph data on the primal graph, we can use the proposed convolution theorem to learn the dual graph and thereby introduce an innovative data-driven dual graph estimation technique.
...
This paper focuses on the field of graph signal processing (GSP) and studies the node-varying graph filter (NV-GF) which has been proposed as a way to broaden the applicability of the classical graph filter (C-GF). In particular, we state and prove a new convolution theorem for a NV-GF which extends both the one for a C-GF and the one for a time-varying filter. The theorem relies on the definition of a so-called dual graph which characterizes the support of the frequency domain. The dual graph concept has been studied only very recently and many versions exist, yet the proposed convolution theorem is independent of the particular version. More interestingly, using non-stationary graph data on the primal graph, we can use the proposed convolution theorem to learn the dual graph and thereby introduce an innovative data-driven dual graph estimation technique.
Signal processing and machine learning algorithms for data sup-ported over graphs, require the knowledge of the graph topology. Unless this information is given by the physics of the problem (e.g., water supply networks, power grids), the topology has to be learned from data. Topology identification is a challenging task, as the problem is often ill-posed, and becomes even harder when the graph structure is time-varying. In this paper, we address the problem of dynamic topology identification by building on recent results from time-varying optimization, devising a general-purpose online algorithm operating in non-stationary environments. Because of its iteration-constrained nature, the proposed approach exhibits an intrinsic temporal-regularization of the graph topology without explicitly enforcing it. As a case-study, we specialize our method to the Gaussian graphical model (GGM) problem and corroborate its performance.
...
Signal processing and machine learning algorithms for data sup-ported over graphs, require the knowledge of the graph topology. Unless this information is given by the physics of the problem (e.g., water supply networks, power grids), the topology has to be learned from data. Topology identification is a challenging task, as the problem is often ill-posed, and becomes even harder when the graph structure is time-varying. In this paper, we address the problem of dynamic topology identification by building on recent results from time-varying optimization, devising a general-purpose online algorithm operating in non-stationary environments. Because of its iteration-constrained nature, the proposed approach exhibits an intrinsic temporal-regularization of the graph topology without explicitly enforcing it. As a case-study, we specialize our method to the Gaussian graphical model (GGM) problem and corroborate its performance.
Topology identification is an important problem across many disciplines, since it reveals pairwise interactions among entities and can be used to interpret graph data. In many scenarios, however, this (unknown) topology is time-varying, rendering the problem even harder. In this paper, we focus on a time-varying version of the structural equation modeling (SEM) framework, which is an umbrella of multivariate techniques widely adopted in econometrics, epidemiology and psychology. In particular, we view the linear SEM as a first-order diffusion of a signal over a graph whose topology changes over time. Our goal is to learn such time-varying topology from streaming data. To attain this goal, we propose a real-time algorithm, further accelerated by building on recent advances in time-varying optimization, which updates the time-varying solution as a new sample comes into the system. We augment the implementation steps with theoretical guarantees, and we show performances on synthetic and real datasets.
...
Topology identification is an important problem across many disciplines, since it reveals pairwise interactions among entities and can be used to interpret graph data. In many scenarios, however, this (unknown) topology is time-varying, rendering the problem even harder. In this paper, we focus on a time-varying version of the structural equation modeling (SEM) framework, which is an umbrella of multivariate techniques widely adopted in econometrics, epidemiology and psychology. In particular, we view the linear SEM as a first-order diffusion of a signal over a graph whose topology changes over time. Our goal is to learn such time-varying topology from streaming data. To attain this goal, we propose a real-time algorithm, further accelerated by building on recent advances in time-varying optimization, which updates the time-varying solution as a new sample comes into the system. We augment the implementation steps with theoretical guarantees, and we show performances on synthetic and real datasets.
The forecasting of multi-variate time processes through graph-based techniques has recently been addressed under the graph signal processing framework. However, problems in the representation and the processing arise when each time series carries a vector of quantities rather than a scalar one. To tackle this issue, we devise a new framework and propose new methodologies based on the graph vector autoregressive model. More explicitly, we leverage product graphs to model the high-dimensional graph data and develop multidimensional graph-based vector autoregressive models to forecast future trends with a number of parameters that is independent of the number of time series and a linear computational complexity. Numerical results demonstrating the prediction of moving point clouds corroborate our findings.
...
The forecasting of multi-variate time processes through graph-based techniques has recently been addressed under the graph signal processing framework. However, problems in the representation and the processing arise when each time series carries a vector of quantities rather than a scalar one. To tackle this issue, we devise a new framework and propose new methodologies based on the graph vector autoregressive model. More explicitly, we leverage product graphs to model the high-dimensional graph data and develop multidimensional graph-based vector autoregressive models to forecast future trends with a number of parameters that is independent of the number of time series and a linear computational complexity. Numerical results demonstrating the prediction of moving point clouds corroborate our findings.
Data defined over a network have been successfully modelled by means of graph filters. However, although in many scenarios the connectivity of the network is known, e.g., smart grids, social networks, etc., the lack of well-defined interaction weights hinders the ability to model the observed networked data using graph filters. Therefore, in this paper, we focus on the joint identification of coefficients and graph weights defining the graph filter that best models the observed input/output network data. While these two problems have been mostly addressed separately, we here propose an iterative method that exploits the knowledge of the support of the graph for the joint identification of graph filter coefficients and edge weights. We further show that our iterative scheme guarantees a non-increasing cost at every iteration, ensuring a globally-convergent behavior. Numerical experiments confirm the applicability of our proposed approach.
...
Data defined over a network have been successfully modelled by means of graph filters. However, although in many scenarios the connectivity of the network is known, e.g., smart grids, social networks, etc., the lack of well-defined interaction weights hinders the ability to model the observed networked data using graph filters. Therefore, in this paper, we focus on the joint identification of coefficients and graph weights defining the graph filter that best models the observed input/output network data. While these two problems have been mostly addressed separately, we here propose an iterative method that exploits the knowledge of the support of the graph for the joint identification of graph filter coefficients and edge weights. We further show that our iterative scheme guarantees a non-increasing cost at every iteration, ensuring a globally-convergent behavior. Numerical experiments confirm the applicability of our proposed approach.