PaperlayerView exact revision on arXiv

Source-linked AI summary

Topological Signal Processing over Simplicial Complexes

Sergio Barbarossa, Stefania Sardellitti

arXiv:1907.11577v2eess.SP

TL;DR

The paper addresses how to analyze signals on non-metric topological spaces when pairwise graph relations are insufficient. It develops an algebraic framework for simplicial-complex signals, including spectral and sampling tools and topology inference, and demonstrates benefits for real edge signals and discrete vector fields.

  • Problem

    Graph-based signal processing represents vertex signals and may miss complex interactions that require multiway relations; the paper seeks tools for signals defined over simplicial complexes.

  • Method

    The paper develops algebraic-topology and spectral tools for signals on simplices, derives sampling conditions, infers second-order simplicial-complex structure from data, and analyzes edge signals and vector fields.

  • Results

    The framework exploits second-order simplicial structure for edge-signal analysis, significantly outperforms graph-only methods on real wireless traffic data, and highlights RNA velocity-field behaviors.

  • Takeaways & Limitations

    Simplicial-complex structure supports analysis of higher-order signal relations and reveals irrotational and solenoidal behaviors that graph-Laplacian eigenvectors would make difficult to highlight.

Abstract

from arXiv · show

The goal of this paper is to establish the fundamental tools to analyze signals defined over a topological space, i.e. a set of points along with a set of neighborhood relations. This setup does not require the definition of a metric and then it is especially useful to deal with signals defined over non-metric spaces. We focus on signals defined over simplicial complexes. Graph Signal Processing (GSP) represents a special case of Topological Signal Processing (TSP), referring to the situation where the signals are associated only with the vertices of a graph. Even though the theory can be applied to signals of any order, we focus on signals defined over the edges of a graph and show how building a simplicial complex of order two, i.e. including triangles, yields benefits in the analysis of edge signals. After reviewing the basic principles of algebraic topology, we derive a sampling theory for signals of any order and emphasize the interplay between signals of different order. Then we propose a method to infer the topology of a simplicial complex from data. We conclude with applications to real edge signals and to the analysis of discrete vector fields to illustrate the benefits of the proposed methodologies.

I. INTRODUCTION

The paper extends signal processing from metric and graph-based settings to signals on simplicial complexes, whose multiway relations capture interactions beyond pairs. It introduces algebraic-topology foundations and develops tools for high-order signal analysis, sampling, topology inference, and applications.

  • Motivation: Graph signal processing analyzes vertex signals, but graph representations cannot capture interactions that require multiway relations.Simplicial complexes provide a structured setting for representing such relations through sets closed under inclusion of faces.
  • Foundations: A simplicial complex is a collection of simplices closed under inclusion of faces, whereas restricting hypergraphs to this class limits the model but enables richer algebraic tools.The paper notes applications of simplicial-complex learning in brain, neuronal, collaboration, and tumor-progression analyses.
  • Scope: Topological signal processing generalizes graph signal processing to signals defined on simplices of various orders, including nodes, edges, and triangles.The paper focuses especially on edge signals and second-order complexes containing triangles.
  • Contributions: The paper derives a real-valued function for triple-wise relations, a sampling theory for high-order signals, topology-inference algorithms, and edge-signal applications to vector fields.The applications include RNA velocity-field recovery, wireless data traffic, and discrete vector-field analysis.
  • Foundations: The framework uses oriented simplices, chain spaces, and boundary operators, including the property that the boundary of a boundary is zero.These algebraic-topology principles form the background for later signal-processing tools.

III. SPECTRAL SIMPLICIAL THEORY

The spectral simplicial framework represents signals of each order using eigenvectors of the corresponding high-order Laplacian and relates spectral components across orders. For edge signals, the Hodge decomposition distinguishes behaviors associated with lower and upper structure, including inter-cluster edges.

  • Signal representation: Signals on k-simplices are real-valued maps, and the paper focuses on orders 0, 1, and 2 corresponding to vertices, edges, and triangles.The associated signals are denoted s0, s1, and s2 over V, E, and T.
  • Spectral representation: The order-k Graph Fourier Transform projects a k-order signal onto the eigenvectors of its corresponding Laplacian Lk.This generalizes the graph Fourier representation based on the eigenvectors of L0.
  • Hodge decomposition: The Hodge decomposition separates signals into components associated with different behaviors, exploiting the interplay between signals of different orders.For edge signals, the paper introduces discrete curl and divergence operators to interpret these components.
  • Spectral interpretation: Eigenvectors of L1 associated with the smallest eigenvalues of B1B1^T are approximately null on within-cluster links and large on edges across clusters.These eigenvectors are therefore useful for highlighting inter-cluster edges.

