In recent years, substantial progress has been made on graph convolutional networks (GCN). In this paper, for the first time, we theoretically analyze the connections between GCN and matrix factorization (MF), and unify GCN as matrix factorization with co-training and unitization. Moreover, under the guidance of this theoretical analysis, we propose an alternative model to GCN named Co-training and Unitized Matrix Factorization (CUMF). The correctness of our analysis is verified by thorough experiments. The experimental results show that CUMF achieves similar or superior performances compared to GCN. In addition, CUMF inherits the benefits of MF-based methods to naturally support constructing mini-batches, and is more friendly to distributed computing comparing with GCN. The distributed CUMF on semi-supervised node classification significantly outperforms distributed GCN methods. Thus, CUMF greatly benefits large scale and complex real-world applications. In recent years, works on graph convolutional networks (GCN) (Kipf & Welling, 2017) have achieved great success in many graph-based tasks, e.g., semi-supervised node classification (Kipf & Welling, 2017) , link prediction (Zhang & Chen, 2018) and recommendation systems (Ying et al., 2018) . GCN defines a graph convolution operation, which generates the embedding of each node by aggregating the representations of its neighbors. Given a graph, GCN performs the graph convolution operation layer by layer to obtain the final node representations, which will be passed to neural networks to support various tasks. To perform GCN on large scale graphs in constrained memory or distributed computing environments, different sampling methods have been proposed, such as neighbor sampling (Hamilton et al., 2017) and importance sampling (Chen et al., 2018b) . Instead of sampling, Cluster-GCN (Chiang et al., 2019) proposes an approach to convert computation on a huge matrix to computing on a set of small matrices. However, these methods still suffer from performance loss when conducting distributed computing. To take use of various contextual information on edges in a graph, Relational GCN (RGCN) (Schlichtkrull et al., 2018) extends neighbor aggregation by using edge types in link prediction. Besides the edge types, Edge-enhanced Graph Neural Networks (EGNNs) (Gong & Cheng, 2019) takes more contextual features into consideration. However, in general, GCN still has the efficiency problem when facing complex forms of contextual information. Besides GCN, graph embedding methods (Perozzi et al., 2014; Tang et al., 2015b; a; Grover & Leskovec, 2016) are also widely applied. In general, these methods rely on first-order and secondorder proximity to embed very large information networks into low-dimensional vector spaces. The first-order proximity in a graph is the local pairwise proximity between two vertices, and the secondorder proximity between a pair of vertices in a graph is the similarity between their neighborhood structures. As for GCN, previous work shows that the graph convolution operation is actually a special form of Laplacian smoothing . Thus, as the converging of the model, the smoothing process can keep the final representation of a node more and more similar to those of its neighbors. Therefore, GCN is consistent with graph embedding methods in capturing the structural information. According to previous work (Qiu et al., 2018) , graph embedding methods have been successfully unified as matrix factorization (MF). Thus, we believe that there might be some connections between GCN and MF. Meanwhile, comparing with GCN, MF-based methods are extremely flexible and suitable for distributed computing (Gemulla et al., 2011; Zhuang et al., 2013; Yu et al., 2014) . MF-based methods are also easy and efficient to be extended to tasks with complex forms of contextual information on graph edges (Rendle et al., 2011; Rendle, 2012; Jamali & Lakshmanan, 2013; Shi et al., 2014; Liu et al., 2015) . Thus, if we can unify the GCN model as a special form of MF, large scale and complex real-world applications will benefit from this. In this paper, we theoretically reveal the connections between GCN and MF, and unify GCN as matrix factorization with co-training and unitization in section 2. Here, the co-training process means co-training with the classification task of labeled nodes as in (Weston et al., 2012; Yang et al., 2016) , and the unitization indicates conducting vector unitization on node representations. Then, under the guidance of our theoretical analysis, we formally propose an alternative model to GCN named Co-training and Unitized Matrix Factorization (CUMF) in section 3. Extensive experiments are conducted on several real-world graphs, and show co-training and unitization are two essential components of CUMF. Under centralized computing settings, CUMF achieves similar or superior performances comparing with GCN. These observations strongly verify the correctness of our theoretical analysis. Moreover, GCN performs poor on dense graphs, while CUMF has great performances. This is may caused by the over-smoothing of graph convolution on dense graphs, while CUMF can balance the smoothing of neighbours and the classification of labeled nodes through the co-training process. Experiments under distributed computing settings are also conducted, and distributed CUMF significantly outperforms the state-of-the-art distributed GCN method, i.e., cluster-GCN (Chiang et al., 2019) . Thus, CUMF is extremely friendly to large scale real-world graphs. Meanwhile, lots of works have been done to model contextual information in MF-based methods (Rendle et al., 2011; Rendle, 2012; Jamali & Lakshmanan, 2013; Shi et al., 2014; Liu et al., 2015) , which have shown great effectiveness, efficiency and flexibility. To the best of our knowledge, CUMF is the first work that connects GCN to MF. We theoretically unify GCN as co-training and unitized matrix factorization, and a CUMF model is therefore proposed. We conduct thorough and empirical experiments, which strongly verify the correctness of our theoretical analysis. The experimental results show that CUMF achieve similar or superior performances compared to GCN. We also observe that GCN performs poor on dense graphs, while CUMF has great performances. This is may caused by the over-smoothing of graph convolution on dense graphs, while CUMF can balance the smoothing of neighbours and the classification of labeled nodes via co-training. Moreover, due to the MF-based architecture, CUMF is extremely flexible and easy to be applied to distributed computing for large scale real-world applications, and significantly outperforms state-of-the-art distributed GCN methods.
We unify graph convolutional networks as co-training and unitized matrix factorization.
{"src": "scitldr-AIC_train", "paper_id": "HJxf53EtDr"}