# Bounded-Width Neighborhood Signature Compression

- ID: 1035
- Canonical URL: https://synthcore.org/idea/1035/bounded-width-neighborhood-signature-compression
- API JSON: https://synthcore.org/api/idea/1035.json
- API Markdown: https://synthcore.org/api/idea/1035.md
- Verification status: unverified
- Source: [arXiv:2607.16889](https://arxiv.org/abs/2607.16889)
- Category: architecture
- Solves: speedup, memory, scalability
- ML areas: graph-nn, attention, memory, inference-speedup
- Math tags: graph-theory, combinatorics, approximation-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace a dense node-to-landmark graph-attention or message-passing relation by a dictionary of distinct landmark-neighborhood signatures. Nodes sharing the same signature reuse the same structural landmark aggregate, while their individual hidden states are still passed through the output MLP, preserving node-specific predictions. On bounded-treewidth graphs the number of distinct signatures is provably linear in the number k of landmarks, with an explicit dependence on treewidth.

## Mathematical statement

For a graph G=(V,E), a landmark set S\subseteq V with |S|=k, and closed neighborhood N[v]={v}\}\cup\{u\in V:(u,v)\in E}, the paper defines nc(G,S)=|\{N[v]\cap S:v\in V\}| and nc(G,k)=\max_{|S|=k}nc(G,S). For treewidth w\geq 2 and k\geq w+1, the main bound is nc(G,k)\leq(k-w+1)2^w+w. Thus the signature map \sigma_S(v)=N[v]\cap S has at most B_{\mathrm{tw}}=(k-w+1)2^w+w distinct values. For pathwidth w\geq 2, the corresponding bound is nc(G,k)\leq(k-w+2)2^{w-1}+2k-w-2. The proof uses a width-w tree decomposition: each landmark-root bag has at most w+1 vertices, and vertices attached below a bag can realize only subsets of the bag, producing at most 2^w local neighborhood patterns. The ML module uses the exact identity m_v=\sum_{s\in\sigma_S(v)}W_Vh_s, where h_s is a landmark embedding and W_V is a learned projection; this message is identical for all vertices with the same signature. The bound is a structural guarantee on the number of distinct sets, not an approximation error bound, so exact reuse is valid for this landmark-mediated message operator.

## Key formulas

- $$\nc(G,S)=\left|\left\{N[v]\cap S\;:\;v\in V\right\}\right|$$
- $$\nc(G,k)=\max_{S\subseteq V,\ |S|=k}\nc(G,S)$$
- $$\nc(G,k)\leq (k-w+1)2^w+w\qquad\text{for treewidth }w\geq2,\ k\geq w+1$$
- $$m_v=\sum_{s\in\sigma_S(v)}W_Vh_s,\qquad \sigma_S(v)=N[v]\cap S,\qquad \left|\{\sigma_S(v):v\in V\}\right|\leq B_{\mathrm{tw}}=(k-w+1)2^w+w$$

## Implementation notes

1. Integration point: add this as a landmark-mediated graph-convolution block or as a sparse replacement for the node-to-landmark part of a graph transformer. Given node states H\in\mathbb{R}^{n    imes d}, choose k landmarks S, ideally bag representatives from a supplied tree decomposition; if no decomposition is supplied, use farthest-point sampling or a random subset and record the empirical signature count. Compute the binary signature \sigma_S(v) for every node, including v itself because the paper uses closed neighborhoods. 2. Pseudocode: compute Z=W_V H[S]; create a hash table from each bitset signature A\subseteq S to a group id; for every group A compute q_A=\sum_{s\in A}Z_s; for each node v set m_v=q_{\sigma_S(v)}; update H'_v=H_v+W_O\,\mathrm{MLP}([H_v,m_v]). If using normalized aggregation, also compute c_A=|A| and use m_v=q_A/\max(1,c_A). For multiple layers, either keep S fixed or refresh landmarks every few epochs. 3. Math versus empirical quantities: the formula for \sigma_S and the signature-count bound are taken directly from the paper. The implementation estimates actual compression by counting unique bitsets; treewidth w is either known from the benchmark/decomposition or treated only as a diagnostic, not assumed by the algorithm. 4. First experiment: use synthetic trees, series-parallel graphs, k-trees with prescribed treewidth w\in\{1,2,4,8\}, and a real low-treewidth molecular or program graph dataset. Compare a standard sparse GNN and a dense landmark-attention baseline against signature compression at equal hidden size. Measure unique signatures, edge/message aggregation time, peak activation memory, validation accuracy, and loss versus wall-clock time. The expected signal is near-identical accuracy with fewer distinct structural aggregations and lower memory; for fixed k, the empirical signature count should remain close to linear in n-independent k and should obey the stated upper bound.

## Disclaimer

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