Budgeted Tree Message-Passing Planner

Integrate this at graph-neural-network inference time, immediately before the expensive message-passing layers. The inputs are a rooted tree or a block-cut-tree approximation of the graph, node importance scores $h_k$ such as gradient sensitivity or a learned positive scorer, landmark costs $c^{land}_j$, edge activation costs $c^{edge}_e$, total budget $B$, and maximum receptive-field radius $R$. First precompute subtree tables $V(v,b,r)$ for integer budgets $b=0,\ldots,B$ and residual radii $r=0,\ldots,R$. For each leaf, enumerate whether the node is selected as a landmark and whether it is covered. For each internal node, enumerate budget splits $b_1+b_2\leq b$, edge decisions $x_{e_1},x_{e_2}\in\{0,1\}$, and the resulting child residual states $r x_{e_i}$; add the node's weight when the node is covered, then retain the maximum value and backpointers. Use $\mathcal A$ when no coverage enters from the parent and $\mathcal B$ when coverage enters. At the root, backtrack to obtain selected landmarks and active edges, then run the GNN only on the induced sparse communication pattern. Cache the DP plan for every budget from $0$ through $B$ to obtain an anytime accuracy-versus-latency curve. Compute the DP exactly; estimate $h_k$ from a frozen pilot model, node gradients, attention mass, or a cheap auxiliary scorer. For graphs that are not trees, construct a block-cut tree, solve each biconnected block with a small local integer program or enumerate only the block's boundary states, and combine child tables through selector variables. The first experiment should use a 2--8 layer GCN or graph transformer on synthetic trees and real low-treewidth molecular or road graphs, comparing dense inference, independent top-$k$ node pruning, and greedy edge pruning at equal message-passing FLOPs. Measure weighted node accuracy, end-task accuracy, active-edge count, and planning overhead. Success means higher accuracy than independent pruning at the same budget, or a useful monotone accuracy-versus-budget curve with less than 5% planning overhead.