B. Hodge decomposition

The paper decomposes signals on simplicial complexes into orthogonal components tied to gradients, curls, and harmonic structure. For edge signals, triangle and vertex relations support topology-aware representations and regularization.

  • Hodge decomposition: Hodge decomposition expresses each order-k signal as three orthogonal components associated with adjacent-order boundaries and the harmonic subspace.The decomposition uses signals of orders k−1, k, and k+1, with the harmonic component lying in ker(Lk).
  • Hodge decomposition: The dimensions of Laplacian kernels are Betti numbers, topological invariants representing connected components, holes, and cavities.β0 counts connected components, β1 counts holes, and β2 counts cavities.
  • Hodge decomposition: For edge signals, B1 maps encode divergence while B2 maps encode curl, separating irrotational, solenoidal, and harmonic flow components.Divergence measures net flow through vertices; curl measures circulation around triangles.
  • Topology-aware unitary basis: The proposed edge-domain Lovász extension measures the sum of absolute triangle curls and provides a triple-wise regularizer for edge-signal analysis.It generalizes cut-based constructions from bipartitions to tripartitions and is defined over the edge space.
  • Topology-aware unitary basis: Laplacian eigenvectors arise as a relaxed solution for constructing a unitary basis that reflects intrinsic topological properties of the simplicial complex.The approach extends graph total-variation methods from node signals to edge signals using triple-wise relations.

IV. EDGE FLOWS ESTIMATION

The edge-flow estimation framework formulates denoising through Hodge components and convex constraints under additive Gaussian noise. KKT analysis yields component-recovery relations, including harmonic flow obtained from the observed signal after estimating the other parts.

  • IV. EDGE FLOWS ESTIMATION: The denoising problem estimates vertex, edge-harmonic, and triangle signals from a noisy edge observation under Hodge-consistency constraints.The noise is assumed Gaussian with zero-mean entries sharing variance σ_n^2.
  • IV. EDGE FLOWS ESTIMATION: The constrained estimation problem is convex, so its solution satisfies Karush-Kuhn-Tucker conditions with vertex and triangle multipliers.The formulation uses the orthogonality relation B1B2 = 0.
  • IV. EDGE FLOWS ESTIMATION: The estimated triangle signal can differ from the true triangle signal only by a vector in the nullspace of B2^T.This ambiguity follows from the KKT conditions and the structure of the second-order boundary operator.
  • IV. EDGE FLOWS ESTIMATION: The harmonic component is recovered by subtracting the estimated solenoidal and irrotational components from the observed flow signal.The paper explicitly identifies this subtraction as the route to harmonic-flow recovery.
  • IV. EDGE FLOWS ESTIMATION: Recovering the irrotational component from vertex signals requires solving a singular graph-Laplacian system with a Moore-Penrose pseudo-inverse.For connected graphs, L0 has rank V−1 and a kernel spanned by the all-ones vector.

2 B2)†BT 2 x1

The paper applies Hodge-based projection to noisy edge flows to isolate irrotational traffic patterns. In the example, the reconstructed component localizes significant activity around the anomalous source nodes.

  • Edge-flow application: Projecting the observed edge flow onto the irrotational subspace targets nodes that inject anomalous traffic.An anomalous source generates an edge signal with a strong divergence-like component.
  • Edge-flow application: The observed flow contains measurement errors, with edge values encoded by gray levels across the network links.The example represents simulated data-packet flow on a simplicial complex.
  • Edge-flow application: The projection result shows significant contributions only on edges surrounding two traffic-source nodes, whose divergence is encoded by node color.The reconstruction therefore visually identifies the locations associated with injected traffic.
  • Topological signal processing: The framework uses simplicial-complex structure to analyze edge signals rather than restricting processing to vertex signals.TSP extends GSP to signals defined on simplices of multiple orders.

A. Single-layer sampling

