△ Mechanism confirmed, baseline not beaten 2026

Sparse rational fractional graph layer

Implementation & benchmark of arXiv:2608.01932 — Numerical approximation of fractional diffusion equations on metric graphs

Usefulness7/10

Difficulty6/10

Novelty5/10

Architecture Accuracy Scalability Speedup Graph nn Architecture Inference speedup Spectral theory Graph theory Functional analysis Numerical analysis

Source paper: Numerical approximation of fractional diffusion equations on metric graphs arXiv:2608.01932 ⓘ · analyzed Aug 31, 2026

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

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.

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).$$

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)$.

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

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

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.

Agent confidence: 8/10

Baseline: Two-step normalized-Laplacian propagation: accuracy 0.484375; feature/fit time 0.0181 s.
Idea: 4-resolvent rational layer: accuracy 0.734375; feature/fit time 0.0211 s; maximum relative spectral error 0.0177; maximum sparse-solve residual 4.12e-16.
Math predictions: Bank relative L2 error: m=1 0.1706, m=2 0.0447, m=4 0.00840, m=8 0.00577, m=16 0.00581. Shift stability predictions matched measurements for all shifts 0.001-2.0. Radius-8 outside-energy fraction increased 4.04e-5, 3.93e-4, 1.57e-3, 4.02e-3 for alpha 0.2, 0.4, 0.6, 0.8.

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.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.01932) Sep 2, 2026

No significant difference vs. the tuned baseline (+102.7%, p=0.0626, wins 1 / 8 paired seeds).

Benchmark: Geometric_graph_diffusion
Model: custom_graph_filter
Paired seeds: 8
Baseline mean: 0.0366
Idea mean: 0.0742
Effect (Δ): 0.0376 (+102.7%; negative = idea better)
Wins: 1 / 8 paired seeds
p-value: 0.0626 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±106.0%
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 9 configs

Limitations:

Used the small built-in geometric graph diffusion track with 24-node dense batched solves rather than production sparse iterative GPU solves; did not test ogbn-arxiv, larger graph families, APPNP/deep GCN, wall-clock scaling, memory scaling, or cached sparse factorizations.

How to run: python3 bench_experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented an end-to-end sparse rational fractional graph layer and matched two-step propagation baseline on the structurally appropriate geometric graph diffusion track. The trained-model mechanism signature was confirmed (predicted long-range influence 0.224 versus observed 0.390 within tolerance), but the rational model had higher test MSE than baseline (0.0742 versus 0.0366), with paired delta +0.0376 and permutation p=0.0626, so there was no significant win.

Baseline: Best swept config lr=0.003, steps=2; 8-seed test MSE mean 0.0366054, std 0.0588916.
Idea: Best parity-swept config lr=0.01, m=8; 8-seed test MSE mean 0.0742067, std 0.0315612.
Mechanism signature: Predicted long-range influence 0.2239789; observed trained-model input-gradient influence 0.3903521; tolerance 0.25; confirmed=true.
Paired delta: idea - baseline = +0.0376013 MSE; idea wins 1/8 pairs; permutation p=0.0626.

Benchmark result