Permutation-Invariant graph partitioning: How graph neural networks capture structural interactions?

Area of Science:

• Graph Neural Networks
• Machine Learning
• Graph Theory

Background:

• Graph Neural Networks (GNNs) are fundamental for graph-related tasks.
• The capacity of GNNs to capture intricate structural interactions within graphs is not fully understood.

Purpose of the Study:

• To address the under-exploration of structural interactions in GNNs.
• To propose a novel architecture enhancing GNNs' ability to learn structural interactions.

Main Methods:

• Leveraging permutation invariant graph partitioning to explore structural interactions.
• Establishing theoretical links between graph partitioning and graph isomorphism.
• Introducing Graph Partitioning Neural Networks (GPNNs) architecture.
• Analyzing the impact of partitioning schemes on GNN expressivity and complexity.

Main Results:

• GPNNs demonstrate superior performance in capturing structural interactions compared to existing GNN models.
• Empirical validation across diverse graph benchmark tasks confirms the effectiveness of GPNNs.

Conclusions:

• Permutation invariant graph partitioning offers a potent method for investigating graph structural interactions.
• GPNNs represent a significant advancement in enhancing the expressive power of GNNs for learning complex graph structures.