# Spectrum-preserving conditional binary graph sampler

- ID: 1302
- Canonical URL: https://synthcore.org/idea/1302/spectrum-preserving-conditional-binary-graph-sampler
- API JSON: https://synthcore.org/api/idea/1302.json
- API Markdown: https://synthcore.org/api/idea/1302.md
- Verification status: unverified
- Source: [arXiv:2607.22991](https://arxiv.org/abs/2607.22991)
- Category: sampling
- Solves: stability, sample-efficiency
- ML areas: graph-nn, vae, world-model, diffusion-sampling
- Math tags: stochastic-processes, spectral-theory, linear-algebra, probability, graph-theory
- Ratings: usefulness 5/10; difficulty 5/10; novelty 8/10

## Idea description

Build a graph-structured binary latent layer whose local heat-bath probabilities are predicted by a neural network, while particle-exchange and refresh rates remain fixed. The learned probabilities change the stationary distribution and encode input-dependent conditioning, but the spectral invariance result predicts that they do not change the Markov-chain eigenvalues or relaxation modes. This provides a conditional sampler with a fixed, calibratable mixing budget instead of requiring a new mixing analysis for every input.

## Mathematical statement

For an edge with pre-exchange bits $(a,b)\in\{0,1\}^2$ and post-exchange bits $(c,d)\in\{0,1\}^2$, the paper defines $S_{a,b}^{c,d}=1$ exactly when $a=d$ and $b=c$, and zero otherwise; $S_e$ therefore swaps binary states at the endpoints of edge $e$. At a heat-bath vertex $v$, it defines the rank-one matrix $H(v)=\mathbb{1}\cdot h_v$, where $\mathbb{1}=(1,1)^\top$ is the all-ones column vector and $h_v=(h_v(0),h_v(1))$ is a probability row vector satisfying $h_v(1)=1-h_v(0)$. Thus $H(v)$ discards the old local state and redraws it from $h_v$. For graph $G=(V,E)$, let $B\subseteq V$ be bath vertices, let $r_e\geq0$ be exchange rates, let $q_v\geq0$ be bath-refresh rates, and let $I$ be the identity on global configurations $z\in\{0,1\}^{|V|}$. The continuous-time generator is $L_h=\sum_{e\in E}r_e(S_e-I)+\sum_{v\in B}q_v(H(v)-I)$. The paper proves that the spectrum is independent of the bath probabilities: $\operatorname{Spec}(L_h)=\operatorname{Spec}(L_{h'})$ for any two collections $h,h'$ with the same graph and rates. We exploit this by learning $h$ while freezing $r_e,q_v$.

## Key formulas

- $$S_{a,b}^{c,d}:=\begin{cases}1&\text{if }a=d\text{ and }b=c,\\0&\text{otherwise},\end{cases}\qquad a,b,c,d\in\{0,1\}.$$
- $$H(v)=\mathbb{1}\cdot h_v,\qquad h_v=(h_v(0),h_v(1)),\qquad h_v(1)=1-h_v(0).$$
- $$L_h=\sum_{e\in E}r_e\bigl(S_e-I\bigr)+\sum_{v\in B}q_v\bigl(H(v)-I\bigr),\qquad P_h=I+\delta L_h.$$
- $$\operatorname{Spec}(L_h)=\operatorname{Spec}(L_{h'})\quad\text{for any }h,h'\text{ with identical }G,r_e,q_v.$$

## Implementation notes

(1) Exact integration point: insert this sampler as a stochastic graph-refinement block in a graph VAE, graph world model, or discrete graph denoiser. Let node features be $u_v=f_\theta(x,G)_v$ and let the network output bath logits $\ell_v$ for $v\in B$. Define $p_v=\sigma(\ell_v)$ and $h_v=(1-p_v,p_v)$. Maintain a binary state vector $z\in\{0,1\}^{|V|}$ and apply $K$ Markov events before decoding or computing the task loss. Keep exchange rates $r_e$ and bath rates $q_v$ fixed across all examples. (2) Pseudocode: initialize $z$ from encoder Bernoulli samples or a deterministic binary seed; form an event list containing each edge $e$ with weight $r_e$ and each bath $v$ with weight $q_v$; repeat $K$ times, sample one event proportionally to its weight, swap $(z_u,z_v)$ if the event is edge $(u,v)$, and otherwise sample $z_v\sim\operatorname{Bernoulli}(p_v)$ for a bath event. Decode the final $z$. Use straight-through Bernoulli samples for a first differentiable prototype, or optimize a variational objective with the sampler treated as a discrete latent transition. (3) Computed from the mathematics: the exact local operators $S_e,H(v)$, the generator, and the fixed event-rate schedule. Estimated empirically: the second-largest eigenvalue modulus on small graphs, integrated autocorrelation time, effective sample size, and downstream loss. Explicitly build $P_h$ for several different $p_v$ settings and verify that its eigenvalues remain unchanged up to numerical error. (4) First cheap experiment: train a binary graph-VAE on 8- to 32-node cycles, grids, and random geometric graphs. Compare against independent Bernoulli resampling and ordinary single-site Gibbs updates at equal event count and wall-clock cost. Sweep bath probabilities from 0.01 to 0.99 while holding rates fixed. Success requires nearly unchanged autocorrelation or relaxation curves across probability settings, plus better conditional reconstruction log-likelihood or sample quality than independent resampling at equal sampling cost. Also test whether the fixed spectrum makes the sampler more stable than a learned transition-rate baseline.

## Disclaimer

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