Topological Data Analysis

Contents

• Introduction and overview
• 0. Refresher: topology, distances, algebra
• 1. Simplices and simplicial complexes
• 2. From point cloud to complex: Rips and Čech
• 3. Simplicial homology
• 4. Persistent homology: the algorithm
• 5. Diagrams, barcodes and landscapes
• 6. The Mapper algorithm
• 7. Stability and statistics
• 8. TDA × machine learning
• 9. Hands-on: GUDHI, scikit-tda, ripser
• 10. Course research notes — Inria Datashapes (Oudot)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an ML engineer who feels that means and variances are not enough to describe data made of clusters, loops or cavities. Empirical first: each topic starts from an observation — two datasets with the same statistics but opposite topologies, a hole that vanishes as soon as the scale ε is poorly chosen — and only then names the tools: simplices, Rips complexes, persistence diagrams.

The module teaches how to read the shape of data, a complement to the linear methods and to the GNNs of the program.

What you will be able to do

• Build simplicial complexes (Rips, Čech) from a point cloud and understand what they encode.
• Compute simplicial homology groups by hand on small complexes.
• Run the persistent homology algorithm and read diagrams, barcodes and landscapes.
• State the stability theorems and leverage them to do statistics on diagrams.
• Vectorize persistence in order to plug it into a machine learning pipeline.
• Apply the Mapper algorithm to visually explore a complex dataset.
• Carry out TDA in practice with the GUDHI, scikit-tda and ripser libraries.

Official objectives and syllabus (2026-2027 catalog)

The official course description presents topological data analysis as “a recent branch of machine learning and data mining”, whose idea is to leverage tools from algebraic topology to analyze complex datasets whose observations lie on or near non-trivial geometric structures, which can fool classical methods.

The goal is to familiarize students with this topic “at the crossing of pure mathematics, applied mathematics and computer science”, with an emphasis on the methods, their theoretical guarantees and hands-on work on complex data (notably multimedia: images, 3D shapes). The official course alternates lectures with exercise or machine sessions, and suggests the readings of Edelsbrunner & Harer, Oudot and Munkres (repeated in our references).

All the topics of the official syllabus are covered: singular homology (def. 3.6) and topological inference (prop. 7.4) were added earlier to calibrate these materials to the course description, and the clustering introduction to persistence (chapter 2, Definitions 2.7 and 2.9) was added against the 2026-2027 sheet, which lists it first.

Our extensions, beyond the official syllabus: the refresher chapter 0, chapter 6 (the Mapper algorithm), chapter 9 (hands-on with GUDHI, scikit-tda, ripser) and chapter 10 (the work of the Inria Datashapes team).

Official prerequisites: “solid foundations in linear and bilinear algebra”, notions of general topology, a background in statistics useful but not indispensable on the mathematics side; a background in algorithms and programming on the computer science side (the École Polytechnique engineering students must moreover have validated the FMA_51057_EP course unit).

Where this course fits in the program

Module of period 1 of M1 (36 h, 4.5 ECTS), one of the “Choose 3” electives of Period 1, preselected by the Graph × LLM route of the home page: it reads the shape that graphs and embeddings inherit. It also suits research-oriented profiles and demanding data science.

• Prerequisites — official: solid foundations in linear and bilinear algebra, notions of general topology, a background in algorithms and programming. Internally: the probabilistic background of the Refresher in Statistics and linear algebra (vector spaces, eigenvalues). The refresher chapter 0 covers topology, distances, algebra and the graph vocabulary used here (components, cliques, cycles), so no graph course is assumed.
• Downstream modules — Digital Representation and Analysis of Shapes, a sibling Period 1 option, recalls chapters 3–4 in its chapter 9 and adds its own alpha-complex filtration. In Period 2, Graph ML classifies graphs with kernels and GNNs, the setting of the graph lab of ch. 9; in M2, Advanced GNN studies the 1-WL limit that topological descriptors can bypass.
• A bridge, not a topic — Analysis and Deep Learning on Geometric Data (M2) teaches no persistence, but its heat kernel signature is the filtration function of the graph lab of ch. 9; combining the two is a project subject below. TDA is also a strong marker for a research orientation, Steve Oudot’s Inria Datashapes team supervising work along this line.

Canonical statements. Other LLGA pages link here instead of re-deriving: simplicial homology, the standard persistence algorithm and the bottleneck stability theorem.

Course outline

• Refresher: topology, distances, algebra — the topological and algebraic veneer indispensable for the rest of the course.
• Simplices and simplicial complexes — the bricks that approximate a continuous space from points.
• From point cloud to complex: Rips and Čech — building a shape at several scales from raw data, and a first look at persistence through clustering (single linkage, density persistence).
• Simplicial homology — counting the components, loops and cavities of a complex.
• Persistent homology: the algorithm — tracking the appearance and disappearance of holes as the scale grows.
• Diagrams, barcodes and landscapes — the canonical representations of persistence, and their uses.
• The Mapper algorithm — an exploratory map of a dataset from a function of interest.
• Stability and statistics — why persistence resists noise, and how to do statistics with it.
• TDA × machine learning — plugging persistence into standard ML pipelines.
• Hands-on: GUDHI, scikit-tda, ripser — going from theory to code on real data.
• Course research notes — Inria Datashapes (Oudot) — a tour of the research work of the Inria Datashapes team.
• Exercises, Projects and assessment and References — systematic training, project subjects with a sample exam, and sources to go further.

Session plan

36 h in class = 9 blocks of 4 h. The volume is the one of the SynapseS 2026–2027 sheet: “36 hours in person (9 blocks or slots)”, without a lecture / small-class split; the sheet lists its topics but publishes no session-by-session programme, so the split below is our proposal for covering these notes in nine blocks, in the order of the official topic list (clustering introduction to persistence first, in block 2).

