Persistent Homology of Time Series through Complex Networks

1.1 Why Topology for Time Series?

• Persistence diagrams summarize shape across scales, and the stability theorem guarantees small diagram changes under small input perturbations.Persistent homology tracks topological features as scale varies, complementing classical time-series descriptors.Source: §1.1 · pp. 1–2
• Graph representations provide a compact intermediary for applying persistent homology to time series, avoiding computation on the full embedded point cloud.The pipeline maps a time series to a complex network, then to a graph-derived pairwise matrix and persistence diagram.Source: §1.1 · p. 2

1.2 Scope and Contributions

• The study compares five graph constructions across visibility, transition, and proximity families, using a shared downstream route.Natural and horizontal visibility graphs are treated as separate pipelines.Source: §1.2 · p. 2, Figure 1 · p. 3
• Persistence diagrams are converted to fixed-length features with landscapes, Adcock–Carlsson coordinates, and diagram statistics to isolate representation and distance effects.The scope is univariate time series; direct sublevel-set filtrations, sliding-window periodicity analysis, and topological forecasting are not treated.Source: §1.2 · p. 2

2.1 Simplicial Complexes and Filtrations

• A simplicial complex extends a graph to higher-dimensional simplices, while a filtration adds simplices in nested complexes as the scale increases.Higher dimensions allow detection of loops and cavities that graphs alone cannot capture.Source: §2.1 · p. 4

2.2 Constructing a Graph-Based Pairwise Matrix

• Four graph-derived matrices encode separation: unweighted hop distance, frequency-optimal hop count, reciprocal-weight shortest path, and diffusion distance.Diffusion distance compares random-walk profiles, is more global, and can be more robust to isolated low-weight edges, but is typically more computationally demanding.Source: §2.2 · pp. 4–5

2.3 The Vietoris–Rips Filtration

• The Vietoris–Rips route thresholds the symmetric matrix D, including a simplex when every pair of its vertices is within ε.For a metric, this is the Vietoris–Rips complex; for a general graph-derived dissimilarity, the same rule defines a flag filtration.Source: §2.3 · pp. 5–6

2.4 Persistent Homology

• Persistent homology tracks births and deaths of classes across the filtration, producing diagrams that summarize feature lifespans; this study computes H0 and H1.H0 records component merging, while H1 records loops that are later filled; Figure 2 illustrates the route using a 4-cycle.Source: §2.4 · p. 6, Figure 2 · p. 7

2.5 The Stability Theorem

• The stability theorem bounds persistence-diagram changes by the largest discrepancy between filtration values on the same finite complex.Its guarantee applies after the graph-derived matrix has been converted into simplex entry values.Source: §2.5 · p. 8

2.6 Software and Workflow

• The workflow constructs a graph, computes D, passes it to Ripser for Vietoris–Rips persistence, then vectorizes the diagrams.The implementation primarily uses Python and teaspoon, with ts2vg generating visibility graphs.Source: §2.6 · p. 8
• With the downstream route fixed, the remaining methodological choice is how to convert the raw signal into a graph.This section leads into the five network constructions.Source: §2.6 · p. 8

Visibility methods

• Visibility methods operate directly on the raw signal, connect timestamps by geometric line-of-sight criteria, and produce parameter-free connected graphs.Natural and horizontal visibility graphs are distinct constructions.Source: §3 · p. 8

Transition methods

• Transition methods embed the signal, map embedded points to symbolic states, and yield compact graphs at the cost of parameter choices.OPN and CGSSN can produce directed weighted networks that are symmetrized before the common downstream route.Source: §3 · p. 8

Proximity methods

• Proximity methods use delay embeddings and connect nearby states, preserving reconstructed phase-space geometry more directly.K-nearest neighbor graphs are one proximity construction in the study.Source: §3 · p. 9

