Examinando por Autor "Segarra, Santiago"

Mostrando 1 - 5 de 5

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 Inference of Multiple Graphs with Hidden Variables from Stationary Graph Signals
(IEEE, 2022) Rey, Samuel; Buciulea, Andrei; Navarro, Madeline; Segarra, Santiago; Marques, Antonio G.
Learning graphs from sets of nodal observations represents a prominent problem formally known as graph topology inference. However, current approaches are limited by typically focusing on inferring single networks, and they assume that observations from all nodes are available. First, many contemporary setups involve multiple related networks, and second, it is often the case that only a subset of nodes is observed while the rest remain hidden. Motivated by these facts, we introduce a joint graph topology inference method that models the influence of the hidden variables. Under the assumptions that the observed signals are stationary on the sought graphs and the graphs are closely related, the joint estimation of multiple networks allows us to exploit such relationships to improve the quality of the learned graphs. Moreover, we confront the challenging problem of modeling the influence of the hidden nodes to minimize their detrimental effect. To obtain an amenable approach, we take advantage of the particular structure of the setup at hand and leverage the similarity between the different graphs, which affects both the observed and the hidden nodes. To test the proposed method, numerical simulations over synthetic and real-world graphs are provided
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
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