  Graph Neural Networks (GNNs) have achieved significant success in learning
better representations by performing feature propagation and transformation
iteratively to leverage neighborhood information. Nevertheless, iterative
propagation restricts the information of higher-layer neighborhoods to be
transported through and fused with the lower-layer neighborhoods', which
unavoidably results in feature smoothing between neighborhoods in different
layers and can thus compromise the performance, especially on heterophily
networks. Furthermore, most deep GNNs only recognize the importance of
higher-layer neighborhoods while yet to fully explore the importance of
multi-hop dependency within the context of different layer neighborhoods in
learning better representations. In this work, we first theoretically analyze
the feature smoothing between neighborhoods in different layers and empirically
demonstrate the variance of the homophily level across neighborhoods at
different layers. Motivated by these analyses, we further propose a tree
decomposition method to disentangle neighborhoods in different layers to
alleviate feature smoothing among these layers. Moreover, we characterize the
multi-hop dependency via graph diffusion within our tree decomposition
formulation to construct Tree Decomposed Graph Neural Network (TDGNN), which
can flexibly incorporate information from large receptive fields and aggregate
this information utilizing the multi-hop dependency. Comprehensive experiments
demonstrate the superior performance of TDGNN on both homophily and heterophily
networks under a variety of node classification settings. Extensive parameter
analysis highlights the ability of TDGNN to prevent over-smoothing and
incorporate features from shallow layers with deeper multi-hop dependencies,
which provides new insights towards deeper graph neural networks. Code of
TDGNN: http://github.com/YuWVandy/TDGNN
