2FWL-SIRGN: A Scalable Structural 2-dimensional Folklore Weisfeiler Lehman Graph Representation Learning Approach Via Structural Graph Partitioning

Graph representation learning has numerous applications, ranging from social networks to bioinformatics, with a major focus on Graph Neural Networks (GNNs). However, many GNN models face challenges in capturing intricate graph structures, such as cycles, and are prone to overfitting and high computational costs, limiting their scalability on medium to big graphs.In this paper, we propose 2FWL-SIRGN, a novel approach that integrates higher-order Weisfeiler-Lehman (WL) test algorithm while mitigating its computational challenges. Our method combines the Structural Iterative Representation Learning for Graph Nodes (SIRGN) framework with the 2-dimensional Folklore Weisfeiler-Lehman (2FWL) isomorphism test. The unsupervised training of the SIRGN component improves the model’s resistance to overfitting, while the 2FWL component enhances its expressive power, enabling it to capture complex patterns, such as cycle structures. However, the inclusion of 2FWL increases computational overhead. To address this, we introduce a Structural Graph Partitioning algorithm, which allows 2FWL-SIRGN to scale efficiently to big graphs.Extensive experiments demonstrate that 2FWL-SIRGN outperforms state-of-the-art methods by addressing key challenges in graph representation learning. Our model captures richer structural information while maintaining computational efficiency, surpassing other higher-order WL approaches. Additionally, our partitioning strategy enables 2FWL-SIRGN to effectively handle large-scale graphs, and its inherent resistance to overfitting addresses a common limitation of GNNs. These advancements position 2FWL-SIRGN as a robust solution for real-world applications where both scalability and accuracy are critical.