CSCN: The Crossed Subtree Convolutional Network

Message Passing Neural Networks (MPNNs) commonly suffer from over-squashing and over-smoothing issues, which limit their performance on graph-level tasks. To this end, we propose a novel Crossed Subtree Convolutional Network (CSCN) for graph classification. Specifically, CSCN first introduces an ordered subtree alignment strategy to decompose the original graph into an ordered sequence of structured subtrees. This sequence preserves rich local connectivity patterns and maintains the permutation invariance of the graph representation. Based on this, we design a crossed subtree convolution. It utilizes a sliding window to enable information interactions across different subtrees while simultaneously aggregating node features within each subtree. This design captures local information effectively while also modeling long-range dependencies. In this way, CSCN avoids deep message passing over the global graph topology and thus alleviates both over-squashing and over-smoothing. Experimental results on multiple graph classification benchmarks show that CSCN achieves competitive performance.