Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology

Bastian Rieck; Matteo Togninalli; Christian Bock; Michael Moor; Max Horn; Thomas Gumbsch; Karsten Borgwardt

Source-linked AI summary

Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology

Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, Karsten Borgwardt

arXiv:1812.09764v3Dec 23, 2018cs.LGmath.ATstat.ML

TL;DR

Existing approaches largely interrogate neural networks with input data, leaving structural properties without formal measures. The paper introduces neural persistence, a topological complexity measure on weighted stratified graphs, and shows that it reflects dropout and batch normalization while supporting validation-free early stopping with comparable accuracy.

Problem
Formal measures for assessing and monitoring the structural complexity and generalization-related properties of deep neural networks remain undeveloped beyond input-data interrogation.
Method
Neural persistence uses topological data analysis on weighted stratified graphs to measure neural-network structural complexity from weights and connectivity.
Results
Neural persistence identifies the benefits of dropout and batch normalization and enables early stopping without validation data while losing only 0.06% accuracy when stopping earlier by 0.62 epochs on average for b ≤8.
Takeaways & Limitations
Neural persistence provides a theoretically grounded, computationally efficient structural measure with a competitive validation-free early-stopping use case.
Takeaways & Limitations
The measure is expected to increase as a network learns, a property evaluated empirically rather than established solely by its definition.

Abstract

from arXiv · show

While many approaches to make neural networks more fathomable have been proposed, they are restricted to interrogating the network with input data. Measures for characterizing and monitoring structural properties, however, have not been developed. In this work, we propose neural persistence, a complexity measure for neural network architectures based on topological data analysis on weighted stratified graphs. To demonstrate the usefulness of our approach, we show that neural persistence reflects best practices developed in the deep learning community such as dropout and batch normalization. Moreover, we derive a neural persistence-based stopping criterion that shortens the training process while achieving comparable accuracies as early stopping based on validation loss.

1 INTRODUCTION

The paper addresses a gap in structural measures for deep neural networks by introducing neural persistence, which combines network weights and connectivity without input-data interrogation. It establishes theoretical properties and demonstrates practical utility for recognizing regularization benefits and guiding early stopping.

The measure combines network weights and connectivity rather than interrogating networks through input data.
Neural persistence is a computationally efficient measure of neural-network structural complexity based on algebraic topology.The method is designed to characterize both individual layers and entire networks.
The paper proves upper and lower bounds that normalize neural persistence for comparisons across networks of varying sizes.
Neural persistence captures the benefits of dropout and batch normalization during training.
A neural-persistence stopping criterion provides early stopping without requiring validation data.

2 BACKGROUND: TOPOLOGICAL DATA ANALYSIS

Topological data analysis provides a rigorous algebraic-topology framework for analyzing complex data. The paper uses simplicial and persistent homology to represent connectivity features across scales, addressing limitations of coarse and unstable Betti-number summaries.

Topological data analysis supplies computational tools for analyzing complex data within a rigorous mathematical framework based on algebraic topology.
Simplicial homology derives homology groups from a simplicial complex to describe topological features such as holes at different dimensions.
Persistent homology represents a weighted simplicial complex as a filtration, a nested sequence of complexes describing its growth as scale changes.
Persistent homology was developed because Betti numbers provide representations that are too coarse and unstable for real-world data.

3 A NOVEL MEASURE FOR NEURAL NETWORK COMPLEXITY

Neural persistence measures neural-network structural complexity by applying persistent homology to normalized weighted layers, combining connectivity and weight information. The method is efficiently computable, supports comparisons across architectures through theoretical bounds and normalization, and captures structural differences across network types.

Neural persistence calculation: The method represents feedforward networks as stratified graphs whose edges connect only adjacent neuron layers.Each layer is the bipartite subgraph formed by two consecutive vertex sets and their connecting edges.
Neural persistence calculation: Neural persistence applies zero-dimensional persistent homology to each normalized weighted layer, tracking connected components as thresholded edge weights are progressively lowered.The filtration uses transformed absolute weights in [0, 1], preserving connection strength while making the measure invariant to scaling.
Neural persistence calculation: Neural persistence for a layer is summarized from persistence-diagram points using a p-norm, which captures their distance from the diagonal when p = 2.The p-norm provides a stable summary of the topological features represented in the diagram.
Neural persistence calculation: The calculation is efficient: sorting n weights costs O(n log n), while union–find persistent-homology computation costs O(n · α(n)).The algorithm computes a persistence diagram separately for each layer and returns the corresponding layerwise persistence values.
Properties of neural persistence: Theoretical lower and upper bounds enable comparisons across neural networks with different architectures, with bounds derived for individual layers and empirical diagram tuples.A fully connected layer with equal weights realizes the lower-bound construction, while a layer with one larger edge provides the upper-bound construction described in the supplied passages.

4 EXPERIMENTS

