Quantifying the non-isomorphism of global urban road networks using GNNs and graph kernels

A novel concept of quantifying graph non-isomorphism is introduced to measure structural differences between graphs, and thus overcoming the strict limitations of traditional graph isomorphism tests. This paper trains Graph Neural Networks (GNNs) and graph kernels to classify urban road networks and proposes using graph classification accuracy as a metric to quantify graph non-isomorphism. Experimental results demonstrate that Edge Convolutional Neural Network (EdgeCNN) not only leverages node attributes effectively but also fully utilizes edge features, achieving an 85% classification accuracy, which surpasses that of the Weisfeiler-Lehman (WL) kernel algorithm (80%). This finding challenges the claim that "GNNs are at most as powerful as the WL test in distinguishing graph structures." Furthermore, the paper explores the non-isomorphism of 10,361 road networks from 30 cities worldwide, providing valuable insights for future urban development.