PaperlayerView exact revision on arXiv

Source-linked AI summary

Skeletal Prototypes on Iterative Nerve Expansions

Jordan Eckert, Henry Schenck

arXiv:2609.16170v1cs.LGstat.ML

TL;DR

Prototype reduction usually represents a training set with a finite set of points, whereas SPINE represents each class with a Mapper-initialized embedded 1-complex whose segments enter classification. Across seventeen datasets, SPINE attains the highest mean accuracy and best average rank among eight methods, with performance and segment contributions varying across budgets.

  • Problem

    Established prototype-reduction methods return finite point sets, while class connectivity can carry information useful for reduction.

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

  • Method

    SPINE initializes each class’s embedded 1-complex with a class-conditional Mapper graph, fits its vertices for classification, and assigns observations to the nearest complex.

    Source: §5 · pp. 13–14

  • Results

    Across seventeen datasets at a matched budget, SPINE attains the highest mean accuracy at 0.9110 and is significantly better than five of seven competitors under Wilcoxon tests with Holm correction.

    Source: §5 · p. 14

  • Takeaways & Limitations

    The full graph’s median accuracy gain over vertices alone rises from 0.0009 at a 25% budget to 0.0056 at 0.5%, while SPINE is recommended over competitors at moderate budgets.

    Source: §5 · p. 14

    SPINE’s performance worsens under multiclass classification, where its independent per-class construction divides the fixed budget more finely as class count grows.

    Source: §5.1 · p. 15

Abstract

from arXiv · show

Prototype reduction replaces a training set with a smaller representation, and the established methods return a finite set of points. We propose Skeletal Prototypes on Iterative Nerve Expansions (SPINE). The model for each class is an embedded 1-complex rather than a point set. Its initial edge set is a class-conditional Mapper graph, so the data decide which localized clusters are joined. Later phases fit the vertices under a classification objective, and an observation is assigned to the class whose complex is nearest. The segments therefore enter the decision rule and not only the fitting. We evaluate SPINE on seventeen benchmark datasets under stratified 10-fold cross validation, against seven other prototype reduction methods at a matched budget. SPINE attains the highest mean accuracy and the best average rank. It is significantly better than five of the seven competitors under Wilcoxon signed-rank tests with Holm correction. A budget sweep shows that the decision rule using the entire graph segments contribute most when prototypes are scarce, while the method as a whole competes best at moderate budgets. Construction cost places SPINE with the discriminative methods, and it is faster than generalized learning vector quantization on fourteen of the seventeen datasets.

1 Introduction

Prototype reduction seeks a compact representation that preserves classification accuracy, while prior topology-based approaches either use graphs to select points or retain connectivity as part of quantization. SPINE instead uses a class-conditional Mapper graph as the edge structure of a fitted prototype model, which the paper evaluates against seven methods at matched budgets.

1 Introduction

  • A Mapper graph joins clusters that share observations, giving a data-driven account of how a class is connected at a chosen resolution.The noisy-annulus illustration uses eight nodes and eight edges and recovers β0 = 1 and β1 = 1.Source: §1 · p. 1, Figure 1 · p. 3
  • Prior topology-based reduction either uses proximity graphs to select points and then discards them, or maintains connectivity as part of vector quantization.The paper identifies a gap between these approaches and TDA, whose summaries had largely not been used in supervised prototype reduction.Source: §1 · p. 2

1.1 Previous Work and Contributions

  • SPINE models each class as an embedded 1-complex initialized by class-conditional Mapper, with segments included in the nearest-complex decision rule.The Mapper graph determines which localized clusters are joined; later fitting adjusts the structure for classification.Source: §1.1 · p. 2
  • The evaluation compares SPINE with seven prototype-reduction baselines on seventeen benchmark datasets under stratified 10-fold cross-validation at a matched prototype budget.The budget sweep also compares the full graph-segment decision rule with using vertices alone.Source: §1.1 · p. 3

2.1 Mapper Background

Mapper turns a filtered dataset into a graph by covering the filter range, clustering each cover-set preimage, and linking clusters that share observations. Its cover sets resolution, and the resulting graph’s adjacency and cycles shape later stages of SPINE.

2.1 Mapper Background

  • Mapper covers the lens range with overlapping intervals, clusters observations in each interval’s preimage, and joins clusters that share an observation.For a one-dimensional lens with gain below one, the resulting nerve is a graph that approximates the lens’s Reeb graph.Source: §2.1 · p. 3
  • The number of intervals and their overlap set the Mapper summary’s resolution, while adjacency records which localized clusters share data points.Figure 1 illustrates a leading-principal-direction lens and a five-interval cover with gain g = 0.25.Source: §2.1 · p. 3
  • SPINE carries Mapper adjacency into vertex placement, and later operations do not create cycles, so fitted-model cycles originate in the initial graph.In the toy example, the ring’s β1 = 1 is preserved throughout the phases.Source: §2.1 · p. 3, Figure 2 · p. 4

