# Uniform spectral graph coreset

- ID: 2760
- Canonical URL: https://synthcore.org/idea/2760/uniform-spectral-graph-coreset
- API JSON: https://synthcore.org/api/idea/2760.json
- API Markdown: https://synthcore.org/api/idea/2760.md
- Verification status: unverified
- Source: [arXiv:2608.27624](https://arxiv.org/abs/2608.27624)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: graph-nn, pruning, attention, memory
- Math tags: graph-theory, spectral-theory, convex-analysis, combinatorics
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace random node or token subsampling by a subset selected to preserve the averages of low-frequency graph signals exactly or approximately. Build a graph over nodes or tokens, compute its Laplacian eigenspace, and choose a fixed-cardinality subset whose eigenvector moments match those of the full graph; use the retained subset for graph pooling or downstream attention.

## Mathematical statement

The graphical-design condition is that a weighted subset W averages every function in a selected Laplacian eigenspace exactly: (1/n)\sum_{v=1}^{n} f(v)=\sum_{w\in W}a_w f(w). Let L be the graph Laplacian, with eigenvalues 0=\lambda_0<\lambda_1<\cdots and an eigenvector matrix U whose first row is the constant eigenvector. For a uniform subset of size m, define z\in\{0,1\}^n by z_j=1 iff j\in W. Exact averaging of the first s_t eigenvector rows is equivalent to \frac{1}{m}\sum_{j=1}^n z_jU_{rj}=\frac{1}{n}\sum_{j=1}^nU_{rj} for every r\le s_t. Since the nonconstant eigenvectors are orthogonal to the constant vector, this reduces to U_{\mathrm{low}}z=0 together with \mathbf{1}^{    op}z=m, where U_{\mathrm{low}} contains the selected nonconstant rows. The paper's eigenconfiguration consists of the columns b_j=(U_{rj})_{r\in I_t}; a design is a subset whose column sum is zero, equivalently whose selected-point centroid is the origin. The polytope P_t=\operatorname{conv}\{b_1,\ldots,b_n\} characterizes feasible positive weighted designs through faces and supports cardinality bounds. In neural networks, use the exact residual R(z)=\|U_{\mathrm{low}}z\|_2^2/m^2 as a differentiable proxy when no exact 0-1 design exists.

## Key formulas

- $$\frac{1}{n}\sum_{v\in[n]}f(v)=\sum_{w\in W}a_w f(w)$$
- $$\frac{1}{m}\sum_{j=1}^{n}z_jU_{rj}=\frac{1}{n}\sum_{j=1}^{n}U_{rj}\quad (r\in I_t),\qquad z_j\in\{0,1\},\quad \mathbf{1}^{\top}z=m$$
- $$U_{\mathrm{low}}z=0,\qquad R(z)=\left\|\frac{1}{m}U_{\mathrm{low}}z\right\|_2^2$$
- $$P_t=\operatorname{conv}\{b_1,\ldots,b_n\},\qquad b_j=(U_{rj})_{r\in I_t}$$

## Implementation notes

Integrate this at the node-pooling stage of a message-passing GNN, or at a token-pruning stage before an expensive attention block. For each graph or token set with n items, construct a symmetric affinity matrix A from existing node edges or from cosine similarities of current embeddings, define L=D-A with D_{ii}=\sum_jA_{ij}, and compute the first q nonconstant eigenvectors U_low using Lanczos or a randomized eigensolver. Use this procedure: (1) choose target retention m=\lceil\rho n\rceil and eigen-dimension q; (2) solve the binary problem min_{z\in\{0,1\}^n,\ 1^Tz=m} ||U_low z||_2^2, optionally adding a coverage term that discourages all selected nodes from being adjacent; (3) test whether the optimum is zero, which indicates an exact uniform design; (4) during training, use the selected indices as a hard mask and pass only retained nodes to later layers; (5) refresh the mask every K steps, or learn soft gates g_j\in[0,1] with a straight-through top-m operator and penalty ||U_low g||_2^2/m^2. The paper-derived computation is the spectral residual and exact zero-moment constraint. The graph, eigenvectors, and q are estimated from the current batch, so no paper-specific constants are required. Start with a 2-4 layer GraphSAGE or GCN on Cora, Citeseer, or OGBN-Arxiv, retaining 25%, 50%, and 75% of nodes before a global readout or expensive cross-node layer. Compare random sampling, degree sampling, and leverage-score sampling at equal retained-node FLOPs. Measure validation accuracy, spectral residual R(z), loss at equal wall-clock/FLOPs, and memory. A successful result should show lower low-frequency reconstruction error and higher accuracy than random pruning at the same retention ratio, with approximately proportional reduction in the cost of subsequent message passing or attention. For a transformer adaptation, construct an affinity graph from token embeddings and evaluate perplexity together with KV-cache size, since the method only guarantees preservation of the selected low-frequency graph-signal subspace.

## Disclaimer

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