Deep Partial Multiplex Network Embedding

Single network embedding methods (GongLSW20, ; aaai2021_a, ; aaai2021_b, ; feng2021should, ; chen2021catgcn, ; wu2022graph, ) learn an information preserving embedding of a single-view network for node classification, node clustering and many other related tasks. A spectral based method (BelkinN01, ) has been proposed, which uses the top-k eigenvectors to represent the network nodes. DeepWalk (DeepWalk, ) introduces the idea of Skip-gram to learn node representations from random-walk sequences. LINE (LINE, ) tries to use the embedding to approximate the first-order and second-order proximities of the network. On top of DeepWalk, Node2Vec (node2vec, ) adds two parameters to control the random walk process and make it biased random walk. SDNE (SDNE, ) uses deep neural networks to preserve the neighbors structure proximity in network embedding. Recently, graph neural network (GNN) based methods (SAGE, ; ArmandpourDHH19, ; YangPZP0RL20, ) have been proposed, which generate embedding by sampling and aggregating features from a node local neighborhood in the network. GraphSAGE (SAGE, ) is a general inductive framework that leverages node feature information to efficiently generate node embeddings for previously unseen data. DEGNN (LiWWL20, ) presents a distance encoding GNN that learns a generator to approximate the node connectivity distribution and a discriminator to differentiate fake nodes and the nodes sampled from the true data distribution. For a comprehensive review on GNN models, please refer to (WuPCLZY21, ).

Various approaches have been proposed to learn network embedding on multiplex data (ChangHTQAH15, ; CenZZYZ019, ; ChenY0DLZ19, ; abs-2008-10085, ; abs-2004-00216, ; abs-2012-12517, ; YanZT21, ; XieOCLXYZ21, ; qifan2021deep, ). Such methods effectively integrate information from individual views while exploiting complementary information supplied by different views. MVE (MVE, ) is one of the pioneer work in this category. This work combines the information from multiple sources using a weighted voting scheme. MVN2Vec (mvn2vec, ) further studies how varied extent of preservation and collaboration can impact the multiplex embedding learning. DANE (GaoH18b, ), DONE (BandyopadhyayNV20, ) and ProGAN (ProGAN, ) treat the attribute/tag information associated with the nodes as additional feature and learn embedding with deep neural networks. More recently, MNE (MNE, ) uses a latent space to integrate the information across multiple views. MAGCN (ChengWTXG20, ) proposes a multi-view attribute graph convolution networks model for the clustering task. A quick survey on multiplex network representation is provided in (abs-2004-00216, ). These multiplex network embedding methods (WangJSWYCY19, ; HuDWS20, ; XueYRJWL21, ) achieve promising results. However, the partial data scenarios are not considered.

It is also worth mentioning that there are few single network embedding approaches that deal with incomplete data (WeiCSLY16, ; ZhangYZZ18, ). Obviously, these methods are not suitable in multiplex network setting. There are also some multi-view approaches (LiJZ14, ; RaiNCD16, ; GuoY19, ; XuGZWNL19, ; LiuZLTZY20, ) proposed to deal with incomplete data in clustering task. For example, PVC (LiJZ14, ) develops a two-view clustering method that learns a unique representation between views to handle incomplete data in each view. Most recently, IMVC (LiuZLTZY20, ) uses multiple kernel k-means with incomplete kernels to jointly conduct clustering and kernel matrix imputation. Although these methods obtain reasonable performance, they are not directly applicable to network embedding as network information can not be modeled by these methods. Moreover, none of these methods learn the deep representations for the multiplex network. We compare and summarize these approaches in Table 1.

Given a multiplex network $\boldsymbol{G}$=$(\boldsymbol{V},\boldsymbol{E})$, where $\boldsymbol{V}$=$\{v_{i}\ |\ i=1,\dots,n\}$ denotes the set of nodes. $\boldsymbol{X}$=$\{\boldsymbol{X}^{1},\boldsymbol{X}^{2},\dots,\boldsymbol{X}^{t}\}$ are the multiplex features associated with the nodes, where $t$ is the total number of views, $\boldsymbol{X}^{s}$={$x_{i}^{s}\ |\ i=1,2,\dots,n\}$ with $x_{i}^{s}\in\mathbb{R}^{d_{s}}$ is the feature of the $i$-$th$ node in the $s$-$th$ view. $\boldsymbol{E}$=$\{\boldsymbol{E}^{s}\}$ denotes the edge sets in the multiplex network, where $\boldsymbol{E}_{i,j}^{s}$=$1$ indicates that $v_{i}$ and $v_{j}$ are linked in the $s$-$th$ view. In the partial data setting, a partial data ${\bar{\boldsymbol{X}}}$=$\{{\bar{\boldsymbol{X}}}^{1},{\bar{\boldsymbol{X}}}^{2},\dots,{\bar{\boldsymbol{X}}}^{t}\}$ instead of $\boldsymbol{X}$ is given, where some of the node features are missing from each individual views, e.g., $x_{4}^{1}$ is missing from View 1 and $x_{5}^{2}$ is missing from View 2 in Figure 1. The purpose of DPMNE is to learn a low-dimensional embedding representation $\boldsymbol{Y}$=$\{y_{1},y_{2},\dots,y_{n}\}\in\mathbb{R}^{n\times d}$ of $\boldsymbol{G}$, where $d\ll d_{s}$ is the latent embedding dimension.

