PaperlayerView exact revision on arXiv

Source-linked AI summary

M-Fibration Theory with Applications to Neural Network Compression

Paolo Boldi

arXiv:2608.25598v1cs.LG

TL;DR

Existing graph-fibration theory does not adequately handle algebraically composed labels or errors and noise. This paper develops M-fibration theory for commutative-monoid-labelled graphs, extends it to approximate fibrations, and applies it to compress arbitrary neural networks, including CNNs.

  • Problem

    Existing graph-fibration theory struggles with algebraically composed labels and is incompatible with errors or noise, while a well-grounded foundation for these contexts remains missing.

  • Method

    The paper develops a theoretical framework for M-fibrations on commutative-monoid-labelled graphs, including minimum bases and ε-approximate fibrations.

  • Results

    The framework establishes unique minimum bases for weighted graphs and applies ε-approximate fibrations to compress arbitrary neural networks, including CNNs.

  • Takeaways & Limitations

    M-fibration theory provides a theoretical basis for weighted-graph analysis and neural-network compression within the stated framework.

  • Takeaways & Limitations

    Finding a minimum-class ε-approximate M-equitable partition is difficult, can be formulated as a MILP, and is conjectured to be NP-hard.

Abstract

from arXiv · show

The purpose of this paper is to provide a general, comprehensive, theoretical framework that allows one to deal with fibrations on graphs labelled on a commutative monoid. This is a genuine extension of the theory of graph fibrations (as introduced in "Fibrations of Graphs" [Discrete Math., vol. 243, pp. 21-66, 2002]), that makes it possible to deal with weighted graphs, and also graphs labelled with other algebraic structures. The derived theory also lends itself naturally to consider approximate fibrations. As an example, we show how this framework can be applied to the compression of arbitrary neural networks (including CNNs), providing a strong theoretical underpinning to the recent results in "The role of fibration symmetries in geometric deep learning" [Proc. Natl. Acad. Sci. USA, vol. 123, no. 4, p. e2416552123, 2026]

1 Introduction and Motivations

The paper addresses missing theoretical foundations for extending graph fibrations to algebraically labelled graphs by developing a framework over commutative monoids. It applies this theory to compress arbitrary neural networks, including CNNs.

  • Motivation: Graph fibrations originated as a formal tool for describing computations in distributed systems and later supported symmetry analysis in dynamical systems and biology.Related notions include equitable partitions, the Weisfeiler–Leman test, colour refinement, and groupoids.
  • Motivation: Two shortcomings hinder broader use: adapting fibrations to weighted or algebraically composable labels is difficult, while existing label-preserving morphisms require exact preservation.The supplied passage introduces a second problem but does not state its full content.
  • Contribution: The paper develops a general, comprehensive framework for fibrations on graphs labelled on a commutative monoid, grounding previously ad hoc applications theoretically.The approach is related to weighted bisimulation of weighted automata and exact lumpability of Markov chains.
  • Application: The derived theory applies to compression of arbitrary neural networks, including CNNs, and provides theoretical underpinning for recent neural-network results.Related instances include equitable partitions of weighted graphs, message-passing graph neural networks, and lossless dimension reduction of linear programs.

2 Notations and Preliminaries

This section establishes the basic language of equivalence relations, partitions, finite graphs, and graph morphisms used throughout the paper.

  • Equivalence relations and partitions: Equivalence relations are symmetric, reflexive, and transitive, while partitions are pairwise disjoint, non-empty subsets whose union is the underlying set.The two concepts correspond one-to-one through equivalence classes.
  • Equivalence relations and partitions: A relation is finer than another when every pair related by the first is also related by the second; conversely, the second is coarser.This ordering applies equivalently to partitions.
  • Graphs and graph morphisms: A graph consists of node and arc sets together with source and target maps assigning each arc its endpoints.The notation G(x, y) denotes arcs from x to y and extends to node subsets; G(-, y) denotes arcs ending at y.
  • Graphs and graph morphisms: The paper considers only finite graphs, with finite node and arc sets, and omits subscripts when context makes them clear.This finiteness condition applies throughout the following notation.
  • Graphs and graph morphisms: A simple graph has at most one arc between any ordered pair of nodes, and a graph morphism is a pair of node and arc functions satisfying commuting diagrams.Morphisms are classified as surjective, injective, or bijective when both component functions have the corresponding property.

3 M-graphs and M-fibrations