Level 1 = foundations (refreshers, definitions, first complete computations), 2 = core theory and algorithms, 3 = advanced material (stability theorems, learning with persistence); the level never goes down from one session to the next.

Self-study, outside the 36 h (about 2 h in total): ch. 10 Course research notes — Inria Datashapes (Oudot), which supplies the papers of Ex. 11 (≈ 2 h, plus the reading of the chosen paper).

How to study this module

• Do the refresher section without skipping it: the topological vocabulary (open sets, connectedness, distances) is used as-is everywhere afterwards.
• Compute by hand the homology of small complexes (a few triangles) before running ripser: the algorithm becomes crystal clear once the trivial cases are mastered.
• Draw the barcodes: a long feature is a true signal, a collection of short features is noise — the eye gets trained.
• Simulate: add noise to a circle, a union of two circles, and observe the stability of the diagrams promised by theory.
• Redo the exercises of each section before moving on to the next; the final software implementation reuses all of them.
• For a project or an internship, confront TDA early with a dataset familiar to you: it is the best test of understanding.

0. Refresher: topology, distances, algebra

Classical machine learning treats a point cloud \mathcal{X} \subseteq \mathbb{R}^d as a collection of individuals; topological data analysis (TDA) treats it as a space whose shape we want to understand: how many pieces, loops, cavities? Three toolboxes are needed: distances (they build the complexes of ch. 2), a bit of topology (it defines shape equivalence), and linear algebra over \mathbb{F}_2 (it makes homology computable).

Module outline. Chapters 1 to 3 build the theory: simplices, complexes, homology — with each time the complete computation on human-sized examples. Chapter 4 is the algorithmic heart (persistence, boundary matrix, reduction demonstrated step by step).

Chapter 5 gives the statistical objects (diagrams, barcodes, landscapes) and chapter 6 the Mapper algorithm, which needs only complexes and clustering; chapter 7 proves the guarantees (stability theorems) on which the bridges toward learning of chapter 8 rest. Chapter 9 puts everything into code, and chapter 10 presents the research of the teaching team.

1. Simplices and simplicial complexes

Concrete scene: a clustering with a “perfect” score that still misses a loop in the data — say, a cyclic process that the clusters cut into pieces. To see such a loop, a dataset must be turned into a space made of points, edges, triangles and their higher analogues; this chapter defines these building blocks, the simplices, and the complexes they form.

A graph can only represent binary relations. To encode ternary relations (three points close to one another), quaternary ones… at the end of which live loops and cavities, we generalize edges and triangles: these are the simplices. The whole rest of the course rests on this single generalization.

2. From point cloud to complex: Rips and Čech

Given a cloud \mathcal{X} = \{x_1, \dots, x_n\} \subseteq \mathbb{R}^d sampled “on” an unknown shape M, how do we build a complex whose realization has the same shape as M? The idea: grow balls around the points and connect the balls that intersect. Two families stand out, with an accuracy/cost trade-off that Proposition 2.4 quantifies.

A first look at persistence: clustering across scales

The official course introduces persistence through a clustering application, before any homology: dimension 0 only needs connected components.

Watch the Rips filtration of Definition 2.2, \{\mathrm{Rips}_\varepsilon(\mathcal{X})\}_{\varepsilon \geq 0}, and keep only its graph: as \varepsilon grows, the components of the \varepsilon-neighbourhood graph merge, and each merge is an event that can be recorded.

3. Simplicial homology

This chapter turns geometry into algebra, so that holes can be counted by computing ranks of matrices. At each dimension k, we build a vector space of k-chains (formal combinations of k-simplices); the boundary operator \partial_k satisfies \partial_{k-1} \circ \partial_k = 0 (Proposition 1.3). Homology measures the failure of exactness: cycles that are not boundaries.

This chapter and the next are the master’s reference for simplicial homology and persistence. The Shapes module, ch. 9 recalls them and adds its own alpha-complex filtration.

4. Persistent homology: the algorithm

Let us come back to the data. At which scale \varepsilon should we build the Rips complex? Too small: dust of points. Too large: one contractible ball. The answer of persistence: all scales at once, with a ledger that records, for each topological feature, its birth and its death. Features that live long are the “true hole” candidates; ephemeral ones are noise.

# Standard persistence algorithm (Edelsbrunner-Letscher-Zomorodian,
# Zomorodian-Carlsson), over F2. low[j] = row of the last 1 of column j.
import numpy as np

def persistence(M):                        # M : m x m boundary matrix (0/1)
    m = M.shape[1]
    R = (M % 2).astype(np.uint8)
    pivot = {}                             # low index -> column that owns it
    pairs, born = [], []
    for j in range(m):
        while True:
            nz = np.nonzero(R[:, j])[0]
            if len(nz) == 0:               # zero column: a class is born at j;
                born.append(j)             # it dies if a later column has low = j
                break
            low = int(nz[-1])
            if low not in pivot:           # free pivot: pair (low, j), bar [low, j)
                pivot[low] = j
                pairs.append((low, j))
                break
            R[:, j] ^= R[:, pivot[low]]    # column addition (XOR in F2)
    essential = [j for j in born if j not in pivot]    # never killed: bars [j, inf)
    return pairs, essential

# Example 4.5 with 0-based indices (simplex k of the text is row/column k - 1)
cols = {5: [1, 2], 6: [2, 3], 7: [3, 4], 8: [1, 3], 9: [5, 6, 8], 10: [1, 4]}
M = np.zeros((10, 10), dtype=np.uint8)
for j, rows in cols.items():
    M[[r - 1 for r in rows], j - 1] = 1
