Community Discovery Algorithm Based on Multi-Relationship Embedding

1  Introduction

The analysis of multilayer networks is crucial in the research of complex networks. Network structures that are modeled based on real-world complex systems can usually be represented using multilayer networks, i.e., the interaction processes between node entities in a network structure can be described as many different types of relationships, and the interaction processes of these different relationship types can be represented using multilayer networks that represent each of these network layers as one interaction type. These different interaction types constitute a multilayer network that can more accurately describe complex systems in the real world. Multipath networks [1], multilevel networks [2], interdependent networks [3], and multidimensional networks [4] can usually be considered multilayer networks [5].

The information mining for multilayer networks is based on the research of single-layer networks, and the information mining for multilayer networks can further mine the implicit information in multilayer networks by fully considering the complex relationships between different network layers. The communities in the multi-layer networks consist of a set of strong connections of nodes in the layer. Community structures appear frequently in many real-world complex systems, such as sociological, biological, and transportation systems [6]. The community discovery algorithms in multilayer network information mining tasks can identify the community structure in the multi-layer network and thus determine the set of strong connection nodes. Although nodes with different relationship types can form various single-layer networks independently, there are usually correlations among these single-layer networks. In citation networks, references vary from paper to paper, but researchers can usually infer the research topic of a paper by analyzing the published topics of the paper’s authors, thus allowing the prediction of the paper’s topic. Furthermore, the nodes in the network can also contain some attribute information, which plays a key role in many domains. For example, the abstract information of a paper in a citation network can help infer the topic of the paper. Therefore, network representation learning should consider not only the structural information of nodes but also the attribute information of nodes.

Recently, most such studies have been based on homogeneous networks, using network models with a single relationship between nodes and achieving certain results, but ignoring the information implied in the network structure [7]. Furthermore, existing researches seldom discuss the attribute embedding of nodes and generally has weak global feature modeling capabilities. The fact that networks exist in the real world is inherently multiple, i.e., nodes have multiple types of relationships. In the citation network, papers have multiple types of relationships with each other, including authorship relationships between papers and citation relationships between papers. In movie networks, different movies have the same director or use the same actors, thus creating connections between different movies. At present, the research for multilayer network representation learning usually focuses on the fusion of network layers without considering the nodes’ attribute features themselves. The use of label information of nodes also poses a challenge in terms of algorithmic complexity. Furthermore, traditional community discovery methods in topology-based multilayer network analysis require complete alignment of nodes between layers, and the complexity of the algorithms is usually high.

In this paper, we propose the Community Discovery Algorithm Based on Multi-relationship Embedding (CDBMRE). This paper uses a network representation learning method based on a Graph Convolutional Network (GCN) to solve the problem of community discovery in multilayer networks. The network representation learning method can obtain low-dimensional vector representations of nodes from the network, preserving their node attribute feature information while preserving the node structure information in the network. First, the nodes in the network are modeled to obtain the embedding matrix h(r) of the nodes. Then, the encoder gr generates the node embedding matrix H(r) for each specific relation type in the network G(r) . Finally, the node embedding matrix H(r) for each specific relation type is integrated using GCN to obtain multiple nodes embedding matrices S(r) for specific relation types. Experimental results on real-world network datasets show that the proposed algorithm has a high accuracy of community discovery.

Overall, the main contributions of the proposed algorithm are as follows.

1)   The proposed algorithm overcomes the limitations of single-layer networks and fuses the attribute information of nodes into the learning process of network embedding.

2)   The proposed algorithm enables the creation of specific embedding matrices for nodes and node relationship types and aggregates the node embedding matrix for each specific relationship type with GCN. This strategy allows capturing of rich structural and attributes information in multi-relational networks.

3)   The proposed algorithm obtains significant performance improvement in community discovery, node clustering, and similarity search tasks, which proves the effectiveness of the proposed algorithm.

2  Related Work

Community detection is one of the most active topics in the field of graph mining and network science [8], where the community structure can represent the implicit structure in the network [9]. Community discovery algorithms can find the most reasonable division of communities in a network by the observed topology, thus providing support for researchers to analyze the network topology. Traditional community discovery algorithms based on network topology analysis include Girvan-Newman (GN) algorithm [10], Fast-Newman (FN) algorithm [11], Louvain algorithm [12], etc.

