In urban centers, cycling is increasingly popular as an eco-friendly transportation mode and a short-distance transport option, driving higher demand for accurate bicycle travel time estimation. Policymakers need to understand bicycle traffic for urban traffic management and sustainable transport promotion, while cyclists benefit from better route planning and improved network efficiency. However, urban bicycle travel time estimation has not received as much attention as car traffic estimation and presents several challenges: 1) Limited availability of structural cycling data, which can be inaccessible due to privacy concerns and/or severely biased by user demographics. 2) The diverse and complex behaviors of cyclists. 3) The lack of strict road constraints for cyclists and frequent rule violations, complicating the model definition of a comprehensive cycling infrastructure network. This paper presents the first study on urban bicycle travel time estimation using GPS tracking data. Leveraging graph-based deep learning's ability to learn from topological network information, we introduce the Dual Graph-based approach for bicycles (DG4b), which employs two parallel encode-process-decode pipelines: one for a shared undirected road network graph to capture intrinsic road characteristics, and another for a directed trip-specific graph reflecting unique trip features. The outputs are combined to estimate road segment speeds and overall trip travel time. When applied to a real-world dataset from Berlin, our method shows superior accuracy and reliability compared to baseline models, while maintaining low complexity. Our approach provides a novel perspective on integrating bicycling-specific characteristics and aims to inspire more future research in bicycle-related traffic estimation.

Neural networks on simplicial complexes (SCs) can learn representations from data residing on simplices such as nodes, edges, triangles, etc. However, existing works often overlook the Hodge theorem that decomposes simplicial data into three orthogonal characteristic subspaces, such as the identifiable gradient, curl and harmonic components of edge flows. This provides a universal tool to understand the machine learning models on SCs, thus, allowing for better principled and effective learning. In this paper, we study the effect of this data inductive bias on learning on SCs via the principle of convolutions. Particularly, we present a general convolutional architecture that respects the three key principles of uncoupling the lower and upper simplicial adjacencies, accounting for the inter-simplicial couplings, and performing higher-order convolutions. To understand these principles, we first use Dirichlet energy minimizations on SCs to interpret their effects on mitigating simplicial oversmoothing. Then, we show the three principles promote the Hodge-aware learning of this architecture, through the lens of spectral simplicial theory, in the sense that the three Hodge subspaces are invariant under its learnable functions and the learning in two nontrivial subspaces is independent and expressive. Third, we investigate the learning ability of this architecture in optic of perturbation theory on simplicial topologies and prove that the convolutional architecture is stable to small perturbations. Finally, we corroborate the three principles by comparing with methods that either violate or do not respect them. Overall, this paper bridges learning on SCs with the Hodge theorem, highlighting its importance for rational and effective learning from simplicial data, and provides theoretical insights to convolutional learning on SCs.

Topological Deep Learning (TDL) has emerged as a paradigm to process and learn from signals defined on higher-order combinatorial topological spaces, such as simplicial or cell complexes. Although many complex systems have an asymmetric relational structure, most TDL models forcibly symmetrize these relationships. In this paper, we first introduce a novel notion of higher-order directionality and we then design Directed Simplicial Neural Networks (Dir-SNNs) based on it. Dir-SNNs are message-passing networks operating on directed simplicial complexes able to leverage directed and possibly asymmetric interactions among the simplices. To our knowledge, this is the first TDL model using a notion of higher-order directionality. We theoretically and empirically prove that Dir-SNNs are more expressive than their directed graph counterpart in distinguishing non-isomorphic directed graphs. Experiments on a synthetic source localization task demonstrate that Dir-SNNs outperform undirected SNNs when the underlying complex is directed, and perform comparably when the underlying complex is undirected.

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.

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.

Simplicial complexes prove effective in modeling data with multiway dependencies, such as data defined along the edges of networks or within other higher-order structures. Their spectrum can be decomposed into three interpretable subspaces via the Hodge decomposition, resulting foundational in numerous applications. We leverage this decomposition to develop a contrastive self-supervised learning approach for processing simplicial data and generating embeddings that encapsulate specific spectral information. Specifically, we encode the pertinent data invariances through simplicial neural networks and devise augmentations that yield positive contrastive examples with suitable spectral properties for downstream tasks. Additionally, we reweight the significance of negative examples in the contrastive loss, considering the similarity of their Hodge components to the anchor. By encouraging a stronger separation among less similar instances, we obtain an embedding space that reflects the spectral properties of the data. The numerical results on two standard edge flow classification tasks show a superior performance even when compared to supervised learning techniques. Our findings underscore the importance of adopting a spectral perspective for contrastive learning with higher-order data.

In this paper, we propose a topology-aware Kalman filter for hidden dynamics over simplicial complex. Specifically, we consider that the hidden dynamics of a system can be expressed as a simplicial process that respects the structure of the underlying network. And these dynamics are observed through an observation matrix, which can be represented using simplicial convolution filters. This combination allows us to model effectively a broader spectrum of network dynamics than graph-based alternatives, such as edge flow evolution. Additionally, we propose a parametric, structure-aware noise covariance model for the system dynamics. We alternate between estimating the process state using the Kalman filter and updating the parameters through maximum likelihood estimation. The efficacy of the proposed approach is demonstrated through experiments on both real-world and synthetic datasets.

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.

We propose principled Gaussian processes (GPs) for modeling functions defined over the edge set of a simplicial 2-complex, a structure similar to a graph in which edges may form triangular faces. This approach is intended for learning flow-type data on networks where edge flows can be characterized by the discrete divergence and curl. Drawing upon the Hodge decomposition, we first develop classes of divergence-free and curl-free edge GPs, suitable for various applications. We then combine them to create Hodge-compositional edge GPs that are expressive enough to represent any edge function. These GPs facilitate direct and independent learning for the different Hodge components of edge functions, enabling us to capture their relevance during hyperparameter optimization. To highlight their practical potential, we apply them for flow data inference in currency exchange, ocean currents and water supply networks, comparing them to alternative models.

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.

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.

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.

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.

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.

Inference of time varying data over graphs is of importance in real-world applications such as urban water networks, economics, and brain recordings. It typically relies on identifying a computationally affordable joint spatiotemporal method that can leverage the patterns in the data. While this per se is a challenging task, it becomes even more so when the network comes with uncertainties, which, if not accounted for, can lead to unpredictable consequences. To target this setting, we model graph uncertainties as Gaussian noise on the edges and design a stochastic partial differential equation (SPDE) based on it. We use this SPDE as a state equation to model the time varying signal evolution and extend it further to a state-space model where the observations are graph-filtered versions of the state. This allows us to have a joint spatiotemporal expressive kernel that can be estimated online via Kalman filtering and which parameters can also be estimated online via maximum likelihood principles, ultimately, reducing the computational cost. We corroborate the proposed approach on numerical experiments, showing a superior performance to approaches ignoring either the uncertainty or considering a separable spatiotemporal kernel.

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.

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.

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.

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.