Persistent homology

Overview

Persistent homology summarises the topological features of a structure, each with a birth time and a death time, so that features which last across the analysis are separated from short-lived ones 2105.04100 §3. The paper uses it on a sequence of graphs instead of one graph. Its two feature dimensions are the 0-th and the 1-st 2105.04100 §3.

The paper says that earlier uses of persistent-homology features in deep networks treat the topology as static 2105.04100 §1. The variant below is the one zigzag persistence supplies for graphs that change over time.

Only one card on wikillm lists this concept, so this page describes one variant. Other forms of persistent homology, such as filtrations of a single complex, are not covered yet.

Variants

Zigzag persistence over a window of graphs

Zigzag persistence follows features across a sequence of graphs that are linked by inclusions alternating in direction. Each snapshot is included in the union of itself and its neighbour in the sequence. A zigzag diagram of Vietoris–Rips complexes at a fixed scale ν* is built over these inclusions. A union of two consecutive snapshots counts as a half-step, so birth and death times are integers or integers plus one half 2105.04100 §3 [Definition 3.1].

The paper turns the diagram into a zigzag persistence image (ZPI) in three steps: map the diagram to a surface of weighted Gaussians, discretise the surface on a grid, and integrate over each grid box 2105.04100 §3. The ZPI is a 100 × 100 image in the paper's appendix 2105.04100 app. A. The paper states a Wasserstein-1 stability result for the image, but the compiled text has no proof 2105.04100 §3.

In Z-GCNETs, a small CNN reads the ZPI and outputs one value per channel. These values scale the spatial and temporal graph-convolution features inside a graph-convolutional GRU forecaster 2105.04100 §4 eq. 4. The authors report that removing the zigzag part makes the forecast worse on both traffic datasets 2105.04100 tab. 5.

When to use which

Only one variant is covered, so the table compares the settings the paper explores rather than competing methods.

The paper's results are on two traffic datasets and two token networks, each with a single reported number per cell. No standard deviations or repeated runs appear in the main table 2105.04100 tab. 2. Treat the gains as author-reported until someone reproduces them.

Implementation sketch

Pseudocode for one ZPI from a window of graphs. Each step names its source; the choices the paper leaves open are marked.

# Build one zigzag persistence image from a window of tau graphs  [§3]
# Input:  tau graph snapshots on N nodes; threshold nu_star  [§5.1] [eq. 6]
# Output: a 100 x 100 grid of values  [app. A]

def zigzag_persistence_image(snapshots, nu_star):
    # Keep the edges that pass the threshold  [§5.1] [eq. 6]
    # (the paper's edge rule; see Contradictions)
    graphs = [keep_edges(g, nu_star) for g in snapshots]
    # Link neighbours by inclusions in alternating directions  [§3]
    # The paper defines the union's edges but not its weights  [§3]
    unions = [union(graphs[i], graphs[i + 1])
              for i in range(len(graphs) - 1)]
    # Vietoris-Rips complexes over the zigzag, at a fixed scale  [§3]
    # Read the birth and death time of each feature  [§3]
    diagram = zigzag_diagram(graphs, unions, dims=(0, 1))
    # Map each point to (x, y - x) and place weighted Gaussians  [§3]
    # The variance is not stated in the paper  [§3]
    surface = sum(g(mu) * gaussian(z - mu)
                  for mu in diagram for z in grid)
    # Integrate the surface over each grid box  [§3]
    return box_integrals(surface, shape=(100, 100))

Contradictions

• Filtration. The paper says the main results use the weight rank clique filtration 2105.04100 §5.2. The released code builds Vietoris–Rips complexes; see item 3 in the card's Paper vs code section. The paper's appendix B reports token results with three filtrations, and their MAPE values differ by about 3 points for Decentraland 2105.04100 tab. 8.
• Edge rule for traffic. The paper uses an RBF weight and keeps edges with weight at most ν* 2105.04100 §5.1 eq. 6. The code cuts edges whose normalised feature distance exceeds a threshold. The two rules keep different edges, since similar pairs survive under one and dissimilar pairs under the other. See the card's Paper vs code section.
• Diagram transform and grid. The paper maps the diagram to (x, y − x) 2105.04100 §3. The code uses birth and death directly. The paper's grid is 100 × 100 2105.04100 app. A, while the repository's generator defaults to 50 × 50 and no call in the repository changes it.
• Pooling in the ZPI network. The paper describes global max-pooling 2105.04100 §4 and a 5 × 5 pool 2105.04100 app. A. The code adds extra pooling between convolutions, so its pooling differs from the text.
• Size of the token data. The paper gives 285 and 206 token networks 2105.04100 §5.1. The loader's comments give 259 and 193 ZPI samples. The paper does not state how a window count maps to a network count.

Papers

• Z-GCNETs: introduces zigzag persistence images as a gate for a graph-convolutional GRU, with author-reported results on two traffic datasets and two token networks.