mlsanityData to 7 Oct 2026

Theoretical Insights into Line Graph Transformation on Graph Learning

arXiv 2410.16138 ↗First posted 21 Oct 2024cs.LG math.CO stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

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"urer-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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 13 of its 34 references that are in the map. First posted on arXiv 21 Oct 2024.

Builds on

13 of 34 references.

References · 13

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  3. 2019Graph Neural Networks for Social Recommendationcited by 711
  4. 2019Provably Powerful Graph Networkscited by 385
  5. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  6. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  7. 2020Graph Clustering with Graph Neural Networkscited by 163
  8. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  9. 2020Line Graph Neural Networks for Link Predictioncited by 89
  10. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  11. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  12. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
1 more
  1. 2018Spectral Graph Forge: Graph Generation Targeting Modularitycited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Educationcited by 1
  2. 2026On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Lemancited by 0