• For a series of length L, delay embedding forms vectors in R^n from n coordinates separated by delay τ, yielding N = L − (n−1)τ points.These points make up the reconstructed point cloud χ.Source: §3.1 · p. 9
• Takens’ theorem motivates delay coordinates, but unknown attractor dimension and noisy finite data make data-driven parameter heuristics more practical.For generic smooth dynamics and observables, the stated embedding condition is n ≥ 2d + 1.Source: §3.1 · p. 9
• The first local minimum of mutual information I(τ) is a common delay choice, balancing reduced redundancy with continued relation between adjacent coordinates.The section also describes multiscale permutation entropy as a complementary delay-selection approach; a resonance dip may cue the dominant period in periodic or quasiperiodic signals, while a prominent entropy maximum is a fallback for chaotic signals.Source: Delay Selection (τ) · pp. 9–10
• Embedding dimension is commonly chosen with false nearest neighbors, selecting the smallest n for which the FNN fraction falls below 1–2%.The passage gives Rtol = 15 as typical and n = 3 to 7 as common practical values.Source: Dimension Selection (n) · p. 10
• For OPNs, MsPE can select dimension by maximizing normalized permutation entropy over candidate n values, while modest n helps avoid sparse transition counts.Practical starting ranges are τ ∈ [1, 50] and n ∈ [3, 7]; CGSSN bin count and k-NN k are application-tuned, not universal defaults.Source: Dimension Selection (n) · p. 10
• The embedding definition assumes uniform sampling; irregular series may be interpolated or resampled, with the method and target rate affecting reconstructed attractor geometry.Source: Dimension Selection (n) · p. 10

Natural Visibility Graph (NVG)

• The NVG connects two observations when the joining line clears every intermediate value, and its graph is connected, undirected, and invariant to affine transformations of signal values.Local maxima often become hubs.Source: Natural Visibility Graph (NVG) · pp. 10–11

Horizontal Visibility Graph (HVG)

• The HVG connects two observations only when every intermediate value is below the smaller endpoint value.Thus every HVG edge is also an NVG edge, making HVG a subgraph; exact degree-distribution results for i.i.d. variables provide a null model for hypothesis testing.Source: Horizontal Visibility Graph (HVG) · p. 11

3.2 Visibility Graphs

• Both visibility variants are parameter-free, and each graph has one node per time step.The naïve NVG algorithm is O(L^2), while divide-and-conquer implementations achieve O(L log L).Source: Horizontal Visibility Graph (HVG) · p. 11

Horizontal Visibility Graph (HVG)

• Identical ordering structures with different amplitude ranges can yield the same unweighted graph, which may discard discriminative amplitude information.That insensitivity can instead benefit tasks where scaling robustness matters.Source: Horizontal Visibility Graph (HVG) · p. 11
• For x = [1, 2, 1, 5, 2], the NVG has 6 edges and the HVG has 5; the HVG omits edge (1, 4).The intermediate value x2 = 2 blocks that edge under the horizontal criterion; Figure 3 depicts the comparison.Source: Horizontal Visibility Graph (HVG) · p. 11, Figure 3 · p. 12

• The OPN was introduced by McCullough et al. and is rooted in the permutation entropy framework of Bandt and Pompe.Source: §3.3 · p. 12
• The OPN maps each delay vector to its ordinal pattern, uses observed patterns as nodes, and records transitions between consecutive patterns with edge weights counting their occurrences.Ties are broken by temporal order, and directed transition counts are symmetrized into undirected weights.Source: §3.3 · p. 12
• Because ordinal patterns retain relative ordering, OPNs are invariant to monotone amplitude transformations, but signals with identical ordinal sequences and different amplitude ranges produce the same network.Canonical examples associate periodic dynamics with cycle-like networks and chaotic dynamics with more richly connected structures.Source: §3.3 · pp. 12–13
• In the illustrated example, five observed patterns form the nodes, and π2 is the hub with degree 3.Figure 4 shows the bidirectional {π1, π2} edge with weight 2 because each direction occurs once.Source: Figure 4 · p. 13, §3.3 · p. 13