Experiments test whether neural persistence reflects regularization practices and can support early stopping without validation data. It yields higher persistence for batch normalization and dropout, and often stops earlier than validation loss with nearly unchanged accuracy.

4.1 DEEP LEARNING BEST PRACTICES IN LIGHT OF NEURAL PERSISTENCE: Neural persistence identifies higher structural complexity for networks using batch normalization or dropout than for an unmodified network.The comparison uses two-layer [650, 650] networks on MNIST; dropout produces the more pronounced persistence effect, paralleling test accuracy.
4.2 EARLY STOPPING BASED ON NEURAL PERSISTENCE: Neural persistence provides an early stopping rule that monitors mean normalized persistence instead of validation loss.Training stops when persistence fails to increase by more than Δmin for g epochs, after a burn-in period b.
4.2 EARLY STOPPING BASED ON NEURAL PERSISTENCE: On Fashion-MNIST, persistence-based stopping ends half an epoch earlier on average while losing only 0.08% accuracy across 625 configurations.The reported barycentre is (−0.53, −0.08) relative to validation-loss stopping.
4.2 EARLY STOPPING BASED ON NEURAL PERSISTENCE: For burn-in b ≤8, persistence-based stopping occurs 0.62 epochs earlier on average with only a 0.06% accuracy decrease.The comparison is made against validation loss using the same patience and burn-in configurations.
4.2 EARLY STOPPING BASED ON NEURAL PERSISTENCE: Persistence-based stopping triggers for more parameter combinations than validation loss and stops earlier when overfitting can occur, but later when longer training helps.Figure 4 summarizes accuracy, epoch, and triggering-frequency comparisons; final test accuracies provide context independent of early stopping.

5 DISCUSSION

The discussion presents neural persistence as a theoretically grounded, efficient structural-complexity measure that reflects deep-learning performance. It identifies dropout and batch normalization and supports competitive validation-free early stopping.

5 DISCUSSION: Neural persistence is a topological measure that captures structural information related to deep-learning performance.The authors describe it as generally applicable, computationally efficient, and theoretically well-defined relative to previous work.
5 DISCUSSION: The measure identifies networks using dropout and batch normalization and supports competitive early stopping without a separate validation set.The authors state that this can preserve data for training in smaller-sample regimes.
5 DISCUSSION: Using the p-norm of all network weights as a proxy did not produce an early stopping measure because it was never triggered.This comparison suggests that neural persistence captures information not exposed by aggregating all weights with the p-norm.

A.1 COMPARISON WITH GRAPH-THEORETICAL MEASURES

The appendix compares neural persistence with graph-theoretical complexity measures using trained and deliberately poorly trained MNIST perceptrons. Neural persistence separates the resulting accuracy regimes, whereas clustering coefficient does not.

A.1 COMPARISON WITH GRAPH-THEORETICAL MEASURES: Neural persistence clearly distinguishes trained MNIST perceptrons from poorly converged networks, while clustering coefficient does not.The trained perceptron reaches approximately 0.91 test accuracy, whereas sabotaged training produces accuracies from 0.38–0.65; the persistence regimes have significantly lower variance for trained networks.

A.2 PROOF OF THEOREM 2

The proof rewrites neural persistence as a p-norm expression over the selected weights in a layer's persistence diagram. It then bounds the selected-weight norm between the minimum and maximum weight norms.

A.2 PROOF OF THEOREM 2: For a layer, neural persistence depends only on the selected weights represented as (1, w_i) tuples in the persistence diagram.The proof introduces the selected-weight vector e_w and rewrites persistence as NP(G_k) = ‖1 − e_w‖_p.
A.2 PROOF OF THEOREM 2: The selected-weight vector satisfies ‖w_min‖_p ≤ ‖e_w‖_p ≤ ‖w_max‖_p.These inequalities provide the norm bounds used in the proof.

A.3 ADDITIONAL VISUALIZATIONS AND ANALYSES FOR EARLY STOPPING

Across MNIST, CIFAR-10, and IMDB, neural persistence often enables earlier stopping than validation loss, but its accuracy and reliability depend on dataset and parameter configuration.

Visualization scheme: The visual analyses compare accuracy and epoch differences for parameter configurations and show how often each stopping measure is triggered.Heatmap cells represent individual combinations of burn-in rate b and patience g; colors encode relative accuracy and stopping-time differences where described.
Overall findings: Neural persistence stops earlier than validation loss across many configurations, with dataset-dependent accuracy changes and triggering frequency.MNIST often stops more than four epochs earlier with virtually no accuracy loss; IMDB reaches up to two epochs earlier and up to 0.10% higher accuracy, while CIFAR-10 is more sensitive.
MNIST: On MNIST, neural persistence stops for more parameter combinations and can stop more than four epochs earlier with virtually no accuracy loss.One configuration loses 0.8% accuracy, while many others show virtually no loss; the measure is not triggered as often for some configurations.
CIFAR-10: On CIFAR-10, neural persistence can improve accuracy by almost 10%, but may also fail to stop earlier or require up to 15 additional epochs.It triggers reliably for more configurations than validation loss, while practical behavior is affected by unreliable convergence of fully connected networks.
IMDB: On IMDB, most configurations stop up to two epochs earlier with accuracy increases up to 0.10%, but one configuration loses 21% accuracy.The severe outlier occurs at g = 1 and b = 0 and is omitted from the scatterplot for display clarity.

