Unifying Graph Convolutional Networks as Matrix Factorization
Authors: Zhaocheng Liu
Qiang Liu
Haoli Zhang
Jun Zhu
Venue:  (2020)
Keywords: graph convolutional networks
matrix factorization
unification

Abstract: 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.

Under review as a conference paper at ICLR 2020
UNIFYING GRAPH CONVOLUTIONAL NETWORKS AS MATRIX FACTORIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In recent years, substantial progress has been made on graph convolutional net- works (GCN). In this paper, for the first time, we theoretically analyze the con- nections 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 anal- ysis is verified by thorough experiments. The experimental results show that CUMF achieves similar or superior performances compared to GCN. In addition, CUMP inherits the benefits of MF-based methods to naturally support construct- ing mini-batches, and is more friendly 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.
INTRODUCTION
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 (018 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 convolu- tion 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.] (017)) ) and importance sampling (Chen et al. 2018b). Instead of sampling, Mluster-GCN (Chiang al., 2019) proposes an approach to convert computation on huge matrix to computing a set of small matrices. However, these methods still suffer from performance loss when conducting distributed computing. To take use of various contextual infor- mation on edges in 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 consider- ation. However, in general, GCN still has the efficiency problem when facing complex forms of contextual information.
Grover & Leskovec 2016) are also widely applied. In general, these methods rely first-order and second- order proximity to embed very large information networks into low-dimensional vector spaces. The first-order proximity a graph is the local pairwise proximity between two vertices, and the second- order 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 actually a special form of Laplacian smoothing (Li et al.) 2018). 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 connec- tions between GCN and MF. Mcanwhile, comparing with GCN, MF-based methods are extremely flexible and suitable for distributed computing (Gemulla et al. 2011 Zhuang et al. 2013 Yu al.
Besides GCN, graph embedding methods (Perozzi et al., 2014; Tang et al. 2015b a

---

Under review as a conference paper at ICLR 2020
MF-baaed 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 Shi et al. 2014 Liu al. 2013). Thus, if we unity the GCN model as a special form of MF. large scale and complex real-world applications will benefit from this.
2014).
2013
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 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.] (201)). Thus, CUMF is extremely friendly to large scale real-world graphs. Meanwhile, lots of works have been done model contextual information in MF-based methods (Rendle et al., [2011] [Rendle| (2012) Jamali & Lakshmanan [2013] Shi et al. 2014
Liu et al., 2013), which have shown great effectiveness, efficiency and flexibility.
GCN AS CO-TRAINING AND UNITIZED MF
In this section, we plan theoretically unify GCN specific form of matrix factorization. First, we need to start from the analysis of how node representations are learned in GCN. According to the definition in previous work (Kipf & Welling 2017), we can formulate each layer of GCN as
H ((+) = Ho D AD H w()),
(1)
where Á = A + IN is the adjacency matrix of the graph G with added self-connections, In is the identity matrix for N nodes in graph G. D a diagonal degree matrix with D..: E, Aig. H is the representation of each node at layer I, w(!) is layer-specific trainable weight matrix, and (-) denotes an activation function (such as ReLU (-) = max (0, -))
For node classification task, we can obtain a classification loss
lelass CrossEntropy YY softmax H (1):
(
(2)
where Y is the ground truth labels for the classification task, (-1) is the representation of each node at the final layer of GCN. Via optimizing Eq. 2 the cross-entropy error of the node classifi- cation task can be minimized, and the GCN model can be learned.
As in the implementation in previous work (Kipf & Welling 2017 Veličković et al. 2017 Wu et al. 2019), there is activation function the last layer of GCN, and the final representations can be formulated as
H In (Li et 2018 GCN has been proven be special form of Laplacian smoothing. The final
D AD H
(-2))
(3)
representations in Eq. B tends to converge to
H
AD H(-))
(4)
i which is an approximate solution of the final representations in GCN. Specifically, for each node in graph G, the approximate solution of the corresponding final representation is
( Σ, +1) +1) i h1 -
(5)
2

---