• The CGSSN follows a phase-space coarse-graining construction and replaces ordinal patterns with discretized amplitude states.The cited construction follows Wang and Tian and relates to phase-space reconstruction networks such as Gao and Jin.Source: §3.4 · p. 14
• CGSSN partitions the amplitude range into b equal-width bins, maps each delay-vector coordinate to a bin, and encodes the resulting bin tuple as a state.Observed states become nodes, temporal transitions become edges, and transition counts become weights; the graph is symmetrized for persistence.Source: §3.4 · p. 14
• The CGSSN has b^n possible states, which can greatly exceed the OPN’s n! states and raise sparsity risk for short series.For b = 8 and n = 4, the passage gives 4096 CGSSN states versus 24 OPN states.Source: §3.4 · p. 14
• In the example with n = 3, τ = 1, and b = 2, five observed states form the network, with state 6 as the degree-3 hub.Figure 5 shows the bidirectional {3, 6} edge with weight 2; other edges have weight 1.Source: Figure 5 · p. 15, §3.4 · p. 15

3.5 k-Nearest Neighbor Graphs

• k-NN graphs connect nearby delay-embedded states, preserving reconstructed geometry rather than encoding temporal succession.The neighbors are determined using Euclidean distance in delay-coordinate space.Source: §3.5 · pp. 15–16
• Unlike the transition networks, a k-NN graph preserves metric information but uses N = L − (n−1)τ nodes, potentially increasing downstream Rips-computation cost.The transition networks have at most n! or b^n nodes.Source: §3.5 · p. 16
• The symmetric-union rule makes the graph undirected, while k controls density and can trade disconnection risk against loss of local structure.An edge is included if either endpoint is among the other's k nearest neighbors.Source: §3.5 · p. 16
• In the example, the symmetric-union graph has 5 nodes and 6 edges, with v1 as a degree-3 hub.The graph is built from five delay vectors using n = 3, τ = 1, and k = 2.Source: §3.5 · p. 16, Figure 6 · p. 17

3.6 Relationships Between the Methods

• Visibility graphs act directly on observations and emphasize temporal geometry; the horizontal visibility graph is a subgraph of the natural visibility graph.Each visibility graph has one node per observation.Source: §3.6 · p. 17
• Ordinal partition and coarse-grained state-space networks encode transitions between reconstructed symbolic states, while k-NN graphs link nearby embedded states.Transition networks emphasize symbolic evolution; k-NN emphasizes spatial proximity.Source: §3.6 · p. 17
• Ordinal partition networks retain ordinal information and are insensitive to monotone rescaling, whereas coarse-grained state-space networks retain coarse amplitude through discretized bins.The ordinal network has at most n! nodes; the coarse-grained network has at most b^n.Source: §3.6 · p. 17
• Perturbation sensitivities differ: bin-boundary shifts can affect coarse-grained networks, local peaks can alter visibility edges, and coordinate noise affects k-NN graphs.Increasing k can smooth small k-NN perturbations while weakening local detail.Source: §3.6 · p. 17

3.7 Comparative Summary

• The graph-construction comparison closes this part of the chapter.The upstream representation is fixed and the downstream filtration standardized.Source: §3.7 · p. 17
• With those stages fixed, the remaining methodological question is converting Dgm0 and Dgm1 into classifier-ready numerical features.Source: §3.7 · p. 17
• Table 1 provides a comparative summary of the five network construction methods.Source: Table 1 · p. 18

4.1 Persistence Landscapes

• Each diagram point yields a tent peaking at the birth–death midpoint with height half its lifetime; landscape layers select the k-th largest tent value.The complete landscape is injective and lives in a function space, but finite discretization is lossy.Source: §4.1 · p. 18
• The complete landscape map is injective, and the stated stability bound means small filtration perturbations produce small changes in every landscape layer.The finite discretization described next deliberately compresses this full representation lossily.Source: §4.1 · pp. 18–19

Discretization for Machine Learning

