Multivariate Relations Aggregation Learning in Social Networks

The emergence of the Internet and the development of related technologies have not only increased information but also changed the nature of traditional libraries and information services. The Digital Library (DL) has become an important part of the modern digital information system. In a narrow sense, the digital library refers to a library that uses digital technology to process and store various documents; in a broad sense, it is a large-scale, knowledge-free knowledge center that can implement multiple information search and processing functions without time and space restrictions. Academic data sets and online academic literature search platforms, such as IEEE / IEE Electronic Library, Wiley Online Library, Springer LINK, Google Academic Search, etc., can be regarded as representative modern digital libraries.

The knowledge information of digital libraries often need to sort and repair. Due to the large number of documents or the loss of knowledge information, manual repair is often inefficient and inaccurate. To this end, based on existing knowledge information, such as the author of the document, keywords, citation data and other information, efficient and automated realization of knowledge or document classification and missing information prediction has become one of the important topics in the field of digital library research. In the process of solving this research topic, machine learning technology play an important role. Wu et al. (Wu et al., 2015) have developed CiteSeerX, a digital library search engine, over 5-6 years. They combined traditional machine learning, metadata and other technologies to achieve document classification and deduplication, document and citation clustering, and automatic metadata extraction. Vorgia et al.  (Vorgia et al., 2017) used many traditional machine learning methods, including 14 classifiers such as Naive Bayes, SVM, Random Forest, etc., to classify documents based on literature abstracts, and achieved good classification results on their datasets. However, the existing method requires a large number of training samples, to obtain a better model through a long iterative learning process. Meanwhile, because it is based on traditional scatter tables or binary relations, it does not take into account the multivariate relations between knowledge or literature, which limits the further optimization of its task accuracy.

Classification task is one of the most classic application scenarios in the field of machine learning. Many researchers have studied “how to classify data” and have created a variety of classification algorithms. Among these algorithms, the logistic regression (LR) algorithm and the support vector machine (SVM) algorithm (Singh et al., 2016) are the most famous. These algorithms are usually based on mathematical knowledge and optimization theory, and they are simple to implement. By repeatedly performing gradient descent on a unit, the algorithm can obtain very effective classification results (Kurt et al., 2008; Caigny et al., 2018). However, these algorithms have huge flaws: They only consider the attributes of the nodes during the iteration process, and cannot consider the dependencies between the data. In the network data with rich relationships between data nodes, the classification accuracy of such algorithms is not high, and their training efficiency is usually low.

Over time, networks have become the focus of researchers’ attention. Machine learning in complex graphs or networks is becoming the focus of research by artificial intelligence scientists. Because traditional machine learning methods cannot effectively combine the related information in the network environment, to improve the efficiency and accuracy of tasks, graph learning algorithms have been proposed to solve graph-related problems. Meanwhile, the great success of the recurrent neural network (RNN) (Chung et al., 2014) and the convolutional neural network (CNN) (Krizhevsky et al., 2012) in the field of natural language (Vu et al., 2016; Kumar et al., 2016; Goldberg, 2017) and computer vision (Zhang et al., 2017; Hershey et al., 2017; Xiong et al., 2019) have provided new ideas and reference objects for graph learning methods. As a result, graph recurrent neural networks (GRNN) and graph convolutional neural networks (GCNN) have become mainstream methods.

Graph Recurrent Neural Network (GRNN). The graph neural network algorithm suitable for graph structure is first proposed by Gori et al. (Gori et al., 2005), aiming at improving the traditional neural network (NN) algorithm. Gori et al. use the recursive method to continuously propagate neighbor node information until the node state is stable. This neighborhood information propagation mechanism has become the basis for many subsequent graph learning algorithms. Later, Scarselli et al. (Scarselli et al., 2009) ameliorated this method. The new algorithm combines the ideas of RNN and applies to many types of graph structures, including directed and undirected graphs, cyclic graphs and acyclic graphs. Li et al. (Li et al., 2016) combined it with the Gated Recurrent Unit (GRU) theory (Cho et al., 2014). The resulting Gated Graph Neural Network (GGNN) reduced the number of iterations required, thereby improving the overall efficiency of the learning process. However, on the whole, the GRNN algorithm still costs a lot: From the space perspective, this overhead is reflected in the huge parameter and the intermediate state nodes that need to be stored. From the time perspective, these algorithms require a large number of iterations and long training time.

