This paper proposes a novel algorithm to retroactively compute the evolution of edge signals from a given sequence of partial observations from topological structures, a concept referred to as evolution backcasting. Our backcasting algorithm exploits the spatio-temporal dependencies present in the real-world edge signals using the simplicial vector autoregressive (S-VAR) model. The proposed algorithm jointly estimates the S-VAR filter coefficients and recovers missing data from the partial observations. Subsequently, the algorithm capitalizes on the learned S-VAR model and the reconstructed signals to execute the backcasting of edge signal evolution. Using traffic and water distribution networks as case studies, we showcase the superior capabilities of our algorithm compared with baseline alternatives.

@en

Filters are fundamental in extracting information from data. For time series and image data that reside on Euclidean domains, filters are the crux of many signal processing and machine learning techniques, including convolutional neural networks. Increasingly, modern data also reside on networks and other irregular domains whose structure is better captured by a graph. To process and learn from such data, graph filters account for the structure of the underlying data domain. In this article, we provide a comprehensive overview of graph filters, including the different filtering categories, design strategies for each type, and trade-offs between different types of graph filters. We discuss how to extend graph filters into filter banks and graph neural networks to enhance the representational power; that is, to model a broader variety of signal classes, data patterns, and relationships. We also showcase the fundamental role of graph filters in signal processing and machine learning applications. Our aim is that this article provides a unifying framework for both beginner and experienced researchers, as well as a common understanding that promotes collaborations at the intersections of signal processing, machine learning, and application domains.

@en

Graph filters are a staple tool for processing signals over graphs in a multitude of downstream tasks. However, they are commonly designed for graphs with a fixed number of nodes, despite real-world networks typically grow over time. This topological evolution is often known up to a stochastic model, thus, making conventional graph filters ill-equipped to withstand such topological changes, their uncertainty, as well as the dynamic nature of the incoming data. To tackle these issues, we propose an online graph filtering framework by relying on online learning principles. We design filters for scenarios where the topology is both known and unknown, including a learner adaptive to such evolution. We conduct a regret analysis to highlight the role played by the different components such as the online algorithm, the filter order, and the growing graph model. Numerical experiments with synthetic and real data corroborate the proposed approach for graph signal inference tasks and show a competitive performance w.r.t. baselines and state-of-the-art alternatives.

@en

Temporal networks arise due to certain dynamics influencing their connections or due to the change in interactions between the nodes themselves, as seen for example in social networks. Such evolution can be algebraically represented by a three-way tensor, which lends itself to using tensor decompositions to study the underpinning factors driving the network evolution. Low rank tensor decompositions have been used for temporal networks but mostly with a focus on downstream tasks and have been seldom used to study the temporal network itself. Here, we use the tensor decomposition to identify a limited number of key mode graphs that can explain the temporal network, and which linear combination can represent its evolution. For this, we put for a novel graph-based tensor decomposition approach where we impose a graph structure on the two modes of the tensor and a smoothness on the temporal dimension. We use these mode graphs to investigate the temporal network and corroborate their usability for network reconstruction and link prediction.@en

An online topology estimation algorithm for nonlinear structural equation models (SEM) is proposed in this paper, addressing the nonlinearity and the non-stationarity of real-world systems. The nonlinearity is modeled using kernel formulations, and the curse of dimensionality associated with the kernels is mitigated using random feature approximation. The online learning strategy uses a group-lasso-based optimization framework with a prediction-corrections technique that accounts for the model evolution. The proposed approach has three properties of interest. First, it enjoys node-separable learning, which allows for scalability in large networks. Second, it offers privacy in SEM learning by replacing the actual data with node-specific random features. Third, its performance can be characterized theoretically via a dynamic regret analysis, showing that it is possible to obtain a linear dynamic regret bound under mild assumptions. Numerical results with synthetic and real data corroborate our findings and show competitive performance w.r.t. state-of-the-art alternatives.@en

Current spatiotemporal learning methods for complex data exploit the graph structure as an inductive bias to restrict the function space and improve data and computation efficiency. However, these methods work principally on graphs with a fixed size, whereas in several applications there are expanding graphs where new nodes join the network; e.g., new sensors joining a sensor network or new users joining a recommender system. This paper focuses on the non-trivial extension of spatiotemporal methods to this setting, where now it is key to jointly capture both the topological and signal dynamics. Specifically, it considers a graph vector autoregressive (GVAR) model for multivariate time series. The GVAR is a multivariate linear model that leverages a bank of graph filters allowing scalability and data efficiency. To account for the dynamic nature of the graphs, the filters’s parameters are learned on-the-fly via adaptive gradient descent with provable sub-linear regret. Numerical results on both synthetic and real data corroborate the proposed method.@en

