VECoDeR - Variational Embeddings for Community Detection and Node Representation
Authors: Rayyan Ahmad Khan
Muhammad Umer Anwaar
Omran Kaddah
Martin Kleinsteuber
Venue:  (2021)
Keywords: Generative Models
Node representation
VECoDeR
Graph Neural Networks
Variational Embeddings

Abstract: In this paper, we study how to simultaneously learn two highly correlated tasks of graph analysis, i.e., community detection and node representation learning. We propose an efficient generative model called VECoDeR for jointly learning Variational Embeddings for COmmunity DEtection and node Representation. VECoDeR assumes that every node can be a member of one or more communities. The node embeddings are learned in such a way that connected nodes are not only ``closer" to each other but also share similar community assignments. A joint learning framework leverages community-aware node embeddings for better community detection. We demonstrate on several graph datasets that VECoDeR effectively outperforms many competitive baselines on all three tasks i.e. node classification, overlapping community detection and non-overlapping community detection. We also show that VECoDeR is computationally efficient and has quite robust performance with varying hyperparameters.

Under review as a conference paper at ICLR 2021
VECODER VARIATIONAL EMBEDDINGS FOR COM- MUNITY DETECTION AND NODE REPRESENTATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, study how to simultaneously learn two highly correlated tasks of graph analysis, i.c., community detection and node representation learning. We propose an efficient generative model called VECODER for jointly learn- ing Variational Embeddings for Community Detection and node Representation. VECODER assumes that every node can be a member of one or more commu- nities. The node embeddings are learned in such a way that connected nodes are not only "closer" to each other but also share similar community assignments. joint learning framework leverages community- aware node embeddings for better community detection. We demonstrate on several graph datasets that VECoDER effectively outperforms many competitive baselines all three tasks i.e. node classification, overlapping community detection and non-overlapping community detection. We also show that VECODER is computationally efficient and has quite robust performance with varying hyperparameters.
INTRODUCTION
Graphs are flexible data structures that model complex relationships among entities, i.c. data points as nodes and the relations between nodes via edges. One important task in graph analysis community detection, where the objective to cluster nodes into multiple groups (communi- ties). Each community is set of densely connected nodes. The communities can be overlapping or non-overlapping, depending on whether they share some nodes not. Several algorithmic (Ahn et al. 2010; Derényi et al. 2005) and probabilistic approaches (Gopalan & Bleil 2013 Leskovec & Mcauley Wang et al. 2017, Yang et al., 2013) community detection have been proposed. Another fundamental task in graph analysis is learning the node embeddings. These embeddings
can then be used for downstream tasks like graph visualization (Tang et al. [2066] Wang et al. 2016
Gao et al. 2011 Wang et al., 2017) and classification (Cao al. [015 Tang al. 2015)).
In the literature, these tasks are usually treated separately. Although the standard graph embed- ding methods capture the basic connectivity, the learning of the node embeddings is independent of community detection. For instance, a simple approach can be to get the node embeddings via DeepWalk (Perozzi et al., 2014) and get community assignments for each node by using k-means or Gaussian mixture model. Looking from the other perspective, methods like Bigclam (Yang & Leskoved (2013)), that focus on finding the community structure in the dataset, perform poorly for node-representation tasks e.g. node classification. This motivates us to study the approaches that jointly learn community-aver node embeddings.
Recently several approaches. like CNRL (Tu et al. 2018), ComE (Cavallari et al.) 2017), vGraph (Sun al. (2019) etc, have been proposed to learn the node embeddings and detect communities simultaneously in unified framework. Several studies have shown that community detection is improved by incorporating the node representation the learning process (Cao al. 2015; Kozdoba & Mannor 2015). The intuition is that the global structure of graphs learned during community detection can provide useful context for node embeddings and vice versa.
The joint learning methods (CNRL, ComE and vGraph) learn two embeddings for each node. One node embedding is used for the node representation task. The second node embedding is the "con- text" embedding of the node which aids in community detection. As CNRL and ComE are based on Skip-Gram Miikolov et al., 2013) and Deep Walk (Perozzi et al., 2014), they inherit "context" em- bedding from it for learning the neighbourhood information of the node. vGraph also requires two

---

Under review as a conference paper at ICLR 2021
node embeddings for parameterizing two different distributions. In contrast, we propose learning single community-awasn node representation which is directly used for both tasks. In this way, we not only get rid of an extraneous node embedding but also reduce the computational cost.
In this paper, we propose an efficient generative model called VECODER for jointly learning both community detection and node representation. The underlying intuition behind VECODER is that every node can be a member of one or more communities. However, the node embeddings should be learned in such way that connected nodes are "closer" to each other than unconnected nodes. Moreover, connected nodes should have similar community assignments. Formally, we assume that for i-th node, the node embeddings 2; are generated from a prior distribution p(z). Given 2,, the community assignments are sampled from p(c (zt), which is parameterized by node and community embeddings.
order to generate an edge (i, we sample another node
embedding 2; from p(z) and respective community assignment cj from p(cy (1y))) Afterwards, the node embeddings and the respective community assignments of node pairs are fed a decoder. The decoder ensures that embeddings of both the nodes and the communities of connected nodes share high similarity. This enables learning such node embeddings that are useful for both community detection and node representation tasks.
We validate the effectiveness of our approach on several real-world graph datasets. In Sec. 4 we show empirically that VECODER is able to outperform the baseline methods including the direct competitors on all three tasks i.e. node classification, overlapping community detection and non- overlapping community detection. Furthermore, we compare the computational cost of training different algorithms. VECODER is up to 40x more time-elficient than its competitors. We also conduct hyperparameter sensitivity analysis which demonstrates the robustness of our approach. Our main contributions are summarized below:
We propose efficient generative model called VECODER for joint community detec- tion and node representation learning.
We adopt novel approach and argue that single node embedding is sufficient for learning both the representation of the node itself and its context.
Training VECODER is extremely time-efficient in comparison to its competitors.
2 RELATED WORK
Community Detection. Farly community detection algorithms are inspired from clustering algo- rithms (Xie et al., 2013). For instance, spectral clustering (Tang & Liu 201T) is applied to the graph Laplacian matrix for extracting the communities. Similarly, several matrix factorization based meth- ods have been proposed to tackle the community detection problem. For example, Bigclam (Yang non-negative matrix factorization (NMF) task. It aims
& Leskovee )) treats the problem to recover the node-community affiliation matrix and learns the latent factors which represent com- al. (2013)) extends Bigelam by mod- elling the interaction between the network structure and the node attributes. The performance of matrix factorization methods is limited due to the capacity of the bi-linear models. Some generative models, like vGraph (Sun et al., 2019), Circles (Leskovec & Mcauley) (2012) etc. have also been proposed detect communities graph.
munity affiliations of nodes. Another method CESNA(Yang
Node Representation Learning. Many successful algorithms which learn node representation in an unsupervised way are based on random walk objectives (Perozzi al. 2014; Tang et al., 2013 Grover & Leskovec 2016; Hamilton et al. 2017). Some known issues with cundom-walk based methods (e.g. DeepWalk, node2vee etc) are: (1) They sacrifice the structural information of the graph by putting over-emphasis on the proximity information (Ribeiro et al. (017)) and (2) great dependence of the performance on hyperparameters (walk-length, number of hops etc) (Perozzi et al. 2014| Grover & Leskovec] 2016)) Recently, Gilmer et al. (2017) recently showed that graph convolutions encoder models greatly reduce the need for using the random-walk based training objectives. This is because the graph convolutions enforce that the neighboring nodes have similar representations. Some interesting GCN based approaches include graph autoencoders e.g. GAE and VGAE & Welling (2016b)) and DGI (ellikocccovicc et al. 2019).
Joint community detection and node representation learning. In the literature, several attempts have been made to tackle both these tasks in single framework. Most of these methods propose
2

