# Sparse rational fractional graph layer

- ID: 1691
- Canonical URL: https://synthcore.org/idea/1691/sparse-rational-fractional-graph-layer
- API JSON: https://synthcore.org/api/idea/1691.json
- API Markdown: https://synthcore.org/api/idea/1691.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.01932](https://arxiv.org/abs/2608.01932)
- Category: architecture
- Solves: accuracy, scalability, speedup
- ML areas: graph-nn, architecture, inference-speedup
- Math tags: spectral-theory, graph-theory, functional-analysis, numerical-analysis
- Ratings: usefulness 7/10; difficulty 6/10; novelty 5/10

## Idea description

Replace a stack of local message-passing layers by a fractional spectral graph filter implemented through a small bank of sparse shifted Laplacian solves. The fractional exponent controls how strongly the layer mixes information across graph distances, while rational approximation avoids dense eigendecomposition and supports efficient differentiation through iterative linear solvers.

## Mathematical statement

Let $G=(V,E)$ be a weighted graph with sparse symmetric positive-semidefinite Laplacian $L$, let $\tau>0$ be a shift, and define the shifted operator $A=L+\tau I$, which is positive definite. For $0<\alpha<1$, the fractional inverse has the resolvent representation $A^{-\alpha}=\frac{\sin(\pi\alpha)}{\pi}\int_0^\infty \mu^{-\alpha}(A+\mu I)^{-1}\,d\mu$. A rational quadrature approximation replaces the integral by $r_m(A)=\sum_{j=1}^{m}w_j(A+\mu_j I)^{-1}$, where nodes $\mu_j>0$ and weights $w_j>0$ approximate the integral. Given node features $X\in\mathbb{R}^{|V|\times d}$, compute $Z_j=(A+\mu_jI)^{-1}X$ from sparse linear solves and form $H=\sigma(\sum_{j=1}^{m}w_jZ_jW_j+XW_0)$. The transferable property is that a nonlocal fractional operator is represented by a short sum of local elliptic resolvents, each preserving graph sparsity. In an implementation, $\mu_j,w_j$ may be fixed by quadrature or learned subject to positivity, while $\alpha$ can be fixed, searched, or parameterized as $\alpha=\operatorname{sigmoid}(a)\in(0,1)$.

## Key formulas

- $$A=L+\tau I,\qquad A^{-\alpha}=\frac{\sin(\pi\alpha)}{\pi}\int_0^\infty \mu^{-\alpha}(A+\mu I)^{-1}\,d\mu,\quad 0<\alpha<1,$$
- $$r_m(A)=\sum_{j=1}^{m}w_j(A+\mu_jI)^{-1},\qquad Z_j=(L+(\tau+\mu_j)I)^{-1}X,$$
- $$H=\sigma\!\left(XW_0+\sum_{j=1}^{m}w_jZ_jW_j\right).$$

## Implementation notes

(1) Exact integration point: use this as a drop-in replacement for two to six standard graph-convolution/message-passing layers in a GNN. For each graph, construct its sparse weighted Laplacian $L=D-C$, where $C$ is the sparse adjacency matrix and $D_{ii}=\sum_k C_{ik}$. Use a small shift $\tau=10^{-3}$ or tune it on the validation set. Apply the filter to node features $X$ before the classifier, or insert it between residual blocks. Start with $m=4$ resolvents and one shared feature projection to isolate the operator’s effect. (2) Pseudocode: `A = sparse_laplacian(edge_index, edge_weight) + tau*I`; `H = X @ W0`; for `j in range(m)`: `B = solve_sparse(A + mu[j]*I, X)`; `H += w[j] * (B @ W[j])`; `H = activation(H)`; add a residual connection and normalization. Each solve can use preconditioned conjugate gradients to tolerance $10^{-5}$; for fixed graphs, cache a factorization or preconditioner for every shift. Backpropagate through unrolled CG for an MVP, then compare with implicit differentiation through $(A+\mu_jI)Z_j=X$. (3) Compute from the mathematics: the resolvent form, positive shifts, sparse systems, and weighted sum. Estimate empirically: choose $\alpha$, $\tau$, $m$, quadrature nodes $\mu_j$, and weights $w_j$. A practical initialization is logarithmically spaced $\mu_j$ between $0.01\lambda_{\max}$ and $100\lambda_{\max}$, with weights obtained by least-squares fitting $r_m(\lambda)\approx(\lambda+\tau)^{-\alpha}$ over logarithmically spaced spectral frequencies; estimate $\lambda_{\max}$ with 10 sparse power iterations. Enforce $w_j>0$ with softplus and optionally regularize the fit on held-out spectral frequencies. (4) First cheap experiment: use a 2-layer GCN baseline and replace its message-passing stack with the rational layer on ogbn-arxiv or a synthetic long-range node-classification dataset where labels depend on nodes 10--20 hops away. Compare $m\in\{2,4,8\}$ against GCN, APPNP, and a polynomial graph filter at equal hidden width. Record validation accuracy, wall-clock time, peak memory, number of sparse matrix-vector products, and accuracy as graph diameter increases. Success means higher long-range accuracy than a 2-layer GCN without materially increasing memory, or matching a deeper 8--16-layer GNN with fewer sequential propagation steps and faster loss descent.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a sparse rational fractional graph layer using positive shifted-Laplacian resolvents and NNLS-fitted weights. The mechanism manifested: relative spectral error fell from 17.1% at m=1 to 0.84% at m=4, inverse-norm and condition-number predictions matched measured values to numerical precision, and influence beyond radius 8 increased monotonically from 0.004% to 0.402% as alpha rose from 0.2 to 0.8. In the tiny classification test, the rational layer reached 0.734 accuracy versus 0.484 for two-step propagation, with comparable runtime; this is promising but not evidence of a general speedup.

### Mechanism check

- Verdict: Built a sparse rational fractional graph layer using positive shifted-Laplacian resolvents and NNLS-fitted weights. The mechanism manifested: relative spectral error fell from 17.1% at m=1 to 0.84% at m=4, inverse-norm and condition-number predictions matched measured values to numerical precision, and influence beyond radius 8 increased monotonically from 0.004% to 0.402% as alpha rose from 0.2 to 0.8. In the tiny classification test, the rational layer reached 0.734 accuracy versus 0.484 for two-step propagation, with comparable runtime; this is promising but not evidence of a general speedup.
- Confidence: 8/10
- Limitations: Only a 128-node cycle graph and one fixed seed/settings were tested. Solves used SciPy direct sparse solves rather than iterative preconditioned CG or differentiable PyTorch GPU kernels; no real benchmark, training-through-layer experiment, memory profiling, FLOP accounting, graph-family sweep, or comparison with APPNP/deep GCN was performed. The m=16 error was slightly worse than m=8, so monotonic improvement is empirical rather than guaranteed for this NNLS/quadrature setup.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0626
- Paired wins: 1/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/624/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/624/bench_report.json)
- [experiment.py](https://synthcore.org/code/624/experiment.py)
- [report.md](https://synthcore.org/code/624/report.md)
- [report_bench_2026-08-31T200355.md](https://synthcore.org/code/624/report_bench_2026-08-31T200355.md)
- [results.json](https://synthcore.org/code/624/results.json)
- [Download all files as ZIP](https://synthcore.org/download/624)

## Disclaimer

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