Graph Convolutional Neural Network (GCNN). Different methods for defining convolution have created various graph convolutional neural network models. Bruna et al. (Bruna et al., 2014) combined spectral graph theory with graph learning methods. They used the graph Fourier transform and Convolution theorem in the field of graph signal processing (GSP) (Sandryhaila and Moura, 2013; Perraudin and Vandergheynst, 2017; Ortega et al., 2018), to obtain the graph convolution formula. Defferrard et al. (Defferrard et al., 2016) made further improvements on their basis. By cleverly designing convolution kernels and combining Chebyshev polynomials, this algorithm has fewer parameters and can effectively aggregate local features in the graph structure. The GCN model proposed by Kipf et al. (Kipf and Welling, 2017) is the master of this direction. By approximating the Chebyshev polynomial of the first order, their method is more stable while avoiding overfitting. Seo et al. (Seo et al., 2018) combined the long short-term memory (LSTM) mechanism (Sak et al., 2014) in RNN, and proposed the GCRN model that can be applied to dynamic networks. On the other hand, Micheli (Micheli, 2009) proposed to directly use the neighborhood information aggregation mechanism to implement the graph convolution operation. Gilmer et al. (Gilmer et al., 2017) integrated this theory and proposed a general framework for this kind of GCNN. Hamilton et al. (Hamilton et al., 2017) used the sampling method to unify the number of neighbor nodes and established the well-known GraphSage algorithm. Velickovic et al. (Velickovic et al., 2018) combined the attention mechanism (Chorowski et al., 2015) with GCNN and proposed the graph attention network (GAT) model. These two ideas have their advantages, but they are still limited to neighborhood information. This will lead to partial omission or even complete loss of the rich multivariate relationship information in the network.

The network motif firstly refers to a part that has a specific function or a specific structure in a biological macromolecule. For example, a combination of amino acids that characterize a particular function in a protein macromolecule can be called as a motif. Milo et al. (Milo et al., 2002) extended this concept to the field of network science in 2002. Their research team discovered a frequent subgraph structure while studying gene transcription networks. In subsequent research work, they found some special subgraphs with similar characteristics but different structures in many natural networks. Milo et al. summarized the relevant results and proposed a new network subgraph concept called the network motif.

Unlike network graphlets and communities, the network motif is a special type of subgraph structure in the network, which has a stronger practical scene and significance. By definition, the network motif is a kind of connected induced subgraphs, which have the following three characteristics:

(1) Network motifs have stronger practical meaning. Similar to the concept of motifs in biology, network motifs also have some specific practical significances. This practical meaning is determined by the certain structure of the network motif, the type and the characteristic of the network. For example, a typical three-order triangle motif can represent a three-person friendship in a general social network. Therefore, the number of such network motifs can be effectively used to study the correctness of the ternary closure principle in social networks.

(2) Network motifs appear more frequently in real world networks. This phenomenon is caused by the structural characteristics of the network motif and its practical significance. In a real network and a random network with the same number of nodes and edges, the network motif appears much more frequently in the former than the latter. In some real sparse networks, such as transportation networks, some complex network motifs may still occur frequently. But they cannot be found in the corresponding random networks.

(3) Network motifs are mostly low-order structures. Network motifs can be regarded as a special kind of low-order subgraph structure. In general, the number of nodes that make up a network motif will not exceed eight. Scholars refer to a network motif consisting of three or four nodes as a low-order network motif, and a network motif composed of five or more nodes is called a high-order network motif. High-order network motifs are numerous, complex, and are often used in the super-large-scale network. Applying it to the analysis of a general network requires a lot of time to perform preprocessing, and it is difficult to obtain better experimental results than using low-order motifs. That is, the input time cost and the output experimental effect often fail to balance. Therefore, in this paper, we mainly use low-order network motifs composed of three or four nodes for network analysis.

At present, the research scope of network motif researchers has expanded from the biochemical network, gene network, and biological neural network to social networks, academic collaboration networks, transportation networks, etc. In these networks, they found a large number of network motifs with different structural characteristics. In this sense, the network motif can reveal the basic structure of most network structures and play an important role in the specific application functions of the network. In Table 2, we list various network motifs used in this paper. Among them, $\bm{\bar{d}}$ denotes the average degree, $\bm{\max{(d)}}$ denotes the maximum degree, $\bm{D}$ denotes the diameter, $\bm{\rho}$ denotes the density, and $\bm{|T|}$ denotes the number of triangles contained in the network motif.

