LNC-Compressed Dense Message Passing

Integrate this at the fixed-graph aggregation operation of a message-passing GNN, not at the learned feature transformation. Given node states H in R^{n x d}, the baseline computes Z=MH with a dense matrix multiply and then applies H' = phi(ZW + H W_0). In the proposed model, run a one-time preprocessing routine on the fixed graph G: construct the paper's LNC/sd-degeneracy representation and store the auxiliary structures needed by its adjacency-matrix-vector query algorithm. At every training or inference step, compute each feature column by calling the exact query routine: for j=1,...,d, set Z_{:,j}=Q_G(H_{:,j}), where Q_G(x)=Mx. In practice, batch columns into blocks of width b and use the same traversal/decomposition while accumulating b scalar coordinates per vertex; this preserves the O(nb) query target while improving CPU vectorization. Pseudocode is: state = preprocess(G); for layer: H_in = H; Z = zeros(n,d); for feature_block X in blocks(H,d,b): Z_block = query_adjacency(state,X) # exact M X; H = activation(Z W + residual(H_in)). The mathematical quantities computed from the paper are the neighborhood-complexity/decomposition data and the exact identity Z=MH; the constant c and whether the input graph satisfies LNC should be estimated or certified empirically by sampling subsets X and counting distinct restricted neighborhoods. The first cheap experiment should use dense planar-derived or low-clique-width synthetic graphs with n in {4096,16384,65536}, a 2-4 layer GCN, and compare dense matmul, ordinary sparse matmul, and the compressed query at equal outputs. Measure preprocessing time separately, per-layer wall-clock time, peak memory, and numerical error. Success means amortized aggregation approaching linear scaling in n and at least a 3x speedup over dense aggregation once several layers or repeated inference queries amortize preprocessing, with identical validation accuracy.