# Dirichlet-to-Neumann Graph Pooling

- ID: 199
- Canonical URL: https://synthcore.org/idea/199/dirichlet-to-neumann-graph-pooling
- API JSON: https://synthcore.org/api/idea/199.json
- API Markdown: https://synthcore.org/api/idea/199.md
- Verification status: mechanism_works
- Source: [arXiv:2608.26458](https://arxiv.org/abs/2608.26458)
- Category: architecture
- Solves: memory, scalability, accuracy
- ML areas: graph-nn, memory
- Math tags: graph-theory, linear-algebra, spectral-theory
- Ratings: usefulness 7/10; difficulty 6/10; novelty 6/10

## Idea description

Replace a large graph submodule by a compact boundary response operator that maps boundary node features to induced boundary fluxes after the interior has been eliminated. Stack these operators recursively to obtain a hierarchical graph neural network whose coarse-level computation preserves long-range effects of discarded vertices more faithfully than average pooling or simple node clustering.

## Mathematical statement

For a graph with vertex set partitioned into boundary vertices B and interior vertices I, let L be its symmetric graph Laplacian, with blocks L_BB, L_BI, L_IB, and L_II. The Dirichlet-to-Neumann operator is the Schur complement D=L_BB-L_BI L_II^{-1} L_IB, assuming the interior Dirichlet problem is nonsingular; it maps fixed boundary potentials to boundary currents after solving for optimal interior potentials. This is the operator used by the paper in expressions such as DN(G,P_l)=L(Y)+hat D. For the glued cycle example, hat D=c(e_1-e_l)(e_1-e_l)^T, where c=(m-l+1)^(-1)+(n-l+1)^(-1), and det'(DN(G,P_l))=l(mn-(l-1)^2)/((m-l+1)(n-l+1)). The neural adaptation treats D as a coarse weighted Laplacian. Its key property is exact preservation of the quadratic boundary energy x_B^T D x_B induced by minimizing the full Laplacian energy over interior variables.

## Key formulas

- $$\mathrm{DN}(G,B)=L_{BB}-L_{BI}L_{II}^{-1}L_{IB}.$$
- $$x_B^\top \mathrm{DN}(G,B)x_B=\min_{x_I}\begin{bmatrix}x_B\\x_I\end{bmatrix}^{\!\top}L\begin{bmatrix}x_B\\x_I\end{bmatrix}.$$
- $$\mathrm{DN}(G,P_l)=L(Y)+\hat D,\qquad \hat D=\left(\frac{1}{m-l+1}+\frac{1}{n-l+1}\right)(e_1-e_l)(e_1-e_l)^\top.$$
- $${\det}^{\prime}(\mathrm{DN}(G,P_l))=\frac{l(mn-(l-1)^2)}{(m-l+1)(n-l+1)}.$$

## Implementation notes

Integrate this at the graph pooling boundary, before a coarse graph-attention or message-passing layer. Partition each cluster into interior nodes I and a small interface B, such as the 4-16 nodes with highest inter-cluster degree. Given the cluster adjacency matrix A, form L=diag(A1)-A and extract L_BB, L_BI, L_IB, and L_II. Compute D=L_BB-L_BI solve(L_II,L_IB); use D as the weighted adjacency or Laplacian of the pooled interface. The forward pass is: (1) encode node features h; (2) solve z_I=-solve(L_II,L_IB)h_B for the harmonic interior response; (3) form boundary features h_B' by concatenating h_B with a projected summary of z_I; (4) run message passing using D as the local coarse operator; (5) recursively repeat. For numerical stability add epsilon*I to L_II and symmetrize D. Do not explicitly invert matrices: use Cholesky solves, with dense solves for interfaces below 32 nodes and sparse factorization otherwise. The paper supplies the exact Schur-complement and energy-preservation rationale; cluster boundaries, epsilon, and solve tolerances are estimated or selected empirically. First test on ogbn-arxiv or ZINC using a 10-layer GNN, comparing DiffPool, ClusterGCN, and mean pooling at equal memory. Measure peak memory, validation accuracy, and sensitivity to graph diameter. Success is at least 2x lower activation memory with no more than 1% accuracy loss, or improved long-range accuracy at the same node budget.

## Verification

- Status: mechanism_works
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a dense Schur-complement DTN pooling primitive and a reproducible toy comparison. The harmonic-extension energy identity had relative error 2.35e-11, and perturbing the interior increased energy by 20.36. On 41 held-out two-path graphs, DTN conductance achieved RMSE 6.61e-11 versus 0.1664 for constant-feature mean pooling, demonstrating preservation of this long-range property; however, the task is deliberately controlled and does not establish a general GNN accuracy or memory improvement.

### Mechanism check

- Verdict: Built a dense Schur-complement DTN pooling primitive and a reproducible toy comparison. The harmonic-extension energy identity had relative error 2.35e-11, and perturbing the interior increased energy by 20.36. On 41 held-out two-path graphs, DTN conductance achieved RMSE 6.61e-11 versus 0.1664 for constant-feature mean pooling, demonstrating preservation of this long-range property; however, the task is deliberately controlled and does not establish a general GNN accuracy or memory improvement.
- Confidence: 7/10
- Limitations: Only a synthetic two-terminal parallel-path family was tested; the comparison is against mean pooling rather than DiffPool/ClusterGCN or a trained message-passing GNN. No recursive hierarchy, node-feature learning, sparse solver, wall-clock benchmark, activation-memory measurement, noisy features, or real graph dataset was evaluated.

## Artifacts

- [dtn_pooling_experiment.py](https://synthcore.org/code/13/dtn_pooling_experiment.py)
- [report.md](https://synthcore.org/code/13/report.md)
- [Download all files as ZIP](https://synthcore.org/download/13)

## Disclaimer

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