• The default representation samples each landscape on M = 200 grid points, retains J = 3 layers, and averages them; these defaults are not universal optima.A tuned workflow should select M and J by validation or domain constraints.Source: Discretization for Machine Learning · p. 19

4.3 Assembling the Final Feature Vector

• The final vector concatenates 400 landscape features and 18 summary-statistic features into a 418-dimensional input for a standard classifier.Fixing vectorization choices keeps feature length the same across time series.Source: §4.3 · p. 20

4.2 Topological Summary Statistics

• Scalar summaries complement landscapes with diagram-wide measures, including maximum lifetime, total persistence, point count, persistent entropy, landscape norm, and Adcock–Carlsson coordinates.Applied separately to H0 and H1, each scalar statistic contributes two features.Source: §4.2 · pp. 19–20, §4.3 · p. 20

4.4 Illustrative Example

• For D = {(0, 4), (1, 3)}, both tents peak at t = 2, and the example gives A(D) = 4, LD = 6, and |I| = 2.The example also reports f1 = f2 = 2 and f3 = f4 = 16.Source: §4.4 · p. 20, Figure 7 · p. 20

5.1 Experimental Setup

• The study used twelve UCR datasets, stratified five-fold cross-validation, five graph constructions, fixed-length persistence features, and CatBoost to compare pipelines.Parameters were selected once per dataset and shared across its series.Source: §5.1 · pp. 21–23

5.2 Graph Construction Comparison

• CGSSN won five datasets, OPN four, k-NN two, and HVG one; signal structure generally matched each construction’s strengths, though FordB and Plane qualify that alignment.CGSSN and k-NN were essentially tied on Plane, while HVG’s FordA success did not transfer to FordB.Source: §5.2 · pp. 23–24, Table 5 · p. 25

5.3 Distance-Matrix Ablation

• 173% (0.271 → 0.739) was NVG’s mean-F1 gain under diffusion versus shortest-path; diffusion won for every graph, with larger gains on visibility graphs.On ECGFiveDays, switching NVG from shortest-path to diffusion raised F1 from 0.627 to 0.930.Source: §5.3 · p. 25, Figure 8 · p. 27

5.4 Noise Robustness

• At 0 dB, CGSSN retained 72% of Coffee F1 (0.709 to 0.512) and 63% on PowerCons (0.875 to 0.554), while OPN lost its Coffee clean-data lead.CGSSN had the highest absolute F1 among evaluated pipelines below 20 dB in both datasets.Source: §5.4 · pp. 26–27, Figure 9 · p. 28

5.5 Discussion

• The experiments indicate construction-specific alignment, distance as a first-order choice, and gradual rather than catastrophic noise-related accuracy loss; the stability theorem’s behavior is observed empirically, not proved end to end.Diffusion distance’s advantage is consistent with its more global random-walk geometry, particularly for dense visibility graphs.Source: §5.5 · p. 27

6 Conclusion and Future Directions

• CGSSN with diffusion distance is the strongest overall default in the studied benchmarks, while the best graph construction depends on the signal's discriminative structure.OPN suits ordinal information, k-NN graphs suit discriminative reconstructed geometry, and visibility graphs can be useful when parameter-free construction and interpretability matter.Source: §6 · p. 28
• Diffusion distance consistently improves on shortest-path alternatives across the tested graph types, making it the preferred starting point when added computation is acceptable.Source: §6 · p. 28
• Embedding and graph parameters for transition and proximity constructions have heuristics that do not always agree across signal classes, while large visibility or k-NN graphs remain computationally burdensome.Symbolic OPN and CGSSN are plausible starting points for very long series because they keep the vertex set manageable.Source: §6 · p. 28
• On PowerCons, CGSSN maintains the highest F1 at every noise level, while HVG falls to the majority-class baseline even on clean data.Source: Figure 10 · p. 29
• The study covers only univariate series; full-chain stability from raw signal through network and graph-derived matrix remains open, and vectorization discards diagram-level information.Source: §6 · p. 29