The overall model architecture is shown in Figure 1. The objective function of DPMNE is composed of three components: (1) Deep reconstruction loss within each views, where we learn a deep representation of the node feature using autoencoder model. (2) Data consistency among views, where latent common subspace learning is utilized to ensure that the node embeddings generated from different views are consistent. (3) Proximity preservation within view, where graph Laplacian is applied to enforce that linked nodes within each network should have close embeddings.

To capture the sparsity and highly non-linear structure in the feature space, we adopt a deep autoencoder to map the input data to the representation space. Autoencoder is a powerful unsupervised deep model for feature learning. It has been widely used for various machine learning applications (JiangGCH16, ; SDNE, ). The basic autoencoder contains three layers, they are the input layer, the hidden layer, and the output layer, which are defined as follows:

where $h$ is the deep representation from the encoder, $\tilde{x}$ is the reconstructed feature from the decoder. $\boldsymbol{H}$ = $\{\boldsymbol{W}^{(en)},b^{(en)},\boldsymbol{W}^{(de)},b^{(de)}\}$ are autoencoder parameters. $\sigma(.)$ denotes the non-linear activation function. In our implementation, we employ $K$ layers in the encoder:

Similarly, there will be $K$ layers in the decoder. The goal of the autoencoder is to minimize the reconstruction loss of the reconstructed features $\tilde{x}$ and the input features $x$, in each individual views (note that there is one autoencoder per view):

Although minimizing the reconstruction loss does not explicitly preserve the similarity between samples, as shown in (SalakhutdinovH09, ), the reconstruction criterion can effectively capture the data manifolds and thus preserve the similarity between data examples.

In the partial multiplex network setting, the nodes are represented by heterogeneous features of different dimensions, which makes it difficult for learning their embeddings. By investigating the problem from view perspective, in each individual view, the nodes are sharing the same feature space, and different views are coupled/bridged by the shared common nodes. If we can learn a common latent subspace across views, where embeddings belonging to the same node among different views are consistent, while at the same time for each view, the representations for linked nodes are close in the latent subspace. Then the embeddings can be directly learned from this subspace, and we do not need to fill in or complete the partial data. Following the above idea, the deep latent subspace learning can be formulated as:

where $\boldsymbol{I}^{s}\in\mathbb{R}^{n\times n}$ is a diagonal matrix with element $\boldsymbol{I}^{s}_{ii}$ = 0 or 1 indicating whether $x_{i}^{s}$ is missing or not. $\boldsymbol{H}^{s}\in\mathbb{R}^{n\times d_{s}^{h}}$ are the deep representations of the data in $s$-$th$ view as described in Section 3.2. Note that the $i$-$th$ row of $\boldsymbol{H}^{s}$ will be 0 if $x_{i}^{s}$ is missing. $\boldsymbol{B}^{s}\in\mathbb{R}^{d\times d_{s}^{h}}$ is the basis matrix for $s$-$th$ view’s latent space. The same latent space dimension $d$ is shared across views. $\boldsymbol{Y}\in\mathbb{R}^{n\times d}$ is the common representation/embedding of nodes in the latent space. $R(\cdotp)=\|\cdotp\|_{F}^{2}$ is the regularization term and $\lambda$ is the trade-off parameter.

In the above formulation, the individual basis matrix $\boldsymbol{B}^{s}$, which are learned from all available instances from all views, are connected by the common latent representation $\boldsymbol{Y}$. Moreover, no interpolation is needed for the missing data beforehand. In fact, the deep representation of the missing data can even be reconstructed with the learned basis and the common latent embedding, i.e., $h_{i}^{s}=y_{i}B^{s}$. By solving the above problem, the deep representation $\boldsymbol{H}$, the latent space basis $\boldsymbol{B}$ and the homogeneous feature representation $\boldsymbol{Y}$ are simultaneously learned to minimize the latent representation error.

One of the key problems in network embedding algorithms is proximity preserving, which indicates that linked nodes should be mapped to similar embedding within a close distance. Therefore, besides the data consistency across different views, we also preserve the data proximity within each individual network. In other words, we want the learned embedding $\boldsymbol{Y}$ to preserve the proximity structure in each network. In this work, we use the $L_{2}$ distance to measure the proximity between $y_{i}$ and $y_{j}$ as $\|y_{i}-y_{j}\|^{2}$ as in most network embedding work. Then one natural way to preserve the proximity in each network is to minimize the weighted average distance as follows:

here $\boldsymbol{P}_{ij}=\sum_{s=1}^{t}\boldsymbol{P}_{ij}^{s}$ and $\boldsymbol{P}^{s}$ is the proximity matrix in $s$-$th$ view, which can be obtained from the edges in $s$-$th$ network $\boldsymbol{E}^{s}$. A simple way to define $\boldsymbol{P}^{s}$ is to directly use the first-order proximity, i.e., $\boldsymbol{P}^{s}=\boldsymbol{E}^{s}$. However, the first-order proximity is usually very sparse and insufficient to fully model the relationships between nodes in most cases, especially under the partial data setting. In order to characterize the connections between nodes better, we adopt high-order proximity (GaoH18b, ; Li0ZZC19, ) and define $\boldsymbol{P}^{s}$ as:

where $l$ is the order, and $w_{1}$,$\dots$,$w_{l}$ are the weights for each term¹¹1In our implementation, we set $l$ to 5, $w_{1}$ to 1 and $w_{i}$ = $0.5w_{i-1}$.. Matrix $(\boldsymbol{E}^{s})^{l}$ denotes the $l$-order proximity matrix. To meet the proximity preservation criterion, we seek to minimize the quantity in Eqn.5 in the network since it incurs a heavy penalty if two connected nodes have very different embedding representations. By introducing a diagonal matrix $\boldsymbol{D}$, whose entries are given by $\boldsymbol{D}_{ii}=\sum_{j=1}^{n}\boldsymbol{P}_{ij}$. Eqn.5 can be rewritten as:

where $\boldsymbol{L}$ is called graph $Laplacian$ (BelkinN01, ) and $tr(\cdotp)$ is the matrix trace function. By minimizing the above objective in all networks, the proximity between different nodes can be preserved in the learned embedding.

The entire objective function consists of three components: the deep reconstruction loss in Eqn.3, the data consistency among views in Eqn.4 and proximity preservation within views given in Eqn.7 as follows:

where $\alpha$, $\beta$ and $\lambda$ are trade-off parameters to balance the weights among the terms. Directly minimizing the objective function in Eqn.8 is intractable since it is a non-convex optimization problem with $\boldsymbol{Y}$, $\boldsymbol{B}$ and $\boldsymbol{H}$ coupled together. We propose to use coordinate descent scheme by iteratively solving the optimization problem with respect to $\boldsymbol{Y}$, $\boldsymbol{B}$ and $\boldsymbol{H}$ as follows:

(1) Update ${Y}$ by fixing $B$ and $H$. Given the basis matrix $\boldsymbol{B}^{s}$ and encoders $\boldsymbol{H}^{s}$ for all views, we seek to solve the following sub-problem:

where $const$ is the constant value independent with the parameter that to be optimized with. Although Eqn.9 is still non-convex, it is smooth and differentiable which enables gradient descent methods for efficient optimization with the calculated gradient:

(2) Update ${B}^{s}$ by fixing $Y$ and $H$. It is equivalent to solve the following least square problems:

which has a closed form solution and can be simply derived.

(3) Update ${H}^{s}$ by fixing $Y$ and $B$. It is a standard autoencoder with an additional regression loss:

which can be solved with gradient back-propagation. We then alternate the process of updating $\boldsymbol{Y}$, $\boldsymbol{B}$ and $\boldsymbol{H}$ for several iterations to find a locally optimal solution.

This section connects our work to the quantization-based binary embedding techniques (GongLGP13, ; WangZSSS18, ; wang2015learning, ), which learn compact binary representations of the data examples for efficient similarity search tasks. Quantization-based binary embedding methods directly binarize the low-dimensional representation to achieve the binary codes. In this work, we can easily obtain the binary codes $\boldsymbol{C}$ for the nodes in the network by binarizing the learned embedding $\boldsymbol{Y}$. However, the quantization error can be further reduced based on the orthogonal invariant property, by minimizing the quantization error between the binary codes and the orthogonal rotation of the embeddings (since $\boldsymbol{YQ}$ is also an optimal embedding):

The above quantization problem is well studied in the literature (GongLGP13, ).

This section provides some complexity analysis on the training cost of the learning algorithm. The optimization algorithm of DPMNE consists of three steps in each iteration to update $Y$, $B$ and $H$. The time complexities for solving ${Y}$ and $B$ are bounded by $O(tndd_{s}+tnd^{2}+n^{2}d)$ and $O(tnd^{2}+tndd_{s})$ respectively. In practice, $L$ is usually a sparse matrix, and the cost can be reduced from $O(n^{2}d)$ to $O(ld)$ with sparse matrix multiplication, where $l$ is the number of non-zero elements in $L$. The cost of updating $H$ depends on the number of hidden layers and units in the autoencoder network, which is roughly $O(tnmd_{s})$. Here $m$ is the number of unique units in the network. Thus, the total time complexity of the learning algorithm is bounded by $O(tndd_{s}+ld+tnd^{2}+tnmd_{s})$.