Relationships are the foundation of network building. In the network dataset, the edge between two nodes actually reflects a kind of binary relationship, that is, there is a relationship between the two data entities. This low-order relationship is simple, direct, and easy to characterize. However, because it only considers the association between two data, low-order relationships often lose high-order information within many datasets. To this end, researchers have extended the binary relationship into the multivariate relationship, and analyzed the multivariate relationship to mine patterns, features and implicit associations in the network, to obtain more accurate and valuable conclusions.

Multivariate relationships are common in actual networks, and the network motif can effectively characterize them because of their definitions and properties. As shown in Figure 2, in a social network, besides the direct relationship connect one user to another, the ternary closure relationship between three users is a common phenomenon existing in the social environment. This relationship can be regarded as a fully-connected small group, and fully-connected network motifs, such as M31 and M41 (in Table 2), can effectively characterize this multivariate relationship in the social network. This kind of network motifs can also be used to characterize the ubiquitous coauthor team consisting of three or four scholars in the academic network. In transportation networks, such as urban road networks, there are a large number of block-like structures in the network, due to the constraints of realistic conditions such as traffic planning and geographical factors. This multivariate relationship between intersections can be effectively characterized by M43.

In this paper, we utilize the concept of Node Motif Degree (NMD) to characterize the association of a particular multivariate relationship at a node, and its definition is as follows.

As shown in the Figure 4, the number of the nodes represents the node motif degree information of the triangle motif (M31). Through these graph features, we can better connect the single node, the network motif and the multivariate relationship in the network structure.

In this part, we will introduce the MORE model proposed in this article, which is simple and easy to implement. This model can effectively catch the multivariate relationship information in the network. While improving the accuracy of graph learning tasks, MORE greatly speeds up the convergence and reduces the time cost in the learning process.

The framework structure of the entire MORE model is shown in Figure 3. The overall model contains two parts, one is the graph feature information calculation, and the other is the learning and classification process. The attribute feature tensor and structure feature tensor output by the first part will be used as the input of the second part. It is worth noting that in the above figure, due to space constraints, we have not fully expanded the content of the aggregated part (the red dotted box in the figure). The content of the method in this part will be explained in Figure 5.

For the input network dataset, we first extract the characteristic information of its nodes. MORE algorithm considers the attribute features and structural features of the node. The algorithm directly extracts the attribute information of each node in the graph structure, and integrates it into the node Attribute Feature Tensor (AFT) of the total graph. Moreover, to better characterize the structural association and multivariate relationship information, the algorithm calculates five kinds of node motif degree information of each node in the network, including the node motif degree of M31, M32, M41, M42 and M43. This information will be integrated with the original degree of the node, and then the node Structural Feature Tensor (SFT) will be obtained.

Because the two feature tensors obtained in the above process often have large scale differences, and the direct connection two tensors will easily destroy the internal correlation of the feature itself, we consider using a graph representation learning model to reduce or expand the dimension of original tensors. By transform its node feature representation method, we can make the two have the same dimensional information. In this paper, this model uses the GCN model, which uses a graph convolutional network to implement the network embedding process. The GCN model is an effective model to deal with graph-related problems. The core of GCN uses a graph convolution operation based on spectral graph theory, and its formula is expressed as follows:

Wherein, $x$ represents the graph feature vector, $\theta$ represents the weight parameter vector, and $\times_{G}$ represents the graph convolution operation. To improve the stability of the algorithm and avoid gradient explosion or disappearance during the learning process, GCN replaced $I_{n}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ in the above formula with $\widetilde{A}=\bar{D}^{-\frac{1}{2}}\bar{A}\bar{D}^{-\frac{1}{2}}$. Wherein, $\bar{A}=I_{n}+A$ and $\bar{D}_{ii}=\sum_{j}\bar{A}_{ij}$. Through this methodmodel, we transform the original AFT and SFT into their respective embedding tensors, namely the Attribute Feature Embedding Tensor (AFET) and the Structure Feature Embedding Tensor (SFET).