A.4 NEURAL PERSISTENCE FOR CONVOLUTIONAL LAYERS

The section extends neural persistence to convolutional layers by representing convolutions as sparse bipartite graphs and exploiting a closed-form approximation. The approximation is substantially faster while showing very similar behavior, but the edge-focused filtration does not improve accuracy in the tested CNN configurations.

Convolutional representation: Convolutional filters are represented as sparse bipartite weight matrices, preserving the topology needed to compute normalized neural persistence per filter and layer.The layer-level measure is obtained by averaging normalized persistence across filters.
Closed-form calculation: The convolutional persistence calculation simplifies because output neurons share filter weights, reducing destruction events to sorted large filter values with repeated entries.This yields a closed-form expression and motivates the approximation algorithm.
Approximation: The approximation takes about 0.000 38 s per convolutional filter and evaluation step versus 8.77 s for naive exact unrolling, while showing very similar behavior.The experiments use a CNN with 32 + 2048 filters.
Empirical limitation: In the Fashion-MNIST CNN experiment, stopping based on convolutional-layer neural persistence typically incurred a considerable accuracy loss, and no tested configuration increased accuracy.Using the second convolutional layer or both layers did not improve the result; exact calculations showed the same outcome as the approximation.
Approximation algorithm: The approximation algorithm initializes persistence tuples, processes corner weights and remaining sorted weights, then returns the p-norm of the approximated persistence diagram.Corner weights receive special treatment because they merge components differently in the approximation.

A.5 RELATIONSHIP BETWEEN NEURAL PERSISTENCE AND VALIDATION ACCURACY

The experiments find no general correlation between neural persistence and validation accuracy in deeper networks. High-persistence and Xavier-initialized networks converge to similar validation-accuracy regimes despite differing final persistence values.

Relationship with accuracy: Deeper networks show no observable correlation between neural persistence and predictive accuracy, indicating that persistence captures structural properties arising from training procedures or initialization.The authors motivate the analysis by asking whether high neural persistence corresponds to high predictive accuracy.
Initialization regimes: Networks initialized with high neural persistence and Xavier initialization converge to similar validation-accuracy regimes despite differences in final mean normalized neural persistence.For high-NP initialization, networks with final 0.9 ≤ NP ≤0.95 have validation accuracies ranging from 0.098 to 0.863.
Additional analyses: Using the first convolutional layer for Fashion-MNIST produced the reported result, while exact computation agreed and adding the second layer did not improve it.This supplementary convolutional analysis supports the section’s broader negative correlation finding.
Visualization: For a [20,20,20] Fashion-MNIST network, the final two training epochs show no correlation between validation accuracy and normalized total persistence.The visualization samples epochs every quarter epoch.
Additional analyses: The supplementary visualizations examine final persistence distributions across 100 runs and persistence after 15 epochs for architectures with increasing depth.The cited caption specifies the [50, 50, 20] setup and denotes deeper models as [n × 20].

A.6 NEURAL PERSISTENCE FOR DIFFERENT DATA DISTRIBUTIONS AND DEEPER FCN ARCHITECTURES

Neural persistence responds to data distributions, depth, and training-monitoring conditions, while supporting an early-stopping rule for limited or noisy labels. The persistence-based criterion can stop later with scarce data and remains stable under label noise, achieving slightly better or comparable test accuracy than loss-based stopping.

Data distributions: Neural persistence captures differences associated with training on MNIST versus Fashion-MNIST using the same [50, 50, 20] architecture and image dimensions.The experiment is designed to compare data sets with different properties while holding image size and channel count constant.
Deeper architectures: Increasing depth in fixed-width fully connected networks initially increases neural-persistence variability by enabling convergence to more distinct structural regimes.The analysis uses 20 hidden units per layer and measures mean persistence after 15 MNIST training epochs.
Early stopping: The persistence-based stopping rule achieves good performance without being affected by batch size or noisy labels, with results consistent across multiple architectures and most patience parameters.These conclusions summarize the reported stopping experiments.
Early stopping: Neural persistence-based stopping remains stable under increasing label noise and can yield higher test accuracy than validation-loss stopping after prolonged training.The comparison covers MNIST and Fashion-MNIST under label permutation and reduced-data conditions.
Early stopping: With fewer training samples, neural persistence stops later than validation and training loss, producing slightly better test accuracy than those loss-based criteria.Optimal stopping still achieves the highest test accuracy, while fixed early stopping performs worse when only a fraction of the data is available.