2.2 The SPINE model

SPINE replaces a finite prototype set with a class-specific embedded graph whose vertices and connecting segments together represent the class. Classification assigns an observation to the class whose realized complex is nearest.

2.2 The SPINE model

  • Each class is represented by an embedded 1-complex: vertices connected by edges, realized as the union of vertices and their closed segments.For a graph, β0 counts components and β1 counts cycles.Source: §2.2 · p. 4
  • An observation is assigned to the class whose realized complex is nearest, so the model’s segments participate in classification.This contrasts with representing each class only by a finite set of prototype points.Source: §2.2 · p. 4
  • Prototype reduction is measured by the number of vertices, the same unit used for point-based reduction methods.Figure 2 illustrates the phases on a toy dataset.Source: §2.2 · p. 4

2.3 Phase 0: Initial Mapper Structure

Phase 0 builds a separate Mapper graph for each class from fitting data, using within-class PC1 as the lens. Its cover and clustering choices determine the initial graph’s resolution and connectivity.

2.3 Phase 0: Initial Mapper Structure

  • Phase 0 reserves a stratified quarter of each training fold for validation and builds each class’s Mapper graph from fitting points in that class alone.Supervision enters through the class split, not through the lens or cover.Source: §2.3 · p. 4
  • The lens is the within-class first principal component, computed after z-scoring features; downstream vertex positions remain in the original training-space coordinates.The sign of the lens is fixed deterministically, and z-scoring makes the lens invariant to per-feature affine rescaling.Source: §2.3 · pp. 4–5
  • The interval-count heuristic grows resolution like n_c^1/5, while the gain is fixed at g = 0.25 across datasets and intervals.The authors treat the interval count as a heuristic and make no optimality claim for it.Source: §2.3 · p. 5
  • The fixed gain’s sensitivity is untested, and the authors offer no selection principle beyond choosing a value between bounds on overlap.Too little overlap can produce too few edges; the stated gain was not tuned on the evaluation suite.Source: §2.3 · p. 5
  • When a uniform interval has too few observations to resolve clusters, the cover is instead placed on the lens’s empirical distribution function.This monotone reparameterization reallocates resolution toward dense regions while preserving point order along the lens.Source: §2.3 · p. 5
  • HDBSCAN clusters each interval in ambient Euclidean space, and noise points are assigned to their nearest interval cluster for edge computation only.Cluster parameters are global and fixed; the authors make no optimality claim for them and recommend cross-validation when applying SPINE.Source: §2.3 · p. 5

2.4 Phase 1: Annealed Representation

Phase 1 anneals vertex positions over the Mapper nerve, using graph neighborhoods to move each class’s vertices from their initial placement toward a representation of the class. Its schedule is heuristic and was not sensitivity-tested.

2.4 Phase 1: Annealed Representation

  • Vertices move under competitive learning with the nerve graph itself as the neighborhood lattice, rather than a fixed grid.The winning vertex is selected by Euclidean distance, and the graph hop distance controls how other vertices move.Source: §2.4 · pp. 5–6
  • The class points are presented once each per epoch in random order, with updates applied online to the positions left by the previous point.Vertices in disconnected components are assigned hop distance m, larger than any realizable hop distance in a simple graph of m vertices.Source: §2.4 · p. 6
  • The schedule parameters decay geometrically, with σ0 = 2 and σT = 0.05; the resulting one-hop weight falls to exp(−20) at the final width.The σ0 choice was structurally calibrated using a median Phase 0 class graph of six vertices, rather than evaluation accuracy.Source: §2.4 · p. 6
  • T = 30 epochs is a heuristic that was never swept, and the fixed schedule constants have untested sensitivity.The coupling is intended to help reach a better basin of attraction and then withdraw before the solution settles.Source: §2.4 · p. 6

2.5 Phase 2

Phase 2 first screens inherited edges, then fits vertex positions under a classification objective based on distances to class complexes. The phases alternate fitting with structural changes, while preserving limits on which edges and vertices can change.

2.5.1 Phase 2a: Edge Screening

  • Edge screening deletes an inherited edge only when its deletion strictly decreases validation risk, avoiding tie-driven deletions that could strip the graph to isolated points.Screening can split components or break cycles, and later operations cannot reconnect components or close cycles.Source: §2.5.1 · pp. 6–7

