Unsupervised Learning of Node Embeddings by Detecting Communities
Authors: Chi Thang Duong
Dung Hoang
Truong Giang Le Ba
Thanh Le Cong
Hongzhi Yin
Matthias Weidlich
Quoc Viet Hung Nguyen
Karl Aberer
Venue:  (2020)
Keywords: Unsupervised Learning
Graph Embedding
Community Detection
Mincut
Normalized cut
Deep Learning

Abstract: We present Deep MinCut (DMC), an unsupervised approach to learn node embeddings for graph-structured data. It derives node representations based on their membership in communities. As such, the embeddings directly provide interesting insights into the graph structure, so that the separate node clustering step of existing methods is no longer needed. DMC learns both, node embeddings and communities, simultaneously by minimizing the mincut loss, which captures the number of connections between communities. Striving for high scalability, we also propose a training process for DMC based on minibatches. We provide empirical evidence that the communities learned by DMC are meaningful and that the node embeddings are competitive in different node classification benchmarks.

Under review as a conference paper at ICLR 2020
UNSUPERVISED LEARNING OF NODE EMBEDDINGS BY DETECTING COMMUNITIES
Anonymous authors Paper under double-blind review
ABSTRACT
We present Deep MinCul (DMC), an unsupervised approach to learn node em- beddings for graph-structured data. derives node representations based their membership in communities. As such, the embeddings directly provide interest- ing insights into the graph structure, so that the separate node clustering step of existing methods is no longer needed. DMC learns both, node embeddings and communities, simultaneously by minimizing the mincut loss, which captures the number of connections between communities. Striving for high scalability, we also propose a training process for DMC based on minibatches. We provide em- pirical evidence that the communities learned by DMC are meaningful and that the node embeddings are competitive in different node classification benchmarks.
INTRODUCTION
Graphs natural representation of relations between entities in complex systems, such social networks or information networks. To enable inference on graphs, graph embedding may be learned. It comprises node embeddings, each being a vector-based representation of graph's node that incorporates its relations to other nodes (Goyal & Ferrara, 2018; 8; Hamilton et al., 2017b). While supervised node embeddings have received lot of attention, most real-world graphs are not labelled, which calls for unsupervised learning techniques.
The main principle in unsupervised learning of node embeddings that "similar" nodes have close embeddings in the embedding space. The similarity of nodes is often defined based on their distance graph, e.g., based on their co-occurrence probability in a random walk (Goyal & Ferrara, 88; Perozzi et al., 2014; Grover & Leskovec, 2016). Recently, it also argued that two nodes should be similar, if they are similar to a graph summary representation (Veličković et al., 2018).
In this work, we argue that node embeddings shall not only be of high quality for inference tasks, but shall also be meaningful. That is, they shall directly provide insights into interesting structures in graph in order avoid potentially biased post-analysis step. e.g., through clustering of the embeddings. We therefore assess node similarity from the perspective of node communities, where the dimensions of embeddings are some unknown communities instead of some unknown latent features as in traditional techniques. Considering community as set of densely connected nodes with sparse connections to outside nodes, the homophily principle restated as follows: Nodes with similar community membership characteristics shall have close embeddings. Specifically, for each node, we incorporate membership information as a probability distribution over set of communi- ties. Then, nodes are similar, if they are both likely and unlikely to be part of the same communities.
Since communities are generally unknown, we propose minimize the mineut loss for unsupervised learning of communities and node embeddings simultaneously. Mincut loss leverages the principle that communities are well-separated there are few connections between them (Fortunato, 2010). It is theoretically motivated its optimal closed-form solution can be found, while its variant, the normalized cut, is a well-studied problem.
Aiming at realisation of the above idea, propose Deep MinCut (DMC), neural network ap- proach to minimize mincut loss. We learn node embeddings to sample one-hot vectors that represent the assignment of nodes to communities. The vectors drawn from distributions parameterized by continuous node embeddings using Gumbel-Sofine (Jang et al., 2016; Maddison et al., 2016). This renders the process differentiable and, thus, enables joint learning of embeddings and communities.

---

