Matroid-rank interaction bottleneck

Integrate the method at the interaction tensor of a graph neural network or structured attention layer. Let \(X\in\mathbb{R}^{n\times d}\) and \(Y\in\mathbb{R}^{m\times d}\) be node or token embeddings. For each edge pair \(e=(i,k)\in E(G)\), \(f=(j,l)\in E(H)\), define a candidate scalar interaction \(\phi_{e,f}=\langle X_i,Y_j\rangle\langle X_k,Y_l\rangle-\langle X_i,Y_l\rangle\langle X_k,Y_j\rangle\), or replace it with the actual attention feature used by the baseline. During a calibration pass, sample 8--32 random probe vectors \(v_t\) and estimate each Jacobian column through directional derivatives \(j_q=[v_t^T\partial\phi_q/\partial\operatorname{vec}(X,Y)]_t\). Stack the columns into \(J\), run rank-revealing QR or greedy Gram-Schmidt, and retain pivot indices whose residual norm exceeds \(\tau=10^{-3}\|J\|_2\), with \(\tau\) optionally tuned on a calibration set. Pseudocode: form candidate set \(Q\); compute or approximate \(J\); \(B\leftarrow\operatorname{QR\text{-}pivot}(J;\tau)\); during training compute only \(\{\phi_q:q\in B\}\); concatenate them and apply the existing projection/MLP. Refresh \(B\) every 1,000--10,000 steps using an exponential moving average of \(J^TJ\), or keep it fixed for a cheaper MVP. The paper supplies the rank and nullspace rationale; the Jacobian proxy, threshold, and refresh schedule are empirical. First test a 4-layer graph transformer or GAT on ZINC or ogbg-molhiv, with 4--8 times as many candidate edge-pair interactions as the desired bottleneck. Compare dense, random, magnitude, and matroid-rank selection at matched retained-feature counts. Measure interaction FLOPs, activation memory, validation score, and rank-versus-budget curves. A successful result is at least 2x lower interaction memory or FLOPs with no validation degradation, or higher accuracy than random and magnitude pruning at equal budget.