Year: 2019

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.

heading: 1 INTRODUCTION
text: Graphs are a natural representation of relations between entities in complex systems, such as social networks or information networks. To enable inference on graphs, a graph embedding may be learned. It comprises node embeddings, each being a vector-based representation of a graph’s node that incorporates its relations to other nodes (Goyal & Ferrara, 2018; Hamilton et al., 2017b). While supervised node embeddings have received a 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 is that “similar” nodes have close embeddings in the embedding space. The similarity of nodes is often defined based on their distance in a graph, e.g., based on their co-occurrence probability in a random walk (Goyal & Ferrara, 2018; Perozzi et al., 2014; Grover & Leskovec, 2016). Recently, it was also argued that two nodes should be similar, if they are similar to a graph summary representation (Veličković 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 a graph in order to avoid a 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 a community as a set of densely connected nodes with sparse connections to outside nodes, the homophily principle is 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 a set of communities. 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 to minimize the mincut loss for unsupervised learning of communities and node embeddings simultaneously. Mincut loss leverages the principle that communities are well-separated if there are few connections between them (Fortunato, 2010). It is theoretically motivated as its optimal closed-form solution can be found, while its variant, the normalized cut, is a well-studied problem.
Aiming at a realisation of the above idea, we propose Deep MinCut (DMC), a neural network approach to minimize mincut loss. We learn node embeddings to sample one-hot vectors that represent the assignment of nodes to communities. The vectors are drawn from distributions parameterized by continuous node embeddings using Gumbel-Softmax (Jang et al., 2016; Maddison et al., 2016). This renders the process differentiable and, thus, enables joint learning of embeddings and communities.
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; Veličković et al., 2018), while also revealing the graph’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, we can link words to topics, and topics to abstract themes.

