Topological Dictionary Learning

Eva Grimaldi, Claudio Battiloro, Paolo Di Lorenzo

TL;DR

This paper introduces Topological Dictionary Learning (TDL), a framework that extends sparse signal representation from simple graphs to complex multi-way relationships using cell complexes. Beyond just finding efficient ways to represent data, the proposed algorithms can actually infer the hidden higher-order topology (like induced cycles and polygons) of a system directly from the signals it produces.

What Problem Does This Paper Address?

Traditional Graph Signal Processing (GSP) is a powerful tool for data defined on networks, but it has a fundamental "blind spot": it primarily captures pairwise relationships (nodes connected by edges). In many real-world systems—like co-expression in biological networks or synchronized firing in neural circuits—interactions happen in groups of three or more.

While Topological Signal Processing (TSP) uses structures like simplicial and cell complexes to model these higher-order interactions, most existing methods assume the underlying "map" (the topology) is perfectly known. In practice, we often know the basic connections (the 1-skeleton or graph) but don't know which higher-order structures (like polygons or "holes") are actually relevant to the data. This paper tackles the challenge of jointly learning the best dictionary for sparse signal representation and the underlying topological structure itself.

Methods

The authors leverage Hodge Theory to build a dictionary that is mathematically "aware" of the topology.

  1. The Dictionary Structure: Instead of a generic matrix, the dictionary is composed of sub-dictionaries designed as polynomials of the Hodge Laplacians (both lower and upper). This ensures that the "atoms" of the dictionary are localized—meaning they represent patterns that only affect a specific neighborhood of the complex.
  2. Joint Optimization: The problem is formulated as a minimization of a data-fitting term plus a regularization term. It solves for three variables simultaneously:
  3. $h$ (Dictionary Coefficients): The parameters defining the spectral filters.
  4. $S$ (Sparse Representation): The sparse coefficients for the training signals.
  5. $p$ (Topology Parameters): A binary vector indicating which potential polygons are "active" in the complex.
  6. Algorithms:
    • GTDL (Greedy): A robust but computationally heavier approach that iteratively removes polygons to find the best fit.
  7. RTDL (Relaxed): A faster version that uses proximal gradient descent and a sparsity-inducing penalty to "relax" the binary constraints, allowing it to scale linearly with the number of cells.
  8. Sparse Coding: The authors use Orthogonal Matching Pursuit (OMP) to handle the signal sparsity constraint ($K_0$).

Datasets

  • Synthetic Data: The authors generated complexes based on Erdos-Rényi graphs, probabilistically adding 2-cells (triangles) to create various "ground truth" topologies. This allowed them to precisely measure how well the algorithms could recover hidden structures.
  • Real-World Traffic Data: They used edge signals from the DFN-Verein (German National Research and Education Network), consisting of 50 vertices, 89 edges, and 39 potential polygons representing daily traffic flows from February 2005.

Key Insights and Ideas

  • Topology as a Learnable Parameter: The most striking idea is treating the "upper Laplacian" (the structure representing higher-order connections) as a variable. This allows the model to "discover" the geometry of the data domain rather than just processing signals on a fixed grid.
  • The Sparsity-Inference Trade-off: The authors found an "inverse trend" between signal approximation and topology inference. While allowing more non-zero coefficients ($K_0$) improves signal reconstruction, it actually makes it harder to infer the correct topology. This is because a more flexible signal model can "cheat" by fitting the data using the wrong topological structure.
  • Spectral Localization: By using polynomials of the Hodge Laplacian, the dictionary atoms behave similarly to wavelets in Euclidean space—they are concentrated in both the "spatial" (cell) domain and the frequency (spectral) domain.

Key Results

  • Superior Compression: On both synthetic and real data, the learned dictionaries (GTDL/RTDL) significantly outperformed analytic methods like the Topological Fourier Transform, Hodgelets, and Topological Slepians. For the same number of coefficients, TDL achieved much lower Normalized Mean-Squared Error (NMSE).
  • Perfect Recovery: In synthetic tests, when the signal was sufficiently sparse, both GTDL and RTDL were able to perfectly recover the true underlying topology (the set of active triangles) once the percentage of triangles in the true model was high enough.
  • Real-World Validation: On the DFN network, the GTDL algorithm consistently identified a specific set of "active" polygons across different sparsity levels, suggesting these structures represent genuine, significant traffic patterns in the network.

Limitations and Future Work

  • Computational Complexity: While the RTDL algorithm scales linearly, the greedy GTDL approach is computationally expensive for very large complexes.
  • Directionality: The current model focuses on regular cell complexes. The authors suggest that learning task-oriented directional topologies is a promising next step.
  • Deep Unrolling: A suggested future direction is to use "model-based deep learning" to unroll these iterative algorithms into neural network layers, potentially speeding up inference and improving performance on massive datasets.

Summary updated

Abstract

The aim of this paper is to introduce a novel dictionary learning algorithm for sparse representation of signals defined over combinatorial topological spaces, specifically, regular cell complexes. Leveraging Hodge theory, we embed topology into the dictionary structure via concatenated sub-dictionaries, each as a polynomial of Hodge Laplacians, yielding localized spectral topological filter frames. The learning problem is cast to jointly infer the underlying cell complex and optimize the dictionary coefficients and the sparse signal representation. We efficiently solve the problem via iterative alternating algorithms. Numerical results on both synthetic and real data show the effectiveness of the proposed procedure in jointly learning the sparse representations and the underlying relational structure of topological signals.
BibTeX
@article{grimaldi2025topological,
  author = {Eva Grimaldi and Claudio Battiloro and Paolo Di Lorenzo},
  title = {{Topological Dictionary Learning}},
  journal = {IEEE Transactions on Signal Processing},
  year = {2025},
  doi = {10.1109/tsp.2025.3646587},
}
Figure