The random walk-based network representation learning method [13] and the graph convolutional network-based network representation learning method [14] are both able to learn node embeddings in the network by aggregating the neighborhood features of nodes, and by extracting the structural information of the network and mapping the nodes in the network to a low-dimensional continuous space while maintaining the structural features of the network and the node attribute information, to achieve community discovery using node embeddings. Information Fusion in Multilayer Network Embedding (IFMNE) [15] is a method of random walk of multiple information, this method learns node information and multi-type relational information into a unified space, and combines node structure information with network topology information. The accuracy of this method has significant advantages for the link prediction task on multilayer networks. Peng et al. [16] propose a reinforced neighborhood selection-guided multi-relational graph neural network architecture that is capable of guiding the creation of multi-relational graphs with a reinforcement learning method and maintaining relational dependencies in the learning process. The method enables the learning of more discriminative node embeddings with enhanced interpretability. Furthermore, Nie et al. [17] have summarized several solutions to graph structure data mining with reinforcement learning methods. The method proposed by Pourhabibi et al. [18] can capture the position of a given node in a set of neighboring anchor sets and the type of connections between nodes in the anchor sets to learn the structural representation of nodes and relations simultaneously. The method has better community discovery performance on a terrorist dataset and a synthetic network. Analyzing and mining useful knowledge in networks has always been studied by researchers, an approach to learning network embeddings of low-dimensional vector representations of nodes in networks can effectively solve various network tasks among various network mining techniques.

3  Preliminaries

Network representation learning: The network representation learning methods aim to learn a low-dimensional vector representation of the nodes in the graph while preserving the structure of the network as well as various other properties, such as information about the attributes of the nodes, structural roles, and labeling of the nodes. Given an attribute network G=(V, E, X) and a set of adjacency matrices A, the task of network embedding is to learn a d-dimensional vector representation zi∈Z∈Rn×d for each node vi∈V without using any labels of the nodes.