2.5.2 Phase 2b: Discriminative Fitting

  • Phase 2b uses the GLVQ-family relative-distance margin, replacing prototype distance with distance to a realized complex and minimizing smoothed error.The fitting gradient uses the training fold’s fitting portion, not the held-out split.Source: §2.5.2 · p. 7
  • A training point pulls on its nearest segment, splitting the correction between the segment’s two vertices according to its projection position.If the projection lands at an endpoint, the update reduces to the GLVQ update on points.Source: §2.5.2 · p. 7
  • Only vertices incident to a nearest wrong-class object for some training point move, while distance preconditioning prevents the unsquared-distance step from diverging near a good fit.The boundary set is reused across epochs; an edge with one interior endpoint moves only its boundary end.Source: §2.5.2 · pp. 7–8
  • Fitting runs after screening and after each growth or pruning round, with a fixed, a priori selected epoch count whose sensitivity is untested.The step size does not shrink as fitting improves, so the learning rate alone determines how finely the model can settle.Source: §2.5.2 · p. 8

2.6 Phase 3: Attribution-Driven Growth

Phase 3 grows each class complex toward its allotted prototype budget by adding vertices where the current model fails. Error locations determine whether growth extends the graph or adds curvature, with representation error used when held-out errors are exhausted.

2.6 Phase 3: Attribution-Driven Growth

  • Growth selects the object carrying the most attributed held-out misclassifications, then bisects an edge or extends a vertex using the errors’ centroid.Interior errors favor bisection, while errors concentrated at a free endpoint favor extension.Source: §2.6 · p. 8
  • Each class is deliberately grown past its budget toward a cap of ⌈1.2 Mc⌉ vertices, then alternated with fitting over three rounds.Each round adds the larger of three vertices and an equal share of the remaining shortfall before the model is refit.Source: §2.6 · p. 8
  • When held-out errors cannot supply a growth site, the method switches to representation error, adding a vertex at the centroid of assigned same-class training points.This is the phase’s only use of training points rather than held-out points to drive a growth decision, and each use is counted in provenance.Source: §2.6 · p. 8

2.7 Phase 4: Pruning to the Budget

Phase 4 removes vertices one at a time until each class reaches its budget, choosing removals by validation risk while restricting ordinary deletions to topology-preserving inverse growth moves. Forced removals are reported and arise only under specified budget or class-imbalance conditions.

2.7 Phase 4: Pruning to the Budget

  • Vertices are removed one at a time by the least validation-risk increase, with classes pruned independently while other classes remain fixed.Ties go to the first vertex encountered.Source: §2.7 · p. 8
  • Ordinary removals invert extension or bisection: a degree-one vertex may be removed, as may a degree-two vertex with distinct, nonadjacent neighbors.Other deletions can change Betti numbers; degree-three-or-higher vertices cannot be removed while preserving both.Source: §2.7 · pp. 8–9
  • Forced removals occur only in severely imbalanced minority classes or when the fixed cover already exceeds the budget, and may remove an isolated vertex and its component.Every forced removal is counted and reported.Source: §2.7 · p. 9

3 Performance Evaluation

Across seventeen datasets, SPINE achieves the highest mean accuracy and best average rank against seven methods at a matched budget. Results also examine subgroup performance and changes to graph topology during construction.

3.1 Experimental Setup

  • Seventeen numeric datasets were evaluated; RSP3's deterministic, accuracy-blind prototype count sets each fold's matched budget for the competitors.Per-class budgets are apportioned by training-fold class frequencies, with a floor of one prototype per class; SPOT has no per-class quota.Source: §3.1 · p. 9, Table 1 · p. 10

3.2 Method Evaluations

  • Risk-based model choices use a held-out quarter, leaving SPINE fit on 75% of each training fold; comparisons use signed-rank tests with Holm correction.The statistical comparisons follow a Friedman test and exclude exact ties from the signed-rank statistic.Source: §3.2 · pp. 9–10

3.3 Results

  • SPINE's six dataset wins all occur on binary tasks; mean rank is 1.70 on binary versus 3.50 on multiclass, and it exceeds Full on twelve datasets.Letter is a counterexample to a monotone class-count pattern: SPINE ranks second among its 26 classes.Source: §3.3 · p. 10
  • Edge screening alone removed 869 edges, raising mean β0 per class from 1.05 to 2.05 and lowering mean β1 from 0.050 to 0.031.Frozen Betti numbers survived emission on all 860 class-folds, and no Phase 3 removal was forced.Source: §3.3 · p. 10
  • SPINE has the highest mean accuracy (0.9110) and best average rank (2.44); five of seven competitors reject under Holm correction.The significant comparisons are against Random, SPOT, GLVQ, RSP3, and KMeans.Source: §3.3 · pp. 10–11, Table 2 · p. 11, Table 3 · p. 11