heading: 2 RELATED WORK
text: Graph embedding constructs a low-dimensional model of the nodes of a 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 a node’s embedding by performing aggregation of its neighbours’ embeddings.
Unsupervised node embeddings. While different models may be employed to embed nodes (Perozzi et al., 2014; Grover & Leskovec, 2016), the majority of unsupervised learning techniques leverage a contrastive loss function, such as skipgram loss (Hamilton et al., 2017b) or infomax loss (Veličković 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 a 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 performance is highly dependent on the corruption strategy (Veličković 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, it differs in that our approach is nonconstrastive, 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; Fortunato & 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 a 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.

heading: 3 EMBEDDINGS AND COMMUNITY DETECTION
text: Graphs. We consider a directed, weighted graph G = {V,F} with nodes V = {vi} and edges F = {(vi, vj) | vi ∈ V ∧ vj ∈ V}, each edge (vi, vj) being assigned a weight s(vi,vj) ∈ R. Such a graph can also be represented by its adjacency matrix A of size n× n, where each row and column represents a node in G and a cell Aij denotes the edge weight. Note that we allow self-loops 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 ∈ Rn×D.
Communities. We denote by C = {C1,C2, · · · ,Ck} the set of k disjoint communities of graph G, where ⋃k i=1 Ci = V and ∀ Ci 6= Cj ,Ci ∩ Cj = ∅. The assignment of nodes to communities is captured by a membership matrix P ∈ {0, 1}n×k with rows representing nodes in G and columns representing communities in C. As each node is only assigned to one community, the rows of P are one-hot vectors, where Pij = 1 if node vi is assigned to community Cj .
Assuming the membership matrix P is already known, the number of cross-connections between communities Ci and Cj can be captured by the non-diagonal elements of the adjacency matrix C of
the quotient graph, where the nodes are communities:
C = PTAP (1)
On the other hand, elements Cii capture the number of connections within community Ci.
Mincut loss. While community detection is a well-studied problem, there is no consensus on the precise notion of a community (Fortunato, 2010). A common principle is that well-separated communities 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:
LP(A) = − k∑ i Cii = −Tr(PTAP) (2)
where Tr(X) is the trace of matrix X. We call the loss function in Equation 2 mincut loss, as it aims to minimize the number of connections between communities.
Degenerated cases. Minimizing Equation 2 may lead to degenerated cases, where all nodes are assigned to one community while the others are empty (Fortunato, 2010). In practice, there are two solutions to this problem. If there is prior knowledge on the communities (e.g., they shall have equal size), a 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 as follows:
ncut(C) = k∑ i=1 cut(Ci,C−i) assoc(Ci,C−i) = k∑ i=1 PT:,i(D−A)P:,i PT:,iDP:,i = Tr( PT (D−A)P PTDP ) = Tr( PTLP PTDP )
where C−i denotes the set of communities except Ci and assoc(Ci,C−i) is the total degree of nodes in community Ci. Then, the normalized cut (normcut) loss can be captured as follows:
LP(A) = Tr( PTLsymP
PTP ) (3)
where Lsym = I −D−1/2AD1/2 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 on graphs. Yet, it can be applied to any problem comprising a set T of items and a kernel function k : T × T → R that assigns weights to item pairs. This creates a 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.

heading: 4 DEEP MINCUT
text: 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 on minibatches.

heading: 4.1 SPECTRAL APPROACH
text: 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 a real matrix H ∈ Rn×k. However, for the relaxed matrix H to be meaningful, it needs to retain the following semantic constraint from matrix P that each node belongs to only one community: h̃ih̃Tj = 0 where h̃i 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 Lsym. This is captured by the following theorem.
Theorem 1. Let Lsym be the normalized Laplacian matrix of a graph G of size n and its eigendecomposition Lsym = QΛQT . We also denote λ1, · · · , λk to be k smallest eigenvalues of Lsym and
their respective eigenvectors q1, · · · ,qk. Let H ∈ Rn×k be a matrix that satisfies h̃ih̃Tj = 0. Then, LH(Lsym) = Tr( H T LsymH HTH ) is minimized when the i-th column vector of H is parallel with the i-th eigenvector, i.e., h̃i ↑↑ qi.
It is worth noting that closed-form solutions for the mincut loss can be found in a 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.

heading: 4.2 DEEP MINCUT - A NEURAL NETWORK APPROACH
text: 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 a neural network approach called Deep MinCut to learn node embeddings and communities at the same time. Our framework is illustrated in Figure 1, which we explain in detail in the remainder.
Learning the membership matrix. To detect communities, we want to learn the membership matrix P that minimizes the normalized cut LP(A) = Tr(P TLsymP PTP
). Recall that P captures the assignment of nodes to communities. Intuitively, this assignment is based on a node’s role in the graph and the graph structure, which is also the information that shall be encoded in a node embedding (Grover & Leskovec, 2016; Hamilton et al., 2017a). Hence, we propose to compute the membership matrix P based on node embeddings.
An embedding matrix H, which contains all the node embeddings, is derived by an encoder Eθ : V → Rd. The encoder Eθ encodes every node in V to a d-dimensional space, where θ denote parameters. Any existing node embedding techniques such as graph convolutional encoders (Hamilton et al., 2017b; Wu et al., 2019) or shallow encoders (Grover & Leskovec, 2016; Perozzi et al., 2014) can be used to realize Eθ, since the parameters θ can be learned during optimization of the normalized cut. The node embeddings in H can also be used for downstream tasks such as node classification or link prediction.
Differential sampling. To obtain P from H, we sample a one-hot vector p of P from the corresponding node embedding h of H. Intuitively, Hij shall capture the likelihood that the i-th node is assigned to the j-th community. As such, we consider the elements h1, . . . , hk of h to be the unnormalized class probabilities of a k-dimensional categorical distribution. Then, by sampling from this distribution, we are able to obtain the one-hot vector p. 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 = (p1, . . . , pk) is found as follows:
pi = { 1, if i = arg maxj(hj + g) 0, otherwise
where g ∼ Gumbel(0, 1) is a sample from the standard Gumbel distribution. Note that the sampling process is still non-differentiable as the arg max 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 softmax , however, we render
Algorithm 1: Computation of normcut loss. input : Adjacency matrix A, τ , straight-through st, embedding matrix H output: Normcut loss L
1 P = gumbel_softmax(H, τ, st) ; // Sample one-hot vectors from node embeddings 2 C = HTAH ; // Adjacency matrix of the quotient graph. 3 q = 1C ; // Compute the association of communities. 1 is the vector of ones. 4 d = diagonal(C) ; // Diagonal vector of C. 5 l = (q − d)/q ; // Compute the normcut loss 6 L = ∑ l; 7 return L;
the whole process differentiable (Maddison et al., 2016; Jang et al., 2016). That is, an element pi of p can be sampled from the corresponding row h of H as follows:
pi = exp(xi/τ)∑k i exp(xi/τ)
where xi = hi + g and τ is a temperature hyperparameter. Gumbel-Softmax (GS) not only allows to sample discrete values from a continuous distribution, but it is also differentiable. The latter is important for learning the parameters of Eθ 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 we want p to be close to a one-hot vector, we need to set τ to be close to 0. However, a small temperature leads to a high variance of gradients which makes the training process slow to converge (Jang et al., 2016). To this end, we use the Straightthrough Gumbel-Softmax which allows us to set a high temperature while obtaining one-hot vector for p. This is done by taking the arg max of pi to construct the one-hot vector in the forward pass, while in the backward pass, pi is used to compute the gradients. The trade-off is that there is a mismatch between the forward and backward pass which makes Straight-through GS a biased estimator. However, it performs well in practice (Choi et al., 2018; Gu et al., 2018; Niu et 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 supercommunities. 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, our approach is unsupervised and may thus be used in applications where labels are not available.

heading: 4.3 MINIBATCH TRAINING
text: 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 a subgraph is not sufficient as the subgraph may not be connected. Hence, optimization of normcut loss is non-trivial.
Against this background, we propose to construct an 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 a node v ∈ V, its ego-network of depth d is the induced subgraph obtained from a sample of all nodes with a distance of at most d to v. Sampling is done at each level, with replacement of a 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 a theoretical motivation on why it is possible to approximate the normcut loss function with sampled subgraphs. Let K ∈ Rm×k 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 normcut loss to a certain degree with high probability using the subgraph of size m < n where n is the number of nodes in the original graph.
Theorem 2. Let L = ∑k i=1 HT:,iLH:,i
HT:,iDH:,i , L̃ =
∑k i=1 KT:,iL̃K:,i
KT:,iD̃K:,i 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
bound of A then if H is a binary matrix and elements of A and Ã are i.i.d then given an ε ≥ 0, P(| L̃−LL | ≤ ε) ≥ 1−2k(exp( −(nε)2 128k2(b−a)2 )+exp( (−mε)2 128k2(b−a)2 )+exp( −n2ε2 64k(b−a)2 )+exp( −m2ε2 64k(b−a)2 )+ 2 exp(−mε 2
394k ) + 2 exp( −n 8k )).
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 ε.

heading: 5 EXPERIMENTS

heading: 5.1 NODE EMBEDDING EXPERIMENTS
text: Setup. We evaluate the quality of our embeddings for node classification on four datasets, see Table 1. Cora, Citeseer and Pubmed are paper citation networks where a label represents the domain of a paper. Wiki is a word adjacency graph with the word labels being their POS tags.
In this experiment, we use a one-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 et al., 2019). Second, we include unsupervised node embedding methods that use contrastive loss, such as DeepWalk (Perozzi et al., 2014) and DGI (Veličković et al., 2018). For all methods that involve randomization, we train three models with different seeds. The node embedding size is consistently set to 128. The obtained node embeddings are used to learn a logistic classifier. Instead of a fixed train/test split, we use 50 random splits and report the mean accuracy and standard deviation as suggested by Shchur et al. (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 to normcut loss may not be the best embeddings for node classification, as the node labels are more correlated to node features.
In addition to node embeddings, DMC also learns how to 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, we 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 DGI. For instance, the NMI scores with DMC are 7× 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 as node classification or graph analysis through clustering.
Table 3: DMC vs. DGI on cluster quality

heading: 5.2 COMMUNITY DETECTION EVALUATION
text: Setup. Next, we aim to show the applicability of normcut loss to a 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(wi, wj) = max( log(#(wi, wj))
log(#wi) log(#wj) , 0)
where #wi is the number of times word wi appears in the corpus, while #(wi, wj) is the number of times the words appear together. The adjacency matrix obtained using the above function is the PPMI matrix, a well-established concept in NLP (Levy & Goldberg, 2014). Following Yin & Shen (2018), we construct a word corpus of 10000 words that appear >100 times in the Text8 corpus (Mahoney, 2011). Words are said to appear together if they are within a 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 a set of five words for each dimension by selecting the top-4 words and a 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 et al., 2015), and Non-Negative Sparse Coding (NNSC) (Faruqui et al., 2015). For a qualitative analysis, we also report the words with the largest embedding values along exemplary dimensions.
Results. 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 embeddings as input, whereas our methods learn explainable word embeddings directly on a word corpus. Table 5 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 normcut 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 to religion.
Table 4: Test Precision
Table 5: Top-5 words for the first five dimensions

heading: 5.3 EFFECTS OF MINIBATCH TRAINING
text: 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 approximated 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 an initial sharp increase, the differences become smaller. This shows the robustness of our approach to the batch size. Moreover, we observe a reversed trend on 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 as the subgraphs can only cover parts of the whole graph.

heading: 5.4 RELATION BETWEEN EMBEDDING SIZE AND NUMBER OF COMMUNITIES
text: Setup. The aim of this experiment is two-fold. First, we aim to show the merit of the mincut loss. While the normcut prevents degenerate cases, the mincut loss is useful if we have prior knowledge about the graph structure. Second, we want to analyze the effect of the embedding size w.r.t the number of communities. For this experiment, we need a ground truth number of communities, which is why we rely on the Stochastic Block Model (SBM), a well-established benchmark for community detection (Chen et al., 2019; Fortunato & Hric, 2016; Fortunato, 2010). Using SBM, a graph with a known number of communities (#com) is generated. Then, we 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.
Results. Figure 3 confirms that “there is a sweet spot for the dimensionality, [..] neither too small, nor too large” (Arora et al., 2016). Our results provide one possible explanation for the dimensionality 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 are split up further. This also decreases the ROC, but not as drastically, 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.

heading: 6 CONCLUSION
text: We presented a novel perspective on unsupervised learning of node embeddings. Following the idea of community detection, we proposed Deep MinCut (DMC), an approach to minimize the mincut loss function to learn node embeddings and communities simultaneously. DMC learns node embeddings 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.

heading: A ADDITIONAL EXPERIMENTAL RESULTS
text: 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 a clearer community structure, which yields better link prediction. On the other hand, with smaller p values, we observe the dimensionality trade-off better. As p decreases, the graphs converge towards random graphs with no community structure. As a 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.

heading: B DETAILS ON DATASETS AND HYPERPARAMETERS
text: B.1 HYPERPARAMETERS
The embedding sizes of all methods are set to 128 to achieve a fair comparison. For methods that use deep models (DMC, DGI, GAP), we use a learning rate of 0.001 and Adam as the optimizer. All methods are trained for a fixed number of epochs, namely 3000. For DMC, since we use StraightThrough Gumbel-Softmax, we fix the temperature to be 1. For minibatch DMC, we use a batch size of 100 and two-layer neighbourhood sampling, where 10 and 25 neighbours are used in the first and second layer. For word embedding experiment, we use a shallow encoder for DMC. For experiments with k-means, we take the average scores (NMI and HG) over 10 runs.
B.2 DATASETS
Node embedding experiments. Cora (Sen et al., 2008), Citeseer (Sen et al., 2008) and Pubmed (Namata et al., 2012) are three standard benchmark datasets for node classification. Traditionally, a 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 are 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 a library that is publicly available1 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 a minimum occurrence of a word of 100.
1https://github.com/ziyin-dl/word-embedding-dimensionality-selection
Stochastic Block Model (SBM). To build graphs from the SBM, we leverage the networkx library.2 The parameters of SBM include the number of communities #ncom, community sizes and the probability 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 p from 0.3 to 0.5 to generate the graphs. From p, we can compute the probability of connection across communities as p̄ = 1−p1−#ncom . When p ∼ p̄, the graph becomes a random graph with no community structure.
B.3 HARDWARE
Experiments were conducted on a workstation with an Intel Core i7-6700K CPU @ 4.00GHz with 32 GB RAM and an Nvidia GTX 1080Ti GPU with 12 GB and a server with 2 nodes. Each node includes an AMD Ryzen 1900X CPU with 64GB RAM and 1 Nvidia GTX 1080Ti GPU with 12 GB.

heading: C PROOFS
text: C.1 ANALYTICAL SOLUTION FOR MINCUT LOSS
Theorem 1. Let M be a positive semi-definite matrix of size n × n and its eigendecomposition M = QΛQT . We also denote λ1, · · · , λm to be m largest eigenvalues of M and their respective eigenvectors q1, · · · ,qm. Let H ∈ Rn×m be a matrix that satisfies 〈h̃i, h̃j〉 = 0 then LH(M) = −Tr(HTMH) is minimized when the i-th column vector of H is parallel with the i-th eigenvector i.e.hi ↑↑ qi.
Proof. Note that we can factorize any matrix H = UX by a unitary matrix U of size n×m and a diagonal matrix X of size m. We denote XXT = diag(x1, x2, ..., xm) and U1:k is the matrix of k leading columns of U. We also denote I1:k to be the identity matrix of size k × k. Then, we have:
LH(M) = −Tr(HTMH) = −Tr(HHTM) = −Tr(UXXTUTM)
= −Tr( m∑ 1 (U1:k(xk − xk+1)I1:kUT1:kM)) = − m∑ 1 (xk − xk+1)Tr(UT1:kMU1:k)
By applying the Poincare Separation Theorem Abadir & Magnus (2005), we have ∀k = 1,m, Tr(UT1:kMU1:k) is maximized iff ∀k = 1,m, the column vectors of U1:k are proportional to k leading eigenvectors of M. In addition, as the column vectors of U or U1:k are proportional to the column vectors of H, LH(M) is minimized iff the column vectors of H are proportional to m leading eigenvectors of M. In other words, the column vectors of H are parallel with m leading eigenvectors of M.
C.2 ANALYTICAL SOLUTION FOR NORMCUT LOSS
Theorem 2. Let Lsym be the normalized Laplacian matrix of a graph G of size n and its eigendecomposition Lsym = QΛQT . We also denote λ1, · · · , λk to be k smallest eigenvalues of Lsym and their respective eigenvectors q1, · · · ,qk. Let H ∈ Rn×k be a matrix that satisfies h̃ih̃Tj = 0 then LH(Lsym) = Tr( H T LsymH HTH ) is minimized when the i-th column vector of H is parallel with the i-th eigenvector i.e.h̃i ↑↑ qi.
Proof. We can see that if we multiply hi with an arbitrary number, the value of LH(Lsym) is unchanged. So that we can assume HTH = I. With this assumption, the problem becomes finding H to minimize Tr(HTLsymH).
Let µ1 ≥ µ2 ≥ · · · ≥ µk be the eigenvalues of HTLsymH and λ1 ≥ λ2 ≥ · · · ≥ λn be the eigenvalues of Lsym. Then, according to Poincare’seperation theorem, we have:
2https://networkx.github.io/
k∑ i=1 λn−k+i ≤ k∑ i=1 µi ≤ k∑ i=1 λi (4)
Noting that ∑r k=1 µk = Tr(H TLsymH). This means Tr(HTLsymH) is minimized at ∑k i=1 λn−k+i when hi is proportion with k smallest eigenvectors of Lsym.
While the closed-form solutions for the mincut and normcut loss can both be constructed from eigendecomposition, there are difference in application. The normcut loss is able to prevent degenerated cases since they do not correspond to 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 x = ab , y = c d . If P( ∣∣a−c c ∣∣ ≤ ε) ≥ 1− p and P(∣∣∣ b−dd ∣∣∣ ≤ ε) ≥ 1− q with small ε then P(
∣∣∣x−yy ∣∣∣ ≤ 2ε) ≥ 1− (p+ q) Proof. We consider the case where x, y ≥ 0 as similar result can be proved for x, y < 0. Let a = (1 + α)c and b = (1 + β)d. Then, we can rewrite the above statements as
P(|β| ≤ ε) ≥ 1− p
P(|α| ≤ ε) ≥ 1− q This also means: ⇒ P(|β| ≤ ε,|α| ≤ ε) ≥ 1− (p+ q) Moreover, when |β| ≤ ε and |α| ≤ ε with small ε, we have
x = (1 + α)c (1 + β)d ⇒ x ≥ (1− ε)c (1 + ε)d ≥ (1− ε) (1 + ε) y ≥ (1− 2ε)y
Similarly,
x ≤ (1 + ε)c (1− ε)d ≤ (1 + 2ε)y
So that, if|β| ≤ ε and|α| ≤ ε, and a small value of ε, we have∣∣∣∣x− yy ∣∣∣∣ ≤ 2ε
Therefore, we have P( ∣∣∣x−yy ∣∣∣ ≤ 2ε) ≥ 1− (p+ q) with small ε
Lemma 2. Let x1, x2, ..., xm be m independent random variables such that P(xi = 1) = bi. Let X = ∑n i=0 xi and µ = E[X]. Then, for 0 < δ < 1, P(X ≤ (1− δ)µ) ≤ exp(−µδ2/2) Corollary 1. Let H ∈ {0, 1}n×k be an arbitrary binary matrix where the number of 1 elements in H is n. Let pi be the ratio of 1 in column h̃i, then, P(pi ≥ 12k ) ≥ 1− exp( −n 8k )
Proof. Applying Lemma 2 with xi is pi ∀i = 1, k, µ = E[pi] = 1k and δ = 1/2.
Lemma 3. (Chernoff bound) Let x1, x2, ..., xm is m random variables with Poisson distribution with P(xj = 1) = pi,X = ∑m j=1 xj and, µ = E[X]. We have, ∀δ ∈ (0, 1):
P( ∣∣∣∣X − µµ ∣∣∣∣ ≥ δ) ≤ 2exp(−µδ23 )
Lemma 4. (Hoeffding’s bound) Let x1, x2, ..., xm is m independent random variables. E[xi] = µ, P(a ≤ Yi ≤ b) = 1∀i. With arbitrary reals a and b, We have,
P( ∣∣∣∣∣∣ 1n n∑ i=1 xi − µ ∣∣∣∣∣∣ ≤ δ) ≥ 1− 2exp( −2nδ 2 (b− a)2 )
Theorem 3. Let G be a graph with its adjacency matrix A and its subgraph S with adjacency matrix Ã. Let a, b ∈ R be the upper and lower bound of A then if H ∈ {0, 1}n×k and K ∈ {0, 1}m×k and elements of A and Ã are i.i.d then given an ε ≥ 0, P(| k̃ > i Ãk̃i−c.h̃ > i Ah̃i
c.h̃>i Ah̃i | ≤ ε2 ) ≥
1− 2(exp( −(nε) 2 128k2(b−a)2 ) + exp( (−mε)2 128k2(b−a)2 ) + exp( −mε2 394k ) + exp( −n 8k )) ∀i = 1, n where h̃i, k̃i are the i-th column vectors of H,K and c = m 2
n2 .
Proof. Let n(x) be the counting function for the number of 1 elements in a binary vector or matrix. We also denote pi to be the ratio of 1 elements in vector h̃i. As K is sampled uniformly from H and with n large enough, we can assume that each element of k̃i is equally chosen with probability pi. Then, n(k̃i) is a random variable for the number of 1 elements in vector k̃i. We also have n(k̃i) =∑m j=1 Kj,i which means E[n(k̃i)] = mpi with P(Kj,i = 1) = pi.
Then, by applying bound (Lemma 3 with X = n(k̃i), δ = ε8 and µ = E[n(k̃i)] = mpi, we have
P( ∣∣∣∣∣n(k̃i)−mpimpi ∣∣∣∣∣ ≥ ε8) ≤ 2 exp(−mpi ε2192)
Denote c = m 2 n2 , we have n(h̃i) = npi which means mpi = √ c.n(h̃i). Therefore, we have:
P( ∣∣∣∣∣n(k̃i)− √ cn(h̃i)√
cn(h̃i) ∣∣∣∣∣ ≤ ε8) ≥ 1− 2 exp(−mpi ε2192) ⇔ P(
∣∣∣∣∣n(k̃i)2 − cn(h̃i)2cn(h̃i)2 ∣∣∣∣∣ ≤ ε4) ≥ 1− 2 exp(−mpi ε2192) (5)
Note that n(k̃ik̃>i ) = n(k̃i) 2 and n(h̃ih̃>i ) = n(h̃i) 2 which make the above inequality equivalent with:
P( ∣∣∣∣∣n(k̃ik̃>i )− cn(h̃ih̃>i )cn(h̃ih̃>i ) ∣∣∣∣∣ ≤ ε4) ≥ 1− 2 exp(−mpi ε2192) (6)
Since elements of A are i.i.d and bounded by a, b, we have h̃>i Ah̃i = ∑ j∈J Yj with J ⊆ [1, n2]
and|J| = n(h̃i). Similarly, k̃>i Ãk̃i = ∑ j∈T Yj with T ⊆ J and|T| = n(k̃i).
Applying lemma 4, with h̃>i Ah̃i, k̃ > i Bk̃i and δ = ε 8 , we have
P( ∣∣∣h̃>i Ah̃i − n(h̃ih̃>i )µ∣∣∣ ≤ n(h̃ih̃>i )ε8 ) ≥ 1− 2 exp(−n(h̃ih̃>i )ε232(b− a)2 )
and,
P( ∣∣∣k̃>i Ãk̃i − n(k̃ik̃>i )µ∣∣∣ ≤ n(k̃ik̃>i )ε8 ) ≥ 1− 2 exp(−m(k̃ik̃>i )ε232(b− a)2 )
Moreover, since n(k̃ik̃>i ) = (m.pi) 2 and n(h̃ih̃>i ) = (n.pi) 2, we have
P( ∣∣∣∣∣ k̃>i Ãk̃i − n(k̃ik̃>i )µn(k̃ik̃>i ) ∣∣∣∣∣ ≤ ε8 , ∣∣∣∣∣ h̃>i Ah̃i − n(h̃ih̃>i )µn(h̃ih̃>i ) ∣∣∣∣∣ ≤ ε8)
≥ 1− 2(exp( −(npiε) 2
32(b− a)2 ) + exp(
(−mpiε)2 32(b− a)2 )) (7)
⇒ P( ∣∣∣∣∣∣∣ k̃>i Ãk̃i − n(k̃ik̃ > i ) n(h̃ih̃>i ) h̃>i Ah̃i n(k̃ik̃>i )
n(h̃ih̃>i ) h̃>i Ah̃i
∣∣∣∣∣∣∣ ≤ ε 4 )
≥ 1− 2(exp( −(npiε) 2
32(b− a)2 ) + exp(
(−mpiε)2 32(b− a)2 )) (8)
Applying Lemma 1 for inequality 6 and 8 , we have,
P(| k̃ > i Ãk̃i − c.h̃>i Ah̃i
c.h̃>i Ah̃i | ≤ ε 2 ) ≥ 1− 2(exp( −(npiε) 2 32(b− a)2 )
+ exp( (−mpiε)2
32(b− a)2 ) + exp(
−mpiε2
192 )) (9)
From Corollary 1, we also have
P(pi ≥ 1 2k ) ≥ 1− exp(−n 8k ) (10)
From inequality (9) and (10) , we have,
P( ∣∣∣∣∣ k̃>i Ãk̃i − c.h̃>i Ah̃ic.h̃>i Ah̃i ∣∣∣∣∣ ≤ ε2) ≥ 1− 2(exp( −(nε)2128k2(b− a)2 )
+ exp( (−mε)2
128k2(b− a)2 ) + exp(
−mε2
394k ) + exp( −n 8k )) (11)
Theorem 4. Let G be a graph with its adjacency matrix A and its subgraph S with adjacency matrix Ã. Let a, b ∈ R be the upper and lower bound of A then if H ∈ {0, 1}n×k and K ∈
{0, 1}m×k and elements of A and Ã are i.i.d then given an ε ≥ 0, P( ∣∣∣∣ k̃>i Ã1−c.h̃>i A1c.h̃>i A1 ∣∣∣∣ ≤ ε2 ) ≥ 1− 2(exp( −n 2ε2
64k(b−a)2 ) + exp( −m2ε2 64k(b−a)2 ) + exp( −mε2 394k )) + exp( −n 8k )) ∀i = 1, n and c = m2 n2 .
Proof. (Proof sketch) Theorem 4 can be proven in the same manner as Theorem 3.
Given the results in Theorem 4 and Theorem 3, we can now prove Theorem 2. Theorem 5. Let L = ∑k i=1 h̃Ti Lh̃i
h̃Ti Dh̃i , L̃ =
∑k i=1 k̃Ti L̃k̃i
k̃Ti D̃k̃i 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 bound of A then if H is a binary matrix and elements of A and Ã are i.i.d then given an ε ≥ 0, P(| L̃−LL | ≤ ε) ≥ 1−2k(exp( −(nε)2 128k2(b−a)2 )+exp( (−mε)2 128k2(b−a)2 )+exp( −n2ε2 64k(b−a)2 )+exp( −m2ε2 64k(b−a)2 )+ 2 exp(−mε 2
394k ) + 2 exp( −n 8k ))
Proof. First, since L = D −A, L = ∑k i=1 h̃Ti Dh̃i h̃Ti Dh̃i − ∑k i=1 h̃Ti Ah̃i h̃Ti Dh̃i = k − ∑k i=1 h̃Ti (A)h̃i h̃Ti Dh̃i . This
means optimizing L, L̃ is equivalent to optimizing L = ∑k i=1 h̃Ti Ah̃i
h̃Ti Dh̃i , L̃ =
∑k i=1 k̃Ti Ãk̃i
k̃Ti D̃k̃i . Second, observe that both L and L̃ are the sum of d terms. Thus, proving ∣∣∣L−L̃L ∣∣∣ ≤ ε is similar to
prove ∣∣∣∣∣Li − L̃iLi ∣∣∣∣∣ ≤ ε, ∀i = 1, k (12)
in which Li = h̃ > i Ah̃i
h̃>i Dh̃i , L̃i == k̃
> i Ãk̃i
k̃>i D̃k̃i .
Algorithm 2: Minibatch forward propagation of Deep MinCut input : Adjacency matrix A of graph G = {V, F}
Temperature τ Straight-through st Encoder Eθ Node feature matrix F Sampling method f
output: Node embedding matrix H Community assignment P
// 1. Sampling minibatches of nodes 1 U = f(V) 2 A′ = A[U,U] 3 F′ = F[U] // 2. Compute the node embeddings 4 H = Eθ(A′,F′) ; // Embed nodes in batch using the encoder // 3. Compute the mincut loss 5 P = gumbel_softmax(H, τ, st) ; // Sample one-hot vectors from node embeddings 6 C = HTA′H ; // Adjacency matrix of the quotient graph. 7 q = 1C ; // Compute the association of communities. 1 is the vector of ones. 8 d = diagonal(C) ; // Diagonal vector of C. 9 l = (q − d)/q ; // Compute the normcut loss
10 L = ∑ l
From Lemma 1, to prove inequality 12, we need to have the following results:
| k̃ > i Ãk̃i − c.h̃>i Ah̃i
c.h̃>i Ah̃i | ≤ ε 2 (13)
And, the second is
| k̃ > i D̃k̃i − c.h̃>i Dk̃i
c.h̃>i Dk̃i | ≤ ε 2 (14)
⇔ | k̃ > i Ã1− c.h̃>i A1
c.h̃>i A1 | ≤ ε 2 ,∀i = 1, k (15)
where c = m 2
n2 . Inequality 13 is proven in Theorem 3 while Inequality 15 is proven in Theorem 4.

heading: D ALGORITHM
text: Algorithm 2 illustrates one iteration in the forward pass of DMC. The forward pass include 3 steps. In the first step, we sample a subset of nodes of the graph (Line 1) using a sampling strategy. In our work, we use a neighbourhood sampling strategy as discussed in Section 4.3. From the sampled nodes, we extract a submatrix from the adjacency matrix A in Line 2 and from the node feature matrix F in Line 3. The second step involves constructing the node embeddings for the sampled nodes. We use an encoder Eθ to 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 as discussed in Section 5.1 and a shallow encoder for our word embedding experiment. In the last step, we use the node embeddings to compute the mincut loss as shown in Figure 1. From the loss, we can backpropagate and update the parameters θ of the encoder using any automatic differentation framework.

Review summaries:
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,