Devising and analysing learning models for spatiotemporal network data is of importance for tasks including forecasting, anomaly detection, and multi-agent coordination, among others. Graph Convolutional Neural Networks (GCNNs) are an established approach to learn from time-invariant network data. The graph convolution operation offers a principled approach to aggregate information and offers mathematical analysis by exploring tools from graph signal processing. This analysis provides insights into the equivariance properties of GCNNs; spectral behaviour of the learned filters; and the stability to graph perturbations, which arise from support perturbations or uncertainties. However, extending the convolutional learning and respective analysis to the spatiotemporal domain is challenging because spatiotemporal data have more intrinsic dependencies. Hence, a higher flexibility to capture jointly the spatial and temporal dependencies is required to learn meaningful higher-order representations. Here, we leverage product graphs to represent the spatiotemporal dependencies in the data and introduce Graph-Time Convolutional Neural Networks (GTCNNs) as a principled architecture. We also introduce a parametric product graph to learn the spatiotemporal coupling. The convolution principle further allows a similar mathematical tractability as for GCNNs. In particular, the stability result shows GTCNNs are stable to spatial perturbations. owever, there is an implicit trade-off between discriminability and robustness; i.e., the more complex the model, the less stable. Extensive numerical results on benchmark datasets corroborate our findings and show the GTCNN compares favorably with state-of-the-art solutions. We anticipate the GTCNN to be a starting point for more sophisticated models that achieve good performance but are also fundamentally grounded.

@en

Implementing accurate Distribution System State Estimation (DSSE) faces several challenges, among which the lack of observability and the high density of the distribution system. While data-driven alternatives based on Machine Learning models could be a choice, they suffer in DSSE because of the lack of labeled data. In fact, measurements in the distribution system are often noisy, corrupted, and unavailable. To address these issues, we propose the Deep Statistical Solver for Distribution System State Estimation (DSS^2), a deep learning model based on graph neural networks (GNNs) that accounts for the network structure of the distribution system and the governing power flow equations of the problem. DSS^2 is based on GNN and leverages hypergraphs to model the network as a graph into the deep-learning algorithm and to represent the heterogeneous components of the distribution systems. A weakly supervised learning approach is put forth to train the DSS^2: by enforcing the GNN output into the power flow equations, we force the DSS^2 to respect the physics of the distribution system. This strategy enables learning from noisy measurements and alleviates the need for ideal labeled data. Extensive experiments with case studies on the IEEE 14-bus, 70-bus, and 179-bus networks showed the DSS^2 outperforms the conventional Weighted Least Squares algorithm in accuracy, convergence, and computational time while being more robust to noisy, erroneous, and missing measurements. The DSS^2 achieves a competing, yet lower, performance compared with the supervised models that rely on the unrealistic assumption of having all the true labels.

@en

Stochastic graph neural networks (SGNNs) are information processing architectures that learn representations from data over random graphs. SGNNs are trained with respect to the expected performance, which comes with no guarantee about deviations of particular output realizations around the optimal expectation. To overcome this issue, we propose a variance-constrained optimization problem for SGNNs, balancing the expected performance and the stochastic deviation. An alternating primal-dual learning procedure is undertaken that solves the problem by updating the SGNN parameters with gradient descent and the dual variable with gradient ascent. To characterize the explicit effect of the variance-constrained learning, we analyze theoretically the variance of the SGNN output and identify a trade-off between the stochastic robustness and the discrimination power. We further analyze the duality gap of the variance-constrained optimization problem and the converging behavior of the primal-dual learning procedure. The former indicates the optimality loss induced by the dual transformation and the latter characterizes the limiting error of the iterative algorithm, both of which guarantee the performance of the variance-constrained learning. Through numerical simulations, we corroborate our theoretical findings and observe a strong expected performance with a controllable variance.@en

Simplicial convolutional filters can process signals defined over levels of a simplicial complex such as nodes, edges, triangles, and so on with applications in e.g., flow prediction in transportation or financial networks. However, the underlying topology expands over time in a way that new edges and triangles form. For example, in a transportation network, a new connection between two locations is newly built, or in a currency exchange market, two currencies can be exchanged without an intermediate currency that can be understood as a new edge between them. To handle the streaming nature of data, we propose an online prediction for edge flows which generalizes to other higher-order simplicial signals. This is achieved by updating the filter coefficients via an online gradient descent with a provable sub-linear regret relative to the simplicial filter optimized over the whole sequence of edge flows. The update of the filter coefficients associated with the lower and upper Hodge Laplacians can be uncoupled in general. We test the online edge flow prediction on an expanding synthetic simplicial complex and a coauthorship complex showing a close performance to the offline counterpart.@en

