Randomized Block-Krylov Graph Filter

Integrate this at a graph-filter or graph-diffusion layer, before the usual feature-mixing MLP. Let $A$ be a fixed sparse graph operator such as normalized adjacency, a random-walk matrix, or a graph Laplacian; choose a matrix function such as $f(A)=\exp(-\tau A)$ or $f(A)=(I+\tau A)^{-1}$. Given node features $X\in\mathbb{R}^{n\times d}$, sample $r$ Gaussian probe columns $\Omega\in\mathbb{R}^{n\times r}$ and set $B=[X,\Omega]$. Initialize an empty orthonormal basis $Q$. For each of $m$ block steps, compute the sparse product $Z=AB_j$ for the current block, orthogonalize $Z$ against every existing block of $Q$ using modified Gram-Schmidt with reorthogonalization, discard columns whose norm is below a numerical threshold, normalize the remaining columns, and append them to $Q$. Form $H=Q^TAQ$ and evaluate the small dense matrix function $F=f(H)$ with a Schur or Pade routine. Return $Y=QFQ^TX$, discarding the probe output columns. Use stop-gradient on $\Omega$; gradients only need to pass through $X$, $A$ if learnable, and the small matrix-function computation. Estimate the adaptive residual with $\|AY-QHFQ^TX\|_F/\max(1,\|Y\|_F)$ and increase $m$ when it exceeds a tolerance. The paper supplies the block-Krylov projection; residual thresholds, probe count, and stopping rules are engineering choices. First test on Cora or ogbn-arxiv with a GCN whose baseline approximates heat diffusion using 8, 16, or 32 sequential sparse propagation steps. Sweep $r\in\{0,2,4,8\}$ and $m\in\{2,4,6,8\}$. Success means lower error to a high-step diffusion reference at equal sparse matrix multiplications, faster inference at matched validation accuracy, or faster training at equal FLOPs. Record basis memory because storing $Q$ can eliminate the benefit when $m(d+r)$ is large.