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.

Node representation learning (NRL) generates numerical vectors (embeddings) for the nodes of a graph. Structural NRL specifically assigns similar node embeddings for those nodes that exhibit similar structural roles. This is in contrast with its proximity-based counterpart, wherein similarity between embeddings reflects spatial proximity among nodes. Structural NRL is useful for tasks such as node classification where nodes of the same class share structural roles, though there may exist a distant, or no path between them. Athough structural NRL has been well-studied in static graphs, it has received limited attention in the temporal setting. Here, the embeddings are required to represent the evolution of nodes' structural roles over time. The existing methods are limited in terms of efficiency and effectiveness: they scale poorly to even moderate number of timestamps, or capture structural role only tangentially. In this work, we present a novel unsupervised approach to structural representation learning for temporal graphs that overcomes these limitations. For each node, our approach clusters then aggregates the embedding of a node's neighbors for each timestamp, followed by a further temporal aggregation of all timestamps. This is repeated for (at most) d iterations, so as to acquire information from the d -hop neighborhood of a node. Our approach takes linear time in the number of overall temporal edges, and possesses important theoretical properties that formally demonstrate its effectiveness. Extensive experiments on synthetic and real datasets show superior performance in node classification and regression tasks, and superior scalability of our approach to large graphs.

Botnets are an ever-growing threat to private users, small companies, and even large corporations. They are known for spamming, mass downloads, and launching distributed denial-of-service (DDoS) attacks that have a destructive impact on large corporations. With the rise of internet-of-things (IoT) devices, they are also used to mine cryptocurrency, intercept data in transit and send logs containing sensitive information to the master botnet. Many approaches have been developed to detect botnet activities. A few approaches employ graph neural networks (GNN) to analyze the behavior of hosts using a directed graph to represent their communications. However, while designed to capture structural graph properties, GNN may overfit, and therefore fail to capture these properties when the network is unknown. In this work we hypothesize that structural graph patterns can be used to effectively detect Botnets. We then propose a structural iterative representation learning approach for graph nodes, which is designed to perform well on unseen data, called Inferential SIR-GN. Our model creates a vector representation for each node that epitomizes its structural information. We demonstrate that this set of node representation vectors can be used with a neural network classifier to identify bot nodes within an unknown network with better performance than the current state-of-the-art GNN based method.