PaperlayerView exact revision on arXiv

Source-linked AI summary

Constructive Bounds for the Topological Expressivity of Neural Networks

Kosio Beshkov

arXiv:2610.13931v1math.ATcs.LG

TL;DR

Decision-boundary topology is less useful for regression and other non-classification tasks, motivating a measure based on the topology of network outputs. The paper constructs ReLU networks and derives architectural upper bounds for generating specified Betti numbers, including arbitrary sequences on contractible compact inputs.

  • Problem

    Decision-boundary topology is not useful for tasks such as regression, where a decision boundary is undefined, and it can ignore the topology of the data.

    Source: §1 · p. 1

  • Method

    The paper constructs ReLU-realizable images homotopy equivalent to wedge sums and products of spheres, then uses them to derive Betti-number bounds.

    Source: §3.4 · p. 9

  • Results

    The paper derives architectural upper bounds for ReLU networks to generate specified representation Betti numbers, including arbitrary nonzero sequences on contractible compact inputs.

    Source: §1.1 · p. 2, §2 · p. 3

  • Takeaways & Limitations

    Measuring the Betti numbers of a network's image accounts for both data and task and aligns better with non-classification tasks.

    Source: §1 · p. 2

    The product-of-spheres bound applies only to palindromic Betti numbers, while the wedge bound covers arbitrary sequences but requires exponentially many neurons.

    Source: §2.3 · p. 7

Abstract

from arXiv · show

The expressivity of a neural network $\Phi$ describes the class of functions that a network can express. The term topological expressivity refers to a family of measures particularly suited to understand binary classification and is often formulated in terms of the Betti numbers of a decision boundary $\beta (\Phi^{-1}(0))$. Despite its popularity, this measure is not as useful for regression and other problems that do not involve a decision boundary. Instead, we propose to study topological expressivity in terms of the Betti numbers of the output of a neural network $\beta(\Phi(X))$. We formally prove that a ReLU network with architecture $(d,\sum\limits_{k=1}^{d } \beta_k(3k+2),\sum\limits_{k=1}^{d}\beta_k(k+1))$ can express spaces homotopy equivalent to wedge sums of spheres with arbitrary Betti numbers. This gives upper bounds for any arbitrary connected ($\beta_0=1$) sequence of Betti numbers, but by constructing spaces homotopy equivalent to products of $N$ spheres of dimension $d_1,...,d_N$ we achieve much better bounds $(\sum\limits_{n=1} d_n, 3\sum\limits_{n=1}\limits^N d_n + 2N, \sum\limits_{n=1}\limits^N d_n + N) $ for Betti numbers given by $\prod_n (1+x^{d_n})$. Finally we conjecture a much stronger tight bound which gives the architectural bound $(d,d+1,d+1)$ for a space homeomorphic to the sphere.

1. Introduction

Decision-boundary topology is suited to binary classification but does not capture the topology of data or outputs in tasks such as regression. The paper proposes representational topological expressivity and derives architectural bounds for ReLU networks that generate specified Betti numbers.

1. Introduction

  • Decision-boundary topology is undefined for non-classification tasks and can ignore complex data topology even when the data are separable by a hyperplane.This limits its use for understanding the transformations networks perform in tasks beyond classification.Source: §1 · pp. 1–2
  • Representational topological expressivity measures the Betti numbers of a network's image, accounting for both the data and the task.The paper presents this measure as better aligned with non-classification tasks.Source: §1 · p. 2

1.1. Our contributions

  • Earlier studies of neural representation topology were empirical or methodological and did not explicitly connect their results to network expressivity.Source: §1.1 · p. 2
  • The paper derives architectural upper bounds for ReLU networks by constructing images homotopy equivalent to wedge sums and products of spheres.It also conjectures a tighter architecture for spaces homeomorphic to spheres.Source: §1.1 · p. 2

2. Results

This section constructs ReLU-network outputs with prescribed sphere, wedge-sum, and product topologies, relating their architectures to Betti numbers using compact contractible input sets and reduced singular homology over ℤ. It also gives linear-size constructions for products of spheres, identifies limits on their scope, and proposes a tighter sphere architecture bound supported by empirical tests in dimensions 2 and 3 but not proved in general.

2. Results

  • The results use reduced singular homology with coefficients in Z and often treat maps on compact contractible input sets; the longest proofs are in Appendix A.The paper notes that constructions either have compact supports or have the same image on Rd and a compact set.Source: §2 · p. 2

2.1. Expressing the d-sphere

  • A ReLU network of architecture (d, Wd, d + 1), with Wd = min(2d(d + 1), 3d + 2), can map a contractible set in Rd to a space homeomorphic to Sd.The construction uses hat functions in a Helly arrangement; the associated nerves are isomorphic, and the extended map's image is homeomorphic to the sphere.Source: §2 · p. 2, §2.1 · pp. 3–4

2.2. Extending the construction to wedge sums of spheres

  • Wedge constructions represent spaces with any possible Betti numbers, with network size linear in the Betti numbers.The construction places sphere supports apart and glues their images at the origin; it extends to spheres of different dimensions.Source: §2.2 · pp. 5–6

