# Randomized Block-Krylov Graph Filter

- ID: 2256
- Canonical URL: https://synthcore.org/idea/2256/randomized-block-krylov-graph-filter
- API JSON: https://synthcore.org/api/idea/2256.json
- API Markdown: https://synthcore.org/api/idea/2256.md
- Verification status: unverified
- Source: [arXiv:2608.13714](https://arxiv.org/abs/2608.13714)
- Category: architecture
- Solves: speedup, scalability, accuracy
- ML areas: graph-nn, diffusion, inference-speedup
- Math tags: linear-algebra, numerical-analysis, random-matrix
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace a long sequence of graph propagation steps used to approximate a spectral graph filter with one block Krylov projection. Construct a basis from the input node features together with a small number of Gaussian probe vectors, evaluate the desired matrix function only on the resulting small projected matrix, and retain the output columns corresponding to the original features.

## Mathematical statement

The paper targets the matrix-function-vector expression $f(A)\boldsymbol{b}$, where $A\in\mathbb{R}^{n\times n}$ is a large operator, $\boldsymbol{b}\in\mathbb{R}^n$ is an input vector, and $f(A)$ is defined through matrix functional calculus. For a neural layer with $d$ feature channels, replace the single vector by a block $X\in\mathbb{R}^{n\times d}$ and draw $r$ independent probe vectors $\Omega\in\mathbb{R}^{n\times r}$ with entries $\Omega_{ij}\sim\mathcal{N}(0,1)$. Form the block Krylov space $\mathcal{K}_m(A,B)=\operatorname{span}\{B,AB,A^2B,\ldots,A^{m-1}B\}$ for $B=[X\;\Omega]\in\mathbb{R}^{n\times(d+r)}$. Let $Q\in\mathbb{R}^{n\times q}$ have orthonormal columns spanning this space, with $q\le m(d+r)$, and let $H=Q^{\mathsf T}AQ$ be the small projected operator. The approximation is $f(A)B\approx Qf(H)Q^{\mathsf T}B$, and the desired graph-layer output is the first $d$ columns, $Y\approx Qf(H)Q^{\mathsf T}X$. The random probes enrich directions that may be weakly represented in $X$; the extracted text does not provide a specific error theorem or explicit error constant, so the residual must be used for adaptive validation.

## Key formulas

- $$f(A)\boldsymbol{b},\qquad A\in\mathbb{R}^{n\times n},\ \boldsymbol{b}\in\mathbb{R}^{n}.$$
- $$\mathcal{K}_m(A,B)=\operatorname{span}\{B,AB,A^2B,\ldots,A^{m-1}B\},\qquad B=[X\;\Omega],\quad \Omega_{ij}\sim\mathcal{N}(0,1).$$
- $$H=Q^{\mathsf T}AQ,\qquad f(A)B\approx Qf(H)Q^{\mathsf T}B,\qquad Y=\bigl[Qf(H)Q^{\mathsf T}B\bigr]_{:,1:d}.$$
- $$\widehat{e}_m=\frac{\|A\widehat{Y}-QHf(H)Q^{\mathsf T}X\|_F}{\max(1,\|\widehat{Y}\|_F)},\qquad \widehat{Y}=Qf(H)Q^{\mathsf T}X.$$

## Implementation notes

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.

## Disclaimer

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