Idea description

Replace uniform node minibatches in a GNN with a coreset selected from a small random candidate set using local Laplacian-column coherence. Select nodes whose connectivity signatures are least redundant with already selected nodes, while retaining inverse-probability weights for unbiased loss estimates. This should improve coverage of weakly connected graph clusters and preserve smooth graph signals at the same batch size.

Formulas

$$L=U\Lambda U^{\top}=\sum_{k=0}^{n-1}\lambda_k u_k u_k^{\top},\qquad 0=\lambda_0\leq\lambda_1\leq\cdots\leq\lambda_{n-1}.$$

$$\hat f=U^{\top}f,\qquad \hat f_k=u_k^{\top}f.$$

$$c(i,S)=\max_{j\in S}\frac{|L_{:,i}^{\top}L_{:,j}|}{\|L_{:,i}\|_2\|L_{:,j}\|_2+\epsilon},\qquad i_t=\arg\min_{i\in C\setminus S_t}c(i,S_t),\quad S_{t+1}=S_t\cup\{i_t\}.$$

$$\widehat{\mathcal L}(\theta)=\frac{1}{n}\sum_{i\in S}\frac{\ell(f_\theta,i)}{p_i},\qquad p_i\approx\frac{\#\{\text{selection runs containing }i\}}{R}.$$

Mathematical statement

The paper represents the graph Laplacian as $L=U\Lambda U^{\top}=\sum_{k=0}^{n-1}\lambda_k u_k u_k^{\top}$, where $L=D-A$ is the symmetric Laplacian of an $n$-node graph, $U=[u_0,\ldots,u_{n-1}]$ contains orthonormal eigenvectors, and $0=\lambda_0\leq\cdots\leq\lambda_{n-1}$ are eigenvalues. The $i$-th column $L_{:,i}$ is a local connectivity signature containing node $i$'s degree on the diagonal and edge weights to neighbors off-diagonal. The graph Fourier coefficients are $\hat f=U^{\top}f$, so a graph signal $f$ is low-frequency or band-limited when it is concentrated in eigenvectors with small $\lambda_k$; such signals are smooth over strongly connected regions. The abstract's minimum-inner-product greedy rule is operationalized here as a normalized coherence score: for candidate node $i$ and already selected set $S$, $c(i,S)=\max_{j\in S}|L_{:,i}^{\top}L_{:,j}|/(\|L_{:,i}\|_2\|L_{:,j}\|_2+\epsilon)$. Choosing $\arg\min_i c(i,S)$ favors locally distinct connectivity signatures and reduces redundant samples. The candidate set is a fresh random subset of nodes, so the algorithm never constructs all of $L$; each required column is obtained from adjacency lists. For a weighted sampled training loss, if node $i$ is selected with estimated probability $p_i$, use $\widehat{\mathcal L}=n^{-1}\sum_{i\in S}\ell_i/p_i$, where $\ell_i$ is the node loss and $p_i$ is estimated by repeating the candidate-and-greedy procedure or tracked with an exponential moving average.

Implementation notes

(1) Integration point: modify the node-batch sampler before the GNN forward pass, not the message-passing layers. Given a graph in CSR or adjacency-list form, sample a candidate pool $C$ of $M$ nodes uniformly or from the training split. Build a Laplacian column on demand: for node $i$, return a sparse vector with value $d_i$ at coordinate $i$ and value $-w_{ij}$ at every neighbor $j$; do not allocate an $n$-by-$n$ matrix. (2) Pseudocode: initialize $S=\{\text{random seed}\}$. For $t=1,\ldots,B-1$, draw or refresh $C$; for every $i\in C\setminus S$, compute $q_i=d_i^2+\sum_{j\sim i}w_{ij}^2$ and score $c_i=\max_{j\in S}|\operatorname{dot\_sparse}(L_i,L_j)|/(\sqrt{q_iq_j}+\epsilon)$; select $i=\arg\min c_i$ and add it to $S$. Run the GNN on $S$ plus the required one- or two-hop frontier, and compute supervised losses only on $S$. (3) The sparse column construction, inner products, and greedy update come from the paper's mathematics. Estimate $p_i$ empirically using $R$ sampler repetitions before training, or maintain an exponential moving average of selection frequencies; clip $1/p_i$ to control gradient variance. (4) First experiment: train a 2-layer GraphSAGE or GCN on Cora, Citeseer, and a synthetic two-block stochastic block model, matching uniform sampling and GraphSAINT or neighbor sampling for batch size, sampled edges, and FLOPs. Measure validation accuracy, loss decrease per sampled node, cluster coverage, gradient variance, and low-frequency feature reconstruction error, using exact eigenvectors only on small benchmarks. The expected signal is faster loss decrease or higher accuracy at fixed graph accesses, particularly with weak inter-cluster connectivity; failure is no improvement over uniform sampling or excessive importance-weight variance.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

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 on-demand Laplacian-column coherence sampler with greedy min-max selection. The mechanism checks passed: sparse columns and inner products matched dense calculations exactly, disconnected-component coherence was exactly zero with both-block coverage, candidate-pool coverage matched the combinatorial prediction, and the bridge-coherence closed form matched observed values to numerical precision. The estimator remained approximately unbiased, but its standard deviation was 0.389 versus 0.135 for uniform sampling, so inverse-probability weighting needs variance control; no end-to-end GNN win was established.

Agent confidence: 8/10

Baseline: Uniform sampling: mean two-block coverage 1.44/2 on the coupling sweep; HT loss estimate mean 0.6975 versus true 0.7000, std 0.1352.
Idea: Coherence sampling: mean two-block coverage 2.00/2 across all tested bridge weights versus uniform 1.44; HT loss estimate mean 0.6930 versus true 0.7000, std 0.3889; minimum estimated inclusion probability 0.051. Cross-coherence and closed-form bridge prediction agreed to about 1e-15.

Limitations: Only small synthetic two-clique graphs were tested. No Cora/Citeseer dataset, GCN/GraphSAGE training, sampled-frontier FLOP accounting, validation accuracy, low-frequency reconstruction, or multi-hop neighbor sampler comparison was run. The current sampler uses one fixed candidate pool per minibatch and estimates inclusion probabilities via repeated offline sampling; clipping and EMA probability tracking are not implemented.

How to run: python3 run_experiment.py

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

Beats the tuned baseline by 13.5% (p=0.0315, wins 7 / 8 paired seeds; metric: lower is better).

Benchmark: Laplacian_coherence_graph
Model: local_gcn
Paired seeds: 8
Baseline mean: 0.3469
Idea mean: 0.3
Effect (Δ): -0.0469 (−13.5%; negative = idea better)
Wins: 7 / 8 paired seeds
p-value: 0.0315 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±12.6%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 6 configs

Limitations:

The built-in bench has no graph track, so a custom track was necessary. The custom track was registered in-process rather than written into the read-only shared bench directory; graph_track.py satisfies the required contract and stage2_bench.py smoke-tests registration via bench.get_dataset. The graph is synthetic rather than Cora/Citeseer, and GraphSAINT, neighbor sampling, FLOP accounting, multi-hop frontiers, and larger-scale GNNs were not tested.

How to run: python3 stage2_bench.py

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

Stage 2 — Benchmark Aug 31, 2026 latest Worked ✓

Agent confidence: 8/10

Laplacian-coherence graph minibatches produced a significant improvement on the custom registered graph track using the same local GCN architecture and training budget. Best baseline test error was 0.346875, while the idea achieved 0.300000; paired delta was -0.046875 with p=0.0315. The mechanism signature confirmed predicted candidate-pool coverage of 2.0 communities and observed coherent coverage of 2.0, although uniform coverage was also 2.0 in this particular trained-model signature.

Baseline: Uniform GCN, tuned baseline lr=0.006, weight_decay=0, 18 epochs, batch=32: mean test error 0.346875, std 0.092650 over 8 seeds.
Idea: Laplacian-coherence sampler, lr=0.006, candidate pool=64, batch=32, 18 epochs: mean test error 0.300000, std 0.080283 over 8 seeds; 7/8 paired wins; delta=-0.046875; permutation p=0.0315.
Mechanism signature: Predicted candidate-pool coverage=2.0; observed coherent coverage=2.0; observed uniform coverage=2.0; confirmed=true.

Benchmark result