How hard is to distinguish graphs with graph neural networks?
This addresses the fundamental limits of graph neural networks in distinguishing graphs, which is crucial for researchers in graph learning and AI, though it is incremental as it refines existing theoretical bounds.
The study derived hardness results for graph isomorphism classification using message-passing neural networks (MPNN), showing that capacity must grow linearly with nodes for trees and quadratically for general graphs, with empirical validation on 12 tasks and 420 networks.
A hallmark of graph neural networks is their ability to distinguish the isomorphism class of their inputs. This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN). MPNN encompasses the majority of graph neural networks used today and is universal when nodes are given unique features. The analysis relies on the introduced measure of communication capacity. Capacity measures how much information the nodes of a network can exchange during the forward pass and depends on the depth, message-size, global state, and width of the architecture. It is shown that the capacity of MPNN needs to grow linearly with the number of nodes so that a network can distinguish trees and quadratically for general connected graphs. The derived bounds concern both worst- and average-case behavior and apply to networks with/without unique features and adaptive architecture -- they are also up to two orders of magnitude tighter than those given by simpler arguments. An empirical study involving 12 graph classification tasks and 420 networks reveals strong alignment between actual performance and theoretical predictions.