Theoretical Insights into Line Graph Transformation on Graph Learning

Fan Yang, Xingyue Huang
Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations, PMLR 282:996-1016, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v282-yang26a, title = {Theoretical Insights into Line Graph Transformation on Graph Learning}, author = {Yang, Fan and Huang, Xingyue}, booktitle = {Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations}, pages = {996--1016}, year = {2026}, editor = {Acosta, Francisco and Azeglio, Simone and Tolooshams, Bahareh and van de Geijn, Chase and Shewmake, Christian and Sanborn, Sophia and Miolane, Nina}, volume = {282}, series = {Proceedings of Machine Learning Research}, month = {14 Dec 2024--07 Dec 2025}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v282/main/assets/yang26a/yang26a.pdf}, url = {https://proceedings.mlr.press/v282/yang26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Theoretical Insights into Line Graph Transformation on Graph Learning %A Fan Yang %A Xingyue Huang %B Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations %C Proceedings of Machine Learning Research %D 2026 %E Francisco Acosta %E Simone Azeglio %E Bahareh Tolooshams %E Chase van de Geijn %E Christian Shewmake %E Sophia Sanborn %E Nina Miolane %F pmlr-v282-yang26a %I PMLR %P 996--1016 %U https://proceedings.mlr.press/v282/yang26a.html %V 282 %X 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.
APA
Yang, F. & Huang, X.. (2026). Theoretical Insights into Line Graph Transformation on Graph Learning. Proceedings of the 4th (2025) and 3rd (2024) NeurIPS Workshops on Symmetry and Geometry in Neural Representations, in Proceedings of Machine Learning Research 282:996-1016 Available from https://proceedings.mlr.press/v282/yang26a.html.

Related Material