Multi-View Attribute Graph Convolution Networks for Clustering

1 Introduction

Multi-view clustering is a fundamental task in machine learning. It aims to integrate multiple features and discover consistent information among different views [Xie et al., 2019; Li et al., 2019; Zhang et al., 2018a]. Existing multi-view clustering methods have achieved considerable results in the Euclidean domains [Andrew et al., 2013; Gao et al., 2020]. However, those algorithms are no longer suitable for processing intensively studied data, which often occurs in the nonEuclidean domains such as graphs in social network connections, article citations, etc. In light of this, graph embedding methods, which could effectively explore the graph structured data, have received much attention recently.

∗Corresponding Author

†Corresponding Author

Graph embedding converts graph data into a lowdimensional, compact, and continuous feature space, which is usually implemented by matrix-factorization [Belkin and Niyogi, 2002], random-walk [Perozzi et al., 2014], or graph neural networks (GNN) [Salehi and Davulcu, 2019; Kipf and Welling, 2017]. Among existing methods, GNNs, largely owing to their efficiency and inductive learning capability [Hamilton et al., 2017], have become one of the most popular paragons. Generally, GNNs calculate the embedding of a graph node by applying multiple graph convolutional layers to gather the information of node neighbors through nonlinear transformations and aggregation functions. Hence, they can preserve the topological structure, vertex content information of the graph-structured data. Although the above GNNs can effectively process single-view graph data, they are not applicable to multi-view graph data.

To tackle this challenge, some research attempts are made in using GNNs for multi-view data of multiple graph structures. For example, multi-view graphs are used for prediction and classification of drug similarity and medicine in the medical filed [Zhang et al., 2018b; Ma et al., 2018], and are also leveraged for ridehailing demand forecasting and global poverty [Geng et al., 2019; Khan and Blumenstock, 2019]. However, those multi-view graph neural networks have the following limitations: 1) They cannot allocate learnable specifying different weights to different nodes in neighborhood; 2) They may neglect to proceed the reconstruction of both node attributes and graph structure to improve the robustness; 3) The similarity distance measure is not explicitly considered for the consistency relationship among different views. Moreover, existing multi-view GNN methods mainly focus on the case of multiple graphs, while ignoring equally important attribute diversity, i.e. multi-attribute. Nonetheless, in the real world, it is common that we have multiple characteristic attributes with the same connection relationship of a graph. For instance, people could have multiple attributes, such as, job, hobby, etc., in the connection graph of social network.

Motivated by the above observations, in this paper, we propose a novel Multi-view Attribute Graph Convolution Networks for clustering (MAGCN) the graph-structured data of multi-view attributes (see Fig.2). Specifically, 1) to allocate learnable weights to different nodes, MAGCN develops multi-view attribute graph convolution encoders with attention mechanism for learning graph embedding from multi-view graph data. 2) Attribute and graph reconstruction are both computed by the graph convolution decoders of MAGCN. 3) The geometric relationship and the probability distribution consistency among multi-view graph data are incorporated into the consistent embedding encoders of MAGCN to further facilitate the clustering task. The key contributions of our work are summarized as follows.

• We propose a novel Multi-View Attribute Graph Convolution Networks for clustering on the graph-structured data of multi-view attributes.
• We develop multi-view attribute graph convolution encoders with attention mechanism to reduce the noise/redundancy of the multi-view graph data. In addition, reconstruction of both node attributes and graph structure are considered to improve the robustness.
• Consistent embedding encoders are designed to extract the consistency information among multiple views, by exploring the geometric relationship and the probability distribution consistency of different views.

2 RelatedWork

Learning graph node embedding within broader graph structure is crucial for many tasks on graphs. Existing GNNs models in processing graph-structured data belong to a set of graph message-passing architectures that use different aggregation schemes for a node to aggregate feature messages from its neighbors in the graph. Graph Convolutional Networks [Kipf and Welling, 2017] scale linearly in the number of graph edges and learn hidden layer representations that encode both local graph structure and features of nodes. By stacking self-attention layers in which nodes are able to attend over their neighborhoods' features, Graph Attention Networks (GAT) [Velickovic et al., 2018] enable specifying different weights to different nodes in neighborhood. GraphSAGE [Hamilton et al., 2017] concatenates the node's feature with diversified pooled neighborhood information and effectively trades off performance and runtime by sampling node neighborhoods. Message Passing Neural Networks [Gilmer et al., 2017] further incorporate edge information when doing the aggregation.

To handle the problem of multi-view graph node embedding, some researchers have made some attempts. In the medical field, [Zhang et al., 2018b] propose a method based on GCNs for fusing multiple modalities of brain images in relationship prediction, which is useful for distinguishing Parkinson's Disease cases (a prevalent neurodegenerative disease) from controls. Another novel model [Geng et al., 2019], called spatiotemporal multi-graph convolution network, encodes the non-Euclidean correlations among regions using multiple graphs and explicitly captures them using multigraph convolution encoder. In application accounting for social networks, Multi-GCN [Khan and Blumenstock, 2019] incorporates non-redundant information from multiple views into the learning process. [Ma et al., 2018] utilize multiview graph auto-encoder, which integrates heterogeneous, noisy, nonlinear-related information to learn accurate similarity measures especially when labels are scarce.

However, those multi-view GNNs cannot allocate learnable specifying different weights to different nodes in neighborhood, where we can learn from the excellent ideas of GAT. And the clustering performance of them is limited as they do not consider the structure and distribution consistency for clustering embedding. What's more, GNNs for solving graph-structured data of multi-view attributes is still underexplored. Existing multi-view GNNs mainly focus on the case of multiple graphs and neglect the equally important attribute diversity. Thus, in this paper, we propose MAGCN on multi-view attribute graph data.

3 ProposedMethodology

3.1 Notation

A graph can be represented as G = (V,E)(G ∈ Rn×n ), where V = {v1, v2, ..., vn} is the node set and E is the edge set, n denotes the number of nodes, and vi represents the i-th node. In this study, we augment graph G with the node mth view attribute feature Xm = {x1m, ..., xim, ..., xnm}(Xm ∈ Rn×dm ), m = 1, 2, ...,M, where xim refers to the feature vector associated with node vi and M is the number of views.

3.2 The Framework of MAGCN

As shown in Fig.2, our model contains two principle modules: multi-view attribute graph convolution Encoders and consistent embedding Encoders. We first encode multi-view graph data Xm into graph embedding Hm = {h1m, ..., him, ..., hnm}(Hm ∈ Rn×d ) by multi-view attribute graph convolution encoders. Then, fed Hm into consistent embedding encoders and obtain a consistent clustering embedding Z. The clustering process is eventually conducted on the ideal embedding intrinsic description space which is computed by Z.

Multi-view Attribute Graph Convolution Encoder

In multi-view attribute graph convolution encoders, the first pathway encoders map multi-view node attribute matrix and graph structure into graph embedding space. Specifically, for the m-th view, the function of a graph embedding model is fm(G,Xm; θ) → Hm. It maps graph G and m-th view attributes Xm to d-dimensional graph embedding features Hm, where θ represents multi-view graph auto-encoder parameter. As shown in Fig.1, the output of l-th multi-view attribute graph convolution encoders is

where G′ = G + IN is the relevance coefficient matrix with added self-connection. IN is the identity matrix, Dii = ∑j G′ ij andW(l) is the trainable parameter of the l-th multiview auto-encoder layer and σ denotes the activation function. As for H(l) m , when l = 0, H(0) m is the initial m-th view attribute matrix Xm and when l = L, H(L) m is the final graph embedding feature representation Hm.

To determine the relevance between nodes and their neighbors, we use a attention mechanism with shared parameters among nodes. In the l-th multi-view encoder layer, the learnable relevance matrix S is defined as

where ts (l) and tn (l) ∈ R1×dl represent the trainable parameters related to their own nodes and neighbor nodes, respectively. ⊙ refers to the element-wise multiplication with broadcasting capability, and ϕ denotes the activation function which is generally set as the sigmoid activation function (i.e., sigmoid (x) = 1/ (1 + exp-x )). We normalize S to get the final relevance coefficient G, so Gij is computed by

where Ni is the set of all nodes adjacent to node i.

After applying L multi-view encoder layers, we get graph embedding Hm which preserves basically all information about multi-view node attribute matrix X and graph structure G. Then, we consider the feature Hm that contains almost all the information to decode as different views. In the decoding process, we use the same number of layers as encoders for decoders, and each decoder layer tries to reverse its corresponding encoder layer. In other words, the decoding process is the inverse of the encoding process. The final decoded output is reconstructed node attribute matrix ˆXm and the reconstructed graph structure ˆGm, m = 1, 2, ..., V . Specifically, the output of the (l - 1)-th multi-view attribute graph convolution decoders is

After applying L decoder layers, reconstructed multi-view node attribute matrix ˆXm = ˆH(0) m is obtained. As for the reconstructed graph structure ˆGm, ˆGijm is implemented by an inner product decoder of him and hjm, where him and hjm are the node i and j of graph embedding features Hm. Specifically, ˆGijm is computed by

where φ(·) is the inner product operator.

Finally, the reconstruction loss Lre of reconstructed multiview node attribute matrix ˆX and reconstructed graph structure ˆG can be computed by following:

where θ is the network parameter of multi-view attribute graph convolution encoders.

Consistent Embedding Encoders

In consistent embedding encoders, for viewm, we first adopt nonlinear feature extraction mapping for graph embedding Hm. Hm is mapped into low-dimensional space Zm. The mapping function is gm(Hm; η) → Zm, where η represents encoder parameter. Zm contains almost all the original information so that it is not suitable for multi-view integrating directly. Then, we use consistent clustering layer to learn a common clustering embedding Z which is adaptively integrated by all the Zm.

Assume Zm and Zb are the low-dimensional space feature matrices of view m and b obtained from consistent embedding encoders. Then we can use them to compute a geometric relationship similarity score as si(Zm,Zb), where si(·) is a similarity function. si(·) can be measured by the Manhattan Distance, Euclidean distance, cosine similarity, etc. If the simplest difference similarity function is taken, the loss function of geometric relationship consistency Lgeo is

where η is the network parameter of encoder.

Besides the geometric relationship, we also consider the consistency of the probability distribution between common representation Z and latent representation of each view Zm, where Z= ∑Mm=1 βiZi is an adpative fusion on a lowdimensional feature space, Zm = {z1, ..., zi, ..., zn}(Zm ∈ Rn×d ). We show the details of computing the probability distribution of Z and Zm in the following.

Following [Tao et al., 2019; Wang et al., 2018], we use the Student's t-distribution, , as a kernel to measure the similarity between integrated node representation zi and centroid µj. Thus, the original probability distribution Q of Z is

where {µj}kj=1 is the k initial cluster centroids, α is the degree of freedom of the Student's t-distribution, qij is the probability of assigning node i to cluster j. In our experiments, we compute target probability distribution P of Z. pij is the elements of P, and 0 ≤ pij ≤ 1. By raising qi to its second power and normalizing it with the frequency per cluster as follows, we obtain

where fj = ∑i qij are soft cluster frequencies. To this end, we define our objective as a probability distribution consistency loss Lpro between the soft assignment Qm of Zm and the auxiliary distribution P of Z with trade-off parameters ρ as follows

In this way, we could concentrate on the same class data by sharping the data distribution and get a more effective and common representation for multi-view clustering.

3.3 Task for Clustering

By combining Eq. (6), Eq. (7) and Eq. (8), the total loss function of the proposed MAGCN is eventully formulated as

Optimizing the overall loss L, we learn the auxiliary distribution P from the clustering embedding feature Z. Then we predict the cluster of each node from auxiliary distribution P. For node i, its cluster can be calculated by pi, in which the index with the highest probability value is the i's cluster. Hence we could obtain the cluster label of node i as

4 Experimental Analysis

4.1 Experimental Setting

Metrics and Databases

In order to evaluate the effectiveness of our proposed approach, we conduct extensive experiments on three citation network databases (Cora, Citeseer and Pubmed) [Sen et al., 2008] with three evaluation metrics: clustering accuracy (ACC), normalized mutual information (NMI) and average rand index (ARI), and the higher these indicators, the better the clustering effect. The general graph-structured database contains one graph and one attribute and there is no such real graph-structured data with multi-view attributes at present. Due to the databases used in the experiments, the attributes of graph-structured data are 0, 1, which are discrete structured and also one-sided described. So we make attributes continuous by changing the operation of that, for the purpose of describing the graph structure more abundantly. Inspired by multi-graph, which constructs another graph by themselves, we construct additional attribute views by original attributes. Specifically, we use Fast Fourier Transform (FFT), Gabor transform, Euler transform and Cartesian product to construct view 2 based on view 1. In Sec. 4.2, the results of each view 2 are analyzed. Brief statistics of the three databases are shown in Table 1, where view 2 is constructed by Cartesian product. For other experiments, we construct from the first view based on Cartesian product.

Implementation Details

In our experiments, we used two layers of multi-view attribute graph convolution encoders for all three databases. For Cora database, node representation dimensions of the two layer are set as [512, 512]. As to the Citeseer database, node representation dimensions of the two layer are set as

[2000, 512]. For Pubmed, the dimension of two-layer multiview attribute graph convolution auto-encoder is [128, 64]. In integrate-encoder, we use a fully connected layer in all three databases. We use non-linear activation function σ as Relu function in the multi-view graph convolution auto-encoder. As for regular term coefficient λ1, λ2 and λ3, we set λ1 as 1. λ2 and λ3 are set range from 10-2 to 102 , and analyze the influence of parameters later in Sec. 4.2: Impact of Loss Coefficient.

Comparison Algorithms

We choose several state-of-the-art clustering compared algorithms as follows.

• node attribute: K-Means;
• graph structure: Graph Encoder, DeepWalk, denoising autoencoder for graph embedding (DNGR) and modularized nonnegative matrix factorization (M-NMF);
• graph structure & node attribute: graph autoencoders (GAE) and variational graph auto-encoders (VGAE), marginalized graph autoencoder (MGAE), ad-
• versarial regularized graph autoencoder (ARGAE) and adversarial variational regularized graph autoencoder (ARVGAE), deep attentional embedding graph clustering (DAEGA) and graph attention auto-encoders (GATE);
• deep multi-view clustering: deep canonical correlation analysis (DCCA) and deep typical correlated autoencoder (DCCAE).

4.2 Experimental Results

Evaluation Metrics with Comparison Algorithms

Table 2 summarizes the comparative evaluation results on three databases of Cora, CIteseer, and Pubmed. The proposed MAGCN clearly outperforms all the compared methods. Specifically, MAGCN improves on GCNs of single view by a margin of more than 5% on Cora and Citeseer and more than 1% on Pubmed, which indicates that it is effective to integrate different views with the consistency of geometric relationship and the probability distribution. From the suboptimal results, we can see that our method also has a substantial improvement in single-view graph clustering. Meanwhile, the single view graph convolution clustering methods: DAEGC and GATE, have relatively better clustering performance, which shows that attention mechanism aggregating neighborhood information according to trainable attention weights helps improving clustering performance. In addition, deep multi-view clustering methods achieve better performance by using the graph structure information. This shows that the graph structure information can make beneficial contribution to clustering. The performance of deep multi-view clustering methods is even worse than many single-view GCN clustering methods, which also indicates the excellence of GCN in processing graph structured data.

Analysis of Probability Distribution Consistency

To illustrate the advantages of probability distribution consistency in our model, we conduct the following visual experiments on Cora database. We randomly select a sample from the third class and compute original probability distribution Qm for each view's low dimensional representation Zm and the target probability distribution P for the common feature representation Z. Our goal is to get the ideal description space of multi-view. In terms of low-dimensional features Zm, we use the consistency of probability distribution as constraint to reduce the differences between different views. As shown in Fig.4, in the initial iteration, the random initialization makes the probability of each class basically similar, and it is impossible to find out which class the sample belongs to. But the probability in the third class increases with the number of iterations, and the probability distributions on Z, Z1 and Z2 tend to be consistent, which indicates that the ideal multi-view description feature Z is learned gradually.

Impact of Parameters

There are three regularization parameters in our model: λ1, λ2 and λ3, and we use controlling variables method to analyze their impact. We keep the regular parameters λ1 of reconstruction loss unchanged and change the regular parameters λ2 and λ3 of geometric relationship consistency and probability distribution consistency in the model. As shown in Fig.3, when λ2 is between 10-2 and 102 , the corresponding evaluation metrics ACC, NMI and ARI will largely remain the same. That explains that the model has a relatively good clustering robustness on geometric relationship consistency. As for the regular term λ3 of probability distribution consistency, when λ3 was set as 10, the multi-view clustering has the best performance. When the value of λ2 is too large, the model clustering performance is not good. Therefore, we set λ3 of probability distribution consistency around 10 in the experiment.

Analyzing Different View 2

Analyze the performance of our model when the second view are constructed in different ways (FFT, Cartesian, Garbor, and Euler) on Cora database. To facilitate the comparison, we use the view 1 as the baseline. We keep all parameters consistent to ensure the fairness of the experiments. As shown in Fig.5, we can see for all kind of view 2, the clustering results with two views is better than the case of single view 1 (marked by black line). In addition, the Cartesian product way works the better than other constructing ways for view 2 (marked by red line). This is why we construct the second view using Cartesian products in all the other experiments.

5 Conclusions

In this paper, we propose a novel Multi-View Attribute Graph Convolution Networks for Clustering (MAGCN), a generally method to multi-view graph neural network. MAGCN is designed with dual encoders that reconstruct the extracted features in high dimension and integrate the low dimension consistent information. Multi-view attribute graph auto-encoder and consistent embedding encoder network successively reduce the noise and the difference among different views, and finally get the ideal description space of multi-view attribute graph for clustering. Experimental results on the multi-view graph structure databases demonstrate the validity of our method and perform superior advantages over several stateof-the-art algorithms.

Acknowledgments

This work is supported by National Natural Science Foundation of China (Grant 61773302, 61906142, 61906141), Initiative Postdocs Supporting Program (Grant BX20190262), China Postdoctoral Science Foundation (Grant 2019M653564, 2019M663642), National Natural Science Foundation of Shaanxi Province (Grant 2020JZ-19, 2020JQ-317, 2020JQ-327).