Depth-Width Separation for Graph Transformers

Repository: drwjkirkpatrick-web/depth-width-graph-separation
Theorem: Theorem 5 — Pure attention has a strict rank barrier that depth cannot overcome; only FFN width can increase representational rank
Status: Verified — SVD rank tracking on synthetic graphs (Jetson GPU)
Date: 2026-06-20

---

What This Proves

Graph Transformers (GTs) interleave self-attention with feed-forward networks (FFNs). Researchers ask: can we replace FFNs with more attention layers?

Answer: NO.

Theorem 5.1: A depth-$L$ pure-attention GT (no FFN) has node representations bounded by rank $\leq d$ at every layer,> regardless of depth $L$ or graph size $n$.

Theorem 5.2: An FFN with hidden dimension $m$ achieves rank $> d$ in hidden activations, even though output is projected back to $d$.

Theorem 5.3: Consequently, FFN-augmented GTs have strictly larger representational capacity than pure-attention GTs for $m > d$.

---

Quick Start

cd ~/projects/depth-width-graph-separation

# Run GPU verification
source ~/heartlib/.venv/bin/activate
python empirical/verify.py

# Run pytest suite
python -m pytest tests/ -v

---

File Map

depth-width-graph-separation/
├── THEOREM.md              ← Formal theorem statement (3 parts)
├── proof/
│   └── proof.md            ← Full derivations + rank analysis
├── empirical/
│   └── verify.py           ← SVD rank tracking on GT variants
├── tests/
│   └── test_depth_width.py ← pytest suite (12 tests)
├── paper/
│   └── paper.tex           ← AMS-LaTeX paper
└── README.md               ← This file

---

Key Results

Theorem 5.1 — Pure-Attention Rank Barrier

Setup	Metric	Result
$d=8$, $n=16$, depth=1..10	Max rank	8 (exactly $d$)
Multi-head (4 heads)	Barrier	Still $\leq d$
Star graph (degree diversity)	Barrier	Unbroken — still $\leq d$

The rank barrier is a conservation law. Like mixing colored paints — no matter how many times you stir, you can't create new colors from the original palette.

Theorem 5.2 — FFN Hidden Rank Exceeds $d$

Setup	Pure Hidden	FFN Hidden	Gain
$d=8$, $m=32$, $n=16$	8	16	2×

The FFN acts as a prism: input light enters at $d$ wavelengths, the hidden layer splits it into $m$ spectral components, and the output layer merges back to $d$. The splitting creates information that pure attention cannot access.

Theorem 5.3 — Strict Separation

Metric	Pure GT	FFN-GT	Verdict
Max internal rank	8	16	✅ FFN $>$ Pure
Rank bound	$d$	$m$ (hidden)	Capacity separation proved

---

The Three Parts

Part	Claim	Status
5.1	Pure attention rank $\leq d$ (invariant)	✅ Verified (flat across depth)
5.2	FFN hidden rank $> d$ (expansion)	✅ Verified (16 > 8 on star graphs)
5.3	FFN-GT capacity $>$ Pure-GT capacity	✅ Verified (rank separation)

---

Why Depth Fails

Each attention layer computes: $$H^{(\ell)} = \text{softmax}(QK^\top / \sqrt{d_k}) \cdot H^{(\ell-1)} W_V + H^{(\ell-1)}$$

The product $H W_V$ has rank $\leq d_v$. The attention matrix $A$ cannot increase rank (it's a weighted average of rows). The residual adds two rank-$\leq d$ matrices, staying within the same column space.

Depth just remixes the same $d$-dimensional soup.

Why FFN wins: $$Z = \text{ReLU}(H W_1), \quad H' = Z W_2$$

The ReLU creates sparsity patterns: different input rows activate different hidden units. With $m > d$ and row-diverse inputs, $Z$ can have rank up to $m$. The output $H'$ compresses back to $d$, but the hidden layer has already accessed the expanded space.

---

Implications

1. Architecture search: Don't search for "deeper attention" as a replacement for FFN. The rank barrier is structural.
2. Lightweight GTs (no FFN) have a hard expressivity ceiling for tasks requiring high-rank node discrimination.
3. Real-world GTs (GraphGPS, SAN) use both for a reason — the combination is strictly more powerful.

---

Dependencies

• Python ≥ 3.10
• NumPy ≥ 1.26
• PyTorch ≥ 2.0 (GPU on Jetson)
• pytest ≥ 7.0

---

License

MIT.