Search

Our goal in this paper is the robust design of filters acting on signals observed over graphs subject to small perturbations of their edges. The focus is on developing a method to identify spectral and polynomial graph filters that can adapt to the perturbations in the underlying graph structure while ensuring the filters adhere to the desired spectral mask. To address this, we propose a novel approach that leverages approximate closed-form expressions for the perturbed eigendecomposition of the Laplacian matrix associated with the nominal topology. Furthermore, when dealing with noisy input signals for graph filters, we propose a strategy for designing FIR filters that jointly minimize the approximation error with respect to the ideal filter and the estimation error of the output, ensuring robustness against both graph perturbations and noise. Numerical results validate the effectiveness of our proposed strategies, highlighting their capability to efficiently manage perturbations and noise.

In this work, we study the problem of stability of Graph Convolutional Neural Networks (GCNs) under random small perturbations in the underlying graph topology, i.e. under a limited number of insertions or deletions of edges. We derive a novel bound on the expected difference between the outputs of unperturbed and perturbed GCNs. The proposed bound explicitly depends on the magnitude of the perturbation of the eigenpairs of the Laplacian matrix, and the perturbation explicitly depends on which edges are inserted or deleted. Then, we provide a quantitative characterization of the effect of perturbing specific edges on the stability of the network. We leverage tools from small perturbation analysis to express the bounds in closed, albeit approximate, form, in order to enhance interpretability of the results, without the need to compute any perturbed shift operator. Finally, we numerically evaluate the effectiveness of the proposed bound., Comment: Accepted for publication in Proc. of 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2024)

Despite the large research effort devoted to learning dependencies between time series, the state of the art still faces a major limitation: existing methods learn partial correlations but fail to discriminate across distinct frequency bands. Motivated by many applications in which this differentiation is pivotal, we overcome this limitation by learning a block-sparse, frequency-dependent, partial correlation graph, in which layers correspond to different frequency bands, and partial correlations can occur over just a few layers. To this aim, we formulate and solve two nonconvex learning problems: the first has a closed-form solution and is suitable when there is prior knowledge about the number of partial correlations; the second hinges on an iterative solution based on successive convex approximation, and is effective for the general case where no prior knowledge is available. Numerical results on synthetic data show that the proposed methods outperform the current state of the art. Finally, the analysis of financial time series confirms that partial correlations exist only within a few frequency bands, underscoring how our methods enable the gaining of valuable insights that would be undetected without discriminating along the frequency domain., Comment: Accepted at IEEE Transactions on Signal Processing

Graph machine learning methods excel at leveraging pairwise relations present in the data. However, graphs are unable to fully capture the multi-way interactions inherent in many complex systems. An effective way to incorporate them is to model the data on higher-order combinatorial topological spaces, such as Simplicial Complexes (SCs) or Cell Complexes. For this reason, we introduce Generalized Simplicial Attention Neural Networks (GSANs), novel neural network architectures designed to process data living on simplicial complexes using masked self-attentional layers. Hinging on topological signal processing principles, we devise a series of principled self-attention mechanisms able to process data associated with simplices of various order, such as nodes, edges, triangles, and beyond. These schemes learn how to combine data associated with neighbor simplices of consecutive order in a task-oriented fashion, leveraging on the simplicial Dirac operator and its Dirac decomposition. We also prove that GSAN satisfies two fundamental properties: permutation equivariance and simplicial-awareness. Finally, we illustrate how our approach compares favorably with other simplicial and graph models when applied to several (inductive and transductive) tasks such as trajectory prediction, missing data imputation, graph classification, and simplex prediction., Comment: arXiv admin note: text overlap with arXiv:2203.07485 (preliminary version of this paper). 16 pages, accepted for publication at IEEE TSIPN

Weighing the topological domain over which data can be represented and analysed is a key strategy in many signal processing and machine learning applications, enabling the extraction and exploitation of meaningful data features and their (higher order) relationships. Our goal in this paper is to present topological signal processing tools for weighted simplicial complexes. Specifically, relying on the weighted Hodge Laplacian theory, we propose efficient strategies to jointly learn the weights of the complex and the filters for the solenoidal, irrotational and harmonic components of the signals defined over the complex. We numerically asses the effectiveness of the proposed procedures.

