For years, the message passing paradigm has served as the foundation of Graph Neural Networks (GNNs), achieving remarkable success across a wide range of applications. Despite this success, it introduces unexpected challenges for graph-level tasks, such as the long-range problem, information bottleneck, over-squashing phenomenon, and limited expressivity.

To address these issues in graph-level tasks, the Neural Computation and Brain-Computer Interaction Team at the Institute of Automation, Chinese Academy of Sciences, developed a new framework—Graph Trunk Network (GTR). The goal is to break free from the traditional “node-and-edge-centered” mindset and overcome the aforementioned limitations inherent in the message passing paradigm. The core idea is that graph-level tasks typically do not require learning extremely precise representations for every node, as is necessary for node-level tasks. Specifically, the proposed framework first uses a tree decomposition algorithm to extract a skeleton tree from the original graph. This skeleton tree is then decomposed into different levels of “trunks,” with Long Short-Term Memory (LSTM) networks employed to learn representations along the paths of these trunks. Finally, the representations from all levels of trunks are combined to form the representation of the original graph. In-depth theoretical analysis and comprehensive experimental validation further demonstrate the superiority of the proposed model in capturing long-range information and mitigating the over-squashing problem, offering new insights for graph-level tasks.

                       (a) Workflow illustration of GTR on molecular graphs

(b) Workflow illustration of GTR on social networks

Figure 1. Workflow diagram of the proposed Graph Trunk Network (GTR) on two types of graphs. First (left column), graph data structures are extracted from real-world scenarios to build the original graph. Second (middle column), a skeleton tree is extracted from the original graph using a tree decomposition algorithm. Finally (right column), the skeleton tree is decomposed into different levels of trunks, and the representations of these trunks are combined to create the representation of the original graph.

This research has been published in IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), a top-tier journal in artificial intelligence. The code has also been open-sourced. Doctoral student Huang Zhongyu from the NeuBCI team is the first author of the paper, with Researcher He Huiguang as the corresponding author. The work was a collaborative effort with doctoral student Wang Yingheng from Cornell University and Researcher Li Chaozhuo from Microsoft Research Asia. This research was supported by the National Natural Science Foundation of China, the Chinese Academy of Sciences, as well as the CAAI-Huawei MindSpore Academic Award Fund and the Intelligent Foundation project.

Paper link:
https://ieeexplore.ieee.org/document/10330013

Code link:
https://github.com/zhongyu1998/GTR