In order to aggregate the AFET and SFET, get the Aggregated Embedding Tensor (AET), and apply it to practical tasks, MORE proposed three multivariate relationship aggregation methods, as shown in Figure 5. The Hadamard Aggregation (HA) method, or dot multiplication aggregation method, gets AET by performing dot multiplication of two embedding tensors; The Summation Aggregation (SA) method gets AET by adding two embedding tensors. These two aggregation methods will not change the size of the aggregation tensor, consume less time for the iterative process, and will not greatly affect the internal correlation information of the features. The Connection Aggregation (CA) method gets AET by connecting two embedding tensors. Although this method will double the size of the aggregation tensor, and the iterative process requires a higher time cost, it can completely retain all the feature information in the total network dataset. In this paper, we use MORE-HA, MORE-SU, and MORE-CO, to represent the MORE algorithm using three aggregation methods (HA, SA and CA) in the aggregation processing of AFET and SFET, respectively.

Finally, the MORE model is used for node classification tasks to measure and express the performance of our algorithm in real network environments. We have considered inputting AET into a graph learning model again for iterative training. However, it was found through experiments that, when the GCN model was applied, the previous iterative process was sufficient to meet the needs of the processing task. If we add more graph learning models, it will cause severe overfitting. To this end, the algorithm directly adds a Softmax layer at the end to generate the one-hot vector required for node classification.

The above is an iterative process of the MORE model. This process can be expressed by the following formula.

Among them, $GCN(\cdot)$ represents the single GCN iteration process, and $Aggre(\cdot)$ represents the aggregation process, which is selected from three methods. $SM(\cdot)$ represents the Softmax function, which is defined as $SM(x_{i})=\exp{(x_{i})}/\sum_{i}\exp{(x_{i})}$. Next, we use the cross-entropy error as the loss function of the model in the node classification task, and continuously adjust the values of the relevant weight parameters through the gradient descent algorithm. The specific error function of one data $\mathcal{L}_{i}$ can be described by the following formula.

Wherein, $Y$ represents the true node classification label of the network data set, and $\hat{Y}$ represents the node classification label predicted by the model.

We selected 6 different datasets to conduct experiments to reflect the characteristics and advantages of our model. The basic information of these data sets is shown in Table 3. The information of each dataset is divided into three parts: the first part is the basic information, the second part is the structure information, and the third part is the network motif information. In this tabel, #Node represents the number of nodes in the dataset network, #Edge represents the number of edges, #Feature represents the feature number of each node, and #Label represents the type number of node labels in the total network. ‘-’ in #Feature means that the dataset is missing node feature data. In addition to the above basic network information, we have additionally listed the average degree $\bm{\bar{d}}$, the maximum degree $\bm{\max{(d)}}$, the network density $\bm{\rho}$, and the overall clustering coefficient Clustering of the network. These statistical indicators will effectively characterize the density of associations between data and the connection status of the network.

Because our model needs to consider the number of motifs in the network, and use this to characterize the multivariate relationships and high-order structural features in the dataset, we need to count several representative network motifs and get the motif node degree information of each node in the network. The number of network motifs we used in each network dataset is also shown in Table 3. #M31 represents the number of triangle motif, and #M32 represents the number of three-order path motif in the network. #M41, #M42 and #M43 respectively represent the number of three kinds of four-order motif mentioned in this paper.

Because the comparison of the running time is needed in this experiment, we provide information for the computer’s operating environment and hardware configuration. We use a Hewlett-Packard PC, ENVY-13: The operating system is Windows 10 64-bit, the CPU is Intel i5-8265U, and the memory is 8G. We use Python 3.7.3 and Tensorflow 1.14.0 for coding, and use Visual Studio Code for programming.

During the training process, we divide the original dataset into a training set, a validation set, and a test set. If the number of nodes in the dataset is between 1150 and 3000, we randomly select 150 data as the training set (TRS) and 500 data as the verification set (VAS), and finally test the model effect on a test set (TES) consisting of 500 data. For the Email-Eucore, Facebook, and Football, we construct three sets at similar proportions. Besides, since the attribute information of the nodes is used in the iteration, we use a method that assigns a one-hot vector to each node randomly for the network without features. This method is simple, easy to implement, and almost does not affect overall mission performance.

The choice of hyperparameters is also worth considering because they directly affect the final experimental results. In this experiment, if there is no special statement, we optimize the model using Adam with the learning rate $\bm{\alpha}$ of 0.01, and the maximum training iterations number max_epoch of 300. This experiment uses two regularization methods: random inactivation and L2 regularization. The probability of random inactivation drop_out is 0.5, and the L2 regularization factor $\bm{\lambda}$ is 0.0005. To avoid the occurrence of overfitting, the early stopping method is adopted, and the tolerance is 30 (If the loss of the validation set does not decrease during 30 consecutive iterations, the algorithm will automatically stop). Also, the embedding dimension ED is an important attribute, which directly determines the capacity of the model space. In this experiment, the graph representation learning model use one layer of GCN structure. AFT and SFT are embedded in 32, 64, 128, 256, and 512 dimensions, respectively, and the best performance is selected as the final experimental result.

