Joint online estimation of multi-order graph topological signals

Ercan Engin Kuruoglu, PhD Cantab, Prof, Ieee Fellow, Yi Yan, Tian Xie, Ercan E. Kuruoglu

Introduction

Standard Graph Signal Processing (GSP) has proven highly effective for analyzing data residing on the nodes of a graph, such as temperature readings across a sensor network. However, in many complex systems, the signals on the connections between nodes—the "edge signals"—are just as dynamic and critical as the node signals themselves. For instance, in a transportation network, traffic flow on a road (an edge) directly influences congestion levels at intersections (nodes).

Existing GSP methods often treat edge weights as static or ignore them entirely, struggling with three primary challenges: missing data from faulty sensors, non-stationary temporal dynamics, and the high computational cost of processing higher-order topological structures. This paper introduces AJVEE (Adaptive Joint Vertex-Edge Estimation), a framework designed to track time-varying signals on both nodes and edges simultaneously by leveraging the principles of Topological Signal Processing (TSP).

Mathematical Framework and Methodology

To move beyond simple node-centric analysis, the authors model the environment as a simplicial complex. This mathematical structure allows for a rigorous treatment of nodes (0-simplices), edges (1-simplices), and higher-order interactions like triangles (2-simplices).

Table of symbols and their meanings in the Topological Signal Processing framework.

The core of the AJVEE framework is the ALMS-Hodge filter, an Adaptive Least Mean Square procedure based on the Hodge Laplacian (denoted as $\mathbf{L}_k$ in the table above). The Hodge Laplacian is the higher-order generalization of the standard graph Laplacian; it enables the filter to perform denoising and imputation by capturing the "flow" and "divergence" of signals across the entire topology.

To ensure the algorithm is suitable for real-time, online applications, the authors utilize Chebyshev polynomials to approximate filters in the spatial domain. This avoids the computationally expensive spectral decompositions typically required for higher-order signals. The resulting Joint Regression model allows the estimated edge signals at one time step to define the diffusion parameters for vertex signals in the next, effectively learning the mechanism of change within the system.

Experimental Evaluation

The researchers evaluated the AJVEE framework across three distinct scenarios to test accuracy, scalability, and real-world utility:

  1. Sioux Falls Transportation Network: A benchmark network (24 nodes, 38 edges) used to test tracking accuracy with synthetic time-varying traffic signals.
  2. Anaheim Transportation Network: A larger scale network (406 nodes, 624 edges) used to evaluate performance under significant data loss (up to 30% missing observations).
  3. England COVID-19 Dataset: A real-world application involving 61 dynamic graphs where vertices represent regional infection cases and edges represent population mobility between those regions.
Visualization of time-varying signals on the Sioux Falls network at $t=1$ and $t=180$, demonstrating the dynamic nature of the topological data.

Key Insights and Results

The primary "Aha!" moment of this research is the realization that edge signals are the mechanism of change for vertex signals. By estimating them jointly, the model learns how mobility patterns (edges) cause the spread of phenomena like viruses or traffic congestion (vertices). The Hodge Laplacian acts as a structural prior; even when specific sensors fail, the algorithm can "fill in the blanks" by analyzing the signal flow from adjacent edges and nodes.

Key results from the study include:

  • Superior Accuracy: AJVEE consistently achieved a lower Normalized Mean Squared Error (NMSE) compared to standard GSP baselines such as GLMS and G-Sign.
  • Robustness: The algorithm successfully reconstructed signals even with 26-30% missing data.
  • Forecasting Utility: In the COVID-19 experiments, AJVEE outperformed traditional moving averages and node-only models because it could adapt to the non-stationary nature of population mobility during the pandemic.
  • Convergence: The authors provided formal proofs that the ALMS-Hodge filter is stable and converges to a bounded error, ensuring reliability for long-term tracking.

Limitations and Future Outlook

While AJVEE represents a significant step forward, some limitations remain. The current model uses the Hodge Laplacian, which may not fully capture the nuances of directed flow (e.g., one-way streets). Future work may involve "equivariant models" to better handle directionality. Additionally, the algorithm assumes a fixed graph topology; combining AJVEE with Topology Learning to estimate the graph structure itself from raw data is a promising next step. Finally, as the framework is mathematically generalized, it invites the exploration of even higher-order data, such as "triangular signals" representing 3-way interactions, provided that high-quality datasets for such structures become available.

Summary updated

BibTeX
@article{fellow2025joint,
  author = {Ercan Engin Kuruoglu, PhD Cantab, Prof, IEEE Fellow and Yi Yan and Tian Xie and Ercan E. Kuruoglu},
  title = {{Joint online estimation of multi-order graph topological signals}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2025},
  doi = {10.1109/tsipn.2025.3536084},
}
Figure