# Graph Lineages and Skeletal Graph Products

arXiv: https://arxiv.org/abs/2508.00197 · HTML: https://mlsanity.com/paper/2508.00197/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 52 of its 108 references that are in the map.
- First posted on arXiv 31 Jul 2025.

## Builds on (most cited first, 30 of 52)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction](https://mlsanity.com/paper/2404.02905/) (2024)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Progressive Neural Architecture Search](https://mlsanity.com/paper/1712.00559/) (2017)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Neural Architecture Search without Training](https://mlsanity.com/paper/2006.04647/) (2020)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Deep Scale-spaces: Equivariance Over Scale](https://mlsanity.com/paper/1905.11697/) (2019)
- [B-Spline CNNs on Lie Groups](https://mlsanity.com/paper/1909.12057/) (2019)
- [Weak baselines and reporting biases lead to overoptimism in machine learning for fluid-related partial differential equations](https://mlsanity.com/paper/2407.07218/) (2024)
- [A Step Toward Quantifying Independently Reproducible Machine Learning Research](https://mlsanity.com/paper/1909.06674/) (2019)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [Parallel Multiscale Autoregressive Density Estimation](https://mlsanity.com/paper/1703.03664/) (2017)
- [Graph Structure of Neural Networks](https://mlsanity.com/paper/2007.06559/) (2020)
- [Modular Networks: Learning to Decompose Neural Computation](https://mlsanity.com/paper/1811.05249/) (2018)
- [Graph Metanetworks for Processing Diverse Neural Architectures](https://mlsanity.com/paper/2312.04501/) (2023)
- [Semi-Supervised Graph Classification: A Hierarchical Graph Perspective](https://mlsanity.com/paper/1904.05003/) (2019)
- [Learning Algebraic Multigrid Using Graph Neural Networks](https://mlsanity.com/paper/2003.05744/) (2020)
- [Blending Neural Operators and Relaxation Methods in PDE Numerical Solvers](https://mlsanity.com/paper/2208.13273/) (2022)
- [Cognitive Psychology for Deep Neural Networks: A Shape Bias Case Study](https://mlsanity.com/paper/1706.08606/) (2017)
- [Categorical Foundations of Gradient-Based Learning](https://mlsanity.com/paper/2103.01931/) (2021)

## Abstract (arXiv)

Graphs, and sequences of growing graphs, can be used to specify the architecture of mathematical models in many fields including machine learning and computational science. Here we define structured graph "lineages" (ordered by level number) that grow in a hierarchical fashion, so that: (1) the number of graph vertices and edges increases exponentially in level number; (2) bipartite graphs connect successive levels within a graph lineage and, as in multigrid methods, can constrain matrices relating successive levels; (3) using prolongation maps within a graph lineage, process-derived distance measures between graphs at successive levels can be defined; (4) a category of "graded graphs" can be defined, and using it low-cost "skeletal" variants of standard algebraic graph operations and type constructors (cross product, box product, disjoint sum, and function types) can be derived for graded graphs and hence hierarchical graph lineages; (5) these skeletal binary operators have similar but not identical algebraic and category-theoretic properties to their standard counterparts; (6) graph lineages and their skeletal product constructors can approach continuum limit objects. Additional space-efficient unary operators on graded graphs are also derived: thickening, which creates a graph lineage of multiscale graphs, and escalation to a graph lineage of search frontiers (useful as a generalization of adaptive grids and in defining "skeletal" functions). The result is an algebraic type theory for graded graphs and (hierarchical) graph lineages. The approach is expected to be well suited to defining hierarchical model architectures - "hierarchitectures" - and local sampling, search, or optimization algorithms on them. We demonstrate such application to deep neural networks (including visual and feature scale spaces) and to multigrid numerical methods.