print(persistence(M))   # ([(1, 4), (2, 5), (3, 6), (7, 8)], [0, 9]): the barcode below

5. Diagrams, barcodes and landscapes

The barcode is a combinatorial object; to confront it with statistics — comparing, testing, averaging — it must be given a geometric habitat. Two representations dominate: the persistence diagram (point cloud of the half-plane, carrier of Wasserstein-type distances) and the landscape (a function from \mathbb{R} to \mathbb{R}, which transports diagrams into a Hilbert space).

6. The Mapper algorithm

Persistence reads a cloud at all scales; Mapper (Singh, Mémoli, Carlsson, 2007) summarizes it into an interpretable graph — it is the TDA tool most used in industry, because it produces a visualization that the eye of a domain expert knows how to read: arms, flares, isolated groups.

7. Stability and statistics

The whole practical value of persistence lies in one theorem: two close functions have close diagrams. Without it, the diagram of a noisy cloud would mean nothing — an infinitesimal perturbation could change it utterly. With it, TDA becomes a statistic: one can bound the sampling error, build confidence intervals by bootstrap, and test.

8. TDA × machine learning

A diagram is neither a vector nor a probability: it is a variable-size multiset of the half-plane. To plug it into a classifier — SVM, forest, network — one must either vectorize it (landscapes, images), put it into a kernel, or turn it into a differentiable layer. This chapter is the bridge toward the heart of the master’s program; it ends with the flagship applications: shapes, neuroimaging, sensor networks.

9. Hands-on: GUDHI, scikit-tda, ripser

This chapter turns the theory into code. Three tools cover the workflow: GUDHI (complexes), ripser (fast Rips) and scikit-tda (persim: distances, visualizations). The labs make the canonical shapes speak — circle, two circles, sphere, torus, with noise — then measure stability and feed diagrams to a classifier. The last two labs classify molecular graphs by their persistence and draw a Mapper graph.

# Lab 1 -- Rips persistence with GUDHI: the noisy circle
import numpy as np, gudhi
from gudhi import RipsComplex

t = np.linspace(0, 2*np.pi, 200, endpoint=False)
X = np.stack([np.cos(t), np.sin(t)], 1) + 0.05*np.random.randn(200, 2)

rips = RipsComplex(points=X, max_edge_length=2.0)
st = rips.create_simplex_tree(max_dimension=2)
st.compute_persistence(homology_coeff_field=2, min_persistence=0)

dgm = {k: st.persistence_intervals_in_dimension(k) for k in (0, 1)}
h1 = dgm[1][np.argsort(dgm[1][:, 1] - dgm[1][:, 0])[-1]]   # longest H1 bar
print("main hole: birth %.3f, death %.3f" % tuple(h1))
# expected: birth ~0.15 (largest gap), death ~1.6 (close to sqrt(3)) -- cf. example 5.2
pers = st.persistence(homology_coeff_field=2)   # keep F2 for the plots (GUDHI's default is 11)
gudhi.plot_persistence_barcode(pers); gudhi.plot_persistence_diagram(pers)

# Lab 2 -- ripser + persim: bottleneck and stability to resampling
from ripser import ripser
from persim import plot_diagrams, bottleneck

def sample_circle(n, r, sigma):
    t = np.random.rand(n) * 2*np.pi
    return np.stack([r*np.cos(t), r*np.sin(t)], 1) + sigma*np.random.randn(n, 2)

D0 = ripser(sample_circle(200, 1, .05))['dgms']
D1 = ripser(sample_circle(200, 1, .05))['dgms']
print("d_b(H1) =", round(bottleneck(D0[1], D1[1]), 3))   # ~ 0.05-0.1: order of the noise

# vary sigma: d_b is smallest near the reference noise 0.05 and grows as sigma
# moves away from it -- numerical illustration of th. 7.1
for sigma in (.01, .05, .1, .2):
    D = ripser(sample_circle(200, 1, sigma))['dgms']
    print(f"sigma={sigma:4.2f}  d_b={bottleneck(D0[1], D[1]):.3f}")

# Lab 3 -- landscapes and classification (sklearn): circle vs two circles
from gudhi.representations import Landscape, DiagramSelector
from sklearn.svm import SVC
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import cross_val_score

def diag(n):
    """H1 diagram of a cloud made of k = 1 or 2 random circles, and k"""
    k = np.random.randint(2) + 1
    pts = [sample_circle(n, r, .05) + np.random.randn(2)*2.5 for r in (.6, 1.3)][:k]
    return ripser(np.concatenate(pts))['dgms'][1], k

data = [diag(100) for _ in range(60)]
X = [d for d, _ in data]                           # 60 H1 diagrams
y = [k for _, k in data]                           # label = number of circles generated
vec = make_pipeline(DiagramSelector(), Landscape(num_landscapes=3, resolution=100))
model = make_pipeline(vec, SVC(kernel='rbf'))
print(cross_val_score(model, X, y, cv=5).mean())   # expected ~ 0.95-1.0

The label is the number of circles that generated the cloud, never computed from the diagram itself; a label read off the bars would let the classifier relearn its own threshold. The few errors come from draws where the two circles overlap.

# Lab 4 -- graph classification: extended persistence of the HKS + sliced Wasserstein kernel
import numpy as np, gudhi
from gudhi.representations import SlicedWassersteinKernel
from scipy.linalg import eigh
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV, StratifiedKFold, cross_val_score