Since their introduction, graph attention networks achieved outstanding results in graph representation learning tasks. However, these networks consider only pairwise relationships among nodes and then they are not able to fully exploit higher-order interactions present in many real world data-sets. In this paper, we introduce Cell Attention Networks (CANs), a neural architecture operating on data defined over the vertices of a graph, representing the graph as the 1-skeleton of a cell complex introduced to capture higher order interactions. In particular, we exploit the lower and upper neighborhoods, as encoded in the cell complex, to design two independent masked self-attention mechanisms, thus generalizing the conventional graph attention strategy. The approach used in CANs is hierarchical and it incorporates the following steps: i) a lifting algorithm that learns {\it edge features} from {\it node features}; ii) a cell attention mechanism to find the optimal combination of edge features over both lower and upper neighbors; iii) a hierarchical {\it edge pooling} mechanism to extract a compact meaningful set of features. The experimental results show that CAN is a low complexity strategy that compares favorably with state of the art results on graph-based learning tasks., Comment: Preprint, under review

Topological Signal Processing (TSP) over simplicial complexes is a framework that has been recently proposed, as a generalization of graph signal processing (GSP), to extend GSP to analyzing signals defined over sets of any order (i.e., not only vertices of a graph) and to capture multiway relations of any order among the data. However, simplicial complexes are required to satisfy the so-called inclusion property, according to which, if a set belongs to the complex, then all its subsets must also belong to the complex. In some applications, this is a severe limitation. To overcome this limit, in this paper we extend TSP to deal with signals defined over cell complexes and we also generalize the concept of cell complexes to include hollow cells. We show that, even if the algebraic formulation does not change significantly, the extension to the generalized cell complexes considerably broadens the number of applications. Most important, the new representation provides a much better trade-off between the complexity of the representation and its accuracy. In addition, we propose a method to infer the structure of the cell complex from data and we propose distributed filtering strategies, including a method to retrieve the sparsest representation of the harmonic component. We quantify the advantages of using cell complexes instead of simplicial complexes, in terms of the complexity/accuracy trade-off, for different applications such image segmentation and recovering of real flows measured on data traffic and transportation networks., Comment: Submitted to IEEE Transactions on Signal Processing, October 2023

The Topological Signal Processing (TSP) framework has been recently developed to analyze signals defined over simplicial complexes, i.e. topological spaces represented by finite sets of elements that are closed under inclusion of subsets [1]. However, the same inclusion property represents sometimes a too rigid assumption that prevents the application of simplicial complexes to many cases of interest. The goal of this paper is to extend TSP to the analysis of signals defined over cell complexes, which represent a generalization of simplicial complexes, as they are not restricted to satisfy the inclusion property. In particular, the richer topological structure of cell complexes enables them to reveal cycles of any order, as representative of data features. We propose an efficient method to infer the topology of cell complexes from data by showing how their use enables sparser edge signal representations than simplicial-based methods. Furthermore, we show how to design optimal finite impulse response (FIR) filters operating on solenoidal and irrotational signals in order to minimize the approximation error with respect to the desired spectral masks., Comment: Presented in the 2021 Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, 31 Oct.-3 Nov. 2021

The goal of this paper is to establish the fundamental tools to analyze signals defined over a topological space, i.e. a set of points along with a set of neighborhood relations. This setup does not require the definition of a metric and then it is especially useful to deal with signals defined over non-metric spaces. We focus on signals defined over simplicial complexes. Graph Signal Processing (GSP) represents a special case of Topological Signal Processing (TSP), referring to the situation where the signals are associated only with the vertices of a graph. Even though the theory can be applied to signals of any order, we focus on signals defined over the edges of a graph and show how building a simplicial complex of order two, i.e. including triangles, yields benefits in the analysis of edge signals. After reviewing the basic principles of algebraic topology, we derive a sampling theory for signals of any order and emphasize the interplay between signals of different order. Then we propose a method to infer the topology of a simplicial complex from data. We conclude with applications to real edge signals and to the analysis of discrete vector fields to illustrate the benefits of the proposed methodologies., Comment: To appear in IEEE Transactions on Signal Processing, March 2020

