Chain-Compatible Graph Pooling
Implementation & benchmark of arXiv:2607.28621 — Lifting Lifted Product Codes
Source paper: Lifting Lifted Product Codes arXiv:2607.28621 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace an arbitrary graph pooling map with a pooling operator constrained to commute with the graph incidence or boundary operator. This gives a hierarchical GNN an exact coarse-to-fine consistency condition: node and edge features must be pooled in a coordinated way that preserves local conservation and cycle structure.
Formulas
Mathematical statement
The paper constructs chain maps between fine and projected complexes. For tensor-product complexes, the component maps are $p_2=p_{A_1}\otimes p_{B_1}$, $p_1=(p_{A_1}\otimes p_{B_0})\oplus(p_{A_0}\otimes p_{B_1})$, and $p_0=p_{A_0}\otimes p_{B_0}$, where $A_i,B_i$ are chain spaces at degree $i$ and $p_{A_i},p_{B_i}$ map fine spaces to coarse spaces. A chain map commutes with boundaries: $\partial_i^{\mathrm{coarse}}p_i=p_{i-1}\partial_i^{\mathrm{fine}}$. For an ordinary graph, let $B_{\mathrm{fine}}$ and $B_{\mathrm{coarse}}$ be node-edge incidence matrices, $P_0$ the node pooling matrix, and $P_1$ the edge pooling matrix. The neural constraint is $B_{\mathrm{coarse}}P_1=P_0B_{\mathrm{fine}}$. Pooling assignments can be learned, but their violation of this identity is penalized or projected away. The transferable asset is preservation of boundary relations across scales, reducing structural distortion in hierarchical graph representations.
Implementation notes
1. Integration point: modify the pooling or downsampling stage of a hierarchical graph neural network. The fine graph has node features $X_0\in\mathbb{R}^{n_0\times d}$, edge features $X_1\in\mathbb{R}^{n_1\times d}$, and incidence matrix $B_{\mathrm{fine}}\in\mathbb{R}^{n_0\times n_1}$. Produce coarse features with $X_0^c=P_0^TX_0$ and $X_1^c=P_1^TX_1$. 2. Pseudocode: compute soft node assignments P0 = softmax(score_nodes(X0), dim=clusters); compute edge assignments from endpoint assignments, for edge $e=(u,v)$ use P1[e,(a,b)] proportional P0[u,a]*P0[v,b]; construct the coarse incidence matrix Bc; add lambda_chain * ||Bc @ P1.T - P0.T @ Bf||_F^2 to the loss, with matrix orientations adjusted to the implementation. Optionally replace the penalty by a least-squares projection of $P_1$ onto the affine constraint $B_cP_1=P_0B_f$. 3. Mathematics versus estimation: the tensor-product formulas specify how maps are assembled for product or cell complexes; the commutation equation is exact. The assignment matrices and penalty weight $\lambda_{chain}$ are learned or tuned empirically. Track the normalized residual $\|B_cP_1-P_0B_f\|_F/(\|P_0B_f\|_F+10^{-8})$. 4. First experiment: use a 3-level Graph U-Net or MeshGraphNet on molecular graph classification and a synthetic task predicting a conserved flow divergence. Compare standard top-$k$ pooling and DiffPool against chain-compatible pooling at equal hidden size and cluster count. Record validation accuracy, training variance across seeds, gradient norms, and boundary residual. Success is improved accuracy or lower seed variance without significant FLOP increase, particularly on tasks depending on cycles, flows, or higher-order connectivity.
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.