Examinando por Autor "Rey, Samuel"

Mostrando 1 - 8 de 8

Convolutional Learning on Directed Acyclic Graphs
(2024) Rey, Samuel; Ajorlou, Hamed; Mateos, Gonzalo
We develop a novel convolutional architecture tailored for learning from data defined over directed acyclic graphs (DAGs). DAGs can be used to model causal relationships among variables, but their nilpotent adjacency matrices pose unique challenges towards developing DAG signal processing and machine learning tools. To address this limitation, we harness recent advances offering alternative definitions of causal shifts and convolutions for signals on DAGs. We develop a novel convolutional graph neural network that integrates learnable DAG filters to account for the partial ordering induced by the graph topology, thus providing valuable inductive bias to learn effective representations of DAG-supported data. We discuss the salient advantages and potential limitations of the proposed DAG convolutional network (DCN) and evaluate its performance on two learning tasks using synthetic data: network diffusion estimation and source identification. DCN compares favorably relative to several baselines, showcasing its promising potential.
Enhanced graph-learning schemes driven by similar distributions of motifs
(Institute of Electrical and Electronics Engineers, 2023-08-10) Rey, Samuel; T. Mitchell, Roddenberry; Segarra, Santiago; Garcia Marques, Antonio
This paper looks at the task of network topology inference, where the goal is to learn an unknown graph from nodal observations. One of the novelties of the approach put forth is the consideration of prior information about the density of motifs of the unknown graph to enhance the inference of classical Gaussian graphical models. Directly dealing with the density of motifs constitutes a challenging combinatorial task. However, we note that if two graphs have similar motif densities, one can show that the expected value of a polynomial applied to their empirical spectral distributions will be similar. Guided by this, we first assume that we observe a reference graph with a density of motifs similar to that of the sought graph, and then, we exploit this relation by incorporating a similarity constraint and a regularization term in the graph learning optimization problem. The (non-)convexity of the optimization problem is discussed, and a computationally efficient alternating majorization-minimization algorithm is designed. We assess the performance of the proposed method through exhaustive numerical experiments, where different constraints are considered and compared against popular alternatives on both synthetic and real-world datasets
Enhanced graph-learning schemes driven by similar distributions of motifs
(2024) Rey, Samuel; Roddenberry, T. Mitchell; Segarra, Santiago; Marques, Antonio G.
We develop a novel convolutional architecture tailored for learning from data defined over directed acyclic graphs (DAGs). DAGs can be used to model causal relationships among variables, but their nilpotent adjacency matrices pose unique challenges towards developing DAG signal processing and machine learning tools. To address this limitation, we harness recent advances offering alternative definitions of causal shifts and convolutions for signals on DAGs. We develop a novel convolutional graph neural network that integrates learnable DAG filters to account for the partial ordering induced by the graph topology, thus providing valuable inductive bias to learn effective representations of DAG-supported data. We discuss the salient advantages and potential limitations of the proposed DAG convolutional network (DCN) and evaluate its performance on two learning tasks using synthetic data: network diffusion estimation and source identification. DCN compares favorably relative to several baselines, showcasing its promising potential.
Joint Network Topology Inference in the Presence of Hidden Nodes
(Institute of Electrical and Electronics Engineers, 2024-04-23) Navarro, Madeline; Rey, Samuel; Buciulea, Andrei; Garcia Marques, Antonio; Segarra, Santiago
We investigate the increasingly prominent task of jointly inferring multiple networks from nodal observations. While most joint inference methods assume that observations are available at all nodes, we consider the realistic and more difficult scenario where a subset of nodes are hidden and cannot be measured. Under the assumptions that the partially observed nodal signals are graph stationary and the networks have similar connectivity patterns, we derive structural characteristics of the connectivity between hidden and observed nodes. This allows us to formulate an optimization problem for estimating networks while accounting for the influence of hidden nodes. We identify conditions under which a convex relaxation yields the sparsest solution, and we formalize the performance of our proposed optimization problem with respect to the effect of the hidden nodes. Finally, synthetic and real-world simulations provide evaluations of our method in comparison with other baselines
Learning graphs from smooth and graph-stationary signals with hidden variables
(Institute of Electrical and Electronics Engineers, 2022-03-22) Buciulea, Andrei; Rey, Samuel; Garcia Marques, Antonio
Network-topology inference from (vertex) signal observations is a prominent problem across data-science and engineering disciplines. Most existing schemes assume that observations from all nodes are available, but in many practical environments, only a subset of nodes is accessible. A natural (and sometimes effective) approach is to disregard the role of unobserved nodes, but this ignores latent network effects, deteriorating the quality of the estimated graph. Differently, this paper investigates the problem of inferring the topology of a network from nodal observations while taking into account the presence of hidden (latent) variables . Our schemes assume the number of observed nodes is considerably larger than the number of hidden variables and build on recent graph signal processing 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 smooth and/or stationary in the sought graph. The assumptions are codified into different constrained optimization problems, with the presence of hidden variables being explicitly taken into account. Since the resulting problems are ill-conditioned and non-convex, the block matrix structure of the proposed formulations is leveraged and suitable convex-regularized relaxations are presented. Numerical experiments over synthetic and real-world datasets showcase the performance of the developed methods and compare them with existing alternatives
Robust graph filter identification and graph denoising from signal observations
(Institute of Electrical and Electronics Engineers, 2023-08-07) Rey, Samuel; Tenorio, Victor Manuel; Garcia Marques, Antonio
When facing graph signal processing tasks, it is typically assumed that the graph describing the support of the signals is known. However, in many relevant applications the available graph suffers from observational errors and perturbations . As a result, any method that relies on the graph topology and ignores the presence of perturbations may yield suboptimal results. Motivated by this, we propose a novel approach for handling perturbations on 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. As a result, 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. The second part of the paper i) generalizes the design to a robust setup where several GFs are jointly estimated, and ii) introduces an alternative algorithmic implementation that reduces the computational complexity. Finally, the detrimental influence of the perturbations and the benefits resulting from the robust approach are numerically analyzed over synthetic and real-world datasets, comparing them with other state-of-the-art alternatives
Sampling and reconstruction of diffused sparse graph signals from successive local aggregations
(Institute of Electrical and Electronics Engineers, 2019-06-13) Rey, Samuel; Iglesias García, Fernando José; Cabrera, Cristobal; García Marques, Antonio
We analyze the sampling and posterior recovery of diffused sparse graph signals from observations gathered at a single node by using an aggregation sampling scheme. Diffused sparse graph signals can be modeled as the output of a linear graph filter to a sparse input and are useful in scenarios where a few seeding (source) nodes generate a non-zero input, which is then diffused according to the network dynamics dictated by the filter. Instead of considering a traditional setup where the observations correspond to the signal values at a subset of nodes, here the observations are obtained locally at a single node via the successive aggregation of its own value and that of its neighbors. 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 those of the diffusing filter being unknown
Untrained graph neural networks for denoising
(Institute of Electrical and Electronics Engineers, 2022-11-23) Rey, Samuel; Segarra, Santiago; Reinhard, Heckel; Garcia Marques, Antonio
A fundamental problem in signal processing is to denoise a signal. While there are many well-performing methods for denoising signals defined on regular domains, including images defined on a two-dimensional pixel grid, many important classes of signals are defined over irregular domains that can be conveniently represented by a graph. This paper introduces two untrained graph neural network architectures for graph signal denoising, develops theoretical guarantees for their denoising capabilities in a simple setup, and provides empirical evidence in more general scenarios. The two architectures differ on how they incorporate the information encoded in the graph, with one relying on graph convolutions and the other employing graph upsampling operators based on hierarchical clustering. Each architecture implements a different prior over the targeted signals. Finally, we provide numerical experiments with synthetic and real datasets that i) asses the denoising behavior predicted by our theoretical results and ii) compare the denoising performance of our architectures with that of existing alternatives