Under review as a conference paper at ICLR 2020
We demonstrate the applicability of DMC in various applications. In node classification, our node embeddings turn out to outperform traditional embedding techniques (Grover & Leskovec, 2016; Perozzi et al., 2014; Veličković et al., 2018), while also revealing the graph's 's community structure. In community detection, by stacking mincut losses, we are able to learn a hierarchy of communities, e.g.. when generating word embeddings, can link words to topies, and topies abstract themes.
2 RELATED WORK
Graph embedding constructs a low-dimensional model of the nodes of graph that incorporates its structure (Hamilton et al., 2017b; Goyal & Ferrara, 2018). Embedding techniques can be classified into shallow (Perozzi et al., 2014; Grover & Leskovec, 2016) and deep approaches (Hamilton et al., 2017a; Kipf& & Welling, 2016; Wu et al., 2019). Shallow approaches rely on an embedding lookup table to map nodes to embeddings. On the other hand, deep models construct node's embedding by performing aggregation of its neighbours' embeddings.
Unsupervised node embeddings. While different models may be employed to embed nodes (Per- ozzi et al., 2014; Grover & Leskovec, 2016), the majority of unsupervised learning techniques leverage contrastive loss function, such as skipgram loss (Hamilton et al., 2017b) or infomax loss (Veličković et al., 2017). The encoder is trained such that, given a scoring function, a high score is given to positive samples, whereas negative samples receive low score. For skipgram loss, the positive samples are nodes that are close in a random walk, while the negative samples are randomly selected from other graph nodes. A drawback of the random- walk objective is that it can only capture local information around a node (Perozzi et al., 2014; Grover & Leskovec, 2016).
For infomax loss, positive samples are nodes in the original graph, whereas negative samples are nodes in randomly corrupted graphs. While infomax loss can capture the global structure, its perfor- mance is highly dependent on the corruption strategy (Veličković et al., 2018). Since embeddings also need to be learned for the corrupted graphs, it further suffers from high training time. While our proposed method also considers the global graph structure, differs in that our approach non- constrastive, i.e., it does not require unnecessary learning of negative samples. Moreover, due to the nature of our loss function, we are able to learn the node embeddings as well as their clusters.
Community detection is a well-studied problem with many applications (Fortunato, 2010; Fortu- nato & Hric, 2016). While numerous techniques for community detection have been proposed, we focus on those that generate node embeddings, such as spectral methods (Newman, 2006b;a; White & Smyth, 2005). Spectral methods operate either on the modularity matrix (Newman, 2006b) or the Laplacian matrix (White & Smyth, 2005). While embeddings may be learned by reconstructing these matrices (Wang et al., 2016), existing methods leverage matrix factorization, which does not scale to large graphs. Closest to our work is (Nazi et al., 2019), which proposes partition loss function for graph partitioning. As the work focuses on graph partitioning. the loss function aims for balanced partitions based on the number of nodes and, therefore, is not applicable in our setting.
3 EMBEDDINGS AND COMMUNITY DETECTION
Graphs. We consider a directed, weighted graph G = FV with nodes V = { and edges F [ v,) | E V v V). each edge (v,, 0y) being assigned a weight ((r,,y)) E R. Such a graph can also be represented by its adjacency matrix A of size n x n, where each row and column represents a node in G and cell A.y denotes the edge weight. Note that we allow self- in the graph, but not multi-edges between nodes. Also, edge weights can be negative. We also consider attributed graphs in which nodes have features. We denote the node features matrix as F E RTXD
Communities. We denote by C (C1, C2,, CC the set of k disjoint communities of graph G, where U._ C V and V C, # C, C,nc, captured by membership matrix P E (0,1)nxc with rows representing nodes in & and columns representing communities in C. As each node is only assigned to one community, the rows of P are one-hot vectors, where P.j if node v; is assigned to community Cj.
O. The assignment of nodes to communities is
Assuming the membership matrix P is already known, the number of cross- coosscoonnectios between communities C, and C2 can be captured by the non-diagonal elements of the adjacency matrix C of
2

---

Under review as a conference paper at ICLR 2020
the quotient graph, where the nodes communities:
C= AP AP
(1)
On the other hand, elements C₁ capture the number of connections within community C,
Mineut loss. While community detection is well-studied problem, there is consensus on the precise notion of a community (Fortunato, 2010). A common principle is that well-separated com- munities have more connections inside than across communities. Hence, communities are detected by minimizing the number of connections between them, as captured by the following loss function:
(p(A) = - -==
where Tr(X) is the trace of matrix X. We call the loss function in Equation 2 mincut loss, it aims to minimize the number of connections between communities.
Degenerated cases. Minimizing Equation may lead to degenerated cases, where all nodes assigned to one community while the others are empty (Fortunato, 2010). In practice, there are two solutions to this problem. If there prior knowledge on the communities (e.g., they shall have equal size), respective constraint is added to the mincut loss. Another approach is to minimize the normalized cut (Shi & Malik, 2000; Zhang & Rohe, 2018), which is defined follows:
cul(Cr, C_i) assoc C; C_,)
P A)P,, Σ
à
Tr( (D - A)P, DT
PLLP P'
neut (C)
Tr(
D.
where C_; denotes the set of communities except C, and assoc(C,, C-i) is the total degree of nodes in community C, Then, the normalized cut (normcut) loss can be captured as follows:
LLL L
Cp(A) Tr(
(3)
PTP
where Leym I D D-1/2AD is the symmetric Laplacian matrix with D be the degree matrix of A and and L = D - A is the Laplacian matrix.
Graph-like data. For ease of presentation, mincut loss is formulated based graphs. Yet, it can be applied to any problem comprising a set T of items and a kernel function k T x T - IR that assigns weights item pairs. This creates kernel matrix K that can be considered as the adjacency matrix of the items. Mincut loss is designed to separate items into subsets such that the connection strength between every pair of subsets is minimized, which also means the coherence of each subset is maximized. Hence, mincut loss is applicable to a wide range of unsupervised problems.
4 DEEP MINCUT
We first discuss the spectral approach to find optimal solutions for normcut and mincut loss, as it provides a baseline technique for comparison. We then introduce Deep MinCut along with an efficient training process based minibatches.
4.1 SPECTRAL APPROACH
Since P is a binary matrix, optimizing the normcut loss to find P is an NP-hard problem (Fortunato, 2010). Following traditional approaches in community detection (Fortunato, 2010; White & Smyth, 2005), we relax P from a binary matrix to real matrix H Raxk However, for the relaxed matrix H to be meaningful, needs to retain the following semantic constraint from matrix that each node belongs to only one community: h = 0 where h, is the i-th column of the matrix H. The matrix H that minimizes Equation 3 can be found by eigendecomposition of the adjacency matrix L This is captured by the following theorem.
Theorem 1. Let L sym be the normalized Laplacian matrix of graph G of size n and its eigende- , > to be smallest eigenvalues of L sym and composition Lym QAQT. We also denote '
3

---

Under review as a conference paper at ICLR 2020
Membership likelhood matrix
Membership
embedding matris
Neural network
softmax
Community
adjacency
Mincut Minimize(
C- P'AP
Adjacency
Figure 1: Learning embeddings by detecting communities.
their respective eigenvectors 91.-.- , Let H E Raxk be a matrix that satisfies h,hy = 0. Then, ( = Tr( 1² L. is minimized when the i-th column vector of H. is parallel with the i-th eigenvector, iee. h, 1t q,-
H"
worth noting that closed-form solutions for the mincut loss can be found in similar manner where the matrix H that minimizes the mincut loss can be constructed from the largest eigenvectors of the adjacency matrix A. The proofs of these theorems can be found in Appendix C.
4.2 DEEP MINCUT A NEURAL NETWORK APPROACH
Although analytical solutions to Equation 2-3 can be found by eigendecomposition, such approach to minimizing the normcut loss is infeasible for large graphs. We therefore propose neural network approach called Deep MinCut to learn node embeddings and communities at the same time. Our framework illustrated in Figure 1, which we explain detail the remainder.
Learning the membership matrix. To detect communities, we want to learn the membership matrix P that minimizes the normalized (P(A) the assignment of nodes to communities. Intuitively, this assignment is based on node's is role in the graph and the graph structure, which is also the information that shall be encoded in node embedding (Grover & Leskovec, 2016; Hamilton et al., 2017a). Hence, we propose to compute the membership matrix based on node embeddings.
Pr(P"""" Recall that P captures
An embedding matrix H. which contains all the node embeddings, is derived by an encoder d-dimensional space, where 9 denote
Eo : V - Rdd The encoder Eo encodes every node in parameters. Any existing node embedding techniques such as graph convolutional encoders (Hamil- ton et al., 2017b; Wu al., 2019) shallow encoders (Grover & Leskovee, 2016; Perozzi al., 2014) can be used to realize Es, since the parameters 0 can be learned during optimization of the normalized cut. The node embeddings classification link prediction.
can also be used for downstream tasks such as node
Differential sampling. To obtain P from H. we sample one-hot vector p of P from the corre- sponding node embedding h of H. Intuitively, H.j shall capture the likelihood that the i-th node is assigned the j-th community. As such, we consider the elements hı,..., .., h& of h to be the unnor-
malized class probabilities of k-dimensional categorical distribution. Then, by sampling from this distribution, we are able to obtain the one-hot vector Sampling from this distribution can be done using the Gumbel-max trick (Gu et al., 2018; Niu et al., 2019) where the non-zero element of the one-hot vector p = (P.:....) .......P)) is found as follows:
L. if arg max, (hy + g) otherwise
P.
where g ~ Gumbel(O, 1) is a sample from the standard Gumbel distribution.
Note that the sampling process is still non-differentiable the arg operation is discontinuous since the Gumbel-max trick only makes sampling from a categorical distribution an optimization problem. By replacing the arg max function with the differentiable softmaz, however, render

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Computation of normcut loss.
input Adjacency matrix A, r, Straight-hrough st, embedding matrix H
output: Normeut loss
gumbel soft_sorfraarrro (H, st);
Sample one-hot vectors from node embeddings // Adjacency matrix of quotient grapä. // Compute the association of communities. is the vector of cnes. Diagenal vector // Compute the normeut loss
Hº AH:
1C:
d)agonal(C);
I (g d)/q:
= E.
return
the whole process differentiable (Maddison et al., 2016; Jang et al., 2016). That is, an element of p be sampled from the corresponding h of H as follows:
exp(xx/T)
Pj
exp(x1/T)
where h2 + 9 and is a temperature hyperparameter. Gumbel-Softmax (GS) not only allows to sample discrete values from a continuous distribution, but also differentiable. The latter important for learning the parameters of Eg using backpropagation. As the temperature т 0, the row p approaches the one-hot vector. The whole computation process of the normcut loss from an adjacency matrix and the node embeddings is shown in Algorithm 1.
Straight-through Gumbel-Softmax. Since want p be close one-hot vector, we need to set r to be close to O. However, a small temperature leads to high variance of gradients which makes the training process slow converge (Jang al., 2016). To this end, we use the Straight- through Gumbel-Softmas which allows to set high temperature while obtaining one-hot vector for p. This done by taking the arg max p; to construct the one-hot vector the forward pass, while in the backward pass, P; is used to compute the gradients. The trade-off is that there a mismatch between the forward and backward pass which makes Straight-through GS biased estimator. However, it performs well in practice (Choi al., 2018; 8; Gu et al., 2018; Niu al., 2019).
Hierarchical community detection. Several mincut losses may be stacked to learn a hierarchy of items. For instance, another mincut loss can be applied to the adjacency matrix C to learn super- communities. Then, communities and super-communities can be learned in an end-to-end manner, similar to the hierarchical pooling framework in (Ying et al., 2018). However, approach is unsupervised and may thus be used in applications where labels are not available.
4.3 MINIBATCH TRAINING
Sampling method. To improve scalability of DMC, parameters shall be learned with batches of nodes, instead of the whole adjacency matrix. This is equivalent to approximating mincut loss with sampled subgraphs. However, a simple random sampling of nodes to construct subgraph is not sufficient as the subgraph may not connected. Hence, optimization of normcut loss is non-tri trivial.
Against this background, propose construct ego-network for each node in the graph and use this ego-network as the subgraph. This sampling procedure is similar to the neighbourhood sampling method proposed by Hamilton et al. (2017a). Given node V, its ego-network of depth is the induced subgraph obtained from sample of all nodes with a distance of at most to Sampling is done each level, with replacement of fixed amount of neighbours. This is to make the subgraphs to have equal size. To create a batch of size b, we create b such ego-networks.
Theoretical motivation. We provide theoretical motivation why it is possible to approximate the normeut loss function with sampled subgraphs. Let K E m be the embedding matrix of the subgraph S of size m. We also denote the adjacency matrix of this subgraph as A, its degree matrix as D, and its Laplacian matrix as L. The following theorem shows that we can approximate normeut loss to a certain degree with high probability using the subgraph of size m < n where the number of nodes in the original graph.
Theorem 2. Let C = H. LH.., HH HH,,H.,
KT. L.
K. be the normcut loss of the graph G
and subgraph S with adjacency matrices A, A respectively. Let a, b R. be the upper and lower
5

---

Under review as a conference paper at ICLR 2020
Table Statistics of the datasets
Dataset
Nodes
Edges
Features
Classes
Cora (Sen al., 2008)
2,708
5,429
1,433
Citeseer (Sen et al., 2008)
3,327
4,732
3,703
Pubmed (Namata et al., 2012)
19.717
44,338
500
3
Wiki (Grover & Leskovec, 2016)
4,777
184,812
n/a
40
bound of A then if H is a binary matrix and elements of A and A are i.i.d then given an E 0. [-ms)²
P() S E) 2 (exp( (ma)²
(28k"(h-a)> +exp(
128k (288"(b-o) o37 + expp( =n²=a
04R(b-a) +exp( nak(bba)
2 exp(
me? + 2 exp( 8i
394k
Theorem 2 (proof in Appendix C) states that we can choose a batch size such that the difference in the approximated loss and the true loss is small with high probability. Other factors that affect this probability are the bounds a, b of its adjacency matrix and the embedding size k. Finally, the probability also depends on how accurately we approximate the loss function, as controlled by e.
5
EXPERIMENTS
5.1 NODE EMBEDDING EXPERIMENTS
Setup. We evaluate the quality of our embeddings for node classification four datasets, see Table Cora, Citeseer and Pubmed are paper citation networks where a label represents the domain of paper. Wiki is word adjacency graph with the word labels being their POS tags.
In this experiment, we use a onc-layer Graph Convolutional Network (Kipf & Welling, 2016) as the encoder for DMC and also report the results obtained with the spectral approach. We compare DMC with several baselines. First, we compare against community detection techniques that generate node embeddings, such as DANMF (Ye et al., 2018), M-NMF (Wang et al., 2017) and GAP (Nazi al., 2019). Second, we include unsupervised node embedding methods that use contrastive loss, such WeepWalk (Perozzi et al., 2014) and DGI (Veličković al., 2018). For all methods that involve randonization, we train three models with different seeds. The node embedding size is consistently set to 128. The obtained node embeddings are used to learn logistic classifier. Instead of fixed train/test split, we use 50 random splits and report the mean accuracy and standard deviation as suggested by Shchur et (2018).
Results. Table 2 highlights the benefits of generating embeddings by community detection for node classification. Our technique outperforms the baseline methods in three out of four benchmarks. The largest gap is observed for the Wiki dataset, which can be explained by the non-attributed nature of this dataset. DMC considers the whole structure of the graph, whereas most baseline techniques consider only the neighbourhood surrounding a node. While DGI is able to incorporate the whole graph, it relies more on node features, which is less beneficial for non-attributed graphs. The spectral approach underperforms significantly on the bibliographic datasets as it only uses the structure information in the graph. In addition, the optimal solution normeut loss may not be the best embeddings for node classification, as the node labels are more correlated to node features.
In addition node embeddings, DMC also learns how cluster the embeddings. We compare the cluster quality obtained by our approach with the best baseline for node classification, which is DGI. For DGI, we use k-means to cluster the node embeddings into several clusters where the number of clusters is the number of classes. Then, compare the cluster quality obtained using DMC and DGI on two metrics: Normalized Mutual Information (NMI) and Homogeneity (HG).
Table 3 shows that the cluster quality obtained by DMC is significantly higher than the one by DGL. For instance, the NMI scores with DMC are 7x better than those with DGI on the Cora dataset. This illustrates the benefits of jointly learning node embeddings and their clusters. This is particularly important in unsupervised settings, where the learned embeddings are fed into a downstream task, such node classification graph analysis through clustering.

---

Under review as a conference paper at ICLR 2020
Table Node classification results.
Method
Cora
Citeseer
Pubmed
Wiki
GAP
0.76
0,663+4.88
0.754
0.596#4.1e -3
Community
M-NMF
0.775
0.562:10.9c
0.763:10.3e
0.64
detection
NMF
0.
0.443.19.3e -a
0.672.17.4e
0,48511.99e -3
Feat.+Comm.
0.749-10.8e
0.709110.9c
0.851:10.2e
0.65910.1e:
Contrastive
DeepWalk
0.670.12.66
0.479:13.3e
0.722.1-4.9e
0.491
loss
DGI
0.813:10.3e
0.711
0.835:13.6e
0,568
Normcut
DMC (Ours)
0.88 0.303
0.71314.11="
0.833
0.659 14.
loss
Spectral
0.206
0.397
0.581
Dataset
Metric
DGI
DMC
1.0
NMI
0.061
0.429
Cora Citeseer Pubmed
Cora
HG
0.068
0.475
0.9
Accuracy
NMI
0.059
0.212
Citeseer
0.8
HG
0.067
0.264
NMI
0.172
0,215
0.7
Pubmed
HG
0.191
0.277
0.6
NMI
0.272
0,286
20
50
100 200
300 400 500
Wiki
HG
0.345
0.339
Batch size
Table 3: DMC vs. DGI on cluster quality
Figure 2: Effect of batch size
5.2 COMMUNITY DETECTION EVALUATION
Setup. Next, we aim to show the applicability of normcut loss to graph-like setting, such as learning word embeddings. Here, the nodes are words and the connection weight between two words is measured by the following "kernel" function:
k(w; wx) mar( log(# (w,, w)))
(ow(#w,))) (og)::ooog(H)) log(#w,))
where #w; is the number of times word w; appears in the corpus, while #(w, w;) is the number of times the words appear together. The adjacency matrix obtained using the above function is the PPMI matrix, well-established concept in NLP (Levy & Goldberg, 2014). Following Yin & Shen (2018), we construct word corpus of 10000 words that appear >00 times in the Text8 corpus (Mahoney, 201 1). Words are said to appear together if they are within window of five.
We further analyse the quality of the communities constructed by DMC. As those are represented by the dimensions of the node embeddings (in this case, word embeddings), high-quality communities correspond to explainable word topics. We evaluate explainability by a word intrusion test. We create set of five words for each dimension by selecting the top-4 words and single low-ranked word. Human workers on MTurk are asked to detect one word per dimension that does not belong to the respective set. The detection precision then measures explainability. We compare DMC against explainable word embeddings techniques, OIWE (Luo et al., 2015), Sparse Coding (SC) (Faruqui al., 2015), and Non-Negative Sparse Coding (NNSC) (Faruqui et al., 2015). For qualitative analysis, we also report the words with the largest embedding values along exemplary dimensions.
Table 4 shows that DMC outperforms state-of-the-art methods in precision of the word intrusion test. Note that NNSC, SC, and OIWE require additional data such as existing word em- beddings input, whereas our methods learn explainable word embeddings directly on word corpus. Table shows that the top-ranked words indeed assign a meaning to each dimension (here, the first three dimensions concern medieval literature. DC comics, and transportation). By stacking two normeut losses, DMC is also able to learn a hierarchy of words and topics. Figure 4 gives an example, where super-topic #18 captures IT-related words, while supertopic #3 is related religion.
Results.

---

Under review as a conference paper at ICLR 2020
Table 4: Test Precision
Table Top-5 words for the first five dimensions
Precision
#1
Dim
Dim
Dim
Dim #5
NNSC
35.85%
medieval carliest
created features de adaptation batman aviation
flight
full
internet network
SC
47%
pilot
job
OIWE
91.01%
scholars
navy
fair
client
DMC
95.24%
renaissance classical
passenger
offered server
calling
servers
#5
=0
#com-33 35
0.74
Supertopic #3
0.73
0.72
Dim
#72
0.71
0.5
hell seaven
luther accepted prayers
reforred Eaptist
bichaps for Coriidonn practiioe clengy
0.63
0.62
Supertopic #18
0.60
Dim #187
Dim #244 cluster distibutied computing
Dam P231
Dim #208 server adoresses messagges
0.59
0.3
control component slack program
0.58
compatible system
#com-10
#com-S
#com Embedding size
#com+5
#com+10
Figure 3: Embedding size vs. #communities
Figure 4: Hierarchy of words/topics
5.3 EFFECTS OF MINIBATCH TRAINING
Setup. We evaluate the effects of minibatch training on the classification accuracy on three citation networks by varying the batch size from 20 to 500.
Results. Confirming our theoretical analysis, Figure 2 shows that the difference between the approx- imated loss and the true loss depends on the batch size. With increasing batch sizes, the accuracy on the Cora and Citeseer datasets increases as well. However, after initial sharp increase. the differences become smaller. This shows the robustness of our approach to the batch size. Moreover, observe reversed trend the Pubmed dataset, which is the largest among the citation graphs. We believe that this can be attributed to the stochasticity of minibatch training, which renders outlier nodes to be less important the subgraphs can only cover parts of the whole graph.
5.4 RELATION BETWEEN EMBEDDING SIZE AND NUMBER OF COMMUNITIES
Setup. The aim of this experiment is two-fold. First, aim to show the merit of the mineut loss. While the normcut prevents degenerate cases, the mincut loss is useful if we have prior knowledge about the graph structure. Second, want to analyze the effect of the embedding size the number of communities. For this experiment, we need ground truth number communities, which why rely the Stochastic Block Model (SBM), well-established benchmark for community detection (Chen et al., 2019; Fortunato & Hric, 2016; Fortunato, 2010). Using SBM, a graph with known number communities (#com) is generated. Then, construct node embeddings with varying dimensionality using the spectral approach for mincut loss with an additional balancing constraint on the community sizes. The parameters of SBM are discussed in detail in Appendix B. Node embeddings are assessed for link prediction with the ROC metric (avg over 100 runs). We chose two values for parameter p. the probability of an edge between two nodes in a community.
Figure 3 confirms that "there is sweet spot for the dimensionality, [-] neither too small, nor too large" (Arora et al., 2016). Our results provide one possible explamation for the dimen- sionality trade-off. If the embedding size is smaller than the number of communities, unrelated communities are combined, lowering the ROC. If the embedding size is larger than the number of communities, communities since the model has higher capacity. In practice, the embedding quality tends to increase and then stabilize, with increasing embedding sizes, due to the communities often having different sizes.
Results.
split up further. This also decreases the ROC, but not drastically,
8

---

Under review as a conference paper at ICLR 2020
6 CONCLUSION
We presented a novel perspective on unsupervised learning of node embeddings. Following the idea of community detection, we proposed Deep MinCut (DMC), approach to minimize the mincut loss function to learn node embeddings and communities simultaneously. DMC learns node embed- dings that are not only of high quality, but are also meaningful as they capture the graph's structure. We demonstrated the value of node embeddings learned with mincut loss in diverse experiments.
REFERENCES
Karim M Abadir and Jan R Magnus. Mairix algebra, volume 1. Cambridge University Press, 2005.
Sanjeev Arora, Yingyu Liang, and Tengyu Ma. simple but tough-to-beat baseline for sentence embeddings. In ICLR, pp. 1-16, 2016.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. ICLR, pp. 1-23, 2019.
Jihun Choi, Kang Min Yoo, and Sang-goo Lee. Learning to compose task-specific tree structures. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama, Chris Dyer, and Noah Smith. Sparse overcomplete word vector representations. arXiv preprint (lo::156600004 2015.
Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5);75-174,22 2010.
Santo Fortunato and Darko Hric. Community detection in networks: user guide. Physics reports, 659:1-44, 2016.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge- -ooweddge-Based Systems, 151:78-92 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Jiatao Gu, Daniel Jiwoong Im, and Victor OK Li. Neural machine translation with gumbel-greedy decoding. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems, pp. 1024-1034, 7a.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2b.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameteriization with gumbel-softmax. arXiv preprint arXiv: 1.01 144, 2016.
Thomas N Kipf and Max Welling. Sepi-supe classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02277 2016.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Ad- vances neural information processing systems, pp. 2177-2185, 2014.
Hongyin Luo, Zhiyuan Liu, Huanbo Luan, and Maosong Sun. Online learning of interpretable word embeddings. In Proceedings of the 2015 Conference Empirical Methods in Natural Language Processing, pp. 1687-1692, 2015.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:161 1.0o:1221.0002,,11 2016.
Matt Mahoney. Large text compression benchmark. URL: http://www. mattmahoney. net/text/text.
hmm, 2011.

---

Under review as a conference paper at ICLR 2020
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driver active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, pp. 8. 2012.
Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. arXiv preprint arXiv:1903.00614 2019.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006a.
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):557-88882 2006b.
Xing Niu, Weijia Xu, and Marine Carpuat. Bi-directional differentiable input reconstruction for low-resource neural machine translation. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, Volume (Long and Short Papers), pp. 442 448, 2019.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In SIGKDD, pp. 701-710. ACM, 2014.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-955 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojehevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ 1.05868,, 2018.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. Departmental Papers (CIS), pp. 107, 2000.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003, 2017.
Petar Veličković, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. arXiv preprint arXiv:1809.103411 2018.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 1225 1234. ACM, 2016.
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community preserving network embedding. In Fhisty-First AAAI Conference Artificial Intelligence, 2017.
Scott White and Padhraic Smyth. A spectral clustering approach to finding communities in graphs. In Proceedings of the 2005 SIAM international conference on data mining, pp. 274-285. SIAM, 2005.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv:1902.071:: 2019.
Fanghua Ye, Chuan Chen, and Zibin Zheng. Deep autoencoder-like nonnegative matrix factoriza- tion for community detection. In Proceedings of the 27th ACM International Conference Information and Knowledge Management, pp. 1993-1402.0 ACM, 2018.
Zi Yin and Yuanyuan Shen. On the dimensionality of word embedding. In Advances in Neural Information Processing Systems, pp. 887-898. 2018
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810, 2018
Yilin Zhang and Karl Rohe. Understanding regularized spectral clustering via graph conductance.
In A Advances in Neural Information Processing Systems, pp. 10631-10640, 2018.
10

---

Under review as a conference paper at ICLR 2020
c0cm-=2 c5com=25
@coom=30 #com-33
[)#com=20 0 0
& #
=5
0.74
0.69
0.68
2 0.72
0.5
0.66
0.4
0.70
0.65
#com-10
#com+5
#com+5
#com+10
0.66
8
0.70
8 0.64
0.68
0.62
p
#com-10
#com-5
#com Embedding size
*com+5
#com+10
#com-10
#com-5
#com
écom+5
#com+10
Embedding size
Figure 5: Relationship between embedding size and #communities
A ADDITIONAL EXPERIMENTAL RESULTS
A.1 RELATIONSHIP BETWEEN EMBEDDING SIZE AND NUMBER OF COMMUNITIES
Taking up the discussion in Section 5.4, Figure 5 provides additional results with different values of p for the Stochastic Block Model. We observe that the ROC scores increase with p. This is expected as larger p values correlate with clearer community structure, which yields better link prediction. On the other hand, with smaller values, we observe the dimensionality trade-off better. As p decreases, the graphs converge towards random graphs with community structure. As result, it is easier for the model to cluster nodes into communities incorrectly. This effect becomes more severe when the gap between the embedding size and the number of communities is larger. The reason being that the model is forced to cluster nodes into communities that may be larger or smaller than actual communities.
B DETAILS ON DATASETS AND HYPERPARAMETERS
B. HYPERPARAMETERS
The embedding sizes of all methods are set to 128 achieve a fair comparison. For methods that use deep models (DMC, DGI, GAP), we use learning rate of 0.001 and Adam the optimizer. All methods are trained for fixed number epochs, namely 3000. For DMC, since we use Straight- Through Coumeel-Softmas we fix the temperature to be 1. For minibatch DMC, of 100 and two-layer neighbourhood sampling, where 10 and 25 neighbours are used in the first and second layer. For word embedding experiment, use shallow encoder for DMC. For experiments with k-means, we take the average scores (NMI and HG) over 10 runs.
a batch size
B.2 DATASETS
Node embedding experiments. Cora (Sen et al., 2008), Citeseer (Sen et al., 2008) and Pubmed (Na- mata al., 2012) are three standard benchmark datasets for node classification. Traditionally, fixed train/test split is used to evaluate the node embeddings. However, Shchur et al. (2018) showed that using random splits for evaluation is fairer for different methods. As these datasets attributed. we also include the non-attributed Wiki dataset Grover & Leskovec (2016). For this dataset, we initialize the node features using truncated SVD, setting the feature size to 128.
Word embedding experiments. To learn the embeddings, we use the Text8 corpus Mahoney (2011) which is a standard large-scale benchmark for various NLP tasks. To construct the PPMI matrix, we leverage library that is publicly available' and use the same setting as in Yin & Shen (2018) to build the vocabulary and count the co-occurrences of word pairs: A window size of 5 and minimum occurrence of word of 100.

---

Under review as a conference paper at ICLR 2020
Stochastic Block Model (SBM). To build graphs from the SBM, we leverage the networkx library." The parameters of SBM include the number of communities #ncom, community sizes and the prob- abilitty of edges between nodes in a community p. We use the balanced SBM where the community sizes are set to be equal to 100, while we vary from 0.3 to 0.5 to generate the graphs. From we 1-p
can compute the probability of connection across communities as p = 1- #ncomm graph becomes a random graph with no community structure.
When p ~ p, the
B.3 HARDWARE
Experiments were conducted workstation with Intel Core i7-6700K CPU @ 4.00GHz with 32 GB RAM and an Nvidia GTX 1080Ti GPU with 12 GB and server with 2 nodes. Each node includes an AMD Ryzen 1900X CPU with 64GB RAM and Nvidia GTX 1080Ti GPU with 12 GB.
C PROOFS
C.I ANALYTICAL SOLUTION FOR MINCUT LOSS
Theorem 1. Let M be a positive semi-definite matrix of size n. X n. and its eigendecomposition M = =QQQ.. We also denote '1.".. .mm to be largest eigenvalues of M and their respective
eigenvectors "1."." .4m= Let H R be matrix that satisfies (h,, h2) 0 then (H(M) =
-Tr(H"MH) MH) is minimized when the i-th column vector of H is parallel with the i-th eigenvector ieh,, 11 q-
factorize any matrix H UX by unitary matrix U of size diagonal matrix X of size m. We denote XX" = diag(21, Z2, ..., ..,)m) and U1 is the matrix leading columns of U. We also denote 1 to be the identity matrix of size l k. Then, we have:
Proof. Note that
and
(M = Tr MH) = -Tr(HTTHHHHH M) = UUXXX
m
m
--Tr(
2 U - U M))
ao - - Σ
By applying the Poincare Separation Theorem Abadir & Magnus (2005), we have Vk I, m. Tr,, MU1,s) is maximized iff Vk 1, m, the column vectors of U1 proportional to l leading eigenvectors M. In addition, as the column vectors of U or U are proportional to the column vectors of H. (M) is minimized iff the column vectors of H are proportional to m leading eigenvectors of M. In other words, the column vectors H are parallel with m leading eigenvectors of M.
C.2 ANALYTICAL SOLUTION FOR NORMCUT LOSS
Let sy the normalized Laplacian matrix of graph G of size n and its eigende- composition L QAQT. We also denote Xy. AA& be smallest eigenvalues of sym and their respective eigenvectors q....., .q.. Let E jaak be matrix that satisfies h.hţ 0 then (L = Tr( 1."'' is minimized when the i-th column vector of H. is parallel with the i-th eigenvector h, tt q.
Theorem 2.
H"H и
Proof. We can see that if we multiply h; with an arbitrary number, the value of (L is unchanged. So that we can assume H' H = With this assumption, the problem becomes finding H to minimize Tr(H H)
Let μI 2 2 ... 2 Ph be the eigenvalues of H S H and \ 2 A2 2 ... 2 An be the cigenvalues of L sym Then, according Poincare's seperation Poincare'seperation theorem, we have:
hhtps://nttworxx.giiue
12

---

Under review as a conference paper at ICLR 2020
k
As
(4)
Noting that Ex= P4 T L
H). This means Tr(H' sym H) minimized at Σ An An- when h, is proportion with & smallest cigenvectors of L Lam
b+
While the closed-form solutions for the mincut and normeut loss both be constructed from eigendeconposition, there are difference in application. The normcut loss is able to prevent degen- erated cases since they do not correspond the optimal loss value. On the other hand, for these degenerated cases, the mincut loss is minimal.
C.3 APPROXIMATED NORMCUT LOSS
Before proving Theorem 2, we provide the following lemmas.
Lemma 1. Given æ : y = 3. =
S 2 and P b-d
d
< 2 1
g with small
then P
2 z-v
< 2c) 2 (p +
Proof. We consider the case where z, 2 0 as similar result can be proved for x, 0. Let a = (1 + oc and b = (1 + 3)d. Then, we can rewrite the above statements as
PQ S 2 1-p
P(a| I 21
This also means:
= P(3 S c <) 2 (p+
Moreover, when B| S and al
S E with small E, we have
(1+ acc
(1 6)c
(L-E)
x
(1 + 8)d
(1 + e)d
(1+ 2 (1 -2e)y
Similarly,
(1 8)
< (1 + 23)y
(1 e)d
So that, if] S and |a| S 8, and a small value E, we have
y
2
Therefore, we have P(
z- 9
< 28)
> 1 - (p + q) with small
Lemma 2. Let X1, X2, Xm be m independent random variables such that P(x; = 1) = b, Let
X X X; and μ = [[ Then, for 0 < 8 < 1, P(X s (1- б)μ) exp(-po² /2)
Corollary 1. Let H {0, 1]nnk be an arbitrary binary matrix where the number of 1 elements in H is n. Let ps be the ratio of in column h2, then, P(p: 2 + 2 exp(
=n
8k
Proof. Applying Lemma with x; is p: Vi 1,K, p = Espd] = and 1/2.
Lemma 3. (Chernoff bound) Let œ1. 22, .... Zm is m random variables with Poisson distribution with Paz = 1) = P ΣØ Fj and, μ = E[ We have, V8 (0,
X
8²
p
6) S Bexpp--13
1
13

---

Under review as a conference paper at ICLR 2020
Lemma 4. (Hoeffdingg' is bound) Let 21, ....... Im is m independent random variables. B[xy] p4, P(a - Y, $ b) = 1vi. With arbitrary reals a and b, We have.
1 T
n
-2182
P
P
S 8) 2 -2expl
(b a)
Theorem 3. Let be a graph with its adjacency matrix A and its subgraph S with adjacency matrix A. Let a,b E I be the upper and lower bound of A then if Н {0, 13nxk and K
{0, 1) and elements of A and A are i.id then given an 2 O. P( k. Ak.-c.h; Ad. 3
o.h. Ah.
(ns)) 1 - 2(exp( 1288 ayz + exp( (-me)² 128K (b
m² (b-a)7 + expl
-me² 394E
8E 1, where hi, ks, are exp(
the i-th column vectors of H. K and c n
Proof. Let nxx) be the counting function for the number of elements binary vector or matrix. We also denote p; to be the ratio of elements vector h, As K is sampled uniformly from and with n large enough, we can assume that each element of k, is equally chosen with probability Pi-
Then, n (k.) is random variable for the number of elements in vector k, We also have nkk))
Σj=1 K,, which means [[]((;;)] = mp, with P PK j.z 1) = Pt.
Then, by applying bound (Lemma 3 with X n (k;)) 5 and μ B|n(k;)] mp,, we have
n (k:) mpi
E²
P
S exp( (-pp- mp: 192
mpt
Denote
m n we have n nh:;) = np: which means mp: (v.n(h.) Therefore, we have:
n (k,) (hn(
E 2 1 2exp(-mpp 192
P
Von(h,)
8
n(k;)² cn((t,))
g²
+ P
2 1 - 2 2xxp(-1e 1mpp
(5)
cn(h:)2
192
Note that n(kkk)
ni nk:))² 2 and n n(hth))))
n2:))² which make the above inequality equivalent
with:
PC n (o[K,,,]] - ch,
A1 m
E²
N 11 -1-20 2expeexpp-- mmp; 192
(6)
cn(h,h!
Since elements of A are i.i.d and bounded by 6, we have h. Ah; = =EjEr Y, with J S [1,
and [J] = n(h,). Similarly, k.j Ak; = -Ejer Y, with T C and = nkk)).
Applying lemma 4, with h. Ah, K. BK; and 8 = 5. we have
p AZ, n nT6,7o7 mn| ni n(hhh Je
n hh, s²
2exp(
8
32(b - a)²
and,
niki;k )o,
mm kk:kk )E²
P( Al; nkkkki nH4| S
eexp(
8
32(b - a)
Moreover, since n nk(kkk)))
(m..:)² and n n(;hhh,)))) ) (n.p:)2 we have
k Ak;
n nkkkke )p
h Añ; n(Tette )
P
5
8'
n(h:h))
8
> 1 2((exp( - (2ppt)}
exp( (-mpie)2
32(b 2 (7)
32(b a)²
14

---

Under review as a conference paper at ICLR 2020
A 1 m(
k Ak;
Ah
3 P
1
[k,k ) fo Ah; m(hch, )
2 1 (exxp( (npte)²
(-mpie)²
+ exp(
(8)
32(b - a)² -a)
32 a)2
Applying Lemma for inequality and have,
P( k Ak; - -c.h, Ah;
S E 2 2(exp( - (npte)²
c.h.! Ah;
2
32 a)²
mmp;;)
-mpps
+ exp
+ exp(
))
(9)
32(b
a)²
192
From Corollary 1, we also have
1
exp( n
P(p:
(10)
2k
8k
From inequality (9) and (10), we have,
k Ak; c. Aht
E
{nE)²
Pl
21 2(exp(
c. Ah;
2
128k (b a)²
(-me)²
-me²
-
+ exp(
exp(
exp(
(11)
128k2 a)²
394k
8k
Theorem 4. Let G be a graph with its adjacency matrix A and its subgraph S with adjacency
matrix A. Let a, E Th. be the upper and lower bound of A then if H E {0, 10,1 and K
{0,1)mxe and elements of A and A are i.id then given an & 2 0, P Al c.h.
S 2
c. Al
1 1- (exp( = 61k(b-o)²) + exp( ==²= 61k(b-a)2 ) + exp( exp(=m=²) you
)) + exp( 8k Vi I, m and c
m² n
Proof. (Proof sketch) Theorem 4 can be proven in the same manner as Theorem 3.
Given the results in Theorem and Theorem 3, we can now prove Theorem 2.
Theorem 5. Let = Σt
A Lh. Li=l DAD
-= It
be the normcut loss of the graph G and be Di:
i Lkk
subgraph S with adjacency matrices À respectively. Let a. E IR be the upper and lower bound of A then if H is binary matrix and elements of A and A are i.i.d then given & 2 0, (-me)²
P() e)
? (expl 128h (b-o7// ) +expl 128k (b-="(ba)) a)? + +expl 64k(b-a)* + 64k(b a) +
-(ng)²
2
2 expp 394K
me
+ 2 2exp( =D))
DAD ATDA,
AT k.
> (A)R, D'
Proof. First, since A-
This
DT
means optimizing L, E is equivalent to optimizing L
Ahe
Z=
& Ak: D.
Dh:
Second, observe that both L and C are the sum of terms. Thus, proving C-C prove
S is similar to
C; - E
< < I,T
(12)
C,
A.T Añ. b. DA,
R. AR: kT DA,
which L,
C.
15

---

Under review as a conference paper at ICLR 2020
Algorithm 2: Minibatch forward propagation of Deep MinCut
input
Adjacency matris A graph (4
Temperature
Straight-through-..
Encoder E
Sampling method
output: Node embedding matrix
Community assignment P
1/ 1.
Banpling minibatches of nodes
S(V)
A' A,U,U]
F[U]
// 2. Compute the node embeddings
H C,(A',
// Dsbed nodes in batch using the encode:
1/ Compute mincut
P gumbel softmar T,,
// Sample one-hot vectors from node embeddings
C H² :':
// Adjacency matrix of the quotient grapa. // Compuze the associstion of commuitiiss. is the vector of cnes. Diagonal
q IC:
dbagonal(C);;
of C. // Compute the normeut loss
I (g d)/q:
11
From Lemma 1, to prove inequality 12, we need to have the following results:
k Ak: c.h. Ah;
(13)
c. Ah;
2
And, the second is
k DE; - c.h. Dk:
E
(14)
c.h. Dk:
2
K. A1 c.h.J A1
Vi
1,
(15)
c.h.J A1
2
where
m
Inequality 13 is proven in Theorem 3 while Inequality 15 is proven in Theorem 4.
D ALGORITHM
Algorithm illustrates one iteration the forward pass of DMC. The forward pass include steps. In the first step, sample subset of nodes of the graph (Line 1) using sampling strategy. In our work, we use a neighbourhood sampling strategy as discussed in Section 4.3. From the sampled nodes, we extract submatrix from the adjacency matrix A in Line 2 and from the node feature matrix F Line 3. The second step involves constructing the node embeddings for the sampled nodes. We use an encoder Eg embed the nodes in Line 3. The encoder can be shallow which does not use the node features or a deep encoder. In our node classification experiment, we use 1-layer GCN discussed in Section 5.1 and shallow encoder for our word embedding experiment. In the last step, we use the node embeddings to compute the mincut loss shown in Figure 1. From the loss, we can backpropagate and update the parameters of encoder using any automatic differentation framework.
16


Reviews:
[{"review_id": "SylKtUbCFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Although this paper seems to only combine existing techniques in community detection and node embedding into a co-train process. The idea is simple and easy understood and the paper is well-written. Theoretical analysis is provided for the approximation error for the sampling strategy. However, major concerns are:\n\n1. Experimental results show that co-training node embedding and community detection can improve the performance for node classification. The improvements may result from the assumption that papers with the same class label are associated with the same community in the citation graph. However, in the dataset, there are many cases that there are not dense connections among the same labeled papers. The authors should check the correlation between the detected communities and the original paper labels.\n\n2. No comparison with other community-preserving node embedding methods, such as \"Community Preserving Network Embedding\" in AAAI17\n\n3. Since this paper aims to combine community detection and node embedding process, a set of baseline should be considered. For example, if considering the downstream node classification of node embedding as an evaluation task, then how about the performance of the following two-step method. We can first detect communities based on the node features then do graph node embedding by considering the communities' membership and node features together (e.g. simply concatenating both community membership features and node features).\n\n4. Efficiency and scalability evaluations are needed. Spectral clustering has a scalability issue when meeting big graphs. Since the spectral process is also applied in the proposed method, efficiency and scalability evaluations are encouraged to provide, especially for big graphs which are not covered in the selected datasets in this paper.\n\n5. In Sec 5.3 and Fig 2, it's mentioned that trends of the three datasets are different. For the increasing trend, how about the performance for an extreme case where all nodes are considered in one batch. On the other hand, adding more nodes in one minibatch could provide more information, but why there exists a decreasing trend? Though the authors provide a reason in Sec 5.3, it's better to analyze the reason directly from the datasets.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklTIir0FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 work proposes a neural netowrk approach to minimize mincutloss, thus achieving embedding nodes and find communities at the same time. However, it is difficult for me to understand the paper and I feel that it is not clearly written.\n\n1. The algorithm is not written in a box as in Algorithm 1. At first I thought algorithm 1 is the main method, but only after reading it I realized that it is one step of the algorithm. I would appreciate it if the complete algorithm (including input, output, parameters) can be summerized clearly.\n\n2. I am confused about the claim \"spectral approach underperforms significantly on the bibliographic datasets as it only uses the structure information in the graph.\" I thought the input of all methods are the adjencency matrix A.\n\n3. In table 2 and table 4, why does the paper compare different methods with different measures? Is it possible to compare all methods using all measures?", "extra_scores": {"experience_assessment": "I do not know much about 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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Bkg1cfOhYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 is reporting an unsupervised approach to learn node embeddings and communities simultaneously by minimizing the mincut loss function. This approach programs the data through encoder to generate membership likehood matrix H, and then generates corresponding membership matrix P using node selection. The matrix P and adjacency matrix are coupled to generate community adjacency matrix to minimize the cutting. However, despite such attractive points, the novelty and strength of this study is not outstanding enough for publication in ICLR. Details comments are as follows,\n1. Similar work such as the methods of transferring matrix E to H then to P have already been published , which reduce the novelty of this study.\n2. Though there is a schematic, the learning embedding process is still not described clearly. More details of the algorithms need to be discussed to such as how to get the node embedding matrix E.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an approach to learn node embeddings by minimising the mincut loss which ensures that the network simultaneously learns node representations and communities. To ensure scalability, the authors also propose an iterative process using mini-batches. 

I think this is a good paper with interesting results.  However, I would suggest that the authors try to make it more accessible to a larger audience (2 reviewers have indicated that they had difficulty in following the paper). For example, while Theorem 1 and Theorem 2 are interesting they could have been completely pushed to the Appendix and it would have sufficed to say that your work/results are grounded in well-proven theorems as mentioned in 1 and 2. 

I agree that the authors have done a good job of responding to reviewers' queries and addressed the main concerns. However, since the reviewers have unanimously given a low rating to this paper, I do not feel confident about overriding their rating and accepting this paper. Hence, at this point I will have to recommend that this paper cannot be accepted. This paper has good potential and the authors should submit it to another suitable venue soon.
Decision: Reject