MCoGCN-motif high-order feature-guided embedding learning framework for social link prediction Authors: Nan Xiang, Wenjing Yang, Xindi Rao Published: 2024 ABSTRACT AbstractTraditional social link prediction models primarily concentrate on the adjacency features of the network, overlooking the rich high-order structural information within. Therefore, the study of effective extraction and encoding of these high-order features, and their integration into prediction models, holds significant theoretical and practical value. To address this challenge, we propose a novel embedding learning framework guided by motif high-order features for social link prediction tasks. Firstly, we utilize the motif adjacency matrix to capture complex patterns in social networks. Through a propagation process, node embeddings can carry the structural information of the network. Subsequently, we design a simplified attention mechanism, allowing embeddings carrying motif high-order features to guide the representation of embeddings based on adjacency features. We then employ a feed-forward neural network to optimize node embeddings. Specifically, this framework addresses the issue of weakly correlated nodes in the network, which struggle to learn effective embeddings due to a lack of direct information. By guiding with high-order motif features, the framework enhances the similarity and predictive power of these node embeddings. Finally, we conducted a detailed evaluation of the predictive performance of our model on four social networks. The experimental results indicate that our model exhibits high accuracy and advantages in predicting social links.Keywords: Link prediction, Social network, Graph neural network, Motif, Weak linkSubject terms: Engineering, Mathematics and computing Introduction With social networks evolving at a rapid pace, social link prediction has become an important research topic. The goal is to predict potential new links in social networks, which is of great significance for understanding the structure and dynamic changes of social networks. Approaches grounded on conventional topological characteristics, like Common Neighbors (CN), Jaccard index, and Adamic/Adar index (AA), are very classic baselines in link prediction1, providing inspiration and foundations for subsequent research. These established attributes are not just potent but also computationally economical due to their reliance on triangular graph substructures2. However, due to their reliance on manual feature engineering, limited ability to handle high-dimensional data, and inability to fully consider global and local features of the graph, later methods such as Non-negative Matrix Factorization (NMF)3 and graph embeddings4 emerged. NMF can be effectively used for link prediction, especially when dealing with network sparsity and combining node attribute information. Graph embedding techniques have the ability to transform each node’s information into low-dimensional vectors to represent graph-structured data, but there are challenges in attribute selection, scalability, and embedding dimension selection. Therefore, in recent years, researchers’ interest has shifted to Graph Neural Networks (GNNs)5,6, which have demonstrated greater effectiveness in explicitly encoding structural information and node features7,8, resulting in notable achievements and successes9. However, not all GNN models outperform simple heuristic algorithms in link prediction tasks. Most traditional GNNs have limitations in their expressive power when dealing with link prediction tasks, and they might lack the capability to effectively grasp complex structural features in the graph, such as triangle counts. The network contains numerous connected subgraphs, so these complex structural features can be obtained by studying motifs. Network motifs of high-order connectivity are considered as the basic building blocks of networks that exhibit complex structural patterns10. With the in-depth study of complex networks, motif analysis has been employed across various networks, for example, social networks and internet topologies, to understand their structures and characteristics. Additionally, nodes and edges in a network can form structures at multiple scales, such as local node neighborhoods, community structures, and global network features, with complex correlations between different structural scales11. In previous research, many methods for social link prediction have been proposed, but most of these methods consider only a single scale of the network, ignoring its multi-scale characteristics. In the network, not only do influential nodes exist12, typically characterized by having numerous connections or close relationships with other nodes, but there are also nodes that exhibit weak correlations, sharing few or no common neighbors. When two nodes show weak correlations, especially when they are located in different communities, the link prediction model tends to separate the embedding vectors trained for these weakly linked vertices in space due to a lack of sufficient direct information and context to guide the learning process. These vectors each represent their community characteristics, resulting in low similarity. Therefore, learning effective embeddings for these weakly linked vertices becomes a challenge. Therefore, we put forward a new approach named MCoGCN, which learns embedding representations under the guidance of Motif high-order features to achieve the Collaboration of features at different scales, thereby improving the performance of link prediction. High-level data reduces specific details that may contain noise, so high-level features help correct prediction biases that may arise from detailed data. To achieve this goal, we define a simplified version of the attention mechanism that adjusts the vectors obtained from low-order features from the perspective of high-order features. In addition, we use the motif adjacency matrix as a tool for propagating high-order information and judge the intimacy of connections between nodes through the values in the matrix. In the motif, any two vertices have strong connectivity. Although the direct neighbors of two nodes may not be the same, the strong connectivity of the motif structure can help us discover and make up for the weak relevance between nodes, as shown in Fig. 1. Furthermore, in order to obtain higher quality node embeddings without significantly increasing the model complexity, we use feed-forward neural networks for noise reduction. Nodes and are located in two different community structures, exhibiting weak correlation. However, they are located within the same motif instance (as shown in red and pink), which strengthens the connection between the nodes. We conducted link prediction tests on four authentic social network datasets to validate the efficiency of our algorithm. MCoGCN achieved great success, surpassing most of the baseline models. In summary, the contributions of this study are as follows: To address the limitations of traditional link prediction models that cannot fully utilize features at different scales within the network, we propose a novel link prediction model called MCoGCN, which enhances the node representations by jointly modeling multi-scale structural information, and improves model performance by optimizing embedding quality through feed-forward neural networks. To address the limitations of traditional link prediction models that cannot fully utilize features at different scales within the network, we propose a novel link prediction model called MCoGCN, which enhances the node representations by jointly modeling multi-scale structural information, and improves model performance by optimizing embedding quality through feed-forward neural networks. We define a simplified and flexible guided attention mechanism. It can use high-order structural features to guide the learning of low-order structural features, correcting prediction biases that may arise from detailed data. This attention method shows a simple structure, high computational efficiency, and easy-to-expand characteristics. We define a simplified and flexible guided attention mechanism. It can use high-order structural features to guide the learning of low-order structural features, correcting prediction biases that may arise from detailed data. This attention method shows a simple structure, high computational efficiency, and easy-to-expand characteristics. We utilize motifs to capture the high-level topological details of the network. This enables us to better identify and handle potential weak links within the network, and verify the effectiveness of using more complex topological features based on high-order motifs in link prediction tasks; We utilize motifs to capture the high-level topological details of the network. This enables us to better identify and handle potential weak links within the network, and verify the effectiveness of using more complex topological features based on high-order motifs in link prediction tasks; The results of our experiments conducted on four publicly available datasets demonstrate that MCoGCN achieves high accuracy and good consistency. The results of our experiments conducted on four publicly available datasets demonstrate that MCoGCN achieves high accuracy and good consistency. This paper is arranged in the following manner. Section “Related work” offers a review of the work related to Graph Neural Networks and motifs. In “Methods”, we delve into the comprehensive framework of our model and thoroughly explain the loss function. Section “Results” showcases the efficacy of our algorithm through experiments performed on four social networks, thus establishing the advantages of our proposed technique. In the final section, we wrap up the paper and propose possible directions for future investigations. Related work Work related to motifs For motif research, with the rapid development of computing power and algorithms, the ability to enumerate motifs that encompass more than three nodes has been significantly enhanced13. Furthermore, research2 has also demonstrated that high-order motif characteristics substantially improve the accuracy of link prediction algorithms. Early motif research focused on exploring important patterns and substructures in biological networks14, especially protein–protein interaction networks, and demonstrated that specific motif patterns are related to the robustness of perturbations, showing their modeling capabilities in biological networks. Chen et al.15 proposed MGNN, which involves generating node representations, minimizing motif redundancy, integrating representations from multiple motifs, and leveraging an injection function to enhance the discriminative capability of graph neural networks. Wang et al.16 introduced a motif-based algorithm for learning node embeddings specifically tailored for link prediction tasks. This algorithm harnesses the concept of motifs, incorporating two levels of proximity within an autoencoder framework, to capture high-order structural information and mitigate the challenges associated with predicting weak connections. To measure the similarity between two nodes within their immediate surroundings, Li et al.17 integrates existing similarity definitions and motifs, proposing a similarity index based on motifs. To address the issue that existing link prediction methods for directed networks mostly consider only one motif and ignore the impact of multiple motifs, Liu et al.18 proposed a single motif naive Bayes model and studied a two-motif naive Bayes model along with a machine learning framework that utilizes multi-motif features to enhance link prediction performance. The literature19 introduced a specific algorithm for creating motif adjacency matrices and introduces a graph attention network based on motifs for service recommendation. This network captures high-order information of various motifs and makes recommendation predictions using a collaborative filtering model. DeepGL20 leverages motif learning to induce relational functions, serving as a general inductive graph representation learning framework. A paper21 introduces a generalized motif-based framework for network clustering. The clusters formed based on this framework can be mathematically guaranteed to be optimal, and it is capable of scaling to networks with billions of edges. The literature22 describes a versatile structure called High-Order Network Embedding (HONE) based on network motifs for learning from graph data. The HONE framework is remarkably adaptable and expressive, comprising numerous exchangeable elements. A research of graph node classification23 introduces a self-attention model at the motif level that learns the weights of various motifs via differentiation. Luo et al.24 presented a graph neural network, termed as MotifGNN, which is motif-based and is utilized for recommending matches in online dating. Work related to GNNs GNNs generate representations of nodes or entire graphs by integrating information from the surrounding neighborhood of a node, enabling them to more effectively capture the graph structures and node features. Velickovic et al.25 introduced Graph Attention Networks (GATs), which leverage self-attention layers to allocate varying weights to distinct neighbors, making them more accurately capture the relationships between nodes. He et al.26 proposed LightGCN, which only contains the fundamental element of GCNs for collaborative filtering - neighborhood aggregation. This simplifies the design of GCNs, making them more concise and suitable for recommendation tasks. Bojchevski et al.27 presented PPRGo, which uses an effective approximation of information diffusion in GNNs, thereby significantly speeding up computation while improving predictive performance. xGCN28 is an extreme graph convolutional network used in large-scale networks. It abandons the traditional paradigm of GNN and proposes a new iterative paradigm, namely [Propagation, Refnement, SGD, Refresh], which achieves SOTA results and speed improvements in link prediction tasks on large-scale social graphs. However, none of the above studies unifiedly modeled the multi-scale information of networks. Regarding multi-scale collaboration research, the literature11 mentions that networks consist of individuals and their connections to other individuals, thus macro-level dynamics originate from micro-level dynamics. Conversely, the behavior of individuals is also influenced by their social relationships, including political orientations, musical tastes, and even the way people choose new friends29,30. Therefore, there are complex interconnections between various levels. For in-depth studies of networks, it is inevitable to consider their multi-scale characteristics. Methods Task definition Given a graph with nodes, and edges. The corresponding adjacency matrix , where indicates a connection from node to node . The degree of each node is stored in a diagonal matrix D: . The motif structure features are represented by the motif adjacency matrix . The objective is to learn a model f for embedding, that is capable of encoding each node into a d-dimensional embedding vector, formulated as , where . The probability of an edge occurring between nodes u and v is quantified through the dot product operation: . Motif: Typically, a motif is associated with a specific frequency threshold, meaning its occurrence rate must exceed what is expected under random conditions. However, in network analysis, researchers do not impose such constraints and define a motif as a small, connected, non-isomorphic subgraph that represents recurring patterns or structures within the network architecture. Every k-motif illustrates the interconnected topological structure among k nodes within the graph2, as depicted in Fig. 2. There are 7 instances of motifs, where is a 3-motif, and to are 4-motifs. Motif adjacency matrix: This is a unique form of the adjacency matrix that not only considers whether there is an edge between nodes but also accounts for the motif structure in the network. For any position in the matrix, its meaning is the frequency at which two nodes appear in a specific motif instance. The larger the value of is, the closer the connection between node and node , which can be regarded as the intimacy of the connection between the nodes. Based on this, varied intensities of linkages can be identified, and the network’s high-order structural information can be more effectively apprehended. For the network shown in Fig. 1, the intimacy between and under the instance is 2. Model framework The model comprises four key operations: Embedding Propagation, Embedding Fusion, Optimization Learning, and Embedding Refresh. These four stages are executed sequentially in a chained fashion, iterating repeatedly until convergence is achieved. The ultimate objective is to learn high-quality node embeddings that are sensitive to the graph structure, thereby enhancing the model’s resistance to noise and anomalies. The implementation process is illustrated in Fig. 3. We randomly initialize the embedding table Z, and then perform graph convolution operations to obtain smoothed embeddings and propagate node information along the graph structure, as shown in Fig. 3-(i). Next, in the Node Embedding Fusion module in Fig. 3-(ii), we effectively fuse the obtained low-order and high-order embedding tables through a simplified attention network. This hierarchical interaction mechanism can enhance the consistency and richness of node representations. To filter out the noise brought by the propagation process, we use the optimization neural network shown in Fig. 3-(iii) to further transform and refine the fused embeddings, thereby improving the quality of the embeddings. All of the model’s parameters are updated through the conventional gradient descent method. Finally, we obtain embeddings X that contain multi-scale structural features and are of higher quality, and replace Z with X. Each round of iteration brings the embedding table Z closer to the real graph structure. This method not only improves the accuracy of the embeddings but also enhances the model’s overall understanding of graph data, making the node embeddings more comprehensive and detailed. Detailed information about each key operation is as follows. Core architecture of MCoGCN. Embedding propagation We maintain a matrix, denoted as Z, to hold the embeddings of the nodes, where the embedding vector for each node is unique. Initially, Z is set to a random matrix and propagated over both the low-order and high-order structures of the graph. For the low-order structure, P is the normalized adjacency matrix of the graph G: , representing information propagation to the first-order neighborhood: For high-order information, we first generate the corresponding motif adjacency matrices based on the defined motif structures. These matrices are then weighted and summed. Subsequently, we conduct spectral normalization on the result to form a comprehensive network representation , as shown in Fig. 4. Then, the new representation of the nodes is obtained by aggregating the high-order structural details of the network following the motif adjacency matrix: where is the quantity of each motif structure in the graph, and is the largest singular value of , which can be calculated via singular value decomposition (SVD) or the power iteration method. The weighted matrices are added and normalized. Embedding fusion After the propagation process, the structural information of the network is enhanced. Now, we fuse the obtained low-order embedding table and high-order embedding table through an attention mechanism, as shown in Fig. 5. Firstly, we merge the two embedding tables into one embedding table, which can be the addition of two embedding tables or concatenation along the second dimension. Then, through a fully connected layer with a ReLU activation function, we perform a non-linear transformation on the merged embedding table to obtain the attention score for each element. Next, we transform the attention scores into weights through another fully connected layer and a Softmax function. Finally, we carry out an element-wise multiplication between the weights and the low-order embedding table to derive the ultimate weighted embedding table. This procedure realizes dynamic weighting of the embedding table, allowing high-order features to guide and direct the representation of low-order features. In addition, this mechanism is simpler than traditional attention mechanisms, making the model easier to understand and implement. Simplified attention mechanism. is a learnable parameter. This hierarchical interaction mechanism can enhance the consistency and richness of node representation, and can capture information that may be lost in the original network, thus providing a more comprehensive view of the network. Optimization learning Through the multi-scale fusion module, the representation of each node carries information of different structural scales. However, although the propagation process can encode graph structural information into node embeddings, it is an unsupervised operation and inevitably brings a large amount of noise. Therefore, an optimization learning module is necessitated to glean pertinent details from the embeddings and to filter out the noise. It is well known that Feed-Forward Network (FFN) holds a vital position in retaining knowledge and carrying out basic transformations of information in the Transformer architecture, providing the ability to deeply transform and learn features of local information. Therefore, we have chosen FFN as our optimized learning network, paired with a Scaling Neural Network (SNN) to adjust the amplitude of the output vector from the FFN to an appropriate level. Loss function We adopt a pairwise ranking loss, BPR, to uniformly adjust the parameters in the fusion module and optimization learning module, which can make the model generalize better during the training process. The BPR loss function is a loss function used to learn user personalized preferences in recommendation systems, assuming that users prefer positive items over all other unobserved items. The BPR loss function can be minimized through optimization methods such as stochastic gradient descent, thereby learning the appropriate item ranking function: Here, acts as the scoring function, used to predict the probability of an edge existing based on the node embeddings. we implement this through the dot product, i.e., . For each pair of positive edges , we randomly draw a series of nodes that are not part of the edge set to serve as negative instances. Embedding refresh After fusion and optimization, the embeddings can serve as a better representation of the nodes. Therefore, we need to use the output of the optimization network to update the embedding table to a new state. The model uses the new embedding table to start training from scratch: Algorithm design In summary, our model repeatedly executes four steps: embedding propagation, fusion, optimization learning, and embedding refresh. We use an optimization algorithm to improve the embeddings after fusion. If there is no progress in the model’s performance on the validation set within a certain period, we consider the embeddings to have converged. At this point, We update the embedding table with the most recent and optimal embeddings available, and then proceed with the process of propagation, fusion, and optimization learning. The comprehensive training process is described in Algorithm 1. Training procedure for MCOGCN. Experiment setup Datasets In order to assess the efficacy of the model in the link prediction task, we carried out experiments on four publicly available datasets: Facebook (FB), Twitch-DE (TD), Github (GH), and the large-scale network Pokec (PK). Before training, a subset of edges needs to be extracted from the initial graph to formulate the validation and test sets. The introduction of the datasets is shown in Table 1. Table 1Datasets overview. We utilize these four datasets to evaluate the performance of our model.NodesEdgesAvg. degreeDensityFB403979,73439.59.78e−3TD9498103,13821.72.29e−3GH37,700280,50314.93.95e−4PK1,632,80327,560,30816.92.06e−5 Datasets overview. We utilize these four datasets to evaluate the performance of our model. Evaluation strategy We use Recall and Normalized Discounted Cumulative Gain (NDCG)26,31 as main evaluation metrics. Recall@K assesses the model’s effectiveness in identifying positive target nodes within the top K recommendations. It is defined as: For example, suppose there are 10 correct answers, and the model found 5 correct answers in the top K recommendations, then Recall@K is 5/10 = 0.5. We compute the mean of individual Recall@K values across all users to get an estimate of the model’s average performance across all users. NDCG measures the degree to which the positive target nodes are positioned prominently relative to the ideal ranking order. In an ideal scenario, all positive target nodes would be positioned at the top of the recommendation list, resulting in an NDCG value of 1. Other evaluation metrics also include AUC and MRR. Baseline We compare MCoGCN with various models, including the motif-based approach MGNN15, and graph embedding techniques: node2vec32, SimpleX33, UltraGCN34, RandNE35 which does not use graph convolution layers and purely utilizes propagation between nodes to learn representations, as well as other competitive baselines GraphSage36, GAT25, GIN37, xGCN28, SGC38, SIGN39, SSGC40, GBP41. Motif extraction When dealing with datasets of different scales, we flexibly choose the motif extraction strategy according to the characteristics of the dataset and training requirements. For the Twitch-DE, Facebook, and Github datasets, we extract 7 motifs from the network structure for training to capture the rich interaction patterns and community structures in these networks. These 7 motifs represent the most common and important relational patterns in the network and have broad applicability across different types of networks. By utilizing these motifs, we can map out the complex interactions between nodes more deeply, rather than being limited to simple pairwise connections. For example, the triangular motif M1 can reflect the mutual acquaintance relationship among three people, which is very common in social networks. Considering the large scale and computational cost of the Pokec dataset, in order to balance computational resources and model performance, we decide to extract only one representative motif for training on this dataset. Although this strategy may sacrifice the capture of some complex structural information to some extent, we believe that through carefully designed models and training processes, we can still achieve good link prediction results. The performance of the model will be analyzed and discussed in detail in the following sections. Results Overall performance Figure 6 presents the scatter plots of the evolution of various evaluation metrics during the training process of MCoGCN on four datasets. It is evident that our model continuously optimizes its prediction and ranking capabilities, effectively learning and fine-tuning its parameters from the data to better fit the data distribution. Furthermore, it exhibits good stability and convergence properties.The discontinuity observed at the 10th epoch arises from the warm-up phase incorporated into our model training process. During this phase, as per the description in Algorithm 1, a refresh and propagation operation is performed after every T = 10 epochs of optimization updates. Metrics evolution during MCoGCN training on four datasets. Tables 2 and 3 summarize the overall accuracy performance comparison of the four datasets respectively. The visualization of the table data in a bar chart is shown in Fig. 7. We conduct each model’s experiment five times across all datasets and present the average scores. Our observations are as follows: Table 2Comparison of overall performance across three datasets among different models. Values in percentage (%).ModelTDFBGHR@20R@50N@20R@20R@50N@20R@20R@50N@20MCoGCN15.6223.3717.9138.0662.8926.7217.8927.0810.73MGNN1514.0119.2512.3232.7153.8122.1310.2320.015.83xGCN2815.2323.2215.5535.1359.1024.2612.8221.597.44GraphSAGE368.3211.728.333.969.993.4810.7216.846.52GAT2518.3826.2419.5736.9262.0326.4915.0222.348.33GIN379.1716.279.2434.7258.2024.047.1313.554.02SimpleX3312.8517.7912.9217.5029.7312.0217.4524.19.41UltraGCN340.731.330.887.2711.255.170.380.890.23RandNE350.932.160.9936.1657.1123.070.350.780.24SGC381.723.681.8217.0134.9713.091.362.920.83Optimal values are in bold, and sub-optimal values are underlined. Comparison of overall performance across three datasets among different models. Values in percentage (%). Optimal values are in bold, and sub-optimal values are underlined. Table 3Comparison of overall performance among different models on the POKEC social graph. Values in percentage (%).ModelR@50R@100N@100MCoGCN9.8514.283.78MGNN155.418.102.52GraphSAGE367.2210.872.76GAT254.657.601.72GIN377.6211.242.92Node2Vec324.517.451.74SimpleX331.011.530.44UltraGCN345.627.742.16RandNE351.041.690.44SGC386.0110.242.18SIGN395.589.382.00SSGC407.1510.722.59GBP419.2413.233.49Optimal values are in bold, and sub-optimal values are underlined. Comparison of overall performance among different models on the POKEC social graph. Values in percentage (%). Optimal values are in bold, and sub-optimal values are underlined. Overall performance bar chart. For the three regular datasets, we compare with nine models, and MCoGCN outperforms most baseline models. On the Twitch dataset, although the performance of MCoGCN is second to the GAT model, it still ranks second and performs well. On the Facebook and Github datasets, our model performs the best, indicating that our model has higher accuracy on most datasets. For the three regular datasets, we compare with nine models, and MCoGCN outperforms most baseline models. On the Twitch dataset, although the performance of MCoGCN is second to the GAT model, it still ranks second and performs well. On the Facebook and Github datasets, our model performs the best, indicating that our model has higher accuracy on most datasets. For the large-scale Pokec dataset, we compare with twelve models. Despite using only one motif, our model still outperforms the other twelve models in terms of performance.. For the large-scale Pokec dataset, we compare with twelve models. Despite using only one motif, our model still outperforms the other twelve models in terms of performance.. The MCoGCN model has achieved a maximum improvement of 1.14% in accuracy compared to other models, providing a novel and unique approach for link prediction tasks. The MCoGCN model has achieved a maximum improvement of 1.14% in accuracy compared to other models, providing a novel and unique approach for link prediction tasks. In summary, MCoGCN exhibits either superior or comparable performance when benchmarked against SOTA models across various dataset types and scales, indicating its strong generalization ability and adaptability to various social network structures. This fully validates the effectiveness and universality of our model design approach. MCoGCN effectively captures high-order topological information in the graph through motifs, which is crucial for understanding complex relationships between nodes and is one of the key factors for the model’s performance improvement. Furthermore, the model employs a concise attention mechanism to guide feature learning. This approach prevents the loss of global information that would occur if only low-order structures were used. It surpasses the limitations of traditional graph convolutional networks, which consider only first- or second-order neighbors, thereby enhancing the model’s predictive accuracy and performance. Robustness study Next, we study the robustness of MCoGCN and compare it with other models using identical hardware configuration: the GPU is NVIDIA GeForce RTX 2080 Ti, 16GB, and the CPU is Intel Core i9-9900K CPU @ 3.60GHz16. Figure 8 presents a comparison of various models on the Twitch-DE, Facebook, and Github datasets under the same set of seeds, and Table 4 displays the metrics for the test set on the Pokec dataset under varying numbers of seeds. From the results, it can be clearly seen that our model MCoGCN shows relatively consistent performance under different random seeds. This means that even if the seeds are different, MCoGCN can still maintain stable predictive ability, which is very important for model selection and deployment in practical applications. In addition, the performance of MCoGCN exceeds that of most other models. This indicates that our model is competitive in the field of link prediction and performs well on different datasets. Comparative study of test set results for different models under the same seed number. Table 4The performance metrics of the Pokec dataset under different seed numbers. Values in percentage (%).SeedR@20R@50R@100R@300N@20N@50N@100N@30016.1010.7015.6826.302.343.264.065.4925.709.9314.5424.552.313.153.905.2434.757.9811.6019.371.872.513.104.1546.2510.9715.5525.742.453.384.125.5055.339.6514.0223.972.163.013.715.05Avg5.639.8514.2823.992.233.063.785.09 The performance metrics of the Pokec dataset under different seed numbers. Values in percentage (%). In addition, we conducted training for each of the four models over 100 epochs, calculating the Recall@20 score on the validation set at the end of each epoch and monitoring the loss values. The training curves depicted in Fig. 9 illustrate that MCoGCN exhibits rapid convergence, achieving consistently lower loss values quickly and demonstrating relative stability across multiple training cycles. These findings underscore the model’s reliability and effectiveness in addressing pertinent tasks. Hence, our MCoGCN model manifests robust performance characteristics, indicative of its efficacy and reliability in handling relevant tasks within the field of artificial intelligence. Training efficiency study. Recall@20 scores and loss values on the validation set for different datasets. Weak link Here, we specifically define a weak link as a link between two nodes with fewer than three common neighbors. To validate the model’s ability to recognize and distinguish weak links, we identify all positive weak links (actual existing links) in the graph and sample 100 negative weak links (links that do not actually exist). We use the embeddings obtained through training to calculate the inner product scores of these two types of links, serving as a quantitative indicator of link strength. In the experiment, we calculated the average inner product scores of positive and negative weak links for different models on the Facebook and Github datasets, respectively. As shown in Fig. 10, MCoGCN shows the highest average score on positive instances and the lowest average score on negative instances compared to other models. This significant difference not only validates the effectiveness of our model in capturing subtle structural features of the network, but also strongly demonstrates the superior performance of MCoGCN in recognizing and distinguishing weak links in the network. Average similarity score of weak links. Ablation study We conduct ablation studies in four areas: (1) Propagation module; (2) Multi-scale feature fusion module; (3) Embedding optimization module; (4) Examining the influence of the selected number of motifs on model performance. This is to demonstrate the essentiality of certain key components within the model. The results are presented in Table 5, leading to the following conclusions: Firstly, we only validate through the embedding propagation and fusion modules that it is difficult to encode any useful information on randomly initialized embeddings without parameter propagation, which also indirectly proves the role of the optimization module, as shown in data (i.a). (i.b) and (i.c) reflect that relying solely on any one level of structural information will bring deficiencies: using only low-order embeddings will omit key network structural information; while relying only on high-order structural information may overlook details and semantic information in the network. Therefore, using both can complement each other’s advantages and achieve better results. The (ii) series demonstrates the influence of various fusion strategies on model performance, (ii.a) and (ii.b) compare simple addition and concatenation fusion methods, (ii.c)–(ii.e) compare the effects of using 1-layer and 2-layer multi-scale fusion attention. The results show that our attention strategy can well fuse low-order and high-order embeddings, bringing positive effects on model performance. (iii.a)–(iii.d) indicate that FFN can enhance embeddings initially of lower quality, making them more representative, among which the 3-layer network performs the best. (iv.a) and (iv.b) show the impact of using different numbers of motifs on the model. From the results, using 1 kind of motif and 3 kinds of motifs can both achieve good results, proving that using motifs as high-order structural features is a good choice. Table 5Ablation studies for MCoGCN. Explanation of notations: (i) Propagation Module: The effects of having only propagation, fusion modules, and propagating only low-order structures or high-order structures; (ii)The influence of various fusion strategies on model performance; (iii) Number of layers in FFN: FFN is set to 1-4 layers respectively to investigate its impact on the model; (iv) Analyze the effect of different numbers of motifs on the model, proving the effectiveness of motif.FBGHR@20R@50N@50R@20R@50N@50(i.a) Prop-Fusion0.210.490.170.000.040.01(i.b) Only-Low35.1359.1024.2612.8221.597.44(i.c) Only-High14.7126.9611.1611.8216.047.68(ii.a) Fus-OnlyAdd33.9756.9423.3311.4620.966.56(ii.b) Fus-OnlyCat31.9054.9222.167.2312.706.31(ii.c) 1L-Fus-Add32.8556.9123.4612.5618.536.54(ii.d) 1L-Fus-Cat35.6360.2025.3413.0319.158.79(ii.e) 2L-Fus-Cat37.4061.9826.5613.5319.458.52(iii.a) 1L-FFN1.212.470.8212.8519.148.46(iii.b) 2L-FFN1.502.391.248.5617.444.19(iii.c) 3L-FFN38.0662.8926.7217.8927.0810.73(iii.d) 4L-FFN1.683.191.289.1614.947.09(iv.a) 1-Motif37.4360.8025.9312.3519.338.75(iv.b) 3-Motif35.7760.6225.2913.4020.596.14 Ablation studies for MCoGCN. Explanation of notations: (i) Propagation Module: The effects of having only propagation, fusion modules, and propagating only low-order structures or high-order structures; (ii)The influence of various fusion strategies on model performance; (iii) Number of layers in FFN: FFN is set to 1-4 layers respectively to investigate its impact on the model; (iv) Analyze the effect of different numbers of motifs on the model, proving the effectiveness of motif. Additionally, we conducted experiments using these 7 motifs individually. As shown in Table 6, the prediction results using individual motifs range from 31.15 to 37.43, while the prediction result using the combination of all motifs is 38.06, which is significantly higher than the individual results. Table 6R@20 prediction results of each motif structure.ModelR@20 37.43 31.15 31.52 34.88 33.10 35.24 35.35Combination38.06 R@20 prediction results of each motif structure. Next, we calculate the mean and standard deviation of these individual prediction results: The mean () is calculated as: The standard deviation () is calculated as: Finally, we can conclude the following: The distribution of individual prediction results is relatively concentrated, with an average of 34.10 and a standard deviation of 2.14, indicating that the predictive ability of each motif structure is relatively stable. The distribution of individual prediction results is relatively concentrated, with an average of 34.10 and a standard deviation of 2.14, indicating that the predictive ability of each motif structure is relatively stable. The prediction result using the combination of all motif structures is significantly better than using them individually, indicating that these motif structures can complement each other when used together, thereby improving prediction accuracy. The prediction result using the combination of all motif structures is significantly better than using them individually, indicating that these motif structures can complement each other when used together, thereby improving prediction accuracy. Visualization of node embeddings After the model training was completed, we employed the t-SNE tool42 to project the high-dimensional embeddings onto a two-dimensional space and examined whether the node embeddings exhibited a discernible community distribution pattern. Prior to this, we used spectral clustering techniques to divide the social graph into eight independent clusters and labeled each node with the ID of its cluster. To enhance the visualization effect, we assigned a unique color to each cluster. Figure 11 shows the visualization results of four models on the Facebook dataset. Among them, the SimpleX model’s embedding points are relatively dispersed, demonstrating no clear clustering trend. This indicates that the SimpleX model’s ability to capture node similarity and social network structure is relatively weak, resulting in less distinct clustering effects in its embeddings. In contrast, the GAT and xGCN models exhibit more prominent performance in terms of clustering. They are capable of dividing the embedding points in the graph into multiple distinct clusters, with points in the same cluster (represented by the same color) gathering more closely together. However, even within the clustering results of GAT and xGCN, we observed some overlap of embedding points from different clusters (represented by different colors), indicating that these models still face certain limitations in distinguishing different clusters.Notably, by introducing the learning of high-order topological features, our MCoGCN model demonstrated significant advantages in clustering. As shown in Fig. 11d, the embedding points of MCoGCN formed more refined and distinct clusters. This confirms that high-order topological features can provide the model with richer information, aiding the model in more accurately capturing and representing complex relationships between nodes, thereby achieving more refined and accurate clustering. This further underscores the significance of high-order topological features in the analysis of social networks. Visualization of embeddings on the Facebook dataset. Conclusions In this paper, we propose a novel Graph Neural Network (GNN) model called MCoGCN, which addresses the issue of information loss caused by traditional GNN models that mostly consider only single-scale features of the network. This model enhances the accuracy and stability of link prediction tasks based on graph embedding methods, and it exhibits excellent encoding capabilities for weakly linked nodes. MCoGCN learns rich graph structure information through a chain-like execution of four processes: propagation, fusion, optimization, and refresh. We capture high-order topological features of the network through motif structures and fuse low-order and high-order embeddings through a simple, flexible attention mechanism. Our experiments on four social network datasets showcase MCoGCN’s effectiveness in link prediction, offering new insights for various research applications utilizing graph embedding techniques, such as recommendation systems, social network analysis, community division, etc. Future work will focus on mining more effective low-order structural features and more efficient high-order structures, and expanding the model to dynamic link prediction tasks and heterogeneous graphs to better satisfy the demands of social development. Acknowledgements This research was funded by the Natural Science Foundation of Chongqing Province of China, Grant No. CSTB2022NSCQ-MSX0786; the China Postdoctoral Science Foundation, Grant No. 2023M73335; Chongqing Municipal Commission of Education Science and Technology Research Project, Grant Nos. KJQN202201109, KJQN202301125. Author contributions N.X. provided research directions and was responsible for reviewing and overseeing the paper. N.X. and W.J.Y. were jointly responsible for the overall conception of the model, experimental design and implementation, as well as data organization. W.J.Y. extensively collected and organized relevant research, and bore primary responsibility for editing the paper, while also being responsible for experimental result analysis and visualization. X.D.R. participated in discussions regarding model feasibility analysis and experimental design, assisting in data organization, analysis, and paper editing. All three authors jointly participated in the revision and improvement of the paper, ensuring that all viewpoints and data were rigorously verified. Data availability The data underlying this article are available in SNAP, at http://snap.stanford.edu/data. Declarations Competing interests The authors declare no competing interests. Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References Associated Data Data Availability Statement The data underlying this article are available in SNAP, at http://snap.stanford.edu/data.