# Main-Krylov Structural Encoder

- ID: 870
- Canonical URL: https://synthcore.org/idea/870/main-krylov-structural-encoder
- API JSON: https://synthcore.org/api/idea/870.json
- API Markdown: https://synthcore.org/api/idea/870.md
- Verification status: unverified
- Source: [arXiv:2607.13577](https://arxiv.org/abs/2607.13577)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: graph-nn, embedding, inference-speedup
- Math tags: spectral-theory, linear-algebra, graph-theory
- Ratings: usefulness 5/10; difficulty 4/10; novelty 7/10

## Idea description

Add a structural positional channel formed from the Krylov sequence generated by the graph adjacency matrix and the all-ones vector. For graphs with k main eigenvalues, this sequence has rank k, so a GNN can retain all information obtainable from global walk counts using only k node features rather than storing many adjacency powers.

## Mathematical statement

Let G have adjacency matrix A in R^(n x n), all-ones vector j in R^n, distinct adjacency eigenvalues tau_i, and orthogonal projectors P_i onto their eigenspaces. The main angle is beta_i = ||P_i j|| divided by sqrt(n), and tau_i is main exactly when beta_i is nonzero. Define W_L(A) = [j, Aj, A^2j, ..., A^(L-1)j]. By spectral decomposition, A^t j = sum_i tau_i^t P_i j, so the columns of W_L are generated only by eigenspaces with nonzero main angle. If k is the number of main eigenvalues and L is at least k, then rank(W_L) = k. Consequently, there are coefficients c_0 through c_(k-1) satisfying A^k j = sum_{r=0}^{k-1} c_r A^r j. Compute an orthonormal basis Q for the columns of W_L and use each row Q_u as a structural embedding for node u. The paper gives an explicit rank-three example satisfying v_3 = A^3j = 7v_2 + 84v_1.

## Key formulas

- $$\beta_i=\frac{1}{\sqrt{n}}\|P_i\mathbf{j}\|,\qquad \tau_i\text{ is main iff }\beta_i\neq 0.$$
- $$W_L(A)=[\mathbf{j},A\mathbf{j},A^2\mathbf{j},\ldots,A^{L-1}\mathbf{j}],\qquad A^t\mathbf{j}=\sum_{i=1}^{\nu}\tau_i^tP_i\mathbf{j}.$$
- $$\operatorname{rank}W_L=\#\{i:P_i\mathbf{j}\neq0\}=k\quad(L\ge k),\qquad A^k\mathbf{j}=\sum_{r=0}^{k-1}c_rA^r\mathbf{j}.$$
- $$v_3=A^3\mathbf{j}=7v_2+84v_1.$$

## Implementation notes

Integrate the encoder during graph preprocessing, before the node-feature projection of a message-passing GNN. For each graph, let A be its sparse adjacency matrix and initialize w_0 = j. Repeatedly compute w_(t+1) = A w_t. Maintain an orthonormal basis Q using modified Gram-Schmidt: r_t = w_t - Q_t(Q_t^T w_t); if ||r_t||_2 divided by ||w_t||_2 is larger than epsilon, append r_t divided by ||r_t||_2 to Q; otherwise stop or continue until L_max if a fixed-size encoder is required. Pseudocode is: `Q=[]; w=ones(n); for t in range(Lmax): r=w-Q@(Q.T@w); if norm(r)/norm(w)>eps: Q.append(r/norm(r)); w=A@w`. Concatenate Q to the original node features and pass the result to the baseline GNN. Estimate the numerical rank k from the residual threshold epsilon; no eigendecomposition is required. Optionally solve the least-squares system W_k c approximately equal to A^k j, then generate later walk-count channels using the recurrence A^k j = sum_r c_r A^r j instead of additional sparse matrix multiplications. First run on synthetic diameter-five trees, where rank-three cases can be generated directly, and on a small TU graph-classification dataset. Use a 3-layer GIN baseline and compare against 8-step random-walk features and Laplacian eigenvector positional encodings. Measure validation accuracy, preprocessing time, positional-feature memory, and recurrence residual ||A^k j - W_k c|| divided by ||A^k j||. Success is equal or higher accuracy with fewer channels and lower preprocessing cost; for exact rank-three trees, the recurrence residual should approach floating-point precision.

## Disclaimer

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