Graph-based representations play a key role in machine learning. The fundamental step in these representations is the association of a graph structure to a dataset. In this paper, we propose a method that aims at finding a block sparse representation of the graph signal leading to a modular graph whose Laplacian matrix admits the found dictionary as its eigenvectors. The role of sparsity here is to induce a band-limited representation or, equivalently, a modular structure of the graph. The proposed strategy is composed of two optimization steps: i) learning an orthonormal sparsifying transform from the data; ii) recovering the Laplacian, and then topology, from the transform. The first step is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix from the sparsifying transform through a convex optimization method. Numerical results corroborate the effectiveness of the proposed methods over both synthetic data and real brain data, used for inferring the brain functionality network through experiments conducted over patients affected by epilepsy., Comment: Submitted to IEEE Transactions on Signal Processing, March 2018

The evolution of communication networks shows a clear shift of focus from just improving the communications aspects to enabling new important services, from Industry 4.0 to automated driving, virtual/augmented reality, Internet of Things (IoT), and so on. This trend is evident in the roadmap planned for the deployment of the fifth generation (5G) communication networks. This ambitious goal requires a paradigm shift towards a vision that looks at communication, computation and caching (3C) resources as three components of a single holistic system. The further step is to bring these 3C resources closer to the mobile user, at the edge of the network, to enable very low latency and high reliability services. The scope of this chapter is to show that signal processing techniques can play a key role in this new vision. In particular, we motivate the joint optimization of 3C resources. Then we show how graph-based representations can play a key role in building effective learning methods and devising innovative resource allocation techniques., Comment: to appear in the book "Cooperative and Graph Signal Pocessing: Principles and Applications", P. Djuric and C. Richard Eds., Academic Press, Elsevier, 2018

The aim of this paper is to propose a least mean squares (LMS) strategy for adaptive estimation of signals defined over graphs. Assuming the graph signal to be band-limited, over a known bandwidth, the method enables reconstruction, with guaranteed performance in terms of mean-square error, and tracking from a limited number of observations over a subset of vertices. A detailed mean square analysis provides the performance of the proposed method, and leads to several insights for designing useful sampling strategies for graph signals. Numerical results validate our theoretical findings, and illustrate the performance of the proposed method. Furthermore, to cope with the case where the bandwidth is not known beforehand, we propose a method that performs a sparse online estimation of the signal support in the (graph) frequency domain, which enables online adaptation of the graph sampling strategy. Finally, we apply the proposed method to build the power spatial density cartography of a given operational region in a cognitive network environment., Comment: Submitted to IEEE Transactions on Signal and Information Processing over Networks

The analysis of signals defined over a graph is relevant in many applications, such as social and economic networks, big data or biological networks, and so on. A key tool for analyzing these signals is the so called Graph Fourier Transform (GFT). Alternative definitions of GFT have been suggested in the literature, based on the eigen-decomposition of either the graph Laplacian or adjacency matrix. In this paper, we address the general case of directed graphs and we propose an alternative approach that builds the graph Fourier basis as the set of orthonormal vectors that minimize a continuous extension of the graph cut size, known as the Lov\'{a}sz extension. To cope with the non-convexity of the problem, we propose two alternative iterative optimization methods, properly devised for handling orthogonality constraints. Finally, we extend the method to minimize a continuous relaxation of the balanced cut size. The formulated problem is again non-convex and we propose an efficient solution method based on an explicit-implicit gradient algorithm., Comment: To appear in IEEE Journal of Selected Topics in Signal Processing, 2017

