Tree Residual Network: Restoring Graph Connectivity over a Tree Backbone

Graph node classification requires both local connectivity and long-range context. Message-passing networks preserve graph edges but require repeated aggregation to communicate over long distances, whereas dense global attention is expensive. We propose Tree Residual Network (TRN), a cycle-completion architecture that assigns global transport to a tree and restores the constraints of omitted edges through the same routing coordinate system. Bidirectional aggregation over a spanning tree establishes graph-wide context with a linear-size backbone. Because a tree can turn one-hop relations into long detours, TRN measures signed discrepancies on omitted edges and redistributes the resulting corrections through the backbone rather than opening a second residual propagation channel. Complementary theoretical analyses, including a signed-pair reference model and a quadratic graph-smoothing surrogate, provide operator-level perspectives on this tree-to-graph correction. Across 14 homophilic and heterophilic node-classification benchmarks, TRN attains the highest or second-highest reported mean on every dataset; controlled ablations and a matched residual-aggregation control support the proposed decomposition.