# Sparse-Graph Tensorized Linear Layer

- ID: 1731
- Canonical URL: https://synthcore.org/idea/1731/sparse-graph-tensorized-linear-layer
- API JSON: https://synthcore.org/api/idea/1731.json
- API Markdown: https://synthcore.org/api/idea/1731.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.02849](https://arxiv.org/abs/2608.02849)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: mlp, transformer, inference-speedup, quantization
- Math tags: tensor-decomposition, linear-algebra, graph-theory, approximation-theory
- Ratings: usefulness 8/10; difficulty 6/10; novelty 5/10

## Idea description

Replace a dense neural-network weight tensor with a graph tensor network whose physical modes and internal edge ranks are specified by a sparse rank-adjacency matrix. Unlike tensor-train or hierarchical Tucker layers, the graph can contain selected cycles and skip connections between tensor modes, allowing the factorization topology to match correlations in the weight tensor. Fit the layer with GTN-SVD at a prescribed tolerance and compare accuracy, parameter count, and tensor-contraction throughput against dense and TT baselines.

## Mathematical statement

A graph tensor network has p cores, with physical mode size n_j on vertex j and edge rank r_{i,j} on every connected pair. These choices are encoded by the symmetric rank-adjacency matrix R: R_{ij}=n_i when i=j, R_{ij}=r_{i,j} when an edge connects i and j, and R_{ij}=1 when no edge exists; diagonal entries n_j=1 may represent internal vertices. The represented tensor is the contraction W(i_1,...,i_d)=sum over all edge indices of the product of core entries G_k(i_k, incident edge indices), with unit-rank absent edges omitted. GTN-SVD uses the fact that every graph is a subgraph of the complete graph K_p, embeds the target tensor into the corresponding fully connected tensor network, and applies recursive SVDs after grouping indices into matrix unfoldings. For target tensor X and approximation X_tilde, the construction is controlled by the relative Frobenius guarantee ||X-X_tilde||_F <= epsilon ||X||_F. At each SVD A=U Sigma V^T, rank truncation uses the discarded singular-value energy sum_{q>r} sigma_q(A)^2.

## Key formulas

- $$\mathbf{R}_{ij}=\begin{cases}n_i,&i=j,\\ r_{i,j},&i\neq j\text{ and an edge connects }i\text{ and }j,\\ 1,&i\neq j\text{ and no edge connects }i\text{ and }j.\end{cases}$$
- $$\overline{i_1i_2\ldots i_d}=1+\sum_{k=1}^{d}(i_k-1)\prod_{j=1}^{k-1}n_j$$
- $$\|\mathcal{X}-\widetilde{\mathcal{X}}\|_F\leq\varepsilon\|\mathcal{X}\|_F$$
- $$\|A-A_r\|_F^2=\sum_{q>r}\sigma_q(A)^2,\qquad r=\min\left\{s:\sum_{q>s}\sigma_q(A)^2\leq\delta^2\|\mathcal{X}\|_F^2\right\}$$

## Implementation notes

Integrate this at the weight tensor of an MLP projection or Transformer output projection. Reshape a dense matrix W in R^{m x n} into a d-way tensor X with physical dimensions n_1,...,n_d, and choose sparse candidate graphs: a path, a tree, a ring, and a path augmented with one or two chords. Store one core G_k per vertex, with dimensions n_k times the ranks of all incident edges. For offline decomposition, use the following procedure: (1) input X, the symmetric rank-adjacency matrix R, and tolerance epsilon; (2) choose a traceable path through the graph; (3) at each elimination step, reshape the remaining tensor into a matrix using the multi-index ordering above; (4) compute A=U Sigma V^T; (5) retain the smallest rank r such that the discarded singular-value energy is at most delta_k^2 ||X||_F^2, with sum_k delta_k^2 <= epsilon^2; (6) absorb U Sigma into the next incident core and continue until all cores are produced. In training and inference, contract the graph directly with the tensorized input rather than materializing W. The exact mathematical quantities are SVD factors, graph ranks, and truncation energy. Empirically measure which topology gives the best validation loss at fixed parameter count; optionally add a chord when the corresponding mode-group unfolding has slowly decaying singular values. Start with a 4-layer MLP on CIFAR-10 and a small Transformer on WikiText-103, replacing one projection layer. Compare dense, TT, and graph layers at matched loss. Success is at least 2x fewer parameters at equal validation loss, or lower loss than TT at equal parameter count, with measured reconstruction error tracking epsilon.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built a readable sparse graph tensor-network MVP using torch.einsum, with a TT-SVD baseline, topology fitting, parameter counts, and throughput measurements. The numerical checks confirmed the Frobenius tolerance guarantee and monotonic rank/parameter reduction as tolerance loosened; ring/chord connectivity substantially outperformed a path on a chord-generated tensor. This is a mechanism-level success rather than a definitive end-to-end win: the chord only slightly improved over the ring at higher parameter cost, and no CIFAR-10 or Transformer benchmark was run.

### Mechanism check

- Verdict: Built a readable sparse graph tensor-network MVP using torch.einsum, with a TT-SVD baseline, topology fitting, parameter counts, and throughput measurements. The numerical checks confirmed the Frobenius tolerance guarantee and monotonic rank/parameter reduction as tolerance loosened; ring/chord connectivity substantially outperformed a path on a chord-generated tensor. This is a mechanism-level success rather than a definitive end-to-end win: the chord only slightly improved over the ring at higher parameter cost, and no CIFAR-10 or Transformer benchmark was run.
- Confidence: 8/10
- Limitations: Only a 4-way synthetic tensor was tested. Graph fitting used 400-step Adam optimization rather than a full GTN-SVD elimination algorithm; no CIFAR-10, Transformer, matched-parameter training, production contraction kernel, or large-scale speed/memory evaluation was performed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/549/bench_report.json)
- [experiment.py](https://synthcore.org/code/549/experiment.py)
- [report.md](https://synthcore.org/code/549/report.md)
- [report_bench_2026-08-31T173413.md](https://synthcore.org/code/549/report_bench_2026-08-31T173413.md)
- [results.json](https://synthcore.org/code/549/results.json)
- [stage2_bench.py](https://synthcore.org/code/549/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/549)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.