In Part I of this paper, we proposed and analyzed a novel algorithmic framework for the minimization of a nonconvex (smooth) objective function, subject to nonconvex constraints, based on inner convex approximations. This Part II is devoted to the application of the framework to some resource allocation problems in communication networks. In particular, we consider two non-trivial case-study applications, namely: (generalizations of) i) the rate profile maximization in MIMO interference broadcast networks; and the ii) the max-min fair multicast multigroup beamforming problem in a multi-cell environment. We develop a new class of algorithms enjoying the following distinctive features: i) they are \emph{distributed} across the base stations (with limited signaling) and lead to subproblems whose solutions are computable in closed form; and ii) differently from current relaxation-based schemes (e.g., semidefinite relaxation), they are proved to always converge to d-stationary solutions of the aforementioned class of nonconvex problems. Numerical results show that the proposed (distributed) schemes achieve larger worst-case rates (resp. signal-to-noise interference ratios) than state-of-the-art centralized ones while having comparable computational complexity., Comment: Part I of this paper can be found at http://arxiv.org/abs/1410.4754

Migrating computational intensive tasks from mobile devices to more resourceful cloud servers is a promising technique to increase the computational capacity of mobile devices while saving their battery energy. In this paper, we consider a MIMO multicell system where multiple mobile users (MUs) ask for computation offloading to a common cloud server. We formulate the offloading problem as the joint optimization of the radio resources-the transmit precoding matrices of the MUs-and the computational resources-the CPU cycles/second assigned by the cloud to each MU-in order to minimize the overall users' energy consumption, while meeting latency constraints. The resulting optimization problem is nonconvex (in the objective function and constraints). Nevertheless, in the single-user case, we are able to express the global optimal solution in closed form. In the more challenging multiuser scenario, we propose an iterative algorithm, based on a novel successive convex approximation technique, converging to a local optimal solution of the original nonconvex problem. Then, we reformulate the algorithm in a distributed and parallel implementation across the radio access points, requiring only a limited coordination/signaling with the cloud. Numerical results show that the proposed schemes outperform disjoint optimization algorithms., Comment: Paper submitted to IEEE Trans. on Signal and Information Processing over Networks

The aim of this paper is to propose a computation offloading strategy for mobile edge computing. We exploit the concept of call graph, which models a generic computer program as a set of procedures related to each other through a weighted directed graph. Our goal is to derive the optimal partition of the call graph establishing which procedures are to be executed locally or remotely. The main novelty of our work is that the optimal partition is obtained jointly with the selection of radio parameters, e.g., transmit power and constellation size, in order to minimize the energy consumption at the mobile handset, under a latency constraint taking into account transmit time and execution time. We consider both single and multi-channel transmission strategies and we prove that a globally optimal solution can be achieved in both cases. Finally, we propose a suboptimal strategy aimed at solving a relaxed version of the original problem in order to tradeoff complexity and performance of the proposed framework. Finally, several numerical results illustrate under what conditions in terms of call graph topology, communication strategy, and computation parameters, the proposed offloading strategy provides large performance gains., Comment: Submitted to IEEE Transactions on Signal Processing

In this article we consider the problems of distributed detection and estimation in wireless sensor networks. In the first part, we provide a general framework aimed to show how an efficient design of a sensor network requires a joint organization of in-network processing and communication. Then, we recall the basic features of consensus algorithm, which is a basic tool to reach globally optimal decisions through a distributed approach. The main part of the paper starts addressing the distributed estimation problem. We show first an entirely decentralized approach, where observations and estimations are performed without the intervention of a fusion center. Then, we consider the case where the estimation is performed at a fusion center, showing how to allocate quantization bits and transmit powers in the links between the nodes and the fusion center, in order to accommodate the requirement on the maximum estimation variance, under a constraint on the global transmit power. We extend the approach to the detection problem. Also in this case, we consider the distributed approach, where every node can achieve a globally optimal decision, and the case where the decision is taken at a central node. In the latter case, we show how to allocate coding bits and transmit power in order to maximize the detection probability, under constraints on the false alarm rate and the global transmit power. Then, we generalize consensus algorithms illustrating a distributed procedure that converges to the projection of the observation vector onto a signal subspace. We then address the issue of energy consumption in sensor networks, thus showing how to optimize the network topology in order to minimize the energy necessary to achieve a global consensus. Finally, we address the problem of matching the topology of the network to the graph describing the statistical dependencies among the observed variables., Comment: 92 pages, 24 figures. To appear in E-Reference Signal Processing, R. Chellapa and S. Theodoridis, Eds., Elsevier, 2013