Quantifying the Non-isomorphism of Global Urban Road Networks using GNNs and Graph Kernels

The concept of quantifying graph non-isomorphism aims to establish a more flexible framework, overcoming the stringent limitations inherent in graph isomorphism. This approach enables the measurement of the degree of difference between two graphs using appropriate metrics, making it broadly applicable in scenarios where strict graph isomorphism is not required. In this paper, we employ Graph Neural Networks (GNNs) and graph kernels to quantify the non-isomorphism of road networks, analyzing 10,361 road networks from 30 cities worldwide. Our results indicate that Edge Convolutional Neural Network (EdgeCNN) outperforms the Weisfeiler-Lehman (WL) kernel.Therefore, we challenge the assertion that "GNNs are at most as powerful as the WL test in distinguishing graph structures," highlighting that this claim overlooks the diversity and significance of node attributes and is limited to homogeneous graphs. In practice, node attributes are crucial in graph evaluation. Compared to graph kernels, GNNs can more effectively and comprehensively leverage node attributes, thereby enhancing the accuracy of heterogeneous graph classification. By quantifying graph non-isomorphism, we not only gain deeper insights into the differences in urban road networks but also provide quantitative evidence for urban road network planning, promoting more scientifically sound urban development strategies.