Theoretical Insights into Line Graph Transformation on Graph Learning
This work addresses a theoretical gap for researchers in graph learning, but it is incremental as it builds on existing line graph transformation methods.
The study tackled the lack of theoretical understanding of how line graph transformation affects GNN expressivity, showing that it helps exclude challenging graph properties like CFI and strongly regular graphs, potentially aiding WL tests in distinguishing them, with empirical validation through experiments comparing accuracy and efficiency.
Line graph transformation has been widely studied in graph theory, where each node in a line graph corresponds to an edge in the original graph. This has inspired a series of graph neural networks (GNNs) applied to transformed line graphs, which have proven effective in various graph representation learning tasks. However, there is limited theoretical study on how line graph transformation affects the expressivity of GNN models. In this study, we focus on two types of graphs known to be challenging to the Weisfeiler-Leman (WL) tests: Cai-Fürer-Immerman (CFI) graphs and strongly regular graphs, and show that applying line graph transformation helps exclude these challenging graph properties, thus potentially assist WL tests in distinguishing these graphs. We empirically validate our findings by conducting a series of experiments that compare the accuracy and efficiency of graph isomorphism tests and GNNs on both line-transformed and original graphs across these graph structure types.