Main-Krylov Structural Encoder

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.