This section extends rigid standard graph fibrations to labelled graphs by introducing M-graphs and M-fibrations over commutative monoids. It also establishes closure under composition and characterizes bijective M-fibrations as M-graph isomorphisms.

  • Motivation: Standard graph fibrations are too rigid for weighted or labelled neural networks when morphisms need not preserve labels or weights.The section motivates M-fibrations as a more flexible alternative.
  • M-graphs: An M-graph is a graph whose arcs receive labels from a commutative monoid (M, ⊕, 0).The labelling is given by a function λG : AG → M.
  • Relation to standard fibrations: Standard graph fibrations arise as the special case M = (N, +, 0) with every arc labelled 1.Then the M-fibration condition reduces to requiring exactly one lifted arc.
  • Basic properties: The composition of two M-fibrations is an M-fibration, while a bijective M-fibration is an isomorphism of M-graphs.The latter is a bijective graph morphism that preserves arc labels.

4 Minimum base of an M-graph

Every finite M-graph has a canonical minimum base obtained from its coarsest M-equitable partition. This base is M-fibration prime and unique up to isomorphism, while the associated minimum M-fibration is unique up to base isomorphism.

  • M-equitable partitions and fibrations: M-fibrations correspond exactly to M-equitable partitions: fibers induce an equitable partition, and quotient projection is an epimorphic M-fibration.For a partition Π, the quotient has one node per part and arc label W(C, D) whenever arcs exist from C to D.
  • Coarsest equitable partition: Every M-graph has a coarsest M-equitable partition, obtained by iteratively refining nodes with unequal total incoming weights from prior parts until the finite sequence stabilizes.The stabilized partition is equitable and every other M-equitable partition is finer than it.
  • Minimum base theorem: The quotient by the coarsest M-equitable partition is an epimorphic M-fibration onto an M-fibration-prime graph, establishing existence of a minimum base.An M-fibration-prime graph is one whose epimorphic M-fibrations are all isomorphisms.
  • Structural consequences: Minimum bases are always simple, because parallel arcs can be merged into one arc labelled by their monoid sum, even when the original M-graph has parallel arcs.For M = (N, +, 0), this label equals the number of merged arcs, recovering the standard graph-fibration case.
  • Minimum base theorem: The minimum base B is unique up to isomorphism, and every minimal M-fibration differs from the canonical projection only by composition with an isomorphism of B.Thus the paper denotes the base by ˆG and the minimum M-fibration by µG : G →ˆG.
  • Structural consequences: The minimum base depends on the monoid and can change substantially after small label changes, showing sensitivity to every label.The example contrasts (R, +, 0) with (Z31, +, 0), where 15 + 23 is respectively 38 and 7 modulo 31.

5 Properties of the minimum base of an M-graph and pullbacks

The section establishes a factorization property for minimum bases of M-graphs, while showing that standard pullback and universal-total-graph arguments generally fail. Weighted unfoldings instead retain a bisimilarity interpretation.

  • Minimum bases: Every epimorphic M-fibration φ: G → H factors through an epimorphic M-fibration ψ: H → ˆG, with µG = ψ ◦ φ and ˆH isomorphic to ˆG.This extends the corresponding minimum-base property to M-graphs.
  • Limits of standard methods: M-fibrations lack unique path lifting, and the category of M-graphs and M-fibrations does not generally have pullbacks.An arc labelled 2 may lift to two arcs labelled 1, invalidating the standard universal-total-graph route.
  • Pullbacks: No finite or countable pullback exists for the Example 5.1 cospan, because cones Qt for t ∈ [0, 1] have pairwise distinct node matrices.The family of cones forces any pullback to contain uncountably many distinct nodes.
  • Universal total graphs: Universal total graphs lose their universal property: no M-fibration ψ: B → G maps x′ to a′ in Example 5.2.Mapping γ to either α1 or α2 makes the fibration condition for the other arc read 0 = 1.
  • Weighted unfoldings: Although universal total graphs fail, the corresponding in-trees remain bisimilar as weighted transition systems, framing Section 4 as a theory of weighted bisimilarity of unfoldings.This is the surviving structural relationship identified for the weighted setting.

6 ε-approximate M-fibrations

The section defines ε-approximate M-fibrations using metric monoids and local/global fibration error. It establishes composition bounds and introduces fibration distance and the compression–error trade-off function β_G.

  • Metric monoids: A metric monoid combines a commutative monoid with a translation-invariant metric, yielding sum-subadditivity for finite sums.The metric satisfies d(x ⊕ z, y ⊕ z) = d(x, y), and d(x ⊕ x′, y ⊕ y′) ≤ d(x, y) + d(x′, y′).
  • Approximate fibrations: A morphism is an ε-approximate M-fibration when its global fibration error satisfies ∆(φ) ≤ ε.The global error aggregates the local failures of the fibration condition over arcs and nodes.
  • Approximate fibrations: Zero global error characterizes exact M-fibrations, while composition obeys the subadditive bound ∆(ψ ◦ φ) ≤ ∆(φ) + ∆(ψ).Thus approximation errors accumulate additively under successive morphisms.
  • Fibration distance: Fibration distance is a Lawvere quasi-metric: it satisfies identity and triangle properties, but is not symmetric.fd(G, B) = 0 exactly when G can be epimorphically fibred over B.
  • Compression–error trade-off: The function β_G captures compression at error tolerance ε, is non-increasing, equals |N ˆG| at ε = 0, and becomes 1 for sufficiently large ε.It formalizes the trade-off between compression and error in approximate fibrations.

