Research on the Expressive of Graph Neural Networks for Graph Connectivity
Dun Ma, Suixiang Gao · 2024
The expressive power of Message Passing Graph Neural Networks (MP-GNNs) is limited by Weisfeiler-Lehman (WL) test. Although numerous approaches have been proposed to improve GNNs expressive, there is still a lack of deep understanding of the performance of (MP-GNN) for graph connectivity. Graph connectivity refers to whether there is a path between every pair of vertices in a graph. In this paper, we have proved that MP-GNNs fails to identify whether a graph is connective based on model theory and conducted a simulation experiments to verify our theory.