LG-GNNs: Enhancing Node Classification via Line Graph Transformations for Higher-Order Structural Learning

Year 2025, Volume: 9 Issue: 4, 670 - 677, 08.10.2025

Jusuf Qarkaxhija , Engin Melekoglu , Murat Gök

https://doi.org/10.31127/tuje.1704305

Abstract

Graph Neural Networks (GNNs) have demonstrated remarkable success in learning robust representations from complex graph-structured data. However, standard GNNs architectures often fail to capture higher-order structural information effectively, resulting in suboptimal performance on tasks that require a nuanced understanding of intricate node dependencies. In this work, we present a novel architectural innovation—the Line Graph GNN (LG-GNNs)—which integrates the line graph transformation into the traditional GNNs framework. By explicitly modeling higher-order interactions among edges, our approach enriches node embeddings with additional structural context.
We evaluate LG-GNNs on a variety of benchmark datasets that capture both simple and complex network structures, comparing its performance against conventional GNNs architectures. Experimental results demonstrate that LG-GNNs consistently outperforms baseline models in terms of classification accuracy while maintaining competitive efficiency. Motivated by the shortcomings of standard GNNs in capturing complex relational dependencies in real-world networks, our method delivers a more expressive representation that enhances predictive performance across diverse applications.
To encourage reproducibility and further research in the field, we have made our implementation and experimental results publicly available.

Keywords

Graph Neural Networks , Graph Transformation , Node Classification , Higher-Order Learning

References

• Xue, G., Zhong, M., Qian, T., & Li, J. (2024). PSA-GNN: An augmented GNN framework with priori subgraph knowledge. Neural Networks, 173, 106155.
• Li, J., Peng, H., Cao, Y., Dou, Y., Zhang, H., Yu, P. S., & He, L. (2021). Higher-order attribute-enhancing heterogeneous graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 35(1), 560-574.
• Zhang, B., Fan, C., Liu, S., Huang, K., Zhao, X., Huang, J., & Liu, Z. (2024). The expressive power of graph neural networks: A survey. IEEE Transactions on Knowledge and Data Engineering.
• Zhang, S., Tong, H., Xu, J., & Maciejewski, R. (2019). Graph convolutional networks: a comprehensive review. Computational Social Networks, 6(1), 1-23.
• He, L., Bai, L., Yang, X., Du, H., & Liang, J. (2023). High-order graph attention network. Information Sciences, 630, 222-234.
• Xiao, L., Wu, X., & Wang, G. (2019). Social network analysis based on graph SAGE. In 2019 12th international symposium on computational intelligence and design (ISCID), 2, 196-199.
• Adamic, L. A., & Adar, E. (2003). Friends and neighbors on the web. Social Networks, 25(3), 211-230.
• Zhang, M., & Chen, Y. (2018). Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31.
• Xie, C., Huang, J., Shi, Y., Pang, H., Gao, L., & Wen, X. (2025). Ensemble graph auto-encoders for clustering and link prediction. PeerJ Computer Science, 11, e2648.
• Chen, Z., Villar, S., Chen, L., & Bruna, J. (2019). On the equivalence between graph isomorphism testing and function approximation with GNNs. Advances in Neural Information Processing Systems, 32.
• Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019). Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 33(1), 4602-4609.
• Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., & Leskovec, J. (2018). Hierarchical graph representation learning with differentiable pooling. Advances in Neural Information Processing Systems, 31.
• Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4), 452-473.
• Cabanes, C., Grouazel, A., von Schuckmann, K., Hamon, M., Turpin, V., Coatanoan, C., ... & Le Traon, P. Y. (2012). The CORA dataset: validation and diagnostics of ocean temperature and salinity in situ measurements. Ocean Science Discussions, 9(2), 1273-1312.
• Caragea, C., Wu, J., Ciobanu, A., Williams, K., Fernández-Ramírez, J., Chen, H. H., ... & Giles, L. (2014). Citeseer x: A scholarly big dataset. In Advances in Information Retrieval: European Conference on IR Research, 36, 311-322.
• Vibert, N., Ros, C., Bigot, L. L., Ramond, M., Gatefin, J., & Rouet, J. F. (2009). Effects of domain knowledge on reference search with the PubMed database: An experimental study. Journal of the American Society for Information Science and Technology, 60(7), 1423-1447.
• Yigit, G. (2025). A Comparative Study of Deep Learning Approaches for Human Action Recognition. Turkish Journal of Engineering, 9 (2), 281-289.
• Sinap, V. (2024). Comparative analysis of machine learning techniques for credit card fraud detection: Dealing with imbalanced datasets. Turkish Journal of Engineering, 8(2), 196-208.
• Mogaraju, J. K. (2024). Machine learning empowered prediction of geolocation using groundwater quality variables over YSR district of India. Turkish Journal of Engineering, 8(1), 31-45.
• Rampášek, L., & Wolf, G. (2021). Hierarchical graph neural nets can capture long-range interactions. In International Workshop on Machine Learning for Signal Processing (MLSP), 31, 1-6.
• Rossi, E., Charpentier, B., Di Giovanni, F., Frasca, F., Günnemann, S., & Bronstein, M. M. (2023). Edge Directionality Improves Learning on Heterophilic Graphs. Proceedings of the Second Learning on Graphs Conference, PMLR 231, Virtual Event, 27–30.
• Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., & Koutra, D. (2020). Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 7793-7804.
• West, D. B. (2001). Introduction to graph theory, Prentice hall.
• Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, 29.
• Guo, J., Huang, K., Zhang, R., & Yi, X. (2024). ES-GNN: Generalizing graph neural networks beyond homophily with edge splitting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12), 11345-11360.
• Uzer, A. U. (2024). Efficient prediction of compressive strength in geotechnical engineering using artificial neural networks. Turkish Journal of Engineering, 8(3), 457-468.
• Sinap, V. (2025). A novel hyperparameter tuning method for enhanced intrusion detection in network security. Turkish Journal of Engineering, 9(3), 519-534.
• Wang, J., Chen, P., Ma, B., Zhou, J., Ruan, Z., Chen, G., & Xuan, Q. (2021). Sampling subgraph network with application to graph classification. IEEE Transactions on Network Science and Engineering, 8(4), 3478-3490.
• Castro, R. L., Andrade, D., & Fraguela, B. B. (2024). STuning-DL: Model-Driven Autotuning of Sparse GPU Kernels for Deep Learning. IEEE Access, 12(2), 70581-70599.
• Chen, L., Zhu, Y., & Li, M. (2024). Tactile-GAT: tactile graph attention networks for robot tactile perception classification. Scientific Reports, 14(1), 27543.
• Liu, S., Qu, M., Zhang, Z., Cai, H., & Tang, J. (2022). Structured multi-task learning for molecular property prediction. In International Conference on Artificial Intelligence and Statistics, 8906-8920.
• Jin, W., Ma, Y., Liu, X., Tang, X., Wang, S., & Tang, J. (2020). Graph structure learning for robust graph neural networks. In Proceedings of the ACM SIGKDD international conference on knowledge discovery & data mining, 26, 66-74.
• Cengiz, E., & Gök, M. (2023). Reinforcement learning applications in cyber security: A review. Sakarya University Journal of Science, 27(2), 481-503.
• Ayoub, J., Lotfi, D., & Hammouch, A. (2022). Link prediction using betweenness centrality and graph neural networks. Social Network Analysis and Mining, 13(1), 5.