def load_tu(path, name="MUTAG"):                 # TUDataset text files -> [(n, edges)], labels
    f = lambda s: np.loadtxt(f"{path}/{name}_{s}.txt", delimiter=",", dtype=int)
    gid, y, A = f("graph_indicator") - 1, f("graph_labels"), f("A") - 1
    first = np.searchsorted(gid, np.arange(len(y)))     # index of each graph's first node
    graphs = [(n, []) for n in np.bincount(gid)]
    for u, v in A[A[:, 0] < A[:, 1]]:                   # each undirected edge once
        graphs[gid[u]][1].append((u - first[gid[u]], v - first[gid[u]]))
    return graphs, y

def hks(n, edges, t):                            # heat kernel signature of each node
    W = np.zeros((n, n))
    for u, v in edges: W[u, v] = W[v, u] = 1
    d = np.maximum(W.sum(1), 1)
    lam, phi = eigh(np.eye(n) - W / np.sqrt(np.outer(d, d)))   # L_sym = I - D^-1/2 A D^-1/2
    return (np.exp(-t * lam) * phi**2).sum(1)

def ext_dgms(n, edges, t=1.0, min_pers=1e-5):    # extended persistence of the HKS filtration
    f, st = hks(n, edges, t), gudhi.SimplexTree()
    for v in range(n): st.insert([v], filtration=f[v])
    for u, v in edges: st.insert([u, v], filtration=max(f[u], f[v]))
    st.extend_filtration()
    return [np.array([p for _, p in D]).reshape(-1, 2)  # for a graph: Ord0, Rel1, Ext0, Ext1
            for D in st.extended_persistence(min_persistence=min_pers)]

graphs, y = load_tu("MUTAG")                     # 188 molecules, 125 of them mutagenic
D = [ext_dgms(n, e) for n, e in graphs]
K = sum(SlicedWassersteinKernel(num_directions=10, bandwidth=1.0)
        .fit_transform([d[i] for d in D]) for i in range(4))   # one kernel per diagram type
svm = GridSearchCV(SVC(kernel="precomputed"), {"C": [0.01, 0.1, 1, 10, 100]}, cv=5)
outer = StratifiedKFold(10, shuffle=True, random_state=0)
print(cross_val_score(svm, K, y, cv=outer).mean())  # nested CV: C chosen inside

The filtration is the heat kernel signature of each node on the graph, extended to edges by the maximum, and extended persistence also records the classes that never die (components and rings), which ordinary persistence would leave as infinite bars. GUDHI’s kernel is the one of 8.1, with bandwidth in the role of \varepsilon.

Expected: about 0.90 at t = 1, and between 0.87 and 0.91 over three outer splittings and t \in \{0.1, 1, 10\} — without the atom types. The Weisfeiler–Lehman kernel, which uses them, gives 0.84 to 0.87 under the same nested protocol (Graph ML module, lab sheet of ch. 2 — preview).

Questions for the lab:

1. Run ext_dgms on two disjoint triangles and on the 6-cycle, which the 1-WL test cannot tell apart (Advanced GNN module, ch. 2 — preview). Why are both diagrams empty? Rerun with min_pers=-1: what separates the two graphs now? (The HKS is constant on these graphs, so every point lies on the diagonal; the kept points count components and rings, as Proposition 3.4 does.)
2. Replace the four kernels by persistence images of the same diagrams and an RBF SVM: which representation of ch. 5 and 8 wins, and at what cost?

# Lab 5 -- Mapper with GUDHI: a noisy circle becomes a cycle graph
import numpy as np, networkx as nx
from gudhi.cover_complex import MapperComplex
from sklearn.cluster import AgglomerativeClustering

rng = np.random.default_rng(0)
t = rng.uniform(0, 2*np.pi, 1000)
X = np.stack([np.cos(t), np.sin(t)], 1) + 0.05*rng.standard_normal((1000, 2))
f = X[:, :1]                                     # filter: the height x (Definition 6.1)

mapper = MapperComplex(resolutions=[10], gains=[0.3],     # 10 intervals, 30 % overlap
            clustering=AgglomerativeClustering(n_clusters=None, linkage="single",
                                               distance_threshold=0.3))
mapper.fit(X, filters=f, colors=f)
G = mapper.get_networkx()
n, m, c = G.number_of_nodes(), G.number_of_edges(), nx.number_connected_components(G)
print(n, m, c, "loops:", m - n + c)              # Proposition 3.4: expected one loop

Expected: about 16 or 17 nodes, as many edges, one component, hence one loop — the hole of the circle, seen without any homology computation. Ex. 10 asks you to rebuild this pipeline by hand.

10. Course research notes — Inria Datashapes (Oudot)

The module is taught by Steve Oudot, Inria senior researcher (team Datashapes, Inria center of Saclay — the former Geometrica team), member of the computer science laboratory (LIX) of École Polytechnique. The Datashapes team is, with those of Gunnar Carlsson (Stanford) and Herbert Edelsbrunner (IST Austria), one of the three worldwide cradles of TDA: it produced the modern stability theorems, the GUDHI software, and the bridge toward machine learning. Four axes in direct connection with the program; the papers are to be read and presented in project (Exercise 11).

Exercises

1. ★ Boundary of the boundary over \mathbb{Z}. Detail the proof of Proposition 1.3 in the case k = 3 (tetrahedron): write \partial[a,b,c,d], then \partial(\partial[a,b,c,d]), and verify the term-by-term cancellation with the signs (-1)^i.

2. ★ Sphere and torus. Take up the complete computation 3.3 on the torus as a “square with identified edges” triangulated (2 triangles, 3 edges, 1 vertex — explain why this is not a simplicial complex but only a “Δ-complex”, and why the boundary computation still makes sense): show \beta_0 = 1, \beta_1 = 2, \beta_2 = 1, \chi = 0. What is the minimal abstract complex for the “real” torus (Császár, 7 vertices)?