Under review as a conference paper at ICLR 2020
0.80
0.70
accursk
0.60
0.50
Cora
Cora Pahmed
Pubmed
0.40
20
40
60
80
20
40
60
80
epoch
epach
(a) The average cosine similarity between nodes in the (b) The accuracy curves during the training of GCN. graph and their neighbors during the training of GCN.
Consistency estimation between the cosine similarity and the convergence of GCN during training procedure on the Cora dataset and the Pubmed dataset.
Figure I:
from which we have
-1 E,
Aig h3
(-1)
di +1 h
(-1)
(6)
V(d +1) (d) +1)
Then, the representation of node can be obtained as
h ((- Σ
d: +1 A h3
(-1)
di dj +1
where di is the degree of node i.
According to above analysis, to train an approximate GCN model with one loss, which simultane- ously models the structure of graph convolution and the node classification task, can minimize the following loss function
1= a Lelass (1 a:) lstructurer
where hyper-parameter to control the balance between two losses, and the structure loss
lstructure refers to
Istructure Edis dis 1 E,
de +1 dj
Ais nn (6-11)
de
+1
where 7 denotes the set of all the nodes in graph G, and dis we apply the commonly used cosine similarity and obtain
(., a distance measurement. Here,
COS 11. Σ iET
(n(-)) Σ
di +1 dy +1
Aig 11g (-1)
lstructure
(10)
dh
which is equivalent to
(-1)
Aij 45 (111 T
h3
d.
+1
lstructure
(1I)
VEl
h
1)
E, di
As.j h
To verify whether cosine similarity is consistent with the convergence of GCN during the training procedure, we conduct empirical experiments and train GCN models on the Cora dataset and the Pubmed dataset. Figure demonstrates the average cosine similarity between nodes in the graph
3

---

Under review as a conference paper at ICLR 2020
and their neighbors, well as the convergence curves estimated by accuracy during the training of GCN on the two datasets. It is obvious that, the curves on the same dataset share similar tendency. train GCN model. the cosine similarity between nodes in the graph and
That is to say, their neighbors is being optimized. This strongly proves that cosine similarity is consistent with the convergence of the GCN model.
Then, to simplify the form of Eq. 11 we conduct vector unitization in the learned representations
H and thus each representation h (-1) has similar 12-norm. Accordingly, through unitization, Eq. is equivalent to
Σ (1)
de d3 +1
Ans n3 15-1))
latructure
(12)
di
which leads to
N iET JEC;
d+1 di V d,+1 Aty v.
letructure =
(13)
where Cj denotes all the nodes that node i connected to, and = h -11 for simplicity. Moreover, for better optimization, we can incorporate negative log likelihood and minimize the following loss function equivalently to Eq. 13
d: +1 ΣΣ EET JEC.
latructure
+1+1 Aij log (A u))
(14)
di
where A (-) = sigmoid (.).
So far, the structure loss lstructure is equivalent to factorizing all the positive edges in the graph G weighted by B., = d;' (de (1)+1112 (d, +1)-1/2
Usually, in graph embedding methods (Perozzi et al. 2014 Tang et al. 2015b a Grover & Leskovec 2016), negative edges sampling used, for better convergence. Thus, we can randomly sample negative edges for each edge in graph G. Following previous work in unifying word embedding
(Levy & Goldberg 2014) and graph embedding (Qiu et al. 2018) as implicit matrix factorization, we can rewrite Eq. (14 as
Istructure
Σ Σ
(Bes As, log (b(2 + Ey [By log (A +f)))), (15)
iEl jEC:
and
ΣE NET JEC.
B. Ars log (A (A),)))) k Σ de Ey BB log (2 (2(-0) 0s 171)1,
Istructure
(16)
where k is the number of negative samples for each edge, and Pa denotes the distribution that generates negative samples graph G. For each node j. Po (j) = dj [G], where |G] is the number of edges in graph G. Then, explicitly express the expectation term
Brg dy log (A(-u, v; oz)),
Ey-Pa [Pa log (2
(17)
G
jeeT
from which we have
BLg dj |
Bis dy |G
Eyspa BBy log (A (-v,0,))
log (
Σ
log (A 0f v.)))
JEMM
(18)
Via combining Eq. (66) and Eq. edges (i.j)
18). we can obtain the local structure loss Istracture for a specific
Istructure (i.5) = -B,, Ar, log (A (v. (v:,))) B de dj log (A (- (-v4))))
(19)
|G|
4