Metamodels accurately reproduce the output of physics-based hydraulic models with a significant reduction in simulation times. They are widely employed in water distribution system (WDS) analysis since they enable computationally expensive applications in the design, control, and optimisation of water networks. Recent machine-learning-based metamodels grant improved fidelity and speed; however, they are only applicable to the water network they were trained on. To address this issue, we investigate graph neural networks (GNNs) as metamodels for WDSs. GNNs leverage the networked structure of WDS by learning shared coefficients and thus offering the potential of transferability. This work evaluates the suitability of GNNs as metamodels for estimating nodal pressures in steady-state EPANET simulations. We first compare the effectiveness of GNN metamodels against multi-layer perceptrons (MLPs) on several benchmark WDSs. Then, we explore the transferability of GNNs by training them concurrently on multiple WDSs. For each configuration, we calculate model accuracy and speedups with respect to the original numerical model. GNNs perform similarly to MLPs in terms of accuracy and take longer to execute but may still provide substantial speedup. Our preliminary results indicate that GNNs can learn shared representations across networks, although assessing the feasibility of truly general metamodels requires further work.

@en

Vector autoregressive (VAR) model is widely used to model time-varying processes, but it suffers from prohibitive growth of the parameters when the number of time series exceeds a few hundreds. We propose a simplicial VAR model to mitigate the curse of dimensionality of the VAR models when the time series are defined over higher-order network structures such as edges, triangles, etc. The proposed model shares parameters across the simplicial signals by leveraging the simplicial convolutional filter and captures structure-aware spatio-temporal dependencies of the time-varying processes. Targetting the streaming signals from the real-world nonstationary networks, we develop a group-lasso-based online strategy to learn the proposed model. Using traffic and water distribution networks, we demonstrate that the proposed model achieves competitive signal prediction accuracy with a significantly less number of parameters than the VAR models.@en

Reconstructing missing values and removing noise from network-based multivariate time series requires developing graph-time regularizers capable of capturing their spatiotemporal behavior. However, current approaches based on joint spatiotemporal smoothness, diffusion, or variations thereof may not be effective for time series with discontinuities across the graph or time. To address this challenge, we propose a joint graph-time trend filter operating over a product graph representing spatiotemporal relations. Additionally, we develop a graph-time unrolled neural network to learn the prior from the data, which is based on the alternating direction method of multipliers iterations of the graph-time trend filter and on graph-time convolutional filters. Numerical tests with two synthetic and four real datasets corroborate the effectiveness of both approaches, highlight their inherent trade-offs, and show they compare well with state-of-the-art alternatives.@en

Numerical modelling is a reliable tool for flood simulations, but accurate solutions are computationally expensive. In recent years, researchers have explored data-driven methodologies based on neural networks to overcome this limitation. However, most models are only used for a specific case study and disregard the dynamic evolution of the flood wave. This limits their generalizability to topographies that the model was not trained on and in time-dependent applications. In this paper, we introduce shallow water equation–graph neural network (SWE–GNN), a hydraulics-inspired surrogate model based on GNNs that can be used for rapid spatio-temporal flood modelling. The model exploits the analogy between finite-volume methods used to solve SWEs and GNNs. For a computational mesh, we create a graph by considering finite-volume cells as nodes and adjacent cells as being connected by edges. The inputs are determined by the topographical properties of the domain and the initial hydraulic conditions. The GNN then determines how fluxes are exchanged between cells via a learned local function. We overcome the time-step constraints by stacking multiple GNN layers, which expand the considered space instead of increasing the time resolution. We also propose a multi-step-ahead loss function along with a curriculum learning strategy to improve the stability and performance. We validate this approach using a dataset of two-dimensional dike breach flood simulations in randomly generated digital elevation models generated with a high-fidelity numerical solver. The SWE–GNN model predicts the spatio-temporal evolution of the flood for unseen topographies with mean average errors in time of 0.04 m for water depths and 0.004 m2 s−1 for unit discharges. Moreover, it generalizes well to unseen breach locations, bigger domains, and longer periods of time compared to those of the training set, outperforming other deep-learning models. On top of this, SWE–GNN has a computational speed-up of up to 2 orders of magnitude faster than the numerical solver. Our framework opens the doors to a new approach to replace numerical solvers in time-sensitive applications with spatially dependent uncertainties.@en