2.3. Exponential complexity in products of spheres

  • For S1 × S1, stacking two (1, 4, 2) networks gives architecture (2, 8, 4), versus the wedge-bound architecture (2, 16, 7).Independent networks realize product maps by summing their architectures.Source: §2.3 · p. 6
  • For products of spheres, network size scales linearly with the number of spheres while the sum of the resulting Betti numbers can scale exponentially.For S1 × S1 × S2, the Poincaré polynomial is (1+x)^2(1+x^2) = 1 + 2x + 2x^2 + 2x^3 + x^4, giving β = (1, 2, 2, 2, 1).Source: §2.3 · pp. 6–7
  • For the N-torus, β_k=C(N,k) and the Betti numbers sum to 2^N, while a network of shape (N,4N,2N) uses 7N neurons.The construction stacks N copies of the one-circle architecture (1,4,2).Source: §2.3 · p. 7
  • The product-sphere construction applies only to palindromic Betti sequences, whereas the wedge bound covers arbitrary sequences but requires exponentially many neurons.The text notes that product bounds can be much smaller than wedge bounds.Source: §2.3 · p. 7
  • Theorem 2.14 states that a neural network can express a space whose Betti numbers are the coefficients of a Poincaré polynomial containing the factor (1 + x^dn).Source: §2.3 · p. 7
  • Products of wedge sums are also covered: their Poincaré polynomials follow P(X ∨ Y)=P(X)+P(Y)-1 and P(X × Y)=P(X)P(Y).Source: §2.3 · p. 7

2.4. Conjectured tight and lower bounds

  • The paper conjectures that architecture (d,d+1,d+1) is a tight upper bound for expressing the sphere S^d; constructions of this shape were found for d=2,3.The passage also states that no architecture of shape (d,d,d+1) can express such a sphere.Source: §2.4 · p. 7
  • Persistent-homology diagrams from meshes of 1512 points for d=2 and 813 for d=3 reflect sphere structure, but the tests do not prove the conjecture.The study used Ripser with 800 landmarks and suggests the construction likely works for d<4.Source: §2.4 · p. 8, Figure 3 · p. 8

3. Discussion

The discussion presents the paper’s first bounds on representational topological expressivity and considers their implications, scope, and possible extensions.

3. Discussion

  • The paper derives what it describes as the first bounds on representational topological expressivity, contrasting them with existing decision-boundary results.Source: §3 · p. 8

3.1. Topological hierarchy for neural networks

  • Products of high-dimensional spheres are harder to express than wedge sums, although products make exponential Betti numbers easy to obtain.Source: §3.1 · p. 8
  • The bounds can relate families of sphere wedges and products, but are likely not optimal; the tighter sphere bound remains conjectural.Source: §3.1 · p. 8

3.2. Topological guarantees for learning

  • The bounds can guide architecture choices for generating outputs with particular topologies or enforcing geometric features.Source: §3.2 · p. 8
  • Expressibility does not guarantee consistent reachability through gradient descent or backpropagation, and the relation between learning and representational expressivity needs further study.Source: §3.2 · p. 8

3.3. Different input spaces

  • The theory assumes compact contractible inputs and would need adaptation for normalized data on a sphere or non-classification tasks on disjoint spaces.Source: §3.3 · p. 9

3.4. Other invariants

  • Homotopy-equivalent constructions yield Betti bounds, while cohomology rings offer a finer way to distinguish spaces such as the torus and a wedge of spheres.Source: §3.4 · p. 9

AI usage disclosure

Claude models were used in the research, including to develop bounds and refine proofs.

  • Claude models were used for literature search, text refinement, and conducting the research.Source: AI usage disclosure · p. 9
  • Claude helped develop construction bounds, including the conjectured tight (d, d + 1, d + 1) bound, and refine appendix proofs.Source: AI usage disclosure · p. 9

A. Proofs

The appendix proves that the network image is homotopy equivalent to a sphere by establishing that a cover formed from its facets and core is good. It does so by showing that the core and relevant cover intersections are contractible, with the cover’s nerve homotopy equivalent to the sphere \(S^d\).

A. Proofs

  • The cover of the image by its facets and core is good, so the nerve argument shows that the image is homotopy equivalent to a sphere.The proof identifies contractibility of facet intersections and core-facet intersections as the key good-cover condition.Source: A. Proofs · p. 12
  • Strata excluding the last coordinate are simplex faces, while each stratum containing it strongly deformation retracts onto a simplex face and is therefore contractible.The simplex characterization is established for the base stratum and its faces; the lowering lemma handles strata that include the last coordinate.Source: A. Proofs · pp. 13–15
  • The core ¯VI = ˆP(¯UI) is contractible: a contraction of ¯UI to ad+1 induces a map (x,t) ↦ ˆP(x(t)) that factors through ˆP × id.Source: A. Proofs · p. 16
  • The core V̄I is contractible because a continuous homotopy on its image starts at the identity and ends at the constant map with value e_(d+1).The proof establishes that the homotopy factors through the projection, making the induced homotopy continuous.Source: A. Proofs · pp. 16–17
  • Intersections with d+1 not in J are convex simplices, while those with d+1 in J deformation retract to a graph over a convex simplex; both types are contractible.The graph is homeomorphic to the convex base ΔJ.Source: A. Proofs · pp. 17–18
  • Since the listed intersection types exhaust all possibilities and are contractible, C is a good cover of P̂(X).The list includes simplices, deformation retracts to simplices, the contractible core, and the intersections with the core.Source: A. Proofs · p. 18
  • The nerve N(C) is homotopy equivalent to S^d because its intersection pattern realizes the boundary of a (d+1)-simplex.The nerve has d+2 vertices and realizes every intersection except the d+1 face.Source: A. Proofs · p. 18

Related papers

Loading 2610.13931v1…