Bounded-Width Neighborhood Signature Compression
Implementation & benchmark of arXiv:2607.16889 — Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
Source paper: Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth arXiv:2607.16889 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
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.
Formulas
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.
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.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.