---

Under review as a conference paper at ICLR 2020
Node Representation
Features
MLP
Unitization
MLP
Classification
tratrinngg
Structure loss
A
V
Figure 2: Overview of our proposed CUMF model.
To optimize the objective, we need to calculate the partial derivative of Istracture with respect to of
latruature
1: Br.s dj
Bi, Ar, (-
+
x (w; oJ)
(20)
i (
G
After setting Eq. 20 to zero, we can obtain
2010 - G1 Ais - c
|G| Ai.j O, 1: di dj
(21)
d d2
which has solutions, e -1 and
" |G| Aij. k dj
(22)
which leads
(GG) Ais l ds dj
0; vJ = =log
(23)
Accordingly, the GCN model can be unified the following matrix factorization
VVT log
log (k),
(24)
co-training with the classification loss lelass, where node representations V are unitized. is diagonal degree matrix with D d4. Moreover, according to the conclusion in (Qiu et al. 2018 the unified matrix of GCN Eq. 24 is as the same as the unified matrix of LINE with the second order proximity (Tang al. 2015b), except there two representation matrices in LINE. More specifically, the matrix factorization in Eq. (24) as the same as LINE with the first order proximity, which is implicit matrix factorization.
Our theoretical analysis on GCN summarized as:
Conclusion 2.1 Given a connected graph G with adjacency matrix A. graph convolutional net- works can be unified implicit matrix factorization with (1) co-training with labeled node classifi- cation; (2) unitization of node representations.
3 CUMF ARCHITECTURE
In this section, based above analysis. propose alternative model to GCN named Co-training and Unitized Matrix Factorization (CUMF), Figure providdes an overview of the proposed CUMF model, which will be described in detail below.
5

---

Under review as a conference paper at ICLR 2020
Let 2; IR denote the feature vector of node and fi denote the first MLP in Figure Accord- ing to our theoretical analysis, given Di, we conduct vector unitization in fi (zz) to obtain V/ (the representation of node i)
f( = (x:)
(25)
According to the theoretical analysis in section 2 the structural part our proposed CUMF model should be implicit matrix factorization with negative sampling. Thus, latructure can be formulated as
lntructure - GET jEC:
(Ai, log (A (A(v))))) Ey Dlog (2 1. v))))
(26)
Furthermore, as in GCN, the classification loss lelass can be obtained
lelass
Σ iEL.
CrossEntropy (y,, softmax (f2(v)))),
(27)
where Ir is the set labeled nodes, 3/4 is the classification label node i and f2 the second MLP in Figure Combining Eq. (8), Eq. (26) and Eq. (27). we obtain the loss function of the proposed
CUMF model. That is to say. the proposed CUMF model needs to co-train the classification loss lelass with the structural loss lstructure.
In practice, like many supi-super models (Weston et al. 2012 Yang et al. 2016). when we do co-training, the structural loss lstructure and the classification loss letass alternately optimized. To be more specific, we frist pick batches of positive and negative edges, where we sample additional negative edges for each positive edge according to Eq. (26). For each batch, take gradient step for lstructure- Then we pick a batch of labeled instances and take a gradient step for lelass. We repeat this process until convergence.
In summary, the proposed CUMF model is based entirely on our theoretical analysis in section 2 Comparing with previous graph modeling methods (Weston et al., 2012 Perozzi et al.) 2014 Tang ett al. 2015b|a; Grover & Leskovec 2016 Yang et 2016)) the unique features of our proposed CUMF method are mainly illustrated in the unitization of node representations, which derived exactly from our theoretical analysis. Therefore, under the effective guidance of our theoretical analysis on GCN, the proposed CUMF model is extremely clear, concise and reasonable.
RELATED WORK
GCN (Kipf & Welling 2017) updates node representations with the aggregation its neighbors. Based on GCN, Graph Attention Network (GAT) (Veličkovié et al. (017)) proposes aggregate neighbors with taking the diversity of nodes into account.
The GCN model needs the whole graph structure. However, in large scale and complex real-world applications, we have millions of nodes and billions of graph edges. Thus, GCN is both time and space consuming, and is hard to perform in constrained memory or distributed computing. Random sampling (Hamilton et al. (0177) and importance sampling (Chen et al.) 2018b) propose sampling approaches to reduce the computation of aggregation. Instead of approximating the node represen- tations, variance controlled GCN (Chen et al.) 2018a) uses sampled node to estimate the change of node representations in every updating step. Cluster-GCN (Chiang et al., 2019) uses graph partition method to split the whole graph into a set of small sub-graphs, where aggregation happens within each small sub-graph. Thus, ClNster-GCN supports constructing mini-batches and distributed com- puting.
The original GCN only considers node features, while the features on edges are also important in graph. To take contextual features edges into account, RGCN (Schlichtkrull et al. 201 8) uses edge types to identify nodes' transition matrix. It achieves good performances in link prediction and entity classification. EGNN (Gong & Cheng 2019) treats edge features tensor and proposes the doubly stochastic normalization to avoid the element values of output features too big. Based on GCN and GAT, EGNN proposes EGNN(C) and HGNN(A) to handle edge tensor respectively.