3. ★ Persistence by hand. Take up Example 4.5 while permuting indices 9 (triangle) and 10 (edge [v_1v_4]) — the filtration remains legal if edge [v_1v_4] appears before the triangle (the triangle does not contain it). Recompute the barcode; which bars change, which are invariant? Verify with GUDHI (note 4 of the hands-on chapter).

4. ★ Bottleneck and Wasserstein. For \mathcal{D}_1 = \{(1, 3), (2, 2.1)\} and \mathcal{D}_2 = \{(1.2, 2.8)\}: compute d_B, then d_{W,1} (sum of the displacements, optimal matching via the diagonal). Build two diagrams with the same d_B but arbitrarily large d_{W,1} — and interpret in terms of noise sensitivity (ch. 7).

5. ★ Landscapes. Compute \lambda(1, \cdot) and \lambda(2, \cdot) for the diagram \{(1, 3), (2, 4)\} (draw the tents; note that they cross at t = 2.5). Verify the bound of Proposition 5.6 against the diagram \{(1, 3), (2, 4.2)\}.

6. ★★ Homology of graphs. Prove the formula \beta_1 = m - n + c (Proposition 3.4) by induction on the number of edges (adding an edge between two components decreases c and leaves \beta_1 unchanged; within one component, it increases \beta_1). Application: what is \beta_1 of the Petersen graph? of a k \times k grid?

7. ★★ Nerve theorem in dimension 1. Let \mathcal{U} be a family of open intervals of \mathbb{R}. Show that the nerve of \mathcal{U} has the same homotopy type as the union:

   • (i) each component of the union is an interval (connected, hence contractible);
   • (ii) the vertices of the nerve within one component are connected by a path of edges;
   • (iii) using Helly’s theorem in dimension 1 — intervals that intersect pairwise have a common point — show that the nerve is the clique complex of the intersection graph, then prove that each of its components is contractible.

   Hint: remove the interval with the largest left endpoint; its neighbors all contain a common point, so it is attached along a simplex, and argue by induction.

8. ★★ Jung bracket. Verify Example 2.5 numerically (balls and intersections for an equilateral triangle of side 1), then prove the second inclusion of Proposition 2.4 in the plane: every set of diameter \delta of \mathbb{R}^2 fits in a disk of radius \delta/\sqrt{3} (consider the smallest enclosing disk; if its center is not on the boundary…).

9. ★★ DTM stability. Let \mathcal{X} be a sample and \mathcal{X}' obtained by adding an outlier at distance L from the rest. Bound the variation of d_B for the Rips complex (via Proposition 7.3: here d_H(\mathcal{X}, \mathcal{X}') = L, so the bound becomes 2L).

   Explain why the DTM version of ch. 7 degrades only by O(L\sqrt{w/k}), where w is the weight of the outlier and k the mass parameter (the DTM is k^{-1/2}-Lipschitz with respect to the Wasserstein-2 distance between measures).

10. ★★ Mapper. Implement Mapper (30 lines: overlapping histogram + single-linkage from scipy + networkx) on MNIST reduced to 3 dimensions by UMAP; compare two filters (density vs eccentricity). Look for “arms” and loops of the graph and inspect the digits they contain, as Example 6.2 did for tumors (ch. 6).

11. ★★★ Paper. Choose a paper from ch. 10 (Oudot 2015; Chazal et al. 2009/2016; ToMATo 2013; sliced Wasserstein 2017; PersLay 2020), read it and present it in 10 minutes: problem, key theorem, sketched proof, experimental result, limitation. Grid: one figure re-explained, one figure reproduced, one open question.

12. ★★★ Guiding project (optional). Compute the H1 diagrams of the clique complexes of a citation graph (ogbn-arxiv, described in the Graph ML module, ch. 7 — preview) and train a sliced Wasserstein kernel SVM to predict the topic; compare with a GNN (Advanced GNN module — preview); what information does each family capture?

Projects and assessment

The official assessment, as quoted in the fiche above, is a “written final exam, with the possibility of adding a graded lab course” (description of the 2026–2027 sheet; its LLGA assessment section is empty). The subjects below can serve as that graded lab course or as a course project, and the written exam is a sample of the final exam. Everything in this section is a proposal, not an official rule.

The projects exercise mainly O4 (graph-structured data: graph filtrations, graph classification, the 1-WL limit) and O1 (ML foundations: kernels, clustering, auto-encoders, honest evaluation), with O7 (hands-on work with GUDHI and ripser on public data) throughout and O3 for the transformer subject. The ToMATo subject is a course-sized version of the TDA option of the Year 1 capstone Y1.1 (end-of-year projects).

Solo projects

1. [Solo · ≈ 20 h] Persistent homology from scratch, then fast. Papers: Chen and Kerber (2011), Persistent homology computation with a twist; Bauer (2021), Ripser.
   • Question: how much of ripser’s speed comes from the clearing (“twist”) optimisation alone, and how much from its other ingredients: cohomology, an implicit boundary matrix that is never stored, and apparent pairs?
   • Work: in NumPy, build the Rips filtration up to dimension 2 and its boundary matrix (Definition 4.3), and reduce it with the standard algorithm (Theorem 4.4). Then add clearing: reduce the dimensions from the highest down, and when column j ends with \mathrm{low}(j) = i, set column i to zero without reducing it, since a simplex that gives birth has a zero reduced column.
   • Data: Example 4.5, then noisy samples of a circle, a sphere and a torus, checked against GUDHI.
   • Success: diagrams identical to GUDHI’s (bottleneck distance below 10^{-9}) on every test cloud; time and memory curves against n and the maximal dimension for both reductions and for ripser, with the gain of clearing explained.
   • Deliverables: code with unit tests, 4–6 page report, 10-minute talk. Chapters: ch. 1, ch. 2, ch. 4, ch. 9.