Multi-relational networks: Multi-relational networks are networks G|r|=(V, E, X) , where Gr=(V, E(r), X) represents a graph with relation type r∈R , node v is the set of n nodes, E=Ur∈RE(r)⊆v×v is the set of all edges of relation type r∈R . X∈Rn×f is a matrix encoding the node attribute information of n nodes. |R|>1 indicates a multilayer network. |R|=1 indicates a single-layer network. For a given network G, A=(A(1), A(2), …, A(|r|) is a set of adjacency matrices, where A(r)∈{0, 1}|V|×|V| is the adjacency matrix of network G.

4  Methodology

Network representation learning is a method of converting a high-dimensional density matrix into a low-dimensional dense vector. Using the method of network representation learning can reduce the dimensionality of the structural information in the network while preserving the structural information of the nodes in the network. The CDBMRE algorithm proposed in this paper combines multiple types of relationship embeddings between nodes in the network and considers multiple relationship types between node attributes along with network structure information. The overall framework of the CDBMRE algorithm is shown in Fig. 1.

Figure 1: The framework of the CDBMRE algorithm

The algorithm proposed uses GCN to capture the potential network structure information and attribute information in multilayer networks, where GCN considers the information of higher-order neighbor nodes in the network when learning the embedding representation, and the network sparsity problem is solved by using the GCN method to obtain the structure information and node attribute information in multilayer networks. The convolution method of GCN is shown in Eq. (1).

H(l+1)=f(H(l), A|W(l)) (1)

where H(l) is the input of layer l and H(l+1) is the output of layer l. The network G is with n nodes, each node has its features, and the features of these nodes form the n×d -dimensional matrix X. The relationship between each node also forms the n×n -dimensional adjacency matrix A. GCN is a neural network layer, and the propagation between different layers is shown in Eq. (2).

H(l+1)=σ(D^−12A^D^−12H(l)W(l)) (2)

where A^=A+I and I is a unit matrix.

The real-world networks usually contain topological structure information and attribute information of the nodes. In this paper, the node attribute information of nodes is used in the representation of the relationship types of learning nodes to obtain the node embedding matrix h(r) for each node relationship type r∈R . Specifically, this paper defines the interaction between different types of nodes based on the idea of meta-paths, using a meta-path [19] obtained from the modeling of the network containing the node relationship types processes.

The meta-path is defined on the network as TG=(A, R) , i.e., {AR11, AR22, …, ARll, A(l+1)} , that is, between node types A1, A(l+1) defines a combinatorial relation R={R1⋅R2⋅…⋅Rl} , where {⋅} represents the combinatorial operation between relations. For example, there are six types of movie information network: User, Group, Movie, Director, Actor, and Type. The director can be connected by the meta-path “Movie-Director-Movie (M-D-M)”, and also by the meta-path “Actor-Movie-Director-Movie-Actor (A-M-D-M-A)”. The different meta-paths have different meanings: M-D-M means that the director directed two movies with similar styles, while A-M-D-M-A means that different actors acted in the same movie directed by the same director. In addition, in the citation network, the relationship type between Author (A) and Paper (P) can be expressed as P-A-P, and the P-A-P relationship can be that the same author published two papers. The embedding matrix for a specific node relationship type is shown schematically in Fig. 2.

Figure 2: Node embedding matrix h(r)

The algorithm proposed in this paper first models the nodes and obtains the node embedding matrix for each node in the network. Then a node encoder gr:Rn×f→Rn×n→Rn×d is introduced for a node-specific relationship type, and the purpose of using the node encoder gr will be to obtain the node embedding matrix h(r) for each node. The node embedding matrix H(r) is generated for each specific relation type in a network G by using the node encoder gr . The computational procedure for generating the node embedding matrix for each specific relationship type using the node encoder gr is shown in Fig. 3.

Figure 3: Embedding matrix H(r)

The node embedding matrix H(r) for each specific relation type is taken as input and the node embedding matrix for multiple specific relation types is integrated by using the method of GCN with s(r) as output, where GCN is calculated by integrating the node embedding matrix H(r) for each specific relation type by Eq. (3).

H(r)=gr(X, A(r)|W(r))=σ(D^r−12A^(r)D^r−12XW(r)) (3)

where A^(r)=A(r)+wIn , D^ii=∑j⁡A^ii . W(r)∈Rf×d is the trainable weight matrix of decoder gr for each node-specific relation type, σ is a nonlinear activation function. In A^(r)=A(r)+wIn , the weights ω∈R are introduced to control the weights of the connected edges between nodes, and when the weights ω are larger, it indicates that the nodes themselves play a more important role in generating their embeddings in the network, but this reduces the importance of the nodes with their neighboring nodes.

In this paper, we use s(r) to represent the network G(r) using GCN to integrate the node embedding matrix H(r) for each specific relationship type after obtaining the embedding matrix for multiple specific relationship types between nodes using a readout function Readout: Rn×d→Rd is represented as s(r) .

s(r)=Readout(H(r))=σ(1n∑i=1n⁡hi(r)) (4)

where σ is a nonlinear activation function and hi(r) denotes the i -th row vector of the matrix H(r) . The cross-entropy of node-specific relationship types is calculated based on the node-embedding matrix H(r) and s(r) for a given node-specific relationship type.

ℒ(r)=∑vi∈vn⁡log⁡D(hi(r), s(r))+∑j=1n⁡log⁡(1−D(h~i(r), s(r))) (5)

In this paper, when using GCN for community discovery tasks, we found that the inability to discern the importance of nodes among the many neighbors of the target node led to a large amount of noisy data. For example, in the citation network, the relationship type between the author and the paper is P-A-P, while the relationship type between the paper and subject (S) is P-S-P. Although these two relationship types are similar and both have the attribute paper, P-A-P and P-S-P belong to two completely different node relationship types. To distinguish such relationship types which are similar but different in reality, this paper uses the method of attention mechanism to distinguish these different kinds of types of node-specific relationship types, and uses ai(r) to denote the importance of relationship type r in generating the final vector representation of node vi .

Finally, the node embedding matrix h(r) of the node relation type r∈R in the network is obtained, and the node embedding matrix H(r) of each specific relation type in the network G(r) is generated using the node encoder gr . s(r) indicates that the network G(r) uses GCN to integrate the node embedding matrix H(r) of each node embedding matrix H(r) of a specific relation type using GCN to obtain the node embedding matrix H(r) of a specific relation type with global information in the network G(r) . However, each matrix H(r) is trained independently for each r∈R . Therefore, these node embedding matrices H(r) contain only relevant attribute information about each relationship type and do not take advantage of the multilayer nature of the network. To address this one problem, this paper improves the quality of embeddings by jointly integrating embeddings from different relationship types using a consensus embedding matrix Z∈Rn×d on which the consensus matrix allows the node embedding matrix H(r) for each specific relationship type to agree. Specifically, this paper uses a consensus regularization framework, which consists of a regularizer that minimizes the divergence between the original set of node embeddings, i.e., {H~(r)|r∈R} , and a consensus embedding matrix, and another regularizer that maximally damages the divergence between node embeddings, {H(r)|r∈R} , which can be expressed as Eq. (6).

lcs=[Z−Q(H(r)|r∈R)]2−[Z−Q(H(r)|r∈R)]2 (6)

where Q is an aggregation function that combines a set of node-embedding matrices H(r) of a particular relationship type from multiple relationship types into a single matrix H, i.e., H∈Rn×d . Q is a pooling method that can handle any permutation-invariant input. The loss function is shown in Eq. (7).

ℑ=∑r∈R⁡ℒ(r)+αlcs+β||Θ||2 (7)

The pseudo-code of the proposed algorithm is shown in Algorithm 1.

The algorithm proposed in this paper first models the nodes in the network to obtain the node embedding matrix h(r) for each node relationship type r∈R . Based on the idea of meta-path, the node embedding matrix H(r) for each specific relationship type in the network G(r) is generated by the node encoder gr . Embedding matrix H(r) as input, and using GCN to integrate the node embedding matrix H(r) of each specific relation type to get multiple node embedding matrices s(r) of specific relation types to learn the low-dimensional vector representation of nodes in the network.

5  Experiments

Graph structured data mining methods can be applied in several real applications. In this paper, we use the aforementioned Association for Computing Machinery (ACM)1, Internet Movie Database (IMDB)2, and Digital Bibliography & Library Project (DBLP)3 datasets on the community discovery task, and use Macro-F1 [20] and Micro-F1 [20] as evaluation metrics for the experiments, the values of Macro-F1 and Micro-F1 provide the worst value when they are close to 0 and the best value when they are close to 1. The Deepwalk algorithm [21], Node2vec algorithm [13], Deep Graph Infomax (DGI) algorithm [22], and Multiplex Network Embedding (MNE) algorithm [23] are used as the comparison experimental algorithms. Deepwalk and Node2vec are popular graph embedding methods and are considered as baselines in many graph embedding methods. DGI and MNE are the latest multi-relational embedding methods and have better performance and efficiency. Our experiments include (1) Community Discovery and (2) Node Clustering and Similarity Search.

5.1 Datasets

In this paper, we conduct experiments on three multi-relational networks, and the details of the datasets used are shown in Table 1, where Relations (A-B) is the relationship between node A and node B. Num.A is the number of node A, Num.B is the number of node B, Num.A-B is the number of connected edges between node A and node B, and Relation type is the node-specific relationship type.

• DBLP: this is an integrated database system of computer-based English literature in the field of computing for the results of research with authors as the core, including published papers in international journals and conferences, etc.

• ACM: this dataset uses papers published in the International Conference on Knowledge Discovery and Data Mining (KDD), the International Conference on Special Interest Group on Management of Data (SIGMOD), the International Conference on Special Interest Group on Data Communication (SIG-COMM), the International Conference on Mobile Computing and Networking (MobiCOMM), and the International Conference on Very Large Data Bases (VLDB), and classifies papers into three categories (database, wireless communication, and data mining). It includes 3025 papers (P), 5835 authors (A), and 56 subjects (S).

• IMDB: the movies in this dataset are divided into three categories (action, comedy, drama) according to their genres, which contains 3550 movies (M), 4441 actors (A), and 1726 directors (D).

5.2 Experimental Results

5.2.1 Community Discovery

According to Table 2, it can be found that the experimental results of the CDBMRE algorithm are better than those of the comparison algorithms on all three data sets, and the values of Macro-F1 and Micro-F1 reach the optimal results. Compared to the DGI algorithm, the CDBMRE algorithm has a smaller improvement in the case of using Macro-F1 and Micro-F1 as evaluation metrics for the experimental results.

In the ACM dataset, the CDBMRE algorithm improves 1.9% in the Macro-F1 value and 1.6% in the Micro-F1 value over the DGI algorithm; in the IMDB dataset the CDBMRE algorithm improves 0.75% in the Micro-F1 value over the DGI algorithm. This is because the DGI algorithm relies on maximizing local mutual information, which aims to capture the local node characteristics of the global information of the network, while the CDBMRE algorithm proposed in this paper, firstly, obtains node-specific relationship type embeddings, and secondly, integrates multiple types of relationship embeddings between nodes in the network using encoders as well as network representation learning GCN, which considers the network structure information while also Multiple types of relationships between node attributes are considered, so the experimental results of the CDBMRE algorithm on the dataset are slightly better than the DGI algorithm.

Both the Deepwalk algorithm and Node2vec algorithm use the random walk to generate node sequences and use Skip-gram to learn node embeddings, however, they do not utilize the attribute information of the nodes in the network. Therefore, the Deepwalk and Node2vec algorithms are less effective in the experiments on the three datasets, with lower values of Macro-F1 and Micro-F1 than the CDBMRE algorithm. The MNE algorithm jointly models multiple networks by introducing a common embedding and additional embeddings for each node relationship type and does not utilize the attribute information of the nodes in the three datasets. experiments, its Macro-F1 and Micro-F1 values are lower than the algorithm proposed in this paper.

5.2.2 Node Clustering and Similarity Search

In this paper, we also design implementations to evaluate the performance of the CDBMRE algorithm based on node clustering and similarity search. In the node clustering task, the Normalized Mutual Information (NMI) [24] is used as an evaluation metric; in the node similarity search task, the cosine similarity score of the node embedding between all node pairs is calculated, and for each node, the nodes are ranked according to the similarity score, and the percentage of the top 5 nodes (Sim@5) that belong to the same class is calculated.

Experiments are done on the four comparison algorithms, Deepwalk, Node2vec, DGI, MNE, and the CDBMRE algorithm proposed in this paper on ACM, IMDB, and DBLP datasets. The algorithms proposed in this paper outperform the comparison algorithms in two evaluation metrics, NMI and Sim@5. The experimental results on the ACM, IMDB, and DBLP datasets are shown in Figs. 4–6.

Figure 4: Experimental results on ACM

Figure 5: Experimental results on IMDB

Figure 6: Experimental results on DBLP

CDBMRE algorithm experiments on three datasets show that the values of NMI and Sim@5 are higher than those of the DGI algorithm. In the IMDB dataset, the NMI values obtained by the CDBMRE algorithm improved by 2.7% compared to the DGI algorithm, and in the DBLP dataset, it improved by 2%. The CDBMRE algorithm showed an excellent improvement in the NMI and Sim@5 values in all three datasets compared to the Deepwalk algorithm, the Node2vec algorithm, and the MNE algorithm. The effectiveness of the CDBMRE algorithm is demonstrated.

Overall, the experimental results on ACM, IMDB, and DBLP datasets show that the CDBMRE algorithm has the best performance. The use of the network representation learning method can learn the low-dimensional vector representation of the nodes in the network, which preserves the node structure information in the network while also retaining the node attribute information, proving that the CDBMRE algorithm proposed in this chapter is effective.

6  Conclusion

Community discovery algorithms in multi-layer networks are an important direction in the research of complex networks. Community discovery algorithms based on multi-relational interaction information can mine the implicit structure and information of networks based on the interaction information between different types of nodes in multi-layer networks, and help researchers to further understand the formation process and community structure of networks. In reality, there are rich types of relationships between network nodes, and the nodes in the network not only have structural features, but also nodes have attribute information. To learn the consensus representation of a node, not only the structural information of the node, but also the attribute information of the node should be considered. In this paper, we use a network representation learning approach to solve the problem of community discovery in multilayer networks. There are multiple types of relationships between nodes in the network, and the nodes in the network are modeled to obtain node embeddings for each specific relationship type. This paper uses the GCN approach to integrate multiple types of relationship embeddings between nodes in the network. By experimenting with the comparison algorithms on three real network datasets, the results show that the CDBMRE algorithm obtains better node embedding representations and achieves an average improvement of 3.1% on Macro-F1 and 4.7% on Micro-F1.

Funding Statement: This work was supported by the Key Technologies Research and Development Program of Liaoning Province in China under Grant 2021JH1/10400079 and the Fundamental Research Funds for the Central Universities under Grant 2217002.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

1https://www.biendata.xyz/hgb/#/datasets.

2https://www.kaggle.com/datasets/karrrimba/movie-metadatacsv.

3http://web.cs.ucla.edu/~yzsun/data/.