# Compressed threshold-overlap Gram layer

- ID: 481
- Canonical URL: https://synthcore.org/idea/481/compressed-threshold-overlap-gram-layer
- API JSON: https://synthcore.org/api/idea/481.json
- API Markdown: https://synthcore.org/api/idea/481.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.06480](https://arxiv.org/abs/2607.06480)
- Category: architecture
- Solves: memory, scalability, accuracy
- ML areas: graph-nn, attention, embedding, memory
- Math tags: linear-algebra, representation-theory, algebra, combinatorics
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Represent each k-element object by a vector in dimension \(r=\binom{n-2(k-s)}{s}\), and use a PSD Gram matrix to encode the rule that pairs with intersection smaller than s have zero similarity while pairs with intersection at least s have nonzero similarity. Insert this representation into set encoders, graph neural networks, or overlap-aware attention instead of allocating one feature for every s-subset.

## Mathematical statement

For the graph \(J_{\ge s}(n,k)\), vertices are all k-subsets \(S\subseteq[n]=\{1,\ldots,n\}\), and distinct vertices \(S,T\) are adjacent exactly when \(|S\cap T|\ge s\). The paper proves, for \(k\ge2\), \(1\le s\le k-1\), and \(n\ge2k-s\), that the least rank of a symmetric matrix with off-diagonal zeros exactly on nonedges is \(r=\binom{n-2(k-s)}{s}\), over every infinite field. It also proves that the least rank among real positive-semidefinite matrices with this pattern is the same \(r\). A PSD matrix has the form \(K_{S,T}=\langle z_S,z_T\rangle\) for vectors \(z_S\in\mathbb R^r\), so the theorem supplies a target dimension for overlap embeddings. The construction uses the s-th exterior power of a bilinear form: for decomposable wedge vectors, \(\langle v_1\wedge\cdots\wedge v_s,w_1\wedge\cdots\wedge w_s\rangle_{\wedge^s B}=\det(B(v_i,w_j))\). Lagrange interpolation combines exterior-power terms so that intersection sizes \(0,1,\ldots,s-1\) are annihilated, while a generic parameter choice keeps values for intersection sizes at least s nonzero. In the real case, interlacing parameters make the underlying bilinear form positive definite, yielding a PSD matrix. The ML adaptation uses the theorem's rank as a hard embedding-width target and learns or numerically searches for the factor \(Z\).

## Key formulas

- $$\operatorname{mr}^{\mathbb F}\!\left(J_{\ge s}(n,k)\right)=\operatorname{mr}_{+}^{\mathbb R}\!\left(J_{\ge s}(n,k)\right)=\binom{n-2(k-s)}{s},\qquad n\ge 2k-s.$$
- $$K_{S,T}=\langle z_S,z_T\rangle=(ZZ^{\top})_{S,T},\qquad z_S\in\mathbb R^r,\quad r=\binom{n-2(k-s)}{s},$$
- $$\left\langle v_1\wedge\cdots\wedge v_s,\,w_1\wedge\cdots\wedge w_s\right\rangle_{\wedge^s B}=\det\!\left(B(v_i,w_j)\right)_{i,j=1}^{s},$$
- $$\mathcal L(Z)=\sum_{\substack{S\ne T\\|S\cap T|<s}}\!\left|\langle z_S,z_T\rangle\right|^2+\lambda\sum_{\substack{S\ne T\\|S\cap T|\ge s}}\!\max\!\left(0,\,\epsilon-\left|\langle z_S,z_T\rangle\right|\right)^2+\mu\left\|Z^{\top}Z-I_r\right\|_F^2.$$

## Implementation notes

1. Integration point: use this as a fixed-width embedding layer for objects represented by k-element subsets, or as an overlap bias/kernel in set attention. Given a minibatch of sets \(S_1,\ldots,S_b\), store one trainable vector \(z_S\in\mathbb R^r\), or generate \(z_S\) from shared element embeddings followed by an exterior-power pooling module. Replace ordinary dot-product similarity by \(K_{ij}=z_{S_i}^{\top}z_{S_j}\); in attention, add \(\log(|K_{ij}|+\delta)\) as an overlap bias or use a nonnegative transformed version of K as a gated message weight.

2. MVP pseudocode:
```text
r = binom(n - 2*(k-s), s)
Z = trainable_embedding_table(num_k_subsets, r)
for batch of sets S[1:b]:
    K = Z[S] @ Z[S].T
    loss = 0
    for i != j:
        if intersection_size(S[i], S[j]) < s:
            loss += K[i,j]**2
        else:
            loss += relu(epsilon - abs(K[i,j]))**2
    loss += mu * frobenius_norm(Z.T @ Z - I_r)**2
    update network and Z
```
The first term enforces the paper's prescribed zero pattern; the second prevents the trivial all-zero solution; the orthogonality term keeps the learned factor numerically well-conditioned. For a scalable version, parameterize Z through element embeddings and sampled s-wedge features rather than a table over all \(\binom nk\) sets.

3. Computed from the paper: the admissible parameter regime, target rank r, PSD factorization requirement, and exterior-power determinant identity. Estimated empirically: the actual factor Z, positive-pair margins, and whether the rank target is numerically attainable. Monitor the largest forbidden-pair similarity, the smallest positive-pair magnitude, the effective numerical rank of Z, and downstream validation accuracy.

4. First experiment: use \(n=12,k=4,s=2\), where the theorem predicts \(r=\binom{8}{2}=28\), versus the naive pair-feature dimension \(\binom{12}{2}=66\). Train a small DeepSets or set-transformer model on synthetic classification and retrieval tasks whose labels depend on whether query and candidate sets overlap in at least two elements. Compare the proposed 28-dimensional PSD kernel, the 66-dimensional s-subset incidence kernel, and an unconstrained learned embedding at matched parameter counts. Success means at least 2x lower embedding memory with equal retrieval accuracy, or faster convergence at equal width; also report forbidden-pair leakage \(\max_{|S\cap T|<s}|K_{S,T}|\).

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a PyTorch MVP for the compressed threshold-overlap Gram layer, including target-rank calculation, PSD Gram fitting, leakage and margin diagnostics, and a retrieval comparison. The factors had the predicted numerical rank and were PSD up to numerical precision, but compressed retrieval was 0.46 versus 1.00 for the 66-dimensional incidence baseline. The 2.36x memory reduction was real, but this implementation did not preserve downstream retrieval behavior.

### Mechanism check

- Verdict: Built a PyTorch MVP for the compressed threshold-overlap Gram layer, including target-rank calculation, PSD Gram fitting, leakage and margin diagnostics, and a retrieval comparison. The factors had the predicted numerical rank and were PSD up to numerical precision, but compressed retrieval was 0.46 versus 1.00 for the 66-dimensional incidence baseline. The 2.36x memory reduction was real, but this implementation did not preserve downstream retrieval behavior.
- Confidence: 9/10
- Limitations: The exterior-power identity check evaluates the same determinant expression on both sides rather than constructing explicit wedge coordinates, so it is only a weak algebraic sanity check. The learned table was optimized directly and was not integrated into a DeepSets or GNN model; no larger-scale or repeated-seed study was performed.

## Artifacts

- [experiment.py](https://synthcore.org/code/1353/experiment.py)
- [report.md](https://synthcore.org/code/1353/report.md)
- [Download all files as ZIP](https://synthcore.org/download/1353)

## Disclaimer

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