Exact Branch-and-Bound for Subgraph-Count Splits in Second-Order Tree Boosting

Gradient boosting repeatedly fits trees by selecting splits that best improve the current objective. Modern methods typically evaluate this improvement with Newton-style second-order gains. While this optimization is straightforward with a fixed feature table, it becomes combinatorial when features are generated from a tree-structured search space. We study this setting for occurrence-count features, with connected subgraphs as one instance. We derive a safe bound on descendant splits and show that its apparently exponential optimization is solved exactly by a single linear scan in gradient-Hessian ratio order. This enables exact branch-and-bound before descendant feature vectors are constructed. Experiments confirm that the method matches exhaustive search while substantially reducing search cost.