The sampling theory characterizes when bandlimited edge signals can be recovered from partial observations and extends recovery to samples drawn across vertices, edges, and triangles. Recovery conditions depend on spectral support, localization, and cross-order coupling.

  • A. Single-layer sampling: A bandlimited edge signal is recoverable from samples on an edge subset when no nonzero bandlimited signal is perfectly localized on the complementary edges.Equivalently, the relevant sampling operator must satisfy the theorem’s stated invertibility condition.
  • A. Single-layer sampling: For single-layer recovery, ensuring rank(DSFF) = |F| requires at least |S| ≥ |F| samples as a necessary condition.The reconstruction can then use the inverse operator QS = (I − D̄SFF)^−1.
  • A. Single-layer sampling: Because Hodge components occupy lower-dimensional subspaces, a signal known to contain only one component can be recovered over all edges under the theorem’s conditions.The relevant cases are solenoidal, irrotational, and harmonic edge signals.
  • Multi-layer sampling: Cross-order sampling recovers edge signals from vertex and triangle observations by exploiting relations among irrotational, solenoidal, harmonic, and adjacent-order spectral components.The framework considers signals on vertices, edges, and triangles, with bandlimitedness and operator-norm assumptions.
  • Multi-layer sampling: Recovery using all three simplex orders requires at least N0 ≥ |F0|, N1 ≥ |FH|, and N2 ≥ |F2| samples from vertices, edges, and triangles, respectively.The result applies to edge signals whose frequency sets satisfy the stated decomposition and overlap conditions.

VI. ESTIMATION OF DISCRETE VECTOR FIELDS

The paper smooths discrete vector fields by mapping them to edge signals, filtering those signals with metric-aware Hodge-Laplacian regularization, and mapping them back. It applies this procedure to reconstruct RNA velocity fields from noisy observations.

  • Method: Discrete vector-field processing follows three steps: map the field to an edge signal, filter it, then map the result back.The filtering stage differs from prior approaches by incorporating metrics induced by the initial vector-field-to-edge-signal mapping.
  • Assumptions: The method assumes a flat, well-centered simplicial complex embedded in R^n.Flatness places all simplices in one affine n-subspace, while well-centeredness requires each simplex circumcenter to lie inside it.
  • Method: The vector field is projected onto edges using affine piecewise hat functions, producing scalar signals on the simplicial complex.Each hat function is one at its associated vertex, zero at other vertices, and affine over incident 2-simplices.
  • Filtering: The recovered edge flow fits the observed signal while encouraging smoothness through the Hodge Laplacian and sparsity through an l1 penalty.The optimization balances fitting error, λ-weighted smoothness, and γ-weighted sparsity.
  • Application: The procedure is demonstrated on RNA velocity, a vector field derived from gene-expression change and used to predict cells’ future transcriptomic states.The application uses mouse chromaffin-cell differentiation data and distinguishes nascent from mature mRNA to estimate RNA velocity.
  • Application: Figure 3 compares observed, noisy, and reconstructed RNA velocity fields.The displayed panels are labeled (a) observed, (b) noisy, and (c) reconstructed.

VII. INFERENCE OF SIMPLICIAL COMPLEX TOPOLOGY FROM DATA

The paper infers simplicial-complex topology from edge-flow data by selecting filled triangles that yield low total variation, using MTV and a PCA-based robustification. Synthetic and real-data tests show that inferred higher-order structure improves signal representation and reconstruction, while performance depends on noise and solenoidal bandwidth.

  • Topology inference: The hierarchical inference targets a second-order complex from multiple observed edge-flow signals, assuming the lower-order graph layers are known or estimated.For order 2, the method infers the triangle layer B2 after establishing B1 from the graph structure.
  • Topology inference: The algorithm detects three-node cliques, assigns candidate triangle orientations, and estimates which cliques are filled through binary coefficients.Each candidate triangle contributes an oriented edge-incidence vector, and the coefficients t indicate whether the corresponding clique is filled.
  • MTV inference: MTV selects triangles associated with the lowest observed curl, minimizing total variation when the number of triangles is known or cross-validated.The closed-form solution sorts coefficients and chooses the t* lowest; this favors harmonic edge signals whose curl on filled triangles is zero.
  • PCA-BFMTV: PCA-BFMTV jointly fits the observed edge data and topology after projecting onto dominant covariance eigenvectors, improving robustness to solenoidal components and noise.Alternating optimization updates the signal coefficients and triangle indicators, with a trade-off between fitting error and smoothness.
  • Synthetic evaluation: Both methods degrade as the solenoidal bandwidth grows, while PCA-BFMTV significantly outperforms MTV, especially at low SNR.The reported improvement is attributed to denoising through projection onto eigenvectors associated with the largest covariance eigenvalues.
  • Real-data evaluation: On real traffic-flow data, adding the inferred higher-order term captures additional structure and achieves smaller reconstruction error for the same number of samples.The comparison evaluates graph-based and order-two complex representations using sparsity, estimation error, and sampled-signal recovery.

