# Indefinite Sketched Nyström Interaction

- ID: 2625
- Canonical URL: https://synthcore.org/idea/2625/indefinite-sketched-nystr-m-interaction
- API JSON: https://synthcore.org/api/idea/2625.json
- API Markdown: https://synthcore.org/api/idea/2625.md
- Verification status: unverified
- Source: [arXiv:2608.20531](https://arxiv.org/abs/2608.20531)
- Category: architecture
- Solves: speedup, memory, stability
- ML areas: graph-nn, attention, inference-speedup, memory
- Math tags: linear-algebra, optimization, random-matrix, numerical-analysis
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Approximate a dense symmetric interaction matrix in a neural layer by \(\widehat A=C\widehat M C^{\top}\), but compute the small core \(\widehat M\) from a two-sided sketched least-squares fit rather than from the landmark principal submatrix. This preserves signed or indefinite directions and avoids exploding outputs caused by an almost-singular \(A(I,I)\).

## Mathematical statement

The classical Nyström construction uses \(A\approx C A(I,I)^{\dagger}C^{\top}\), where \(A\in\mathbb R^{n\times n}\) is symmetric, \(I\) is a set of \(r\) landmark indices, \(C=A(:,I)\in\mathbb R^{n\times r}\), and \(A(I,I)^{\dagger}\) is the Moore-Penrose pseudoinverse. The paper instead chooses the core by minimizing \(\min_{M\in\mathbb R^{r\times r}}\|X(A-CMC^{\top})X^{\top}\|_{F}\), where \(X\in\mathbb R^{t\times n}\) is a Gaussian or leverage-score row sketch and \(t>r\). Let \(Z=XC\in\mathbb R^{t\times r}\), \(S=XAX^{\top}\in\mathbb R^{t\times t}\), and \(G=Z^{\top}Z\). When \(Z\) has full column rank, the unconstrained least-squares solution is \(\widehat M=G^{-1}Z^{\top}SZG^{-1}\); in implementation use \(G+\lambda I_r\) or a QR/SVD solve. If \(A\) is symmetric, \(S\) and the fitted core are symmetric. The resulting neural interaction is \(\widehat A H=C\widehat M(C^{\top}H)\), and the indefinite eigenvalues of \(\widehat M\) are retained instead of being clipped as in PSD-only approximations.

## Key formulas

- $$A\approx C\,A(I,I)^{\dagger}C^{\top},\qquad C:=A(:,I)\in\mathbb R^{n\times r}.$$
- $$\widehat M=\arg\min_{M\in\mathbb R^{r\times r}}\left\|X(A-CMC^{\top})X^{\top}\right\|_{F},\qquad X\in\mathbb R^{t\times n},\quad t>r.$$
- $$Z=XC,\quad S=XAX^{\top},\quad G=Z^{\top}Z,\qquad \widehat M=(G+\lambda I_r)^{-1}Z^{\top}SZ(G+\lambda I_r)^{-1}.$$
- $$\widehat A H=C\widehat M(C^{\top}H),\qquad \text{cost }O(nrd+r^{2}d)\text{ instead of }O(n^{2}d).$$

## Implementation notes

(1) Integration point: replace a dense symmetric pairwise interaction AH in a graph neural network, set transformer, or symmetric token mixer. Given node or token features H in R^(n by d), construct a symmetric affinity A_ij = k(h_i,h_j), allowing signed kernels such as tanh(q_i^T q_j divided by sqrt(d)), centered dot products, or signed graph weights. Select r landmark indices I, form C = A[:,I], and use a sketch with t = 4r rows. (2) Pseudocode: choose I; sample X in R^(t by n) with entries distributed as N(0,1/t), or select t rows and rescale them; compute Z = XC, S = XAX^T, and G = Z^T Z; set M_hat = solve(G + lambda I, Z^T S Z) followed by a right solve with (G + lambda I), where lambda = 1e-4 times trace(G)/r; return Y = C M_hat (C^T H). Use QR or Cholesky solves rather than explicit inverses. (3) The paper supplies the sketched objective and core formula; estimate A, C, and S from kernel evaluations. Landmark selection can initially be uniform, then be compared with approximate leverage scores from row norms of C. Symmetrize numerically with M_hat = (M_hat + M_hat^T)/2, stop gradients through landmark indices, and optionally recompute the core every few training steps. (4) First experiment: use a 2-layer signed graph convolution or set-classification model on Cora, Citeseer, or a synthetic signed stochastic block model with n = 1000 and r in {32,64,128}. Compare dense AH, classical Nystrom C A(I,I)^dagger C^T H, and the sketched core at equal hidden width. Measure wall-clock time, peak memory, validation accuracy, and the condition number of the landmark core. Success is at least 3 times lower interaction cost or memory at n >= 2000, no instability from indefinite affinities, and accuracy within 1 percentage point of dense propagation; additionally test whether the sketched method beats classical Nystrom specifically when A(I,I) is nearly singular.

## Disclaimer

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