---

Under review as a conference paper at ICLR 2020
Table 1: Statistes of the datasets.
Dataset
Type
#Nodes
#Edges
#Features
#C #Classes
Cora
Citation network
2,708
5,429
1,433
Citeseer
Citation network
3,327
4.732
3,703
Pubmed
Citation network
19,717
44,338
500
BlogCatalog
Social network
5,196
171,743
8,189
6
Flickr
Social network
7,575
239,738
12,047
USA
Air-traffic network
1,190
13,599
Europe
Air-traffic network
399
5,995
4
EXPERIMENTS
In this section, we empirically evaluate the performance of the proposed CUMF model in an all- round way. We first deseribe the datasets and settings of the experiments, then report and analyze the experimental results. Thorough and empirical evaluations are conducted to answer the following research questions:
Q1 What are the roles different components in the CUMF model (co-training unitiza- tion)?
Q2 How does the performance of our CUMF model compare to that of GCN on different datasets?
Q3 How the two hyper-parametern effect the performance of our method?
Q4 Comparing with GCN, is our proposed CUMF model more friendly to distributed com- puting?
5.1 DATASETS
We evaluate our proposed method based seven datasets. The statistic of the datasets are shown in T Cora, Citeseer and Pubmed (Sen al. 2008) are three standard citation network benchmark datasets. BlogCatalog and Flickr (Huang al. 2017) social networks. The posted keywords or tags in BlogCatalog and Flickr networks are used as node features. Therefore, these five datasets all have node features. By removing their node features and preserving only the node itself, we made Cora-F, Citescer-F, Pubmed-F, BlogCatalog-F and Flickr-F. In addition, USA and Europe are two air-traffic networks (Ribeiro al. (0077). where each node corresponds to airport and edge indicates the existence of flights between the airports. So these two datasets do not contain node features.
In summary, in terms of whether or not node features are included, we test our model on two types of datasets:
Structural Datasets: Europe.
Cora-F, Citescer-F, Pubmed-F, BlogCatalog-F, Flickr-F, USA and
Attributed Datasets: Cora, Citeseer, Pubmed, BlogCatalog and Flickr.
5.2 EXPERIMENTAL SET-UP
Firstly, to verify the roles of co-training and unitization, we include CUMF-C (Our method without co-training), CUMF-U (Our method without unitization) and CUMF-C-U (Our method without co- training and unitization) in our comparisons. Specifically, minus C in name means that the model training is conducted two stages. That to say, we first optimize the structure loss independently to obtain the final representations of nodes. Then we keep these representations fixed and only update the parameters of classification model when optimizing the classification loss. Accordingly, minus U in name means that the node representation will not be unitized. Secondly, compare against the strong baseline (Planetoid*) and the state-of-the-ans approach (GCN) as in (Kipf & Welling 2017). Lastly, test the performace of distributed CUMF, also include the baseline

---

Under review as a conference paper at ICLR 2020
Table 2: Summary of results in terms of classification accuracy (in percent) structural datasets.
CUMF-C-U
CUMF-C
CUMF-U
CUMF
GCN
Cora-F
50.78
55.13
51.17
69.11
65.64
Citeseer-F
33.32
35.46
35.36
46.24
44.36
Pubmed-F
43.62
42.23
44.41
66.15
58.26
BlogCatalog-F
45.76
52.94
60.85
67.64
67.07
Flickr-F
24.61
23.03
38.62
43.16
30.86
USA
42.47
50.35
60.61
58.26
53.93
Europe
41.13
40.38
50.00
50.98
41.43
Table 3: Summary of results in terms of classification accuracy (in percent) on attributed datasets.
Cora
Citeseer
Pubmed
BlogCatalog
Flickr
Planetoid*
75.73
64.72
77.20
84.71
70.90
GCN
81.20
70.30
79.00
65.20
62.8
CUMF
81.14
70.91
80.39
91.62
77.84
(Random-GCN) and the state-of-the-art method (Cluster-GCN) as in (Chiang et al. 2019) in our comparisons.
We implement methods Tensorflow. For the other methods, from their github pages. We use the Adam optimizer for all methods with weight decay as zero. And for all methods, report the mean accuracy of 10 runs with random weight initializations. For methods: mini-batch size 256, the dimension of embedding is 0.1* the dimension of feature, dropout rate 0.5, learning important byper-parameters: the number of negative edges (k) and the balance between structure loss and classification loss (b). We will analyze the effects of ls and b in next section.
the original papers' code
[0.001, 0.01]. As mentioned in section 3 there are other
5.3 PERFORMANCE ANALYSIS
Results of our experiments summarized in Table 2 Table 3 described in detail below.
Table 4 and Figure which will be
The Roles of Co-training and Unitization (Q1)
Firstly, we mainly examine the roles of different components of our proposed method (co-training & unitization). Specifically, the impact of different components on the capturing of structural in- formation needs to be verified. Thus we conduct experiments on structural datasets. According to Table 2 CUMF for semi-supervised node classification outperforms other versions of CUMF by significant margin. This fully verifies that unitization and co-training are two essential components of CUMF. Therefore, the correctness of theoretical analysis is also verified. Meanwhile, to be noted that, CUMF is superior to GCN on all structural datasets. This shows that CUMF is most likely to make better use of structural information than GCN.
CUMF vs. GCN (Q2)
After verifying that our proposed CUMF model inferior GCN in capturing structural in- formation, we directly compare CUMF, GCN and Planetoid* on attributed datasets. Based on the results shown in Table the performance of CUMF is consistent to that of GCN on Cora, Citeseer and Pubmed, and it has significant improvement BlogCatalog and Flickr. It is important to note that the average node degree of BlogCatalog or Flickr much higher than that of the former three datasets. That is to say, BlogCatalog and Flickr are denser graphs. Therefore, CUMF is consistent with GCN on sparse graphs and significantly outperforms GCN on dense graphs.
Previous work shows that the graph convolution operation is actually a special form of Laplacian smoothing, and starcking many convolution layers may lead to over-smoothing (Li et al. 2018). From this perspective, the reason might be that dense graphs over-smoothing than sparse gaphs. As mentioned in section 3 we optimize the structure loss by mini-batch gradient descent. Comparing with the graph convolution operation in GCN, the capturing
easier make GCN becoming
8

---

Under review as a conference paper at ICLR 2020
95
95
85
accuracy 01 test set
80
80
70
sccuracy
70
Cora
Cora
65
Citeseer
Citeseer
Pubmed
60
Pubmed
Blog
Blog
55
Flickr
Flickr
16
24
32
10
15
20
25
30
b
(a) Testing performances w.r.t. the number of negative (b) Testing performances w.r.t. the balance between samples for each positive edge.
structure loss and classification loss.
Figure 3: Testing performances w.r.t parameters introduced by our method (see section 3
Table Summary of results of distributed methods on attributed datasets.
Cora
Citeseer
Pubmed
Random- GCN
71.67
61.91
71.78
Cluster- CCN GCN
77.10
64.87
76.60
CUMF
81.11
70.88
80.32
of structural information our approach is much more flexible. Thus, our proposed CUMF model is less likely converge to over-smoothing. The following experimental phenomena in stability analysis also support this view.
Stability Analysis (Q3)
We also formally analyze the effects of two important mance. As mentioned in section 3 b controls the balance between classification loss and structure loss, and the number negative samples for each positive edge. We conduct empirical exper- iments attributed datasets, and the results are shown in Figure The flat lines in Figure 3[a) demonstrates that & has little effect on the testing performances of our proposed CUMF model. As shown in Figure b), for sparse datasets, b has little impact on the testing performances of CUMF. For dense datasets, i.e., BlogCatalog and Flickr, the performances of CUMF model decrease with the increasing of b. The larger value of b indicates the CUMF model pays more attention cap- turing structural information. This may give reason of the poor performances of GCN on dense datasets: the graph convolution operation easily be extremely over-smoothing for capturing structural information on dense datasets. On the other hand, CUMF is flexible with the sparsity of graphs via adjusting the parameter which is relatively stable.
(b & k)) on model perfor-
Distributed CUMF vs. Distributed GCN (Q4)
In the end, we verify the capacity of CUMF (our proposed method) and GCN on distributed com- puting in our experiments. Specifically, as the performances of centralized GCN is close to those of centralized CUMF on Cora, Citeseer and Pubmed, we only conduct empirical experiments on these datasets for convenience of comparisons. And we include Random-GCN and Cluster-GCN as baselines. Besides, our distributed experiments are conducted synchronous mode. Experimental results are shown in Table 4 On these datasets, distributed CUMF does not suffer performance loss. but distributed GCN methods greatly do, comparing with results in Table The reason that CUMF is MF-based, and MF-based methods naturally support constructing mini-batches (Zhuang jet al. 2013 Yu et al., 2014). However, for GCN, constructing mini-batches is equivalent to solv- ing graph partitioning problem (Chiang et al. 2019), which is actually quite challenging work