The edge flow reconstruction task consists of retreiving edge flow signals from corrupted or incomplete measurements. This is typically solved by a regularized optimization problem on higher-order networks such as simplicial complexes and the corresponding regularizers are chosen based on prior knowledge. Tailoring this prior to the setting of interest can be challenging or it may not even be possible. Thus, we consider to learn this prior knowledge via a model-based deep learning approach. We propose a new regularized optimization problem for the simplicial edge flow reconstruction task, the simplicial ElasticNet, which combines the advantages of the 1 and 2 norms. We solve the simplicial ElasticNet problem via the multi-block alternating direction method of multipliers (ADMM) algorithm and provide conditions on its convergence. By unrolling the ADMM iterative steps, we develop a model-based neural network with a low requirement on the number of training data. This unrolling network replaces the fixed parameters in the iterative algorithm by learnable weights, thus exploiting the neural network s learning capability while preserving the iterative algorithm s interpretability. We enhance this unrolling network via simplicial convolutional filters to aggregate information from the edge flow neighbors, ultimately, improving the network learning expressivity. Extensive experiments on real-world and synthetic datasets validate the proposed approaches and show considerable improvements over both baselines and traditional non-model-based neural networks.

@en

Distributed graph filters have recently found applications in wireless sensor networks (WSNs) to solve distributed tasks such as reaching consensus, signal denoising, and reconstruction. However, when implemented over WSNs, the graph filters should deal with network limited energy constraints as well as processing and communication capabilities. Quantization plays a fundamental role to improve the latter but its effects on distributed graph filtering are little understood. WSNs are also prone to random link losses due to noise and interference. In this instance, the filter output is affected by both the quantization error and the topological randomness error, which, if it is not properly accounted in the filter design phase, may lead to an accumulated error through the filtering iterations and significantly degrade the performance. In this paper, we analyze how quantization affects distributed graph filtering over both time-invariant and time-varying graphs. We bring insights on the quantization effects for the two most common graph filters: the finite impulse response (FIR) and autoregressive moving average (ARMA) graph filter. Besides providing a comprehensive analysis, we devise theoretical performance guarantees on the filter performance when the quantization stepsize is fixed or changes dynamically over the filtering iterations. For FIR filters, we show that a dynamic quantization stepsize leads to more reduction of the quantization noise than in the fixed-stepsize quantization. For ARMA graph filters, we show that decreasing the quantization stepsize over the iterations reduces the quantization noise to zero at the steady-state. In addition, we propose robust filter design strategies that minimize the quantization noise for both time-invariant and time-varying networks. Numerical experiments on synthetic and two real data sets corroborate our findings and show the different trade-offs between quantization bits, filter order, and robustness to topological randomness.

@en

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.

@en

Driven by the outstanding performance of neural networks in the structured euclidean domain, recent years have seen a surge of interest in developing neural networks for graphs and data supported on graphs. The graph is leveraged at each layer of the neural network as a parameterization to capture detail at the node level with a reduced number of parameters and computational complexity. Following this rationale, this paper puts forth a general framework that unifies state-of-the-art graph neural networks (GNNs) through the concept of EdgeNet. An EdgeNet is a GNN architecture that allows different nodes to use different parameters to weigh the information of different neighbors. By extrapolating this strategy to more iterations between neighboring nodes, the EdgeNet learns edge- and neighbor-dependent weights to capture local detail. This is a general linear and local operation that a node can perform and encompasses under one formulation all existing graph convolutional neural networks (GCNNs) as well as graph attention networks (GATs). In writing different GNN architectures with a common language, EdgeNets highlight specific architecture advantages and limitations, while providing guidelines to improve their capacity without compromising their local implementation. For instance, we show that GCNNs have a parameter sharing structure that induces permutation equivariance. This can be an advantage or a limitation, depending on the application. In cases where it is a limitation, we propose hybrid approaches and provide insights to develop several other solutions that promote parameter sharing without enforcing permutation equivariance. Another interesting conclusion is the unification of GCNNs and GATs - approaches that have been so far perceived as separate. In particular, we show that GATs are GCNNs on a graph that is learned from the features. This particularization opens the doors to develop alternative attention mechanisms for improving discriminatory power.

@en

This paper proposes convolutional filtering for data whose structure can be modeled by a simplicial complex (SC). SCs are mathematical tools that not only capture pairwise relationships as graphs but account also for higher-order network structures. These filters are built by following the shift-and-sum principle of the convolution operation and rely on the Hodge-Laplacians to shift the signal within the simplex. But since in SCs we have also inter-simplex coupling, we use the incidence matrices to transfer the signal in adjacent simplices and build a filter bank to jointly filter signals from different levels. We prove some interesting properties for the proposed filter bank, including permutation and orientation equivariance, a computational complexity that is linear in the SC dimension, and a spectral interpretation using the simplicial Fourier transform. We illustrate the proposed approach with numerical experiments.@en