ON THE EFFICACY OF GRAPH NEURAL NETWORKS IN DISTINGUISHING DECOMPOSABLE AND EXCEPTIONAL GRAPHS

Abstract

A graph

is locally irregular if for every edge

( u , v ) ∈ E ( G ) $(u,v) \in E(G)$ left parenthesis u comma v right parenthesis element of upper E left parenthesis upper G right parenthesis

, the vertices

u $u$ u

and

v $v$ v

have distinct degrees. The locally irregular edge-colouring problem is a graph decomposition problem in which the edges of a graph are coloured such that each colour induces a locally irregular subgraph. If a graph

G $G$ upper G

can be edge-coloured such that each colour induces a locally irregular subgraph, then

G $G$ upper G

is said to be decomposable ; otherwise,

G $G$ upper G

is exceptional . Graph neural networks (GNNs) are a class of deep learning models designed to operate on graph-structured data and are typically applied to tasks involving rich node features. In this work, we investigate and benchmark several popular GNN architectures for the classification of decomposable and exceptional graphs using minimal feature input. We compare models with different input representations, and provide a detailed analysis of their learning behaviour and the resulting graph embeddings. We show that the performance of many message passing GNNs degrades in the absence of node features in many graph-related problems. However, little work has been done to show why that is the case. Our results show that this is not the case in general and modern GNNs are able to learn meaningful structural representations that enable effective classification of these graphs to a certain extent. Furthermore, we observe some generalization to out-of-distribution graphs, suggesting both the promise and current limitations of GNNs as tools for pattern discovery in theoretical graph problems.