# PPMI-Gated BCM Sparse Graph Encoder

- ID: 2620
- Canonical URL: https://synthcore.org/idea/2620/ppmi-gated-bcm-sparse-graph-encoder
- API JSON: https://synthcore.org/api/idea/2620.json
- API Markdown: https://synthcore.org/api/idea/2620.md
- Verification status: beats_baseline
- Source: [arXiv:2608.20408](https://arxiv.org/abs/2608.20408)
- Category: architecture
- Solves: memory, speedup, stability
- ML areas: graph-nn, embedding, training
- Math tags: probability, statistics, dynamical-systems
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace a dense graph embedding table or end-to-end GNN encoder with a fixed-width binary SDR learned from streaming random-walk context pairs. Use PPMI to amplify informative node-context pairs and a local BCM update to learn detector columns, followed by k-winner-take-all binarization. The resulting sparse code can be used directly for node classification, link prediction, retrieval, or as input to a small downstream predictor.

## Mathematical statement

For a random-walk stream, let C_uv be the number of times node u occurs with context node v within a window, let C_u_dot be the row marginal, C_dot_v the column marginal, and N the total pair count. Define p(u,v)=C_uv/N, p(u)=C_u_dot/N, and p(v)=C_dot_v/N. The PPMI signal is PPMI(u,v)=max(0, log(p(u,v)/(p(u)p(v)))); zero-count pairs receive zero weight. For an input feature vector x in R^d, each output column j has weight w_j in R^d and response y_j=ReLU(w_j^T x). The local BCM rule is Delta w_j=eta g(u,v)x y_j(y_j-theta_j), with learning rate eta and normalized PPMI gate g. The sliding threshold theta_j is updated by theta_j=(1-alpha)theta_j+alpha y_j^2. The BCM term potentiates a column when y_j^2 exceeds its running threshold and depresses it otherwise. A binary SDR with m columns and exactly k active bits is formed by selecting the k largest responses.

## Key formulas

- $$\operatorname{PPMI}(u,v)=\max\left\{0,\log\frac{p(u,v)}{p(u)p(v)}\right\},\qquad p(u,v)=\frac{C_{uv}}{N},\quad p(u)=\frac{C_{u\cdot}}{N},\quad p(v)=\frac{C_{\cdot v}}{N}.$$
- $$y_j=\operatorname{ReLU}(w_j^\top x),\qquad \Delta w_j=\eta\,g(u,v)\,x\,y_j(y_j-\theta_j),\qquad g(u,v)=\frac{\operatorname{PPMI}(u,v)}{\max_{a,b}\operatorname{PPMI}(a,b)+\varepsilon}.$$
- $$\theta_j\leftarrow(1-\alpha)\theta_j+\alpha y_j^2,\qquad z_j=\mathbf{1}\left[j\in\operatorname{TopK}(y,k)\right],\qquad \lVert z\rVert_0=k.$$

## Implementation notes

Integrate this as a graph-nn embedding layer, replacing node2vec's dense embedding table or preceding a lightweight classifier. First generate an online stream of random walks; for each walk, emit every center-context pair (u,v) within a window of radius r. Maintain a Count-Min Sketch or bounded hash table for C_uv and exact or hashed node marginals C_u_dot and C_dot_v. Use additive smoothing delta when computing probabilities, and periodically freeze or refresh the PPMI normalization maximum. Represent x as e_u+e_v followed by a fixed random projection into dimension d, or use concatenated hashed one-hot features. For each pair, compute the smoothed PPMI gate, responses y=ReLU(W^T x), and thresholds theta. Update each column with w_j += eta*g*x*y_j*(y_j-theta_j), then update theta_j with the exponential average of y_j squared. Normalize each weight column after a minibatch and clip its norm to prevent Hebbian divergence. At inference, compute responses for a node-context summary, retain the k largest columns, and store only their indices. For link prediction, test SDR Jaccard overlap, Hamming distance, and a small MLP on two SDRs. Start on Cora or PubMed, comparing a 256-bit SDR with 256-dimensional node2vec and GraphSAGE at matched downstream accuracy. Measure wall-clock training, peak memory, bytes per node, and accuracy after sequential graph updates. A useful success signal is accuracy within two percentage points while using at least four times less embedding storage and degrading less under edge corruption or distribution shift.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: helps
- Verdict: Built a NumPy MVP of PPMI computation, normalized gating, local BCM updates, threshold tracking, and exact-k binary SDR inference in ppmi_bcm_experiment.py. The mechanism manifested: zero PPMI produced exactly zero updates across 8 inputs, update norm scaled linearly with gate from 0 to 1 at relative error below 5e-15, and the BCM threshold closed form matched the iterative update within 9e-16 while all potentiation/depression sign cases matched prediction. The downstream toy result was not a win: SDR accuracy was 0.625 versus 0.825 for the dense random baseline, although storage was 32x smaller (4 versus 128 bytes/node).

### Mechanism check

- Verdict: Built a NumPy MVP of PPMI computation, normalized gating, local BCM updates, threshold tracking, and exact-k binary SDR inference in ppmi_bcm_experiment.py. The mechanism manifested: zero PPMI produced exactly zero updates across 8 inputs, update norm scaled linearly with gate from 0 to 1 at relative error below 5e-15, and the BCM threshold closed form matched the iterative update within 9e-16 while all potentiation/depression sign cases matched prediction. The downstream toy result was not a win: SDR accuracy was 0.625 versus 0.825 for the dense random baseline, although storage was 32x smaller (4 versus 128 bytes/node).
- Confidence: 9/10
- Limitations: Only a synthetic 80-node SBM and a dense random-projection baseline were tested; no Cora/PubMed, node2vec, GraphSAGE, link prediction, corruption robustness, streaming count-min sketch, GPU implementation, wall-clock scalability, or multi-seed statistical comparison was evaluated.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0169
- Paired wins: 7/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/999/bench_report.json)
- [ppmi_bcm_bench.py](https://synthcore.org/code/999/ppmi_bcm_bench.py)
- [ppmi_bcm_experiment.py](https://synthcore.org/code/999/ppmi_bcm_experiment.py)
- [report.md](https://synthcore.org/code/999/report.md)
- [report_bench_2026-09-01T175616.md](https://synthcore.org/code/999/report_bench_2026-09-01T175616.md)
- [results.json](https://synthcore.org/code/999/results.json)
- [Download all files as ZIP](https://synthcore.org/download/999)

## Disclaimer

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