---

Under review as a conference paper at ICLR 2020
Karypis & Kumar 1998 Dhillon et al. 2007). Moreover, it is most likely that only small portion of each mini- batch is labeled, which may greatly affect the convergence of GCN.
6 CONCLUSION
To the best of our knowledge, CUMF the first work that connects GCN to MF. We theoretically unify GCN co-training and unitized matrix factorization, and CUMF model is therefore pro- posed. We conduct thorough and empirical experiments, which strongly verify the correctness of our theoretical analysis. The experimental results show that CUMF achieve similar superior per- formances compared to GCN. We also observe that GCN performs poor on dense graphs, while CUMF has great performances. This 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 extremely flexible and easy to be applied to distributed computing for large scale real-world applications, and significantly outperforms state-of-the-an distributed GCN methods.
REFERENCES
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Neural Information Processing Systems, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint 1rXiv:1801.10244 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2019.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(11): 1944-1957, 2007.
Rainer Gemulla, Erik Nijkamp, Peter J Haas, and Yannis Sismanis. Large-scale matrix factoriza- tion with distributed stochastic gradient descent. ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 69-77. ACM, 2011.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 9211-9219, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems, pp. 1024-1034, 2017.
Xiao Huang, Jundong Li, and Xia Hu. Label informed attributed network embedding. Proceed- ings of the Tenth ACM International Conference on Web Search and Data Mining, pp. 731-739. ACM, 2017.
Mohsen Jamali and Laks Lakshmanan. Heteromf: recommendation in heterogeneous information networks using context dependent factor models. In Proceedings of the 22nd international con- ference on World Wide Web, pp. 643-654, ACM, 2013.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on Scientific Computing, 20(1):359-392 1998.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Ad- vances in Neural Information Processing Systems, pp. 2177-2185, 2014.
10

