Growing Like a Tree: Finding Trunks From Graph Skeleton Trees

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Neural Networks

Background:

• The message-passing paradigm is foundational for Graph Neural Networks (GNNs), enabling success in diverse applications.
• However, GNNs face challenges in graph-level tasks, including the long-range problem, information bottleneck, over-squashing, and limited expressivity.

Purpose of the Study:

• To overcome major challenges in GNNs for graph-level tasks.
• To move beyond conventional node- and edge-centric approaches.
• To develop a novel framework for powerful graph representations.

Main Methods:

• In-depth theoretical analysis of information bottlenecks from an information influence perspective.
• Extracting skeleton trees from original graphs.
• Propagating information distinctively on skeleton trees.
• Identifying graph trunks inspired by natural trees.

Main Results:

• Extensive experiments on real-world datasets demonstrate the proposed model's superiority.
• The model effectively captures long-range dependencies.
• The model alleviates the over-squashing problem in graph data.

Conclusions:

• The proposed framework offers a novel approach to graph-level tasks by breaking conventional GNN limitations.
• The method provides powerful graph representations by leveraging skeleton trees and trunks.
• This research offers new insights into addressing challenges in graph representation learning.