We compare the MORE model with the GCN model proposed by Kipf et al (Kipf and Welling, 2017). As a well-known algorithm in the field of graph convolutional networks, GCN is based on spectral graph theory and has been recognized by many researchers in this field. We think that using it as a comparison algorithm can effectively illustrate the advantages of our algorithm. During the experimental phase, the GCN model used for comparison adopts the double-layer structure as the original paper. The specific iteration formula is as follows:

Wherein, ReLU represents the linear rectification function which used as the activation function, and $\bm{W^{(0)}}$ and $\bm{W^{(1)}}$ represent the training weight matrix.

On the whole, we will show our experimental content in terms of the accuracy and overall efficiency of the node classification task. For experiments on the accuracy, we set three groups of hyperparameters that differ in the learning rate $\bm{\alpha}$ and the maximum number of iterations max_epoch (Their values are [0.01, 300], [0.001, 500], and [0.0003, 1000], respectively), to enhance the persuasiveness of our experimental results. Then, we iterated the MORE model and GCN model using three groups of hyperparameters in six network datasets, and the experimental results are shown in Table 4. It can be seen that in all networks, the highest accuracy of the MORE model is better than that of the GCN model. In the Email-Eucore dataset which is rich in the network motif, our model has improved by 10% based on the 51.50% accuracy of the GCN model.

By comparing the three models proposed in this paper, namely MORE-HA, MORE-SU, and MORE-CO, we can obviously find that the MORE-HA model has the highest times of getting the best accuracy. This is because the MORE-HA model uses the Hadamard product process to make one type of feature information as a bias of another type, and preserves the implicit association as much as possible. The aggregation process of the MORE-SU model and the MORE-CO model leads to the cancellation or even destruction of some of this correlation information, resulting in a decrease in the overall accuracy. However, it is worth noting that in TerrorAttack dataset, we find that the accuracy of the MORE-HA is very low. The reason for this phenomenon is that the number of M42 and M43 motif in the network is zero, causing the Hadamard product to completely lose data. This phenomenon does not occur during the summation process and connection process, so it can be said that the MORE-SU and MORE-CO models have stronger stability than MORE-HA model.

We perform comparative experiments on the efficiency of the node classification task. We iterate the four models to convergence with a learning rate $\bm{\alpha}$ of 0.003. The experimental results are shown in Table 5. Wherein, we use the number of iterations #Iter, the Average Single Training Time (ASTT), the Overall Iteration Time (OIT), and the TEst running Time (TET) to measure the convergence speed and training efficiency of the model. It can be found that by combining the multivariate relationships in the network environment, the overall efficiency of the algorithm has been greatly improved. Compared with the GCN model, the MORE model can reduce the OIT required in the iterative process by up to 19.5% of GCN, and reduce #Iter by up to 15.5% of GCN. Moreover, the MORE model has not reduced the accuracy or even improved it in the node classification tasks of most datasets.

Figure 6 further shows the convergence speed comparison between MORE and GCN models. We run four models on the Email-Eucore dataset with $\bm{\alpha}$ = 0.001, and continue to iterate until one of the models converges. In this process, we calculate the accuracy and loss of the four models on the training set, validation set, and test set for node classification tasks after each iteration, and draw it into a line chart. It can be clearly seen that the convergence speed of the MORE model is significantly higher than that of the GCN model. And compared with MORE-HA and MORE-SU, because the node information is completely preserved during the connection process, MORE-CO using the connection aggregation has more information available during the iteration. This reason ultimately leads that MORE-CO has the highest training efficiency.

It is worth noting that we can clearly find from Figure 6 (a)-(c) that around the 25th iteration, the accuracy trends of all models have shown a large degree of smoothness. Even in the MORE-HA model, the accuracy of the node classification task experienced a local peak. This phenomenon is caused by the data set and the gradient descent algorithm. In the Email-Eucore dataset, comparing the four models, it can be found that MORE-SU and MORE-CO are less affected. They did not experience a sudden increase or decrease in the accuracy of the validation set and the test set. This matches the conclusions we have drawn above, that is, MORE-SU and MORE-CO are more stable than MORE-HA.