4 Discussions

The discussion tests what graph segments add to SPINE and where the method competes across prototype budgets, then compares construction costs. The segments matter most when prototypes are scarce, while SPINE competes best at moderate budgets; its construction cost is comparable to discriminative methods but varies with per-class vertex counts.

4.1 Effect of the Graph Segments and Budget

  • At the matched budget, SPINE+Graph’s 0.9110 average accuracy versus 0.9080 for SPINE+1NN is not a significant advantage (p = 0.091).Scoring the same fitted model with vertices alone still gives the best average rank, 2.79, narrowly ahead of LVQ3 at 2.82; the paired comparison isolates the decision-rule difference.Source: §4 · p. 11, §4.1 · p. 12
  • As budgets shrink from 25% to 0.5%, the median accuracy difference favoring SPINE+Graph over SPINE+1NN rises from 0.0009 to 0.0056, with at least ten wins at each budget.The authors identify this as the strongest evidence for the segments; Table 4 reports paired differences across the seventeen datasets.Source: §4.1 · p. 12, Table 4 · p. 12

4.2 Construction Cost

  • SPINE’s construction exponent is 1.99, similar to GLVQ’s 1.95, and SPINE is faster than GLVQ on fourteen of seventeen datasets (median ratio 0.41).Construction timings came from a separate five-fold study on an Apple M2 with BLAS restricted to one thread.Source: §4.2 · p. 12, Table 5 · p. 13
  • Construction cost tracks vertices within a class more than total budget; SPINE is slower than GLVQ on EEG Eye State and Magic, where per-class counts approach 3,000.Against GNG, the median ratio is 0.80, but it rises with fold size and reaches 2.6 on EEG Eye State and 3.3 on Magic.Source: §4.2 · p. 12

4.1 Effect of the Graph Segments and Budget

  • At 25% of the training fold, SPINE leads at 0.9103, ahead of LVQ3 at 0.9050 and KMeans at 0.8917; at 0.5%, it ranks fifth at 0.8048.SPINE passes RSP3 between 5% and 10% and LVQ3 between 10% and 25%; the authors report its strongest overall competition at moderate budgets.Source: §4.1 · p. 12, Figure 3 · p. 13

5 Conclusion

SPINE models each class as an embedded 1-complex initialized by class-conditional Mapper and evaluated through the nearest-complex rule. Across seventeen datasets it leads at a matched budget, while its budget behavior and limitations qualify where it is most competitive.

5 Conclusion

  • SPINE uses a class-conditional Mapper graph as its initial edge set, then fits each class’s embedded 1-complex under a classification objective.The segments enter the decision rule: an observation is assigned to the class whose complex is nearest.Source: §5 · pp. 13–14
  • At a matched budget across seventeen datasets, SPINE attains the highest mean accuracy, 0.9110, and best average rank, 2.44, significantly outperforming five of seven competitors.The tests use Wilcoxon signed-rank tests with Holm correction; SPINE uses only part of the training fold for fitting, while the other methods use the full fold.Source: §5 · p. 14
  • As budget falls, the median gain from using the entire graph rises from 0.0009 at 25% to 0.0056 at 0.5%, but SPINE competes best at moderate budgets.SPINE leads at 25% and places fifth at 0.5%; the authors recommend it over competitors at moderate budgets.Source: §5 · p. 14
  • The topology-preservation check is modest on this roster: nerves are nearly always forests, so preservation mostly concerns component count.Cycles survive on 26 of 860 class-folds and fall on four datasets; the guarantee is budget-dependent because Phase 0 fixes the nerve before consulting the budget.Source: §5 · p. 14
  • SPINE scales at the same rate as GLVQ and is faster on fourteen of seventeen datasets, while its cost relative to GNG rises with fold size.The construction cost places SPINE with discriminative and graph-building methods.Source: §5 · p. 14

5.1 Limitations and Future Work

  • The evaluation reports one fixed heuristic configuration without sensitivity analysis; performance also worsens on multiclass tasks, and growth can fall back to representation error.Phase 0 fixes the cover before the budget is consulted, leaving no homotopy-preserving removal when the budget is below nerve size; the authors identify budget-aware construction and class interaction as future directions.Source: §5.1 · p. 15
Loading 2609.16170v1…