This paper addresses the problem of online network topology inference for expanding graphs from a stream of spatiotemporal signals. Online algorithms for dynamic graph learning are crucial in delay-sensitive applications or when changes in topology occur rapidly. While existing works focus on inferring the connectivity within a fixed set of nodes, in practice, the graph can grow as new nodes join the network. This poses additional challenges like modeling temporal dynamics involving signals and graphs of different sizes. This growth also increases the computational complexity of the learning process, which may become prohibitive. To the best of our knowledge, this is the first work to tackle this setting. We propose a general online algorithm based on projected proximal gradient descent that accounts for the increasing graph size at each iteration. Recursively updating the sample covariance matrix is a key aspect of our approach. We introduce a strategy that enables different types of updates for nodes that just joined the network and for previously existing nodes. To provide further insights into the proposed method, we specialize it in Gaussian Markov random field settings, where we analyze the computational complexity and characterize the dynamic cumulative regret. Finally, we demonstrate the effectiveness of the proposed approach using both controlled experiments and real-world datasets from epidemic and financial networks.

@en

Developing methods to process irregularly structured data is crucial in applications like gene-regulatory, brain, power, and socioeconomic networks. Graphs have been the go-to algebraic tool for modeling the structure via nodes and edges capturing their interactions, leading to the establishment of the fields of graph signal processing (GSP) and graph machine learning (GML). Key graph-aware methods include Fourier transform, filtering, sampling, as well as topology identification and spatiotemporal processing. Although versatile, graphs can model only pairwise dependencies in the data. To this end, topological structures such as simplicial and cell complexes have emerged as algebraic representations for more intricate structure modeling in data-driven systems, fueling the rapid development of novel topological-based processing and learning methods. This paper first presents the core principles of topological signal processing through the Hodge theory, a framework instrumental in propelling the field forward thanks to principled connections with GSP-GML. It then outlines advances in topological signal representation, filtering, and sampling, as well as inferring topological structures from data, processing spatiotemporal topological signals, and connections with topological machine learning. The impact of topological signal processing and learning is finally highlighted in applications dealing with flow data over networks, geometric processing, statistical ranking, biology, and semantic communication.

@en

Deep-learning-based surrogate models represent a powerful alternative to numerical models for speeding up flood mapping while preserving accuracy. In particular, solutions based on hydraulic-based graph neural networks (SWE-GNNs) enable transferability to domains not used for training and allow the inclusion of physical constraints. However, these models are limited due to four main aspects. First, they cannot model rapid differences in flow propagation speeds; secondly, they can face instabilities during training when using a large number of layers, needed for effective modelling; third, they cannot accommodate time-varying boundary conditions; and fourth, they require initial conditions from a numerical solver. To address these issues, we propose a multi-scale hydraulic-based graph neural network (mSWE-GNN) that models the flood at different resolutions and propagation speeds. We include time-varying boundary conditions via ghost cells, which enforce the solution at the domain’s boundary and drop the need for a numerical solver for the initial conditions. To improve generalization over unseen meshes and reduce the data demand, we use invariance principles and make the inputs independent from coordinates' rotations. Numerical results applied to dike-breach floods show that the model predicts the full spatio-temporal simulation of the flood over unseen irregular meshes, topographies, and time-varying boundary conditions, with mean absolute errors in time of 0.05 m for water depths and 0.003 m2 s−1 for unit discharges. We further corroborate the mSWE-GNN in a realistic case study in the Netherlands and show generalization capabilities with only one fine-tuning sample, with mean absolute errors of 0.12 m for water depth, a critical success index for a water depth threshold of 0.05 m of 87.68 %, and speed-ups of over 700 times. Overall, the approach opens up several avenues for probabilistic analyses of realistic configurations and flood scenarios.@en

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

This paper introduces a hypothesis testing problem to detect whether a noisy simplicial signal lives in some specific Hodge subspaces or not. This is of particular relevance for edge flows in a network since they exhibit, under normal circumstances, different properties in Hodge decomposition. For example, a traffic flow in a road network is often conservative and that can be localized in a particular Hodge subspace. We propose two Neyman-Pearson optimal detectors for this task: the Simplicial Hodge Detector (SHD) and the Constrained Simplicial Hodge Detector (CSHD). They compare the energy of the simplicial embeddings in different Hodge subspaces and distinguish between the two hypotheses. The SHD utilizes the maximum likelihood estimation, while CSHD incorporates signal prior information to estimate the simplicial embeddings. These detectors are validated through numerical simulations on both real-world and synthetic data, indicating great potential in practical applications.

@en

The vector autoregressive (VAR) model is extensively employed for modelling dynamic processes, yet its scalability is challenged by an overwhelming growth in parameters when dealing with several hundred time series. To overcome this issue, data relations can be leveraged as inductive priors to tackle the curse of dimensionality while still effectively modelling the time series. In this paper, we study the role of simplicial complexes as inductive biases when modelling time series defined on higher-order network structures such as edges and triangles. First, we propose two simplicial VAR models: one that models time series defined on a single simplicial level, such as edge flows, and another that jointly models multiple time series defined across different simplicial levels, ultimately capturing their spatiotemporal interdependencies. The proposed models use simplicial convolutional filters to facilitate parameter sharing and capture structure-aware spatio-temporal dependencies in a multiresolution manner. Second, we develop a joint simplicial-temporal Fourier transform to study the spectral characteristics of the models, depicting them as simplicial-temporal filters. Third, targeting streaming signals, we develop an online algorithm for learning simplicial VAR models. We prove this online learner attains a sublinear dynamic regret bound, ensuring convergence under reasonable assumptions. Finally, we corroborate the proposed approach through experiments on synthetic networks, water distribution networks, and collaborating agents. Our findings show that the proposed models attain competitive signal modelling accuracy with orders of magnitude fewer parameters than the 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

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

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

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

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

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

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

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

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

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

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

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