VIII. CONCLUSION

The paper develops an algebraic framework for signals on simplicial complexes, focusing on edge signals in complexes that include triangles. It reports benefits over graph-only tools, topology inference from flow data, and discrete vector-field analysis.

  • The framework analyzes signals on simplicial complexes, with the paper focusing on edge signals in order-two complexes that include triangles.The authors state that the algebraic structure can translate to higher-order signals, although their visual interpretation would be limited there.
  • The proposed method infers the structure of a second-order simplicial complex from flow data.
  • The approach can significantly outperform methods based only on graph representations on real wireless traffic data.
  • The discrete vector-field method recovers an RNA velocity field and highlights irrotational and solenoidal behaviors using eigenvectors of L1.These behaviors would have been difficult to highlight using only eigenvectors of L0.

APPENDIX A PROOF OF THEOREM 1

The appendix proves that a triangle-cut set function has a Lovász extension equal to the corresponding edge-signal function. The proof uses oriented edge sets, the edge-triangle incidence matrix, and case-based evaluation of the extension.

  • The appendix recalls the Lovász extension and submodularity before applying them to a set function on graph edges.The cited property states that submodularity is equivalent to convexity of the Lovász extension and preserves minimization equivalence.
  • The triangle-cut function counts triangles whose vertices lie in the three distinct parts of a node tri-partition.
  • The oriented edge indicator 1_ET records selected-edge orientations, while B2 1_ET identifies triangles crossing all three partition sets.Each nonzero entry corresponds to a triangle with one vertex in each partition set.
  • For the illustrated complex, B2 1_ET = [0, 1, 0]^T, giving a triangle-cut size of 1.
  • The Lovász extension evaluates to xi0 − xi1 + xi2 across the relevant orderings of xi0, xi1, and xi2.The appendix checks representative orderings and states that the remaining cases follow similarly.
  • The proof concludes that f1(x1) is the Lovász extension of the triangle-cut function F1.

APPENDIX B SUPPORTING MATERIAL

The supporting material establishes how bandlimited vertex signals induce bandlimited irrotational edge signals. It derives the resulting bandwidth relation between the two signal orders.

  • The appendix studies the relationship between the bandwidths of an edge signal and its associated vertex signal.
  • If s0 is F0-bandlimited, its irrotational edge component s1_irr is Firr-bandlimited.
  • The induced edge bandwidth satisfies |Firr| = |F0| − c1, where c1 ≥ 0 counts bandwidth eigenvectors belonging to ker(L0).

B. Proof of Theorem 3

The proof establishes sampling conditions for jointly recovering vertex signals and solenoidal or harmonic edge components. Under the stated norm conditions, the relevant recovery matrix is invertible.

  • The proof assumes norm conditions ∥D̄_A F0∥2 < 1 and ∥D̄_S F F_sH∥2 < 1 to ensure invertibility of the recovery matrix G.
  • The full edge signal combines solenoidal and harmonic components with the irrotational component induced by the vertex signal.Its bandwidth is |F| = |F_sH| + |F0| − c1.
  • N1 must be at least |F_sH| to perfectly recover the solenoidal and harmonic edge components.
  • N0 must be at least |F0| to perfectly recover the vertex signal.

P1 P2 P3

The sampling analysis characterizes bandwidth across signal components and derives sample requirements for recovering node, triangle, and harmonic edge signals.

  • Bandwidth characterization: The combined edge-signal bandwidth is |F| = |F0|+|FH|+|F2|−(c1+c2), combining irrotational, harmonic, and solenoidal components.The solenoidal component is itself bandlimited with frequency set Fsol, while the full edge signal uses F = Fsol ∪ FH ∪ Firr.
  • Sampling requirements: Perfect recovery of the harmonic edge component requires at least |FH| edge samples.This requirement follows from the harmonic component's bandwidth.
  • Sampling requirements: The recovery system requires N0 ≥ |F0| node samples and N2 ≥ |F2| triangle-signal samples.These sample counts correspond to the bandwidths of the node and triangle signal components.
Loading 1907.11577v2…