7 ε-approximate M-equitable partitions

The section defines ε-approximate M-equitable partitions through the minimum radius covering each part’s local in-weight vectors, extending exact M-equitability at ε = 0. It establishes their correspondence with ε-approximate M-fibrations, characterizes minimum-class quotients, and presents a certified greedy refinement despite optimization and nonuniqueness challenges.

  • Definition: An ε-approximate M-equitable partition has inequity υ(Π) at most ε, where each part’s local in-weight vectors lie within radius ε of a common center.The inequity is the minimum radius admitting a center for every part.
  • Definition: At ε = 0, ε-approximate M-equitability is exactly M-equitability because every part’s local in-weight vectors must be identical.Thus the approximate notion generalizes the exact one.
  • Fibrations and quotients: Epimorphic ε-approximate M-fibrations induce ε-approximate M-equitable partitions, and canonical projections from such partitions to quotient graphs are epimorphic ε-approximate M-fibrations.The correspondence is stated as the two directions of Proposition 7.1.
  • Minimum bases: Computing βG(ε) is equivalent to finding an ε-approximate M-equitable partition with the fewest classes, but no coarsest partition exists for ε > 0.The counterexample yields non-isomorphic quotient M-graphs from distinct partitions with the same approximation range.
  • Minimum bases: 4, 3, 2, and 1 are the values of βG(ε) on [0, 0.1), [0.1, 0.2), [0.2, 4.5), and ε ≥ 4.5, respectively.These intervals show how increasing tolerance reduces the minimum number of partition classes.
  • Algorithm: The minimum-class problem can be formulated as a MILP and is conjectured NP-hard, while Algorithm 1 greedily refines partitions and guarantees radius at most ε for every class.The greedy method need not minimize the number of classes and supports general center rules, including means and Chebyshev centers.

8 Application: compression of neural networks

The section establishes the mathematical basis for compressing neural networks through graph-fibration symmetries, merging equivalent neurons and summing their incoming weights. It represents MLPs and CNNs as suitably labelled graphs to apply this framework.

  • Compression principle: Fibration-equivalent neurons can be merged into one, with the incoming arc weights summed, providing the paper’s approach to neural-network compression.The framework supplies mathematical foundations for an idea previously introduced in.
  • Compression principle: The framework uses general monoids to support this graph-based compression approach.The supplied passage introduces this point but ends before stating the full consequence.
  • Network representations: In an MLP, neurons are graph nodes, synaptic connections are arcs, and arc weights use the monoid (R, +, 0).An explicit bias node and layer-specific normalization factor make distances between neuron in-weights comparable across layers.
  • Network representations: In a CNN, channels are graph nodes and convolutional kernels are arcs whose weights are kernels of appropriate sizes.The detailed representation is provided in the caption of Figure 8.

9 Experimental results

Post-training compression converts three trained neural networks into M-graphs and applies an ε-approximate M-fibration algorithm. Accuracy remains nearly unchanged at small ε but drops sharply between 0.35 and 0.5, a transition attributed to the certified worst-case criterion.

  • Experimental setup: Three trained networks—two MNIST models and one CIFAR-10 model—were compressed post-training by converting them to M-graphs and applying Algorithm 1.The models were LeNet-300-100, LeNet-5, and a CIFAR-10 network; the compressed graphs were then re-converted.
  • Accuracy and compression: For small ε, compressed-network accuracy remains almost unchanged while the numbers of units and parameters decrease.Figure 9 reports surviving units and test accuracy as functions of ε for all three networks.
  • Accuracy and compression: Between 0.35 and 0.5, accuracy drops dramatically in all three networks, marking a sharp phase transition.The transition region is shown as a shaded band in Figure 9.
  • Interpretation: The sharp transition reflects the certified worst-case criterion rather than an intrinsic property of the networks.Heuristics using tight complete-linkage clusters and mean or least-squares representatives instead trade guarantees for smoothly degrading accuracy-versus-size curves.

11 Conclusions

The paper introduces a general framework for fibrations of weighted graphs and establishes uniqueness of their minimum bases up to isomorphism. It also introduces ε-approximate fibrations and applies them to neural-network compression.

  • The paper introduces a general framework for studying fibrations of weighted graphs.
  • The minimum base of a weighted graph is unique up to isomorphism.
  • ε-approximate fibrations can be used to compress neural networks.
Loading 2608.25598v1…