---

Under review as a conference paper at ICLR 2021
an alternate optimization process, i.e. learn node embeddings and improve community assignments with them and vice versa (Cavallari et al. 2017 Tu et al. 2018). Some approaches, like CNRL (Tu et al. 2018) and ComE (Cavallari al. 2017). inspired from random walk, thus inheriting the shortcomings of random walk. Others, like GEMSEC (Rozemberczki et al. (2019), are limited to the detection of non-overlapping communities. There also exist some generative models like Commu- nityGAN (Jia et al. (2019)) and vGraph (Sun et al. (2019)) that jointly learn community assignments and node embeddings. Some methods have high computational complexity, i.c. quadratic to the number of nodes in graph, e.g. M-NMF (Wang et al. (017)) and DNR (Yang et al. (2016a). CNRL, ComE and vGraph require learning two embeddings for each node for simultaneously tackling the two tasks. Unlike them, VECODER learns single community-awen node representation which is directly used for both tasks.
It is pertinent to highlight that although both vGraph and VECODER adopt variational approach but the underlying models are quite different. vGraph assumes that each node can be represented as mixture of multiple communities and is described by multinomial distribution over communities, whereas VECODER models the node embedding by a single distribution. For a given node, vGraph, first draws community assignment and then connected neighbor node is generated based the assignment. Whereas, VECODER draws the node embedding from prior distribution and then community assignment is conditioned edge information in the generative process whereas VECODER does not require it. VEÇODER relies on the decoder to ensure that embeddings of the connected nodes and their communities share high similarity with each other.
single node only. In simple terms, vGraph also needs
3 METHODOLOGY
3.1 PROBLEM FORMULATION
Suppose an undirected graph 9 = (V,E) with the adjacency matrix A R and matrix X E NF o F--dimensional node features, N being the number of nodes. Given K as the num- ber of communities, following variational approach such that: (1) One more communities can be assigned to every node and (2) the node embeddings can be used for both community detection and node classification.
aim to jointly learn the node embeddings and the community embeddings
3.2 VARIATIONAL. MODEL.
Generative Model: Let us denote the latent node embedding and community assignment for i-th node by the random variables z; E Rd and e; respectively. The generative model is given by:
p(A) / Σ
where c = |c1, .2.-.., cN] and the matrix Z [2,, nN stacks the node embeddings. The joint distribution in (T) is mathematically expressed as
p(Z,c, = p( po(c pe (Alc, 2),
(2)
where A denotes the model parameters. Let denote elements of A by a.j. Following existing
approaches (Kipf & Welling 2016b Khan et al.) 2020), we consider z; to be i.i.d random vari-
ables. Furthermore, assuming Co z; to be i.i.d random variables, the joint distributions 2 can be factorized as
N II po(c)|zi)
p( p(Z) = II p(z))
(3)
Po po(c
(4)
1=1
Po Z
II
Po (aigle;; 2i, 2;),
(5)
where Eq. 5 assumes that the edge decoder po (ais Cis Cj. 2is 2z) depends only on Gi ej: 2, and zj-
3

---

Under review as a conference paper at ICLR 2021
Inference Model: We aim to learn the model parameters A such that (og(po(A)) is maximized. In order to ensure computational tractability, we introduce the approximate posterior
q (, c2) = II qo (z cz = II go (z (zoos/
(6)
where I= (A, (A, ing ELBO bound (for derivation, refer the supplementary material), given by
if node features are available, otherwise I = A. We maximize the correspond-
N Σ DKLlqs [1 [xlllo(((())((le))
N
M
LELBO x
Σ
(xl(20() (m)) II) (o(elzz()))
M
m==
+
Σ (i.))E
E (2 Ree.ssseiee)oo00eee..... (z)
log po (5,
where (-I(- represents the Kl--divergence between two distributions. go(z,, Zj, Ca. Cj (Z) in the third term of Eq. (7) is factorized into two conditionally independent dis- tributions i.e.
The distribution
20, 2s, 9g [Z) (z(2,, (2)))
(8)
3.3 DESIGN CHOICES
In Eq. (3), p(z;) is chosen the standard gaussian distribution for all The corresponding
approximate posterior (z [I) in Eq. (6). used node embeddings encoder, is given by
(z(z)) = (N; diag(o (Z))).
The parameters of q [I) can be learnt by any encoder network e.g. graph convolutional network (Kipf Welling 2016a)) ). graph attention network (Veličković et al. (2017)). GraphSAGE (Hamil-
ton et al. (2017) or even two matrices to learn 14,(Z) (Z) and diag a (Z))). Samples are then generated using reparametrization trick (Doersch) (2016)).
For parameterizing Pa(cy] (c())224) in Eq. (4) we introduce community embeddings [g1,'.. 9kk: ;; Ix Rdd The distribution pa z2)) is then modelled as the softmax of dot products of z; with ga. i...
po(c: = k|z;) exp(<< 2,, 9k >)
(10)
Σ exp(<< < Zi, >)
The corresponding approximate posterior 2o (c. = k| I) in Eq. is affected by the node embed- ding z; as well as the neighborhood. To design this, our intuition with the embedding z, as well as with the embeddings of the neighbors of the i-th node. The overall similarity with neighbors is mathemattcally formulated as the average of the dot products of their embeddings. Afterwards a hyperparameter a is introduced to control the bias between the effect of z; and the set AG of the neighbors of the i-th node. Finally, a softmax applied as follows
consider the similarity of g
exp a < Zi 9k +(1 - a)) Wil JEN,
1
Σ
< <z 2z.
qo (c = k)
=
K Σ Exp a 2., g8 +(1 a)
(II)
E
< <zj,9E>>
WI
JEV.
Hence, Eq. ensures that graph structure information is employed to learn community assign- extraneous node embedding as done in (Sun al. 2019 Cavallari et al. (2017). Finally, the choice of edge decoder in Eq. (5) is motivated by the intuition that the nodes connected by edges have high probability of belonging the same community and vice versa. Therefore we model the edge decoder as:
ments instead of relying
palaszla E, m, Zi. 2z) a(< Zi, Im >) + 0( Zj.9t >)
(12)
4

---

Under review as a conference paper at ICLR 2021
For better reconstructing the edges, Eq. makes use of the community embeddings. node em- beddings and community assignment information simultaneously. This helps in learning better node representations by leveraging the global information about the graph structure via community detec- tion. On the other hand, this also forces the community assignment information to exploit the local graph structure via node embeddings and edge information.
3.4 PRACTICAL ASPECTS
The third term Eq. is estimated in practice using the samples generated by the approximate pos- terior. This term equivalent to the negative of binary cross-entropy (BCE) loss between observed edges and reconstructed edges. Since community assignment follows a categorical distribution, we Gumbel-softmax (Jang et al. (2016)) for backpropagation of the gradients. As for the second term Eq. 7 it is also enough to set M 1, i.e. use only one sample per input node.
For inference, non-overlgpping community assignment can be obtained for i-th node
C; arg max go(c; Z).
(13)
kk(
To get overlapping community assignments for i-th node, we can threshold its weighted probability vector at hyperparameter, follows
C = &
go(c = k(z;
2 2gj. E [0.
(14)
max (c f12;, I)
3.5 COMPLEXITY
Computation of dot products for all combinations of node and community embeddings takes O(Ndd) time. Solving Eq. (11) further requires caleulation of mean of products over the neighborhood for every node, which takes O(EEK)) computations overall as we traverse every edge for every community. Finally, we need softmax over communitics for every node in Eq. (10) and Eq. (1)) which takes O(NK) time. Eq. (12) takes O(E)) time for all edges as we have already calculated the dot products. As result, the overall complex- ity becomes O(EE) + NKd). This complexity is quite low compared to other algorithms de-
signed to achieve similar goals (Cavallari et al. 2017 Wang et al., 2017 Yang et al. 2016a)
Dataset
[V]
[ET
K
F
Overlap
CiteSeer
3327
9104
6
3703
EXPERIMENTS
CiteSecr-full
4230
10674
6
602
Cora
2708
10556
7
1433
Cora-ML
2995
2879
4.1 DATASETS
Cora-full
19793
126842
70
8710
fbo
333
2519
24
N/A
lb107
1034
26749
9
N/A
We have selected 18 different datasets rang- ing from 270 to 126,842 edges. For non- overlapping community detection and node classification, we use 5 the citation datasets (Bojcheskii & Günnemann (2017): Yang et al. 2016b)). The remaining datasets (Lekkovec & Mcauley (2012); Yang Leskovec (2015)), used for overlapping community detection, are taken from SNAP repository (Leskovec & Krevi (2014)). Following (Sun et al.) (2019). we take 5 biggest ground truth communities for youtube, amazon and dblp. Moreover, we also analyse the case of large number of communi- ties. For this purpose, of amazon dataset by randomly selecting 500 and 1000 communities from 2000 smallest communi- ties in the amazon dataset.
fb1684
786
14024
17
N/A
fb1912
747
30025
46
N/A
fb3437
534
4813
32
N/A
Y
fb348
224
3192
14
N/A
Y
lb414
1693
7
N/A
[b698
61
270
13
N/A
youtuhe
5346
24121
5
N/A
amazon
794
2109
5
N/A
amazon500
1113
3496
500
N/A
amazon 1000
1540
4488
1000
N/A
dblp
24493
89063
5
N/A
Table Every dataset has | nodes, ||| edges, K communities and [F] features. |F N/A means that either the features were missing or not used.
prepare two subsets

---

Under review as a conference paper at ICLR 2021
4.2 BASELINES
For overlapping community detection, we compare with the following competitive baselines: MNMF(Wang al. 2017) learns community membership distribution by using joint non-negative
matrix factorization with modularity based regularization. BIGCLAM(Yang & Leskovee (2013)) also formulates community detection as a non-negative matrix factorization (NMF) task. It simul- taneously optimizes the model likelihood of observed links and learns the latent factors which rep- resent community affiliations of nodes. CESNA YYngg al. (013)) extends BIGCLAM by sta- tistically modelling the interaction between the network structure and the node attributes. Cir- cles (Leskovec & Mcauley (2012)) introduces a generative model for community detection in ego-networks by learning node similarity metrics for every community. SVI (Gopalan & Blei (2013) formulates membership of nodes in multiple communities by a Bayesian model of networks. vGraph (Sun et al. (2019)) simultancously learns node embeddings and community assignments by modelling the nodes as being generated from a mixture of communities. vGraph+, a variant further incorporates regularization weigh local connectivity. ComE (Cavallari al. (2017)) jointly learns community and node embeddings by using gaussian mixture model formulation. CNRL et al.) 2018) enhances the random walk sequences (generated by DeepWalk, node2vec etc) to jointly learn community and node embeddings. CommunityGAN (ComGAN)is a generative adversarial model for learning node embeddings such that the entries of the embedding vector of each node refer the membership strength of the node to different communities. Lastly, we compare the results with the communities obtained by applying k-means to the learned embeddings of DGI (Velickovic et al. 2019).
For non-overlapping community detection and node classification, in addition MNMF, DGI, CNRL, CommunityGAN, vGraph and ComE, we compare VECODER with the following base- lines: Deep Walk (Perozzi et al. (2014) makes use of SkipGram (Mikolov et al. (2013) and trun- cated random walks on network to learn node embeddings. LINE (Tang et al. (2015) learns node embeddings while attempting to preserve first and second order proximities of nodes. Node2 Vec (Grover & Leskovee (2016) learns the embeddings using biased random walk while aiming to preserve network neighborhoods of nodes. Graph Autoencoder (GAE & Welling (2016b) extends the idea of autoencoders graph datasets. We also include its variational counterpart i.e. VGAE. GEMSEC is sequence sampling-basee learning model which aims to jointly learn the node embeddings and clustering assignments.
4.3 SETTINGS
For overlapping community detection, we learn mean and log-variance matrices of 16- dimensional node embeddings. We set a 0.9 and 0.3 in all our experiments. Following Kipf & Welling (2016b), we first pre-train a variational graph autoencoder. We perform gradient descent with Adam optimizer (Kingma & Ba (0144) and learning rate 0.01. Community assign- ments are obtained using Eq. (14). For the baselines, we employ the results reported by Sun et al. (2099. For evaluating the performance, we use Fl-score and Jaccard similarity.
For non-overlapping community detection, since the default implementations of most the base- lines use 128 dimensional embeddings, for we use for community assignments. For vGraph, we use the code provided by the authors. We employ normalized mutual information (NMI) and adjusted random index (ARI) as evaluation metrics.
128 for fair comparison. Eq. (13) used
For node classification, follow the training split used in various previous works (Yang et al. 2016b, Kipl & Welling 2016a Velickovic et al. 2019), i.e. 20 nodes per class for training. We train logistic regression using LIBLINEAR (Fan et al. (2008) solver as classifier and report the evaluation results on rest the nodes, For the algorithms that do not use node features, we train the classifier by appending the raw node features with the learnt embeddings. For evaluation, FI-macro and F'-micro scores.
All the reported results are the average over five runs. Further implemennttiioinnnnnnomooo details can be found
in the code:
4.4 DISCUSSION OF RESULTS
In the following, discuss the results gain some important insights into the problem.

---

Under review as a conference paper at ICLR 2021
FT Score (%)
Dataset
MNMF
Rigelam
CESNA
Cireles
SVI
vGrupht
Camk
CNRL.
ComCan
DGJ
VECODER
[b0
14.4
29.5
28.1
28.6
28.1
24.4
26.1
31.1
11.3
35.0
27.35
14.7
fb107
12.6
89.3
37.3
24.7
26.9
28.2
31.8
39.7
20.2
47.5
$5.78
59.7
fb1912
14.9
34.9
34.7
26.2
28.0
25.8
37.3
28.7
8.0
35.6
32.6
45.8
fh.3437
13.7
19.9
20.1
10.1
15.4
20.9
22.7
21.3
3,9
39.3
19.66
50.2
[b414
22.1
58.9
60.1
48.4
38.9
64.7
66.9
53.3
25.3
43.9
56.93
69.6
Th6998
26.6
54.2
58.7
35.2
40.3
54,0
59.5
45.8
16.4
58.2
52.19
64.0
Youtube
Amazon
38.2
46.4
16.8
53.3
47.3
53.3
53,2
50.1
53.5
51.4
44.7
58.1
Amazon500
30.1
52.2
57.3
46.2
41.9
61.2
60.4
59.8
38.4
59.3
33.8
67.6
Amazon
30.8
52.7
Dhip
21.8
23.6
35.9
36.2
33.7
39.3
39.9
47.1
46.8
34.9
44
53.9
Table 2: Fl scores for overlapping communities. Best and second best values are bold and blue respectively.
(56
Datase
MNMF
Bigelam
CESNA
Circles
SVI
vGraph
vGraph+
ComE
CNRL
ComCan
DGI
VECODER
[bll
K.0
18.5
17.3
18.6
17.6
14.6
15.9
19.3
5.8
24.1
16.3
24.7
17.2
38.5
Tb1684
6.6
38.0
38,7
18.7
24.7
29.2
32.7
-0.33
25.8
37.9
38.85
42.5
fb1912
8.4
24.1
23.9
16.7
20.1
18.6
28.0
18.5
4.6
13.5
22.48
37.3
fh3488
11.3
35.9
40.0
39.3
33.6
41.0
40.3
34.4
21.7
23.2
41.77
43.5
fb411
12.8
47.1
17.3
34,2
29.3
51.8
55.9
42.2
15.4
53.6
46.36
58.4
47.7
Youtube
46.7
29.3
24.2
22.1
28.7
34,3
34.8
52.5
35.5
44.0
32.72
53.3
Amazon
25.2
35.1
35.0
36.7
36.4
36.9
36.9
34.6
38.7
38.0
29.09
41.9
Amazon500
51.2
53.8
47.2
45.0
59.1
59.6
58.4
41.1
57.3
Amazon1000
20.3
26.8
28.9
24.9
23.6
54.3
19.7
$2.0
26.9
$4.1
23.25
$7.1
Dhlp
20.9
13.8
22.3
23.3
20.9
25.0
25.1
27.9
32.8
25.0
29.15
37.3
Table Jaccard scores overlapping communities. Best second best values are bold blue respec- tively.
NMI(%)
ARI
Algorithm MNMF
CiteSeer
CiteSeer-ful
Cora
Cora-ML
Cora-fuli
CiteSeer
CiteSeer-full
Cora
Cora-ML
Cora-full
14.1
9.4
19.7
37.8
42.0
2.6
0.4
2.9
24.1
6.1
Deep
15.4
39.7
43,2
48.5
9.5
16.4
31.2
$3.9
LINE
8.7
13.0
32.8
42.3
40.3
3.3
3.7
14.9
32.7
11.7
Node2Vee
22.3
39.7
39.6
48.1
8.1
10.5
25.8
27.9
18.8
GAE
17.4
55.1
39.7
48.3
48.3
14.1
50.6
29.3
41.8
18.3
DGI
37.8
56.7
50.1
46.2
39.9
38.1
50.8
44.7
42.1
12.1
GEMSEC
18.1
CNRL
13.6
23.3
39.4
42.9
47.7
12.8
20.2
31.9
32.5
22.9
ComGAN
3.2
5.7
11.5
15.0
4.9
3.2
6.7
vGraph
9.0
7.6
26.4
29.8
41.7
5.1
4.2
12.7
21.6
14.9
ComB
18.8
32.8
47.6
51.2
20.9
34.2
37.2
19.7
VECODER
38.5
39.0
52.7
56.3
55.2
35,2
60.3
45.1
49.8
28.8
Table 4: Non-overlapping community detection results. Best and second best values are bold and blue respec-
tively.
F1-macro(%)
F1-micro(30
Algorithm
CiteSeer
CiteSeer-ful
Cora
Cora-ML.
Cora-full 30.4
CileSeer
CiteSeer-ful
Cora
Cora-ML
Cora-full
MNMF
57.4
68.6
60.9
64.2
60,8
68.1
62.7
64.2
32.9
DeepWalk
49.0
56.6
69.7
75.8
41.7
$2.0
57.3
70.2
75.6
48.3
75.3
Node2Vee
55.2
61.0
71.3
78.4
42.3
57.8
61.5
71.4
78.6
48.1
VGAE
59.1
74.4
70.4
75.2
32.4
62.2
74.4
72.0
76.4
37.7
GEMSEC
37.5
53.3
60.3
70.6
35.8
39.4
53.5
59.4
72.5
38.9
CNRI.
50.0
58.0
70.4
77.8
41.3
53.2
$7.9
70.4
78.4
45.9
ComGAN
55.9
65.7
56.6
62.5
27.7
59.1
64.9
58.5
62.8
29.4
vGraph
30.8
28.5
44.7
59,8
33.4
32.1
28.5
44.6
62.3
37.6
ComE
69.9
78.5
42.2
63.1
70.2
74,2
79.5
47.8
VECODeR
64.8
76.8
73.1
80.2
43.1
68.2
77.0
75.6
$2.0
49.6
Table 5: Node classification results. Best and second best values are bold and blue respeetively.

---

Under review as a conference paper at ICLR 2021
Tables 2 3 summarize the results of the performance comparison for the overlapping community detection task.
First, we note that our proposed method VECODER outperforms the competitive methods all datasets in terms of Jaccard Similarity. VECODER also outperforms its competitors on 12 out of 13 datasets in terms of F1-score. It is the second best method on the 13th dataset (fb0). These results demonstrate the capability of VECODER to learn multiple community assignments quite well and hence reinforces our intuition behind the design of Eq.
Second, we observe that there is no consistent performing algorithm among the competitive meth- ods. That is, excluding VECODER, the best performance is achieved by vGraph/vGraph+ on 5, ComGAN on 4 and ComE on 3 out of 13 datasets in terms of F1-score. A similar trend can be seen in Jaccard Similarity. Third, is noted that all the methods which achieve second best performance are solving the task of community detection and node representation learning jointly. This supports our claim that treating the two tasks jointly results in better performance.
Fourth, we observe that vGraph+ results are generally better than vGraph. This is because vGraph+ incorporates a regularization term the loss function which based on Jaccard coefficients of connected nodes as edge weights. However, it should be noted that this prepossessing step is com- putationally expensive for densely connected graphs.
Tab. shows the results on non-overlapping community detection. First, we observe that MNMF, Walk, LINE and Node2 provide a good baseline for the task. However, these methods are not able to achieve comparable performance on any dataset relative to the frameworks that treat the two tasks jointly. Second, VECODER consistently outperforms all the competitors in NMI and ARI metries, except for CiteSeer where it achieves second best ARI. Third, we observe that GCN based models i.e. GAE, VGAE and DGI show competitive performance. That is, they achieve second best performance in all the datasets except CiteSeer. In particular, DGI achieves second best NMI results in 3 out of 5 datasets and 2 out of 5 datsets in terms of ARI. Nonetheless, DGI results are not very competitive in Tab. 2 and Tab. 3 showing that while DGI can be good choice for learning node embeddings for attributed graphs with non-overlapping communities, it is not the best option for non-attributed graphs or overlapping communities.
The results for node classification are presented in Tab. VECODER achieves best F1-micro and F1-macro scores on out of 5 datasets. We also observe that GCN based models i.c. GAE, VGAE and DGI show competitive performance, following the trend in results of Tab. 4 Furthermore, we note that the node classification results of CommunityGan (ComGAN) are quite poor. We think a potential reason behind it is that the node embeddings are constrained to have same dimensions as the number of communities. Hence, different components of the learned node embeddings simply represent the membership strengths of nodes for different communities. The linear classifiers may find it difficult to separate such vectors.
4.5 HYPERPARAMETER SENSITIVITY
We study the dependence of VECODER on c and a by evaluating on four datasets of different sizes: fb698(N 61). fb1112(N = 747), (00010)000(N11144) and youtube(N
5346). We 0.3 and sweep for = (0.1, 0.2, 0.9). The average results of five runs for e and a are given in Fig. laland Fig. Ib respectively. Overall VECODER is quite robust to the change in the values of and a. In case of e, we see a general trend of decrease in performance when the threshold is set quite high e.g. E > 0.7. This is because the datasets contain overlapping communities and very high e will cause the algorithm to give only the most probable community assignment instead of potentially providing multiple communities per node. However, for a large part of sweep space, the results are almost consistent. When is fixed and a is changed, the results are mostly consistent except when a is set to low value. Eq. (1I) shows that in such a case the node itself is almost neglected and VECODER tends to assign communities based upon neighborhood only, which may cause a decrease in the performance. This effect is most visible in amazon1000 dataset because it has only 1.54 points on average per community i.c. there is a good chance for neighbours of a point of being in different communities. Therefore, only depending upon the neighbors will most likely result in poor results.
sweep for e 0.2 0.9). For demonstrating effect of a, we fix
8

---

Under review as a conference paper at ICLR 2021
-- F1-1-1912 -- FI-8669
Flamm1000 1000
F1-9h1911 -- F1-8609
Fleyoutthee
Plamm 1000
Jaccmnl-11912
J0ccuno--mma1000
Juscand-hi912 Inccad--b600
-Jcombyoatthe
Juscanl-ams
06
65
04
03
62
61
0.1
02
0.3
11.4
165
160
107
105
89
011
012
113
11.4 16.
168
007
205
3M
(a) Effect of c. Overall slight decrease in scores can (b) Effect of a. The scores generally tend to decrease for small values of a.
be observed after = 0.7 mark.
Figure Effect of hyperparameters on the performance. Fl and Jaccard scores are in solid and dashed lines respectively.
Vode2Voc
LINE
DeepWalk
vGraph
ComE
CNRL
VECoDER
CiteScer
CiteSecr-full
Cora
Cora-MI.
Cora-full
10
100
1000
10000
log(seconds)
Figure 2: Comparison running times of different algorithms.
4.6 TRAINING TIME
Now compare the training times of different algorithms in Fig. 2 As some of the baselines are more resource intensive than others, we select aws instance type g4dn. 4xlarge for fair com- parison of training times. For vGraph, iterations. For all other algorithms we use the default parameters as used in section 4.3 We ob- serve that the methods that simply output the node embeddings take relatively less time compared to the algorithms that jointly learn node representations and community assignments e.g VECODER, vGraph and CNRL. Among these algorithms VECODER is the most time efficient. It consistently trains in less time compared to its direct competitors. For instance, it is about 12 times faster than ComE for CiteSeer-full and about 40 times faster compared to vGraph for Cora-full dataset. This provides evidence for lower computational complexity of VECODER in Section 3.5
train for 1000 iterations and for VECODER for 1500
CONCLUSION
We propose scalable generative method VECODER to simultaneously perform community detec- tion and node representation learning. Our novel approach learns single community-awan node embedding for both the representation of the node and its context. VECODER is scalable due to its low complexity, i.e. O(EEK + Kd). The experiments on several graph datasets show that VECoDER consistently outperforms all the competitive baselines node classification. overlap- ping community detection and non-overlane non-overlap community detection tasks. Moreover, training the VECODER is highly time-efficient than its competitors.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yong-Yeal Ahn, James P Bagrow, and Sune Lehmann. Link communities reveal multiscale com- plexity networks. nature, 466(7307) 2010.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. arXiv preprint arXiv:1707.038/1 2017.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global
structural information, In Proceedings of the 24th ACM International on Conference on Informa- tion and Knowledge Management, CIKM '15, pp. 891900, New York, NY, USA, 2015. Associ- ation for Computing Machinery. ISBN 9781450337946. doi: 10.1 10.11452280441122885512 URL
https://doi.org/IO00 htt..o///00.11122228666666666660
Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuai Chang, and Erik Cambria. Learning community embedding with community detection and node embedding on graphs. In Proceedings of the 2017 ACM on Conference Information and Knowledge Management, pp- 377-386, 2017.
Imre Derényi, Gergely Palla, and Tamás Viesek. Clique percolation in random networks. Physical review letters, 64026, 2005.
Carl Doersch. Tutorial variational autoencoders. arXiv preprint arXiv: 2016.
Rong-En En Fan, Kai-Wei Chang. Cho-Jui Hsich, Xiang-Rut Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. Journal of machine learning research, 9(Aug):187111874 2008.
Sheng Gao, Ludovic Denoyer, and Patrick Gallinari. Temporal link prediction by integrating content and structure information. In Proceedings of the 20th ACM international conference Informa- tion and knowledge management, pp. 1169-1174, 2011.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint 1741v:100..0122,, 2017.
Prem K Gopalan and David M Blei. Efficient discovery of overlapping communities in massive networks. Proceedings of the National Academy of Sciences, 110036):1533411539, 2013.
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, 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterrization with gumbel-softmax. arXiv preprint 1rXiv:1611.000 144, 2016.
Yuting Jia, Qinqin Zhang, Weinan Zhang, and Xinbing Wang. Communitygan: Community detec- tion with generative adversarial nets. In The World Wide Web Conference, pp. 784-794, 2019.
Rayyan Ahmad Khan, Muhammad Umer Anwaar, and Martin Kleinsteuber. Epitomic variational graph autoencoder, 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint TrXiv::4/2.6990 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609000000 2016a.
Thomas N Kipf and Max Welling. 1611:1611.003000 2016b.
Variational graph auto-encoders. arXiv preprint
10

---

Under review as a conference paper at ICLR 2021
Mark Kozdoba and Shie Mannor. Community detection via measure space embedding. In Proceed- ings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' 15, pp. 28902898, Cambridge, MA, USA, 2015. MIT Press.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: citappsstanford.ecddddaaa June 2014.
Jure Leskovec and Julian Mcauley, Learning discover social circles in ego networks. In Advances in neural information processing systems, pp. 539-547, 2012.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv:1301.378. 2013.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. pp. 385 385-394, 2017.
Benedek Rozemberezki, Ryan Davies, Rik Sarkar, and Charles Sutton. Gemsec: Graph embedding with self clustering. In Proceedings of the 2019 IEEE/ACM international conference on advances in social networks analysis and mining, pp. 65-72, 2019.
Fan-Yur Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wei Huang, and Jian Tang. vgraph: A generative model for joint community detection and node representation learning. In Advances in Neural Information Processing Systems, pp. 514 524, 2019.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference world wide web, pp. 1067-1077, 2015.
Jiliang Tang, Charu Aggarwal, and Huan Liu. Node classification in signed social networks. In Proceedings of the 2016 SIAM international conference on data mining, pp. 54 62. SIAM, 2016.
Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 23(3):447-477 2011.
Cunchao Tu, Xiangkai Zeng, Hao Wang. Zhengyan Zhang, Zhiyuan Liu, Maosong Sun, Bo Zhang, and Leyu Lin. A unified framework for community detection and network representation learning. IEEE Transactions on Knowledge and Data Engineering, 31(6); 1051-1065, 2018
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10900, 2017.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. 2019.
Daixin Wang, Peng Cui, and Wenwu Zhu, Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp- 1225-1234, 2016.
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community preserving network embedding. AAAI, volume 17, pp. 203-209, 2017.
Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski. Overlapping community detection in net- works: The state-of-the-art and comparative study. Acm computing surveys (csur), 45(4):1-33. 2013.
Jaewon Yang and Jure Leskovec. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proceedings of the sixth ACM international conference on Web search and data mining, pp. 587-596, 2013.
11

---

Under review as a conference paper at ICLR 2021
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based ground- truth. Knowledge and Information Systems, 42(1):181-213, 2015.
Jaewon Yang, Julian McAuley, and Jure Leskovec. Community detection in networks with node attributes. In 2013 IEEE 13th International Conference Data Mining, pp. 1151-1156. IEEE, 2013.
Liang Yang, Xiaochun Cao, Dongxiao He, Chuan Wang, Xiao Wang, and Weixiong Zhang. Mod- ularity based community detection with deep learning. IJCAL, volume 16, pp. 2252-2256 2016a.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016b.
12


Reviews:
[{"review_id": "pG9e9ykt6Cm", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "(Summary)\n\nThis paper aims to learn node representations of graph to jointly satisfy node embedding properties and community detection property. Node embedding must preserve proximities guaranteeing that adjacent nodes are closer than others. Community detection must promote more similar clustering assignments to adjacent nodes than others. These two problems have been tackled separately or simultaneously but with maintaining two different node representations. The authors claim that the proposed VECoDeR is capable of learning a single community-aware node representation per node, which is jointly effective in both scenarios.\n\n\n(Originality and Contributions)\n\nTheir model assumes several conditional independences such as cluster assignments of different nodes given node representation, and adjacencies on different edges given the cluster assignments and node embeddings of each end. Then the rest of them creating ELBO and using reparametrization trick for training variational autoencoder follows the standard procedure. Posterior distribution of cluster assignment in the encoder adopt the weighted message passing (similar to graph convolution or Sun et al 2019). One possibly small novelty would be the parametrization of the edge decoder. In this sense, readers must find this paper’s contribution more in the practical side – superior performance -- than in the theoretical aspects.\n\n\n(Strength and weakness)\n- Strength is the performance that beats all other famous models. \n- Weakness is the lack of analysis that provide intuitions why and how VECoDeR outperforms other models by a big margin.\n\n\n(Concerns, Questions, and Suggestions)\n\n1) In the equation (12), the query random variable must be $a_{ij}$ rather than $e_{ij}$. \n\n2) It would be also great to double clarify what types of and how many parameters belong to the encoder (in $\\phi$) and the decoder (in $\\theta$). \n\n3) Using Gumbel-softmax trick allows you to efficiently sample one-hot vector of clustering assignment for non-overlapping community detection. For overlapping community detection, in contrast, clustering assignment matrix would be dense by assigning possibly negligible probability mass to all existing clusters. In the inference time, you are able to threshold it to reduce the dense connection by increasing $\\epsilon$, but how to scale the algorithm for learning large number of clusters?\n \n4) Related to the previous point, the number of clusters $K$ in all datasets seem to be orders of magnitudes smaller comparing to the number of nodes. This is often not satisfied in real data and some scenarios could ask overcomplete community detection (see Ananakumar et al 2012). Is the proposed model capable of detecting fine-grained community structures?\n\n5) Similarly, the model seems to be too independent from different hyperparameter settings of $\\alpha$ and $\\epsilon$ than expected. At least one or two datasets where the ground-truth overlapping communities are approximately known must be tested with much larger $K$ for robustness check.\n\n6) Assuming the reported performance are all correct, VECoDeR outperforms a variety of famous models for graph representation learning. Having some qualitative examples (than abstract explanation in high-level about structure preservation) would be beneficial. In particular, some part of the graph that does not performed well in all other models but correctly done by VECoDeR. Current draft rarely provides such intuitions to potential readers and users.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CmDoD71gNBL", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 proposes a generative model for community detection and node representation in a unified framework. The underlying assumption of the work is that connected nodes in a graph should have similar node embeddings and similar community assignments. Experimental evaluations show improvement both on node classification and community detection (both overlapping and non-overlapping).\n\nThe problem of integrating community detection and node representation in a unified framework is important and needs more attention from the researchers. The paper also motivates the problem well. The overall presentation is good and easy to follow. However, there are few concerns I have about the paper, as stated below.\n\n1. The technical approach of the paper seems to be quite similar to the cited work vGraph (NeurIPS 2019). It would be good to point out the major differences between the two works.\n\n2. Joint community detection and node representation learning - more discussion is needed for this subsection. Specifically, the existing works which integrate these two tasks and limitation of those works should be explained.\n\n3. In Eq. 3, is it fair to assume that z_i 's are iid random variables? Embedding of a node should depend on the embeddings of neighbors at the least.\n\n4. The GCN encoder aggregates the embeddings of the neighbors of a node while modeling q_{\\phi}(z_i | I). Then what is the need of Equation 11 instead of Equation 10?\n\n5. The last term of Equation 7 is a sum over all pairs of nodes, not only on the edges. Should not it lead to a computational complexity of O(N^2)?\n\n6. DGI (ICLR 2019) should be used for both non-overlapping community detection and node classification, as it is a SOTA algorithm for unsupervised node representation learning. \n\n7. In Section 4.4, only results in Tables 2-4 are presented in words. I could not see any analysis and insight in this section. The reason of superior performance of VECODER compared to individual baselines is also missing.\n\n8. Can authors also report classification accuracy on Cora and Citeseer, as that is a standard adopted by different SOTA network representation algorithms?\n\n\n------------------------------------\n\nAuthors did answer some of my doubts through their response. However, I am still not very convinced if the paper has sufficient novelty to get accepted in ICLR. I increase my score from 4 to 5.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5BDsYb5613", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "\nIn this work the authors propose a generative model for jointly learning a representation of nodes and communities in a joint framework.  The authors perform a wide variety of experiments on community (overlapping, non-overlapping) detection, and noed classification. This paper is potentially very interesting due to the large improvements it shows on some important tasks, but there are several non-trivial issues that I discuss in the following, and due to which I feel the paper is not above the bar in its current form. \n\n1. The authors should clarify early on, whether the focus is on undirected unweighted graphs, or general directed weighted graphs. \n\n2. The authors mention \"In the literature these tasks are treated separately\". The authors should discuss the problem more precisely. For instance if I have two connected components, each being a clique, most node embedding methods will capture this by placing nodes from each clique on the same point (or really close). If the two connected components are sparse, the nodes from each component will be embedded closer to each other compared to nodes from the other connected component.  So, standard graph embedding methods do capture basic connectivity, i.e., crude connectivity structure. This bring me also to the next point. \n3. How is the notion of a community defined here? Do you consider a community a set of low conductance? Or some set of nodes that share certain common attributes? I assume the former, i.e., some form of a well-connected set of nodes that is less well-connected to the rest of the graph.  \n4. Can the authors comment on the improvements they observe using their method? Is it due to the fact that labels within the community are overwhelmingly similar?  The authors use as competitors methods that do not take into account features. If the difference lies in this, the authors should compare also against graph convolutional networks. In any case, a more detailed explanation of the improvements is required in my opinion. See also point 8 for an important reference to this work. \n5. In terms of competitors for overlapping community detection the authors should take a look at  the recent paper \"SimClusters: Community-Based Representations for Heterogeneous Recommendations at Twitter\" that describes some mechanics of Twitter's recommendation system, and that uses the objective, and a variation of the algorithm  proposed in \"Provably fast inference of latent features from networks: With applications to learning social circles and multilabel classification\" WWW 2015 for overlapping community detection. The algorithms in these two papers for instance outperform BigClam. \n6. Does the proposed method yield any concrete theoretical improvement? For example, have the authors tried to show that it achieves better than Cheeger's approximation guarantee? Perhaps some simulation results on synthetic dataset can provide at least some experimental evidence by looking inner products of nodes within and across communities. \n7. It would be helpful to explain the novelty of this work compared to the vGraph Neurips 2019 paper. \n8. Concerning the top 5 communities choice, the authors should also take a look at this paper  \"The ground truth about metadata and community detection in networks\" Science Advances  where the notion of ground-truth used in this work is questioned.  \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4kimRyN-XOO", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "The paper deals with the problem of simultaneously learning node embeddings and detecting communities on graphs. Although both tasks are particularly important while analyzing networks, most of the proposed approaches address them independently. The paper proposes a generative model, called VECODER, that aims to jointly learn overlapping communities and node representations. The proposed model follows a variational formulation which assumes that the node embeddings are generated from a prior distribution; this can be used to control how community embeddings are sampled. This leads to an encoder-decoder architecture, where the decoder ensures that similar (i.e., connected) nodes will obtain similar embeddings. The proposed model has been empirically evaluated on three tasks (overlapping and non-overlapping community detection, and node classification), and the performance has been compared against various baseline models.\n\nStrong points:\n\n-- The paper addresses two important problems in network analysis, namely community detection and representation learning.  \n\n-- The paper is well-structured and well-written. In particular, the part of the proposed methodology is clearly presented and overall seems to be very interesting.\n\n-- In the experimental evaluation of the proposed model, the performance of VECODER is examined over multiple networks on three different tasks.\n\nWeak points:\n\n-- The main concern about the paper is related to the experimental evaluation. In particular, some important baselines methods are missing. Since the paper examines community-based embeddings, I would expect to consider M-NMF as a baseline. The authors mention M-NMF in the related work but do not consider it in the evaluation mainly due to its scalability issues. In any case, most of the datasets used in the experiments are relatively small, so I expect that M-NMF would be able to scale.\n\n-- Besides, a few other quite important baselines are missing from both the empirical evaluation and the related work. Below, I mention three papers that are highly relevant:\n\n- A unified framework for community detection and network representation learning, TKDD 2018\n- Graph Embedding with Self-Clustering, ASONAM 2019\n- CommunityGAN: Community Detection with Generative Adversarial Nets, CIKM 2019\n\nIs there any particular reason why these models have not been considered?\n\n-- Another point is related to the fact that the proposed model is based on an encoder-decoder framework that leverages features while learning embeddings. On the contrary, most of the used baseline models (e.g., ComE) do not take into account features while learning representations. Although node features are used while training a logistic regression classifier for node classification, to my view this is not a very fair comparison. So, my question is why the paper did not consider variants of GNN models (with unsupervised training) or Graph Autoencoders as baselines?\n\n-- Is there any particular reason why the task of link prediction has not been considered?\n\n-- In Table 3, in both CiteSeer networks, there is a huge gap in the performance of the proposed model compared to the baselines. Why is this happening?\n\n-- The parameter sensitivity experiments are very interesting. Nevertheless, I would expect to also have some experiments that would demonstrate how the design choices have affected the performance of the model. For instance, as mentioned in Sec. 3.3, would there be any impact on the performance on downstream tasks if different GNN architectures are used as encoders?\n\n\nMinor comments/typos:\n\n-- In the Related work section (page 2), it is mentioned that spectral clustering is applied to the adjacency matrix for extracting communities. I would propose the authors to mention the Laplacian matrix instead.\n\n-- Related work (page 3): some spaces are missing before references, and some others should be removed.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method to learn representation and community structure of a network jointly. The reviewers agree that the paper contains some interesting ideas but they raise also some important concerns. For example:

- even after considering the authors' rebuttal, the paper seems not too novel. In particular the results seem a bit incremental over vGraph.

- the notion of community is not formalized by the authors neither in the paper or in the rebuttal. The paper would benefit greatly by having such formal definition 

Overall, the paper is interesting but it does not meet the high acceptance bar of ICLR
Decision: Reject