2. [Solo · ≈ 20 h] Clustering that resists chaining: ToMATo against single linkage and DBSCAN. Paper: Chazal, Guibas, Oudot and Škraba (2013), ToMATo (10.3). Connects this course to Machine Learning, section 7.1 and to the TDA option of the capstone Y1.1.
   • Question: when does density persistence beat single linkage and DBSCAN, and can the prominence threshold \tau be read off the diagram without labels?
   • Work: scale Examples 2.8 and 2.10 to synthetic data — two or three Gaussian blobs joined by sparse bridges, plus 0–5 % uniform outliers. Then cluster the sentence embeddings of four 20 Newsgroups categories (scikit-learn’s fetch_20newsgroups, encoded with a small sentence-transformers model such as all-MiniLM-L6-v2). Use GUDHI’s Tomato, scipy’s single linkage and scikit-learn’s DBSCAN, with \tau taken at the largest gap of the diagram.
   • Success: adjusted Rand index against the labels for each method and outlier rate, mean and spread over 5 seeds; at least one setting where single linkage collapses through a bridge and ToMATo does not, explained with Definition 2.9.
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 2, ch. 7, ch. 10.
3. [Solo · ≈ 20 h] Which bars are signal? Confidence sets for persistence diagrams, reproduced. Paper: Fasy, Lecci, Rinaldo, Wasserman, Balakrishnan and Singh (2014), Confidence sets for persistence diagrams, Annals of Statistics.
   • Question: can a bootstrap band separate the true holes from noise without knowing the shape, as the bootstrap note of ch. 7 promises?
   • Work: implement the subsampling band of the paper. With q the 95 % quantile of the Hausdorff distance between subsamples of size b \ll n and the full cloud, the paper bounds d_H to the hidden shape by c = 2q (its Theorem 3, stated for Čech diagrams). Proposition 7.3 turns it into the bottleneck bound 2c for Rips diagrams. Add the bottleneck bootstrap as a variant: the 95 % quantile of d_B between replica diagrams and the full diagram.
   • Rule: a point farther from the diagonal than the bound, in the sup norm, cannot be matched to it, so its bar is declared significant (Definition 5.3).
   • Data: circle, two circles, sphere and torus at increasing noise levels, then one real cloud of your choice (for example a 3D scan from the Stanford repository).
   • Success: on noiseless and low-noise circles, whose true Rips diagram is known (one H_1 point (0, r\sqrt{3}) for radius r, Example 5.2), an empirical coverage of at least 95 %, with its excess reported, since the paper calls the subsampling band very conservative; and significant bars matching the Betti numbers of each shape at low noise.
   • Deliverables: code, 4–6 page report, 10-minute talk. Chapters: ch. 5, ch. 7, ch. 9.

Group projects

1. [Group of 3 · ≈ 30 h each] Topological descriptors versus GNNs for graph classification. Papers: Carrière, Chazal, Ike, Lacombe, Royer and Umeda (2020), PersLay; Xu, Hu, Leskovec and Jegelka (2019), GIN. Connects this course to Graph ML, ch. 2 and 5 and Advanced GNN, ch. 2.
   • Question: what do persistence diagrams of graph filtrations capture that the 1-WL test, and hence message passing, cannot — and does it help accuracy?
   • Work: on MUTAG, PROTEINS and IMDB-BINARY (TUDataset, Morris et al. 2020), compare the sliced Wasserstein kernel on extended persistence of HKS filtrations (Lab 4, several t), PersLay, the WL subtree kernel and a GIN, under the fair protocol of Errica et al. (2020). Build at least three pairs of 1-WL-indistinguishable graphs, from two triangles against the 6-cycle to larger regular pairs, and test which descriptor separates them.
   • Split: filtrations and kernels; PersLay and GIN in PyTorch; evaluation protocol and the 1-WL study.
   • Success: 10-fold accuracy (mean ± standard deviation) of the four methods on the three datasets, and a table of the indistinguishable pairs saying, for each descriptor, whether it separates them and why (Proposition 3.4, Theorem 4.2).
   • Deliverables: code, joint 8–10 page report, 20-minute talk. Chapters: ch. 3, ch. 4, ch. 8, ch. 9.
2. [Group of 3 · ≈ 30 h each] The shape of transformer embedding spaces. Paper: Naitzat, Zhitnikov and Lim (2020), Topology of Deep Neural Networks, JMLR. Connects this course to Large Language Models (M2) and to Text Mining and NLP (Period 2).
   • Question: Naitzat et al. found that ReLU networks simplify the topology of the data layer after layer. Does the same hold for the hidden states of a small pretrained transformer, and does fine-tuning change it?
   • Work: take bert-base-uncased (or GPT-2 small) from Hugging Face and the SST-2 sentences. At every layer, before and after fine-tuning on SST-2, extract sentence vectors (mean of the token states). For each layer and class, compute Rips persistence of the L2-normalised vectors (ripser, 1,000-point subsamples, H_0 and H_1), landscapes, Betti curves and a Mapper graph. Their Euclidean distance ranks pairs as the cosine distance does but is a metric, which the stability results of ch. 7 need.
   • Split: embeddings and fine-tuning; persistence and statistics; Mapper and interpretation.
   • Success: per-layer summaries with bootstrap bands (ch. 7) over at least 5 subsamples, and every claimed change, between layers or across fine-tuning, larger than its band.
   • Deliverables: code, joint 8–10 page report, 20-minute talk. Chapters: ch. 2, ch. 5, ch. 6, ch. 7, ch. 9.
3. [Group of 3 · ≈ 30 h each] A topology-preserving auto-encoder on images. Paper: Moor, Horn, Rieck and Borgwardt (2020), Topological Autoencoders, ICML. Connects this course to Deep Learning (Period 1) and covers the multimedia practice that the official syllabus asks for.
   • Question: does a loss on the 0-dimensional persistence pairs of each mini-batch keep the connectivity of the data in the latent space, and at what cost in reconstruction?
   • Work: the 0-dimensional pairs of a Rips filtration are the edges of a minimum spanning tree (Definition 2.7). The loss takes the MST edges of the input batch and penalises the squared gap between their lengths in the input space and in the latent space, then does the same with the MST edges of the latent batch. Implement it in PyTorch with scipy’s MST and compare with a plain auto-encoder, PCA and UMAP.
   • Data: the nested Spheres of the paper, Fashion-MNIST, and COIL-20 (Nene, Nayar and Murase, 1996), where the 72 views of each rotating object form a loop.
   • Split: loss and training; image experiments; evaluation and the H_1 study on COIL-20.
   • Success: over 3 seeds, a better trustworthiness (scikit-learn) and density-KL measure of the paper than the plain auto-encoder on all three datasets, at a reconstruction error within 10 % of it; on COIL-20, the number of objects whose latent trace keeps a long H_1 bar, for each method.
   • Deliverables: code, joint 8–10 page report, 20-minute talk. Chapters: ch. 2, ch. 5, ch. 7, ch. 8.

Written exam (proposal)

Three hours, one handwritten A4 sheet allowed, no electronic device; four questions. Rips complexes use the diameter convention of Definition 2.2.

1. Question (5 points). Explain why persistence looks at all scales at once instead of choosing one. State the bottleneck stability theorem and explain how it makes a bootstrap confidence band meaningful. Give the main weakness of the bound and the fix proposed in ch. 7.

   Expected: at one scale the complex is either dust or one contractible ball, and a hole seen at a single scale may be noise (Example 5.2); the barcode records births and deaths, and long bars are the features.

   Theorem 7.1: for tame f, g on a finite complex, d_B\big(\mathrm{Dgm}(f), \mathrm{Dgm}(g)\big) \leq \|f - g\|_\infty , extended to \delta-interleaved modules by Theorem 7.2; hence d_B \leq 2\, d_H for Rips diagrams (Proposition 7.3). Resampled diagrams therefore move by a controlled amount, and the quantile c of their bottleneck distances gives a band: bars longer than 2c are significant.

   Weakness: the sup norm, since one outlier at distance L makes d_H = L. Fix: the distance-to-measure, Lipschitz in Wasserstein-2, where the outlier only costs its mass.

2. Question (7 points). Let S be the four corners of the unit square and R the corners of the rectangle [0, 1] \times [0, 1.2].

   1. Give the H_0 and H_1 barcodes of the Rips filtrations of S and of R. (b) Compute the bottleneck distance between the two H_1 diagrams.

   2. Compute d_H(S, R) and check Proposition 7.3. (d) Check Theorem 3.5 on the Rips complex of R at scale \varepsilon = 1.3.

   Expected: (a) for S, the four sides enter at 1, so H_0 is [0, 1) three times and [0, \infty).

   The 4-cycle is born at 1, and at \sqrt{2} \approx 1.414 the diagonals, all triangles and the tetrahedron enter together, so H_1 is [1, \sqrt{2}).

   For R, the sides of length 1 enter at 1 and those of length 1.2 at 1.2, so H_0 is [0, 1) twice, [0, 1.2) and [0, \infty). The 4-cycle closes at 1.2 and the diagonals have length \sqrt{2.44}, so H_1 = [1.2, \sqrt{2.44}) \approx [1.2,\ 1.562) .

   2. Matching the two points costs \max(0.2,\ 0.148) = 0.2; sending both to the diagonal costs \max(0.207,\ 0.181) = 0.207; hence d_B = 0.2 .

   3. Two corners move by 0.2, so d_H = 0.2 and d_B = 0.2 \leq 2\, d_H = 0.4. (d) At 1.3 the complex is the hollow 4-cycle: \chi = 4 - 4 = 0 = \beta_0 - \beta_1 = 1 - 1.

3. Question (5 points). (a) Show that adding one edge e = uv to a finite graph either decreases \beta_0 by one and leaves \beta_1 unchanged, or leaves \beta_0 unchanged and increases \beta_1 by one. (b) Deduce that, when all pairwise distances are distinct, the death times of the 0-dimensional barcode of a Rips filtration are the edge lengths of a minimum spanning tree.

   Expected: (a) if u and v lie in different components, the chain u + v was not a boundary, so \mathrm{rank}\, \partial_1 grows by one: \beta_0 drops by one and \dim Z_1 is unchanged.

   Otherwise a path already joins them and u + v was a boundary, so the rank is unchanged. Then \dim Z_1 = m - \mathrm{rank}\, \partial_1 grows by one with m, and since B_1 = 0 for a graph, \beta_1 grows by one.

   2. Triangles and higher simplices do not change \partial_1, hence not H_0. Edges enter by increasing length, and an edge kills an H_0 class exactly when it joins two components — Kruskal’s acceptance rule. Kruskal’s output is a minimum spanning tree (cut property), whose n - 1 edge lengths are the death times.

4. Question (3 points). A colleague claims that a sensor network covers its domain if and only if H_1 of the Rips complex of its communication graph vanishes. Give a counterexample to each direction, and say what the criterion of de Silva and Ghrist uses instead.

   Expected: three sensors at the corners of an equilateral triangle of side s equal to the communication radius, with a coverage radius r such that s/2 \leq r < s/\sqrt{3}: the Rips triangle is filled, so H_1 = 0, yet the circumcenter is not covered (Example 2.5).

   Conversely, four sensors at the corners of a square of side s equal to the communication radius: the diagonals are too long, the Rips complex is a hollow square with H_1 \neq 0, yet closed disks of radius s/\sqrt{2} cover the square.

   The real criterion is sufficient only: under r_c \geq r_b/\sqrt{3} and a fence F, a class of H_2(R, F) with non-zero boundary in H_1(F) proves coverage.

Grading rubric (proposal)

References

• H. Edelsbrunner, J. Harer, Computational Topology: An Introduction, AMS, 2010 — the reference textbook of the module: complexes, homology, persistence algorithm (ch. 1, 3, 4).
• J.-D. Boissonnat, F. Chazal, M. Yvinec, Geometric and Topological Inference, Cambridge Texts in Applied Mathematics 57, Cambridge University Press, 2018 — publisher page (free PDF on HAL): reconstruction, sampling, DTM (ch. 2, 3, 7 of the module).
• S. Y. Oudot, Persistence Theory: From Quiver Representations to Data Analysis, Mathematical Surveys and Monographs 209, AMS, 2015 — AMS page: the algebraic reading of ch. 4 (work of the team, ch. 10.1).
• F. Chazal, V. de Silva, M. Glisse, S. Y. Oudot, The Structure and Stability of Persistence Modules, Springer, 2016 — arXiv:1207.3674: interleavings, algebraic stability (ch. 7; team, ch. 10.2).
• H. Edelsbrunner, D. Letscher, A. Zomorodian, Topological Persistence and Simplification, Discrete & Computational Geometry 28, 2002 — the founding paper of the algorithm of ch. 4.
• A. Zomorodian, G. Carlsson, Computing Persistent Homology, Discrete & Computational Geometry 33, 2005 — the modules-over-a-field version (Theorem 4.2).
• D. Cohen-Steiner, H. Edelsbrunner, J. Harer, Stability of Persistence Diagrams, Discrete & Computational Geometry 37, 2007 — Theorem 7.1.
• F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, S. Y. Oudot, Proximity of Persistence Modules and Their Diagrams, SoCG 2009 — algebraic stability (Theorem 7.2; team, ch. 10.2).
• P. Bubenik, Statistical Topological Data Analysis Using Persistence Landscapes, JMLR 16, 2015 — the landscapes of ch. 5.
• F. Chazal, B. Fasy, F. Lecci, A. Rinaldo, A. Singh, L. Wasserman, Stochastic Convergence of Persistence Landscapes and Silhouettes, SoCG 2013 — the convergence of empirical landscapes (note of ch. 7).
• B. T. Fasy, F. Lecci, A. Rinaldo, L. Wasserman, S. Balakrishnan, A. Singh, Confidence Sets for Persistence Diagrams, Annals of Statistics 42(6), 2014 — the subsampling and bootstrap bands of the note of ch. 7 and of solo project 3.
• G. Singh, F. Mémoli, G. Carlsson, Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition, Eurographics Symposium on Point-Based Graphics, 2007 — the Mapper paper of ch. 6.
• M. Nicolau, A. J. Levine, G. Carlsson, Topology Based Data Analysis Identifies a Subgroup of Breast Cancers with a Unique Mutational Profile and Excellent Survival, PNAS 108(17), 2011 — Example 6.2.
• G. Petri, P. Expert, F. Turkheimer, R. Carhart-Harris, D. Nutt, P. J. Hellyer, F. Vaccarino, Homological Scaffolds of Brain Functional Networks, Journal of the Royal Society Interface 11, 2014 — the neurosciences application of ch. 8.
• V. de Silva, R. Ghrist, Homological Sensor Networks, Notices of the AMS 54(1), 2007 — sensor coverage, Rips = Čech in \ell_\infty (ch. 2, 8).
• G. Carlsson, Topology and Data, Bulletin of the AMS 46(2), 2009 — the great survey of the field.
• N. Otter, M. A. Porter, U. Tillmann, P. Grindrod, H. A. Harrington, A Roadmap for the Computation of Persistent Homology, EPJ Data Science 6:17, 2017 — the practical guide (software, pitfalls) of ch. 9.
• M. Carrière, M. Cuturi, S. Oudot, Sliced Wasserstein Kernel for Persistence Diagrams, ICML 2017 — the kernel of ch. 8.1 (team, ch. 10.4).
• M. Carrière, F. Chazal, Y. Ike, T. Lacombe, M. Royer, Y. Umeda, PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures, AISTATS 2020 — the layer of ch. 8.2.
• M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. Salakhutdinov, A. Smola, Deep Sets, NeurIPS 2017 — the sum form of permutation-invariant set functions (ch. 8.2).
• C. Hofer, R. Kwitt, M. Niethammer, A. Uhl, Deep Learning with Topological Signatures, NeurIPS 2017 — a learned input layer for diagrams, the starting point of the topological losses of ch. 8.
• F. Chazal, L. J. Guibas, S. Y. Oudot, P. Škraba, Persistence-Based Clustering in Riemannian Manifolds, Journal of the ACM 60(6), 2013 — ToMATo (ch. 10.3).
• U. Bauer, Ripser: Efficient Computation of Vietoris–Rips Persistence Barcodes, Journal of Applied and Computational Topology 5, 2021 — the fast matrix-free algorithm (ch. 9).
• Software: GUDHI (Inria Datashapes — the library of the labs); scikit-tda (ripser, persim); PersLay.