The steady state of a water distribution system abides by the laws of mass and energy conservation. Hydraulic solvers, such as the one used by EPANET approach the simulation for a given topology with a Newton-Raphson algorithm. However, iterative approximation involves a matrix inversion which acts as a computational bottleneck and may significantly slow down the process. In this work, we propose to rethink the current approach for steady state estimation to leverage the recent advancements in Graphics Processing Unit (GPU) hardware. Modern GPUs enhance matrix multiplication and enable memory-efficient sparse matrix operations, allowing for massive parallelization. Such features are particularly beneficial for state estimation in infrastructure networks, which are characterized by sparse connectivity between system elements. To realize this approach and tap into the potential of GPU-enhanced parallelization, we reformulate the problem as a diffusion process on the edges of a graph. Edge-based diffusion is inherently related to conservation laws governing a water distribution system. Using a numerical approximation scheme, the diffusion leads to a state of the system that satisfies mass and energy conservation principles. Using existing benchmark water distribution systems, we show that the proposed method allows parallelizing thousands of hydraulic simulations simultaneously with very high accuracy.

@en

This paper presents the computational challenge on topological deep learning that was hosted within the ICML 2023 Workshop on Topology and Geometry in Machine Learning. The competition asked participants to provide open-source implementations of topological neural networks from the literature by contributing to the python packages TopoNetX (data processing) and TopoModelX (deep learning). The challenge attracted twenty-eight qualifying submissions in its two month duration. This paper describes the design of the challenge and summarizes its main findings.

@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

Graphs can model networked data by representing them as nodes and their pairwise relationships as edges. Recently, signal processing and neural networks have been extended to process and learn from data on graphs, with achievements in tasks like graph signal reconstruction, graph or node classifications, and link prediction. However, these methods are only suitable for data defined on the nodes of a graph. In this paper, we propose a simplicial convolutional neural network (SCNN) architecture to learn from data defined on simplices, e.g., nodes, edges, triangles, etc. We study the SCNN permutation and orientation equivariance, complexity, and spectral analysis. Finally, we test the SCNN performance for imputing citations on a coauthorship complex.@en

Reconstructing simplicial signals, e.g., signals defined on nodes, edges, triangles, etc., of a network, from (partial) noisy observation is of interest in water/traffic flow estimation or currency exchange markets. Typically, this concerns solving a regularised problem w.r.t. the l2 norm of the divergence or the curl of the signal, i.e., the netflows at nodes and in triangles. Realworld simplicial signals are intrinsically divergence- or curl-free, which makes l2 regularizers inapplicable. To overcome this, we develop a simplicial trend filter (STF) by regularising the total divergence and the curl via their l1 norm. By tuning two scalars, the STF can reduce independently the divergence and curl much more than smooth filtering, leading to a better reconstructed signal. The SFT is a convex problem and can be solved by fast iterative algorithms. We apply the SFT to interpolation and denoising tasks in forex and music/artist transition recordings and show its superior performance to alternatives.

@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

We study linear filters for processing signals supported on abstract topological spaces modeled as simplicial complexes, which may be interpreted as generalizations of graphs that account for nodes, edges, triangular faces, etc. To process such signals, we develop simplicial convolutional filters defined as matrix polynomials of the lower and upper Hodge Laplacians. First, we study the properties of these filters and show that they are linear and shift-invariant, as well as permutation and orientation equivariant. These filters can also be implemented in a distributed fashion with a low computational complexity, as they involve only (multiple rounds of) simplicial shifting between upper and lower adjacent simplices. Second, focusing on edge-flows, we study the frequency responses of these filters and examine how we can use the Hodge-decomposition to delineate gradient, curl and harmonic frequencies. We discuss how these frequencies correspond to the lower- and the upper-adjacent couplings and the kernel of the Hodge Laplacian, respectively, and can be tuned independently by our filter designs. Third, we study different procedures for designing simplicial convolutional filters and discuss their relative advantages. Finally, we corroborate our simplicial filters in several applications: to extract different frequency components of a simplicial signal, to denoise edge flows, and to analyze financial markets and traffic networks.@en

To deal with high-dimensional data, graph filters have shown their power in both graph signal processing and data science. However, graph filters process signals exploiting only pairwise interactions between the nodes, and they are not able to exploit more complicated topological structures. Graph Volterra models, on the other hand, are also able to exploit relations between triplets, quadruplets and so on. However, they have only been exploited for topology identification and are only based on one-hop relations. In this paper, we first review graph filters and graph Volterra models and then merge the two concepts resulting in so-called topological Volterra filters (TVFs). TVFs process signals over multiple hops of higher-level topological structures. First-level TVFs are basically similar to traditional graph filters, yet higher-level TVFs provide a more general processing framework. We apply TVFs to inverse filtering and recommender systems.@en

A critical task in graph signal processing is to estimate the true signal from noisy observations over a subset of nodes, also known as the reconstruction problem. In this paper, we propose a node-adaptive regularization for graph signal reconstruction, which surmounts the conventional Tikhonov regularization, giving rise to more degrees of freedom; hence, an improved performance. We formulate the node-adaptive graph signal denoising problem, study its bias-variance trade-off, and identify conditions under which a lower mean squared error and variance can be obtained with respect to Tikhonov regularization. Compared with existing approaches, the node-adaptive regularization enjoys more general priors on the local signal variation, which can be obtained by optimally designing the regularization weights based on Prony's method or semidefinite programming. As these approaches require additional prior knowledge, we also propose a minimax (worst-case) strategy to address instances where this extra information is unavailable. Numerical experiments with synthetic and real data corroborate the proposed regularization strategy for graph signal denoising and interpolation, and show its improved performance compared with competing alternatives.@en

In this paper, we study linear filters to process signals defined on simplicial complexes, i.e., signals defined on nodes, edges, triangles, etc. of a simplicial complex, thereby generalizing filtering operations for graph signals. We propose a finite impulse response filter based on the Hodge Laplacian, and demonstrate how this filter can be designed to amplify or attenuate certain spectral components of simplicial signals. Specifically, we discuss how, unlike in the case of node signals, the Fourier transform in the context of edge signals can be understood in terms of two orthogonal subspaces corresponding to the gradient-flow signals and curl-flow signals arising from the Hodge decomposition. By assigning different filter coefficients to the associated terms of the Hodge Laplacian, we develop a subspace-varying filter which enables more nuanced control over these signal types. Numerical experiments are conducted to show the potential of simplicial filters for sub-component extraction, denoising and model approximation.@en

While regularization on graphs has been successful for signal reconstruction, strategies for controlling the bias-variance trade-off of such methods have not been completely explored. In this work, we put forth a node varying regularizer for graph signal reconstruction and develop a minmax approach to design the vector of regularization parameters. The proposed design only requires as prior information an upper bound on the underlying signal energy; a reasonable assumption in practice. With such formulation, an iterative method is introduced to obtain a solution meeting global equilibrium. The approach is numerically efficient and has convergence guarantees. Numerical simulations using real data support the proposed design scheme. @en