---

Under review as a conference paper at ICLR 2020
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Qiang Liu, Shu Wu, Liang Wang, et al. Cot: Contextual operating tensor for context- recom- mender systems. Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 701-710, 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459-467, 2018.
Steffen Rendle. Factorization machines with libfm. ACM Transactions on Intelligent Systems and Technology (TTST), 3(3):7,, 2012.
Steffen Rendle, Zeno Gantner, Christoph Freudenthaler, and Lars Schmidt-Thieme. Fast context- aware recommendations with factorization machines. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pp. 635-644. ACM, 2011.
Leonardo Filipe Rodrigues Ribeiro, Pedro H P Saverese, and Daniel Figuciredo. struc2vec Learning node representations from structural identity. knowledge discovery and data mining, pp- 385-394, 2017.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassirad. Collective classification in network data. Ai Magazine, 29(3):93-106, 2008.
Yue Shi, Alexandros Karatzoglou, Linas Baltrunas, Martha Larson, and Alan Hanjalic. Cars2: Learning context-aware representations for context-aware recommendations. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Manage- ment, pp. 291-300 ACM, 2014.
Jian Tang, Meng Qu, and Qiaozhu Mei. Pte: Predictive text embedding through large-scale hetero- geneous text networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1165-1174, 2015a.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067-1077, 2015b.
Large-scale
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2017.
Jason Weston, Frdric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In International Conference on Machine Learning, 2012.
Jun Wu. Jingrui He, and Jiejun Xu. Demo-net: Degree-specifie graph neural networks for node and graph classification. arXiv preprint arXiv:1906.02319, 2019.
Zhilin Yang, William Cohen, and Ruslan Salakhutdinov.
Revisiting semi cemi-supervised learning with graph embeddings. International conference on machine learning. 2016.
Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In ACM SIGKDD International Conference Knowledge Discovery Data Mining, 2018.

---

Under review as a conference paper at ICLR 2020
Hsiang-Fu Fu Yu, Cho-Jui Hsieh, Si Si, and Inderjit Dhillon. Parallel matrix factorization for recom- mender systems. Knowledge and Information Systems, 41(3):793 (19,, 2014.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Neural Infor- mation Processing Systems, 2018.
Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, and Chih-Jen Lin. fast parallel sgd for matrix factorization in shared memory systems. In Proceedings of the 7th ACM conference on Recom- mender systems, pp. ACM, 2013.
12


Reviews:
[{"review_id": "Skx8x7nTuS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a new method for semi-supervised node classification by drawing connection between GCN and MF. The authors borrow the idea of convergence of GCN as Laplacian Smoothing. With this observation, the authors propose a joint loss with two components: classification loss and structure loss for the similarity between embedding of neighboring nodes. The authors train the parameters via optimizing the two losses alternatively. Experiments are carried out on seven networks with comparison to baselines.\n\nStrength:\n1. It is an interesting and innovative idea to draw connection between GCN and MF.\n2. The propose method is more suitable for distributed setting. With negative sampling for structure loss, both structure batch and classification batch can be constructed locally with only one-hop information.\n3. The authors carry out experiments on seven real-world networks with ablation study for components in the model. Moreover, the authors carry out comparison to baselines in distributed setting.\n\nWeakness:\n1. The connection of GCN to MF is very indirect. It holds only when the GCN converges to the Laplacian smoothing. It is not clear whether this holds empirically. Moreover, there are too much intermediate steps and approximation between the Laplacian smoothing to the matrix factorization. As far as I am concerned, the connection is closer to node embedding versus matrix factorization.\n2. Given that GCN serves as Laplacian smoothing, it would be great if the authors can simply add additional regularization on dis(h_i, h_i) for (v_i, v_j)\\in E. Moreover, there is no reference and description to the Planetoid* algorithm.\n3. The authors use alternative batches between structure and classification loss. It would be interesting to see if joint training the two loss in mini-batch among a node and its neighbors can leads to any difference.\n3. The authors report only accuracy as evaluation metrics. It would be better If the authors could report recall@K and F1 score as well.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJxxpshhYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper derives a matrix-factorization approach for node classification. The approach is closely related to GCN. The authors show that the proposed approach outperforms GCN and Planetoid empirically.\n\nThough empirically appealing, this paper has a few pitfalls that need be addressed.\n\n1. The wording \"unifying\" is a misnomer. The title \"unifying graph convolutional networks\" hallucinates a framework that unifies several neural network architectures, which is not precise. In reality, the authors propose a learning objective that consists of two loss terms, the classification loss and the structure loss. The classification loss is nothing but the usual GCN. The structure loss is the contribution of the paper. The derivation of this term starts from GCN and a Laplacian smoothing argument, and arrives at a matrix factorization form through a series of modeling modifications. By and large, the title is misleading.\n\n2. The wording \"correctness of our theoretical analysis\" is dubious. The paper does not present a theoretical analysis. The derivation of the matrix factorization is only a modeling process. In no mathematical sense the factorization is equivalent to GCN.\n\n3. The alternating training is questionable. The authors propose alternately optimizing the structure loss and the classification loss. Since taking the gradient of the whole loss function is straightforward in all graph neural network approaches, it is unclear why the authors prefer the alternating optimization approach. Supplementing a convergence plot and comparing the two approaches may help, if the alternating approach is indeed better.\n\n4. The \"distributed computing\" component needs more substantiation. It is unclear whether this phrase actually means the concept familiar by the parallel computing community. Therein, computation is done by using several machines communicated through networked protocols. Machine setting, parallel implementation details, and speedup are the primary interests in distributed computing. All information should be reported.\n\nQuestions:\n\n1. First sentence of section 5. What does \"all-round\" mean?\n\n2. Stability Analysis. What is b? The reader does not find a definition elsewhere. A probably related concept is alpha (see eqn (8)).\n\n3. Figure 3(b) shows that larger b leads to poorer performance. The authors state that a larger b means a stronger emphasis on the structure loss. Consequently, it appears that putting more emphasis on the structure term leads to poorer performance. Then, does it mean that the structure term is a useless contribution?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BylXmt2nYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe work poses an interesting question: Are GCNs (and GNNs) just special types of matrix factorization methods? Unfortunately, the short answer is **no**, which goes against what the authors say. \n\nUntil recently I thought like the authors, but the concurrent work [1] (On the Equivalence between Node Embeddings and Structural Graph Representations) https://openreview.net/forum?id=SJxzFySKwH changed my mind. \nThe work of (Li et al., 2018) shows that nearby nodes tend to get similar representations. There is mounting experimental evidence of that being the case in real-world graphs (e.g., https://arxiv.org/abs/1908.08572). But [1] shows that GCNs and GNNs are fundamentally different from matrix factorization methods, regardless of the loss function used to learn the embeddings. Consider Figure 1 in [1], and it is easy to see that matrix factorization will give different embeddings to the Lynx and Orca nodes, while GCNs and GNNs must give the same embedding. Even if we connect the graphs through the Spruce and the Zooplankton nodes, their conclusion would not change. Matrix factorization (as broadly understood) will give embeddings that can even be used to cluster nodes. The eigenvectors of the symmetric Laplacian encode the diffusion of a type of random walk and nodes that are far away in the graph must have different embeddings (because through the diffusion operator, they are far away).\n\nIn GCNs, the convergence of the embeddings is better explained by the mixing of a random walk (Theorem 1 of (Xu et al., 2018)), which, in the special case of a GCN, converges to 1/sqrt(degree of node), as shown by (Li et al., 2018) in their Theorem 1 for the symmetric Laplacian. This is unrelated to what we get in matrix factorization as explained earlier. \n\nWhat is wrong with the math: Equation (11) is equated with matrix factorization, but note that it does not account for nonedges, while matrix factorization accounts for nonedges. This issue is more clear in Equation (14). The problem happens when the paper jumps from Equation (14), which is correct but not MF, to Equation (15) which is MF but unrelated to Equation (14). The argument is that “negative edges sampling is used, for better convergence”… sorry, not for better convergence, it completely changes the optimization objective. Hence, GCNs are not matrix factorization methods.\n\nI think the paper is a valiant effort, but unfortunately the core premise is incorrect. The jump from Equation (14) to equation (15) cannot be justified, and I believe showcases a fundamental flaw the argument. I do not see a way to fix the paper. I vote to reject it. \n\n[1] On the Equivalence between Node Embeddings and Structural Graph Representations, https://openreview.net/forum?id=SJxzFySKwH \nXu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.I. and Jegelka, S., 2018. Representation learning on graphs with jumping knowledge networks. ICML 2018.\nLi, Qimai, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. AAAI, 2018.\n\n\n--------------\n\nRead rebuttal. Will keep my original assessment.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes an interesting attempt at connecting graph convolutional neural networks (GCN) with matrix factorization (MF) and then develops a MF solution that achieves similar prediction performance as GCN. 

While the work is a good attempt, the work suffers from two major issues: (1)  the connection between GCN and other related models have been examined recently. The paper did not provide additional insights; (2) some parts of the derivations could be problematic. 

The paper could be a good publication in the future if the motivation of the work can be repositioned. 
Decision: Reject