An Interpretable Graph Generative Model with Heterophily
Authors: Sudhanshu Chanpuriya
Ryan Rossi
Anup Rao
Tung Mai
Nedim Lipka
Zhao Song
Cameron N Musco
Venue: ICLR 2022 Submitted (2022)
Keywords: graph
network
generative
heterophily
community detection
link prediction
interpretability

Abstract: Many models for graphs fall under the framework of edge-independent dot product models. These models output the probabilities of edges existing between all pairs of nodes, and the probability of a link between two nodes increases with the dot product of vectors associated with the nodes. Recent work has shown that these models are unable to capture key structures in real-world graphs, particularly heterophilous structures, wherein links occur between dissimilar nodes. We propose the first edge-independent graph generative model that is a) expressive enough to capture heterophily, b) produces nonnegative embeddings, which allow link predictions to be interpreted in terms of communities, and c) optimizes effectively on real-world graphs with gradient descent on a cross-entropy loss. Our theoretical results demonstrate the expressiveness of our model in its ability to exactly reconstruct a graph using a number of clusters that is linear in the maximum degree, along with its ability to capture both heterophily and homophily in the data. Further, our experiments demonstrate the effectiveness of our model for a variety of important application tasks such as multi-label clustering and link prediction. 

Under review as a conference paper at ICLR 2021
AN INTERPRETABLE GRAPH GENERATIVE MODEL WITH HETEROPHILY
Anonymous authors Paper under double-blind review
ABSTRACT
Many models for graphs fall under the framework of edge-independent dot product models. These models output the probabilities of edges existing between all pairs nodes, and the probability of link between two nodes increases with the dot prod- uct of vectors associated with the nodes. Recent work has shown that these models are unable to capture key structures in real-world graphs, particularly heterophilous structures, wherein links occur between dissimilar nodes. We propose the first edge-independent graph generative model that is a) expressive enough capture heterophily, b) produces nonnegative embeddings, which allow link predictions be interpreted in terms of communities, and c) optimizes effectively on real- world graphs with gradient descent on a cross-entropp loss. Our theoretical results demonstrate the expressiveness of our model in its ability to exactly reconstruct a graph using number of clusters that is linear in the maximum degree, along with its ability to capture both heterophily and homophily in the data. Further, our experiments demonstrate the effectiveness of our model for variety of important application tasks such as multi-label clustering and link prediction.
INTRODUCTION
Graphs naturally arise in data from variety of fields including sociology (Mason & Verwoerd, 2007), biology (Scott, 1988), and computer networking (Bonato, 2004). A key underlying task in machine learning for graph data is forming models of graphs which can predict edges between nodes, form useful representations of nodes, and reveal interpretable structure in the graph, such as detecting clusters of nodes. Many graph models fall under the framework of lnge-inneepedent graph generative models, which can output the probabilities of edges existing between any pair of nodes. The parameters of such models can be trained iteratively on the network, or some fraction of the network which is known, in the link prediction task, e.g., by minimizing cross-entropy loss. To choose among these models, one must consider whether the model is capable of expressing structures of interest in the graph, well the interpretability of the model.
Expressiveness As real-world graphs are nigh-dimensional objects, graph models generally com- press information about the graph. Such models are exemplified by the family of dot product models, which associate each node with a real-valued "embedding" vector; the predicted probability of the link between two nodes increases with the dot product of their embedding vectors. These models can alternatively be seen as factorizing the adjacency matrix of the graph in terms of a low-rank matrix. Recent work (Seshadhri et al., 2020) has shown that dot product models are limited in their ability to model common structures in real-world graphs, such as triangles incident only on low-degree nodes. In response, Chanpuriya et al. (2020) showed that with the logistic PCA (LPCA) model, which has two embeddings per node (i.e. using the dot product of the "left" embedding of one node and the "right" embedding of another), not only can such structures represented, but further, any graph can be exactly represented with embedding vectors whose lengths are linear in the maximum degree of the graph. Peysakhovich & Bottou (2021) show that the limitations of the single-embedding model, which are overcome by having two embeddings, stem from only being able to represent adjacency matrices which are positive -emiidefinite which prevents them from representing heterophilous structures in graphs; heterophilous structures are those wherein dissimilar nodes are linked.

---

Under review as a conference paper at ICLR 2021
Expected Adjacency
Sampled Adjacency
200 400 600 800
200 400 600 800
1.0
200
200
0.8
400
400
0.6
600
600
0.4
800
800
0.0
Figure 1: The motivating synthetic graph. The expected adjacency matrix (left) and the sampled matrix (right); the latter is passed to the training algorithms. The network is approximately union of ten bipartite graphs, each of which correspond to recruiters and non-recruiters of the ten locations.
SVD
BigClam
Ours
Frobenius Error
200 400 600 800
0 200 400 600 800
200 400 600 800
1.0
SVD
BgClam
200
200
200
0.8
Ours
400
400
0.6
0.8
600
600
600
0.4
800
800
800
0.2
15
20
0.0
Embesding Length
Figure 2: (Right) Reconstructions of the motivating synthetic graph of Figure with SVD, BIGCLAM, and our model, using 12 communities singular vectors. Note the lack of the small diagonal structure in BIGCLAM'S reconstruction; this corresponds to its inability to capture the heterophilous interaction between recruiters and non-recruites.. (Leftt) Frobenius synthetic graph of Figure with SVD, BIGCLAM, and our model, as the embedding length varied. The error is normalized by the sum of the true adjacency matrix (i.e., the number of edges).
when reconstructing the motivating
Motivating example To demonstrate how heterophily can manifest in networks, as well as how models which assume homophily can fail to represent such networks, we provide a simple synthetic example. Suppose recruiting website allows its members to contact each other; construct a graph of these members, with an edge indicating that two members have been in contact. Members either recruiters non-recruiters, and each member comes from of ten locations (e.g., a city). Members from the same location are likely to contact each other; this typifies homophily, wherein links occur between similar nodes. Furthermore, recruiters are unlikely to contact other recruiters, and non-recruiters are unlikely to contact other non-recruiters; this typifies heterophily. Figure shows an instantiation of such an adjacency matrix with 1000 nodes, which are randomly assigned to one of the ten locations and one of recruiter non-recruiter We recreate this network with our embedding model and the BIGCLAM algorithm of Yang Leskovec (2013), which explicitly assumes homophily. We also compare with the best low-rank approximation to the adjacency matrix in terms of Frobenius error; this the SVD of the matrix, discarding all but the top singular values. In Figure 1, we show how BIGCLAM captures only the ten communities based on location, i.c., only the homophilous structure, and fails to capture the heterophilous distinction between recruiters and con-recruiters We also plot the emror of the reconstructions the embedding length increases. There are 10 = 20 different kinds nodes, meaning the expected adjacency matrix is rank-20, and our model maintains the lowest error up this embedding length; by contrast, BIGCLAM is unable to decrease error after capturing location information with length-10 embeddings.
Heterophily:
Interpretability Beyond being able to capture a given network accurately, it is often desirable for graph model to form interpretable representations of nodes and to produce edge probabilities in an interpretable fashion. Dot product models can achieve this by restricting the node embeddings to be nonnegative. Nonnegative factorization has long been used to decompose data into parts (Donoho & Stodden, 2003). In the context of graphs, this entails decomposing the set of nodes of the network into clusters or communities. In particular, each entry of the nonnegative embedding vector of node
2

---

Under review as a conference paper at ICLR 2021
represents the intensity with which the node participates in community. Note that this allows the edge probabilities output by dot product models to be interpretable in terms of coparticipation in communities. Depending requirement, meaning the node is assigned a categorical distribution over communities. The least restrictive and most expressive case is that of soft assignments overlapping communities, where the entries can vary totally independently. In models for this case, the output of the dot product is often mapped through nonlinear link function produce a probability, i.e. ensure the value lies in [0, 1]. This link function ideally also facilitates straightforward interpretation.
the model. these vectors may have restrictions such as sum-to-one
We propose the first indeeedndeenddntt graph generative model that a) expressive enough to capture heterophily, b) interpretable in that it produces nonnegative embeddings, and c) optimizes effectively on real-world graphs with gradient descent on a cross-entropy loss.
Summary of main contributions
The key contributions of this work are as follows:
We introduce graph generative model, based on nonnegative matrix factorization, which is able represent both heterophily and overlapping communities. Our model outputs link probabilities which are interpretable in terms of the communities it detects.
We provide a scheme for initialization of the nonnegative factors using the arbitrary real factors generated by logistic PCA. We show theoretically how graph which is represented exactly by LPCA can also be represented exactly by our model.
We show theoretically that, with small number of communities, our model can exactly represent natural class of graphs which exhibits both heterophily and overlapping commu- nities.
In experiments, show that algorithm is competitive real wolld graphs in terms of representing the network, doing link prediction, and producing communities which align with ground-truth.
GRAPH GENERATIVE MODEL
Consider the set of undirected, unweighted graphs on n nodes, i.e., the set of graphs with symmetric adjacency matrices in {0, 1|=xa, We propose an edge-independent, generative model for such graphs Given a diagonal matrix W E gg and a matrix V E [0, 1]n*k, we set the probability of an edge existing between nodes i and j to be the (i.j) entry of matrix A:
À := oV WV), (VV)V,
where a the logistic function. represents the number of clusters; intuitively, if v, R is the i-th row of matrix V. then v, is soft assignment of node i to the i communities. W can be viewed as cluster affinity matrix. An equivalent alternative formulation is
Å., = ov.
Interpretation The edge probabilities output by this model have intuitive interpretation, and to maximize interpretability, we focus on the case where W is diagonal. Recall that there is a one-to-one-to-one relationship between probability p [0, 1]. odds o _"p E [0, oo), and logit l = log(o) E (-o0, +2o). The logit of the link probability between nodes i and j is v. Wv,, which a summation of terms ye over all communities e [k)). If the nodes both fully participate in community c, that is, baseline of 0, or equivalently the odds of an edge multiplied by exp Wco) starting from baseline odds of 1; if either of the nodes participates only partially in community c, then the change in logit and odds is accordingly prorated. Homophily and heterophily also have clear interpretaion in this model: homophilous communities are those with W.. 0, where two nodes both participating in the community increases the odds a link, whereas communities with Wae < 0 are heterophilous, and coparticipation decreases the odds of a link.
Vjc = 1, then the edge logit is changed by W starting from
3

---

Under review as a conference paper at ICLR 2021
3 RELATED WORK
Node clustering There is extensive prior work on the node clustering problem (Schacffer, 2007; Aggarwal & Wang, 2010; Nascimento & De Carvalho, 2011), perhaps the most well-known being the normalized cuts algorithm of Shi & Malik (2000), which produces a clustering based on the entrywise signs of an eigenvector of the graph Laplacian matrix. However, the clustering algorithms which are most relevant to our work are those based on non-negative matrix factorization (NMF) (Lee & Seung, 1999; Berry et al., 2007: Wang & Zhang, 2012: Gillis, 2020). One such algorithm is that of Yu et al. (2005), which approximately factors a graph's is adjacency matrix A E {0, 1)mxn into two positive matrices H and A, where H E 1 is left-stochastic (i.e. each of its columns sums to 1) and A R4** is diagonal, such that HAH = A. Here H represents soft clustering of the nodes into & clusters, while the diagonal entries of A represent the prevalence of edges within clusters. Note the similarity of the factorization to our model, save for the lack of nonlinearity. Other NMF approaches include those of Ding et al. (2008), Yang et al. (2012), Kuang et al. (2012), and Kuang al. (2015) (S (SMMNMF).
Modeling heterophily Much of the existing work on graph models has an underlying assumption of network homophily (Newman, 2002; Johnson et al., 2010; Noldus & Van Mieghem, 2015). There has been significant recent interest in the limitations of graph neural network (GNN) models (Duvenaud et al.. 2015; Li al., 2016; Kipf& & Welling, 2017: Hamilton et al., 2017) at addressing network heterophily (Nt & Maehara, 2019; Zhu et al., 2020), as well as proposed solutions (Pei et al., 2020; Zhu et al., 2021; Yan al., 2021), but relatively less work for more fundamental models such as those for clustering. Some existing NMF approaches to clustering do naturally model heterophilous structure in networks. The model of Nourbakhsh et al. 2)014,, for example, is similar to that of Yu et al. (2005), but allows the cluster affinity matrix A to be diagonaa:: this allows for inter-cluster edge affinity to exceed intra-cluster edge affinity, so heterophily can arise in this model, though it is not focus of their work. Further, the model of Miller et al. (2009) is similar ours and also allows for heterophily, though it restricts the cluster assignment matrix V to be binary; additionally, their training algorithm is not based on gradient descent as ours is, and it does not scale large networks. More recently, Peysakhovich & Bottou (2021) propose a decomposition of the form A ~ D + BB" CC where D Ruxa is diagonal and B, C' Rn*k are low-rank; the authors discuss how, interestingly, this model separates the homophilous and heterophilous structure into different factors, namely B and C. However, this work does not pursue a clustering interpretation or investigate setting the factors B and C' to be nonnegative. One stage of our training algorithm uses a similar decomposition, though it includes the nonnegativity constraint; this is detailed in Section 4.
Overlapping clustering Many models discussed above focus on the single-label clustering task. We are interested in the closely-related but distinct task of multi-label clustering, also known as overlapping community detection (Xie et al., 2013; Javed et al., 2018). The BIGCLAM algorithm of Yang & Leskovec (2013) uses the following generative model for this task: the probability of a link between two nodes and j is given by 1 - exp( ft f)). where f., fy E R represent the intensities with which the nodes participate in each of the communities. This model allows for intersections of communities be especially dense with edges, which the authors generally observe in real-world networks; by contrast, they claim that prior state-of-the-art approaches, including ones based on clustering links (Ahn et al., 2010) and clique detection (Palla et al., 2005), as well as a mixed-membershhip variant (Airoldi et al., 2008) of the stochastic block model (Holland et al., 1983), implicitly assume that intersections are sparse. BIGCLAM assumes strict homophily of the communities, whereas our model allows for both homophily and heterophily. Additionally, unlike in our model, there is no upper bound to the intensities of community participation (i.e. the entries of each f), so it is unclear how to incorporate prior knowledge about community membership in the form of binary labels, as in a superviid situation.
The approach of Zhang & Yeung (2012) is more similar to ours and more amenable to such prior information in that community assignments are bounded; specifically, the model is similar to those of Yu et al. (2005) and Nourbakhsh et al. (2014), but allows the cluster assignment matrix H to be an arbitrary matrix of probabilities rather left-stochastic. However, unlike our model and BIGCLAM, these models lack nonlinear linking function; recent work outside clustering and community detection on graph generative models (Rendsburg et al., 2020; Chanpuriya et al., 2020) suggests that the addition of nonlinear linking function, specifically softmax and logistic nonlinearities as in our
4

---

Under review as a conference paper at ICLR 2021
model, can make matrix factorization-basse graph models more expressive. Lastly, recent approach is the VGRAPH model of Sun et al. (2019), which also lacks a final nonlinear linking function, but, interestingly, has intermediate linking function: the matrix factors (i.e. the cluster assignment matrices) themselves are a product of learned embeddings for the nodes and communities, put through softmax linking function. Their algorithm ultimately determines overlapping communities in link clustering approaches, and they find that it generally achieves state-of-the-ar results in matching ground-truth communities; as discussed in Section 6.2, we find that our algorithm's 's performance on this task compares favorably to VGRAPH.
4 TRAINING ALGORITHM
Given an input graph A E {0, 1,=xn, we find V and W such that the model produces À aVVWVT) (0, 1)mx* as in Eq. (I) which approximately matches A. In particular, we train the model to minimize the sum of binary cross-entropie of the link predictions over all pairs of nodes:
R= R= Σ A log(A))
E(1 (o-)))) - A))
(3)
where Σ denotes the scalar summation of all entries in the matrix. Rather than optimizing the model of Equation I directly, we optimize different parametrizations which we find are more effective. This optimization comprises three stages, Note that while we outline a non-stochastic version of the algorithm, each stage can generalize straightforwardly stochastic version, i.e., by sampling links and non-links for the loss function.
First stage
We first fit the unconstrained logistic principal components analysis (LPCA) model to the input graph in Chanpuriya al. (2020). This model reconstructs graph Á {0, 1] using logit factors X, Y E Ro*k via the model
Á AXo
Factors X and Y are initialized randomly, then trained via gradient descent the loss of Equation so that Á x A. Note that entries of the factors X and Y are not necessarily nonnegative; hence this model does not directly admit an interpretation as community detection. Unlike Chanpuriya et al. (2020), which explicitly seeks to exactly fit the graph, i.e., to find X, Y such that À A, and does not explore the graph structure which is recovered in the factors, employ L2 regularization of the factors to avoid overfitting. See Algorithm for pseudocode of this stage.
Second stage The factors X and Y from the first stage are processed into nonnegative factors B R and C Baxke such that ky + kc = 3k and
BB CC ~ (XYT + +YXT).
Note that the left-hand side can only represent symmetric matrices. Let L -= = + a symmetrization
YXT).
TY if a (XYT) closely approximates the symmetric matrix A as desired, so too should the symmetrized logits. Pseudocode for this stage is given in Algorithm 2. The concept of this stage is to first separate the logit matrix into a sum and difference of rank-1 components via cigendecomposition. Each of these components can be written as +vv or -v with v E R", where the sign depends on the sign of the eigenvalue. Each component is then separated into sum difference of three outer products of nonnegative vectors, via the claim below.
Claim 4.1. Let Φ IR- + IR denote the ReLU activation function, i.e., d(2) = max 12, 0}. For any vector
vv 2 + 2Φ( (o6(-v)ch vv)((v)) + -VVlli
Proof. Take any R& Then
VV (d(vv - (V)) v(
= = T + +0(-v)o(-v) x(v) vv 66- ((-v)((v)
=20(v)Ø(v) + -T (0(v) + +d(-v)) (0(v) + o(-v))
= + +20(- -v)(vv)(vv) TT) /v/lVIT
5

---

Under review as a conference paper at ICLR 2021
where the first step follows from <0(v) <(-v), and the last step follows from |v o(vv) v(-v).
Algorithm 2 constitutes a constructive proof of the following theorem.
Theorem 4.2 (Nonnegative Factorization of Rank-k Matrices). Given a symmetric rank-k matrix L E IR xx there exist nonnegative matrices B E R4 and E IR such that kn + kc 3k: and BB CC
Third stage The factors B and C from the previous stage serve as initialization for the final stage of optimization. Of the 3k communities generated by the previous stage, keep the top k which are most impactful on the edge logits, as ranked by the L2 norms of the columns of B and C. Now B E 1 Bankn and C E paxke such that kn + kg = k.
These remaining communities then directly optimized by minimizing the cross-entropy loss of Equation 3 on the following graph model:
A=o BB -CC).
(5)
This stage proceeds exactly the first stage, i.e. as in Algorithm I, except with Equation 5 as the generative model rather than Equation 4. Additionally, the optimized parameters B and C' are constrained to be nonnegative.
The model Equation 5 is exactly equivalent to that Equation where W is constrained to be diagonal (i.e. diag(w) w)), and parameters can be transformed to that form with small manipulation.
Claim 4.3. Given nonnegative matrices E R4
Raxkn and C E R letting = kg + kc.
there exist a matrix E [0, 1jnk and a diagonal matrix W E BRak such that VWVT
BB CC
Proof. Let mp and mc be the vectors containing the maximums of each column of B and C, respectively. The equality and the constraints on V and W satisfied by setting
V B x diag (m C x diag (m²²))
W diag (++mg: -m
Algorithm 1 Fitting the Unconstrained LPCA Model
input adjacency matrix E 1) rank & < n, regularization weight > 0, number iters. output factors X, Y Ran such that o
A
Initialize elements of X, Y B randomly
2: for i + 1 to I do
3:
À < o
reconstructed adjacency matrix cross-entropy loss > regularization loss
R+ logg( A) 4 - (1- log(1 A)) lo)(1-A)
4:
5:
R+ R+ 1- x
+|
6:
Calculate 0x,y via differentiation through Steps 3 to 5
7:
Update X, Y minimize R using 0x,y
8: end for
9: return Y
Implementation details Our implementation uses PyTorch (Paszke et al., 2019) for automatic differentiation and minimizes the loss using the SciPy (Jones al., 2001) implementation of the L-BFGS (Liu Nocedal, 1989; Zhu et al., 1997) algorithm with default hyperparameters and up to a maximum of 200 iterations for both stages of optimization. We set the magnitude of the regularization to 10 times the mean entry value of the factor matrices. We include code the form of a Jupyter notebook (Pérez & Granger, 2007) demo in the supplemental material.

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Initializing the Constrained Model from LPCA Logits
input logit factors X, Y E R
output B, C' E [0, oo) ) n such that BB CC 2 (XYT+ + Y
1: Set Q R and A R* by truncated eigendecomposition
such that Q x diag(A (A) x Q s 1 1(XY + Y
2: B" Qt diag( V ++++), where X+, Q + the positive eigenvalues//ectors
3: C + Q x diag(v (on(vv--v ->-), where A Q are the negative eigenvalues/vectors
4: B (V20(B*) (2Φ(- C D @ and |. are entrywise ReI.U and absolute value
5: C (v20(C"); (C): B*)
6: return B,C'
THEORETICAL RESULTS
SYMNMF and BIGCLAM, among other models for undirected graph, assume network homophily, which precludes low-rank representation of networks with heterophily. We first show that our model highly expressive in that it can capture arbitrary homophilous and heterophilous structure: using a result from Chanpuriya et al. (2020), we show that our model can exactly reconstruct a graph using a number of communities that is linear in the maximum degree of the graph.
Lemma 5.1 (Exact LPCA Embeddings for Bounded-Degree Graphs, Champuriya al. (2020)). Let A E {0, 1|nxn be the adjacency matrix of a graph G with maximum degree c. Then there exist matrices X, Y E [B=x(2e+1) such that (XYT) )ay > 0 Ang = 1 and (XY )a < Of if Aij = O. Theorem 5.2 (Interpretable Exact Reconstruction for Bounde--Degree Graphs). Let A E {0, 1]mxn be the adjacency matrix of graph G with maximum degree c. Let k 12c + 6. For any e 0, there exist mV E [0, 1|nxk and diagonal W E Rixk such that |o (VWVT) - <c
Proof. Lemma 5.1 guarantees the existence of matrices X, X, Y E (xx(2++11 such that (XY T ")s if A. 1 and (XYT);; )5g 0 if A. = O. Let L
1 (XY + +YXT). the symmetrization of XY Since A is symmetrie, it still holds that L,, > if A., = and Ly < 0 if A, 0: further, as the sum of two rank-(2c + 1) matrices, the rank of L is at most 2 2-2cc + 1). Finally, by Claim 4.2 and Theorem 4.3, with k 3 2. (2c 1) = 12c + 6, there exist matrices V E [0, 1 n* and diagonal W E & such that VWV L, meaning still (VWV )is if Au 1 and
(VWV by < if Af = 0. Since lim (2) 0 and lim; (2) = 1, it follows that
lim o (V(sW)VT) lim (SVWVT) = A. $0000
6+000
that is, W can be scaled larger to match A arbitrarily closely.
The above bound on the number of communities k required for exact representation be very loose. We additionally show that our model can exactly represent a natural family of graphs which exhibits both homophily and heterophily with small k. The family of graphs is defined below; roughly speaking, nodes in such graphs share an edge iff they coparticipate in some number of homophilous communities and don't 't coparticipate in number of heterophilous communities. For example, the motivating graph described in Section 1 would be an instance of such a graph if there exists an edge between two nodes iff the two members are from the same location and have different roles (i.e., one is a recruiter and the other is non-recruiter).
Theorem 5.3. Suppose there is an undirected, unweighted graph on n nodes with adjacency matrix A {0, 1 whose edges are determined by an overlapping clustering and a "thresholding" integer 1 E Z in the following way: for each vertex i, there are two binary vectors b; E (0, 1 and L. Then, for any there exist V E [0, (k+()) and diagonal W E ((++1)x(+++)) such that (|o(VVV Alla <
C, E {0, 1] ke, and there is an edge between vertices i and j iff b,-
Proof. Let the rows of B E {0, 1]mx8f and C E m contain the vectors b and e of all nodes. By Claim 4.3, we find V E 1m and diagonal W & such that V V*T
7

---

Under review as a conference paper at ICLR 2021
Table Datasets used in our experiments. As in Sun al. (2019), for YOUTUBE and AMAZON, we take only nodes which participate in at least one of the largest ground-trute communities.
Name
Reference
Nodes
Edges
Labels
BLOG
Tang & Liu (2009)
10,312
333,983
YOUTUBE
Yang & Leskovec (2015)
5,346
24,121
5
POS
Mahoney
4,777
92,406
40
PPI
Breitkreutz al. (2007)
3,852
76,546
50
AMAZON
Yang Leskovee (2015)
794
2,109
BB CC Now let
W V = 1) W
1 -
0
Then (VWV 3i b; bj c: Cj + -1. Hence (VWVT) )ay 0 by - .. which is true iff A.j 1 by the assumption the graph. Similarly, (VWV )ij 0 iff A, It follows that
lim (V(sW)VT) lim (sVWVT) =. s-200
EXPERIMENTS
6.1 EXPRESSIVENESS
We investigate the expressiveness of our generative model, that is, the fidelity with which it can reproduce an input network. In Section I, used simple synthetic network show that our model is able to represent heterophilous structures in addition to homophilous structure. We now evaluate the expressiveness of our model on benchmark of real-worke networks, summarized in Table 1. As with the synthetic graph, we fix the number of communities or singular vectors, fit the model, then evaluate several types of reconstruction error. In Figure we compare the results of our model with those of SVD, BIGCLAM (Yang & Leskovec, 2013), and SYMNMF (Kuang et al., 2015). The BIGCLAM model is discussed in detail in Section 3. S SYMNMF simply factors the adjacency matrix as RJ HH where H gaxk, note that, like SVD, SYMNMF does not necessarily output matrix whose entries are probabilities (i.c., bounded in [0. 1)). and hence it is not graph generative model like ours and BIGCLAM.
For each method, we fix the number of communities singular vectors at the number of ground-truth -ruth communities the network. For a fair comparison with SVD, we do not regularize the training of the other methods. Our method consistently has the lowest reconstruction error, both in terms of Frobenius error and entrywise cross-entropy (Equation 3).
0.07
Entrywie Cross-Erros Entropy
0.06
Method
Froberius
SymNMFF
0.03
BigClem
0.02
0.01
0.0
0.00
P05
Blog
YouTube
POS
Blog
Amazon
YouTube
Dataset
Dataset
Figure 3: Error when reconstructing real-world graphs with SYMNMF, SVD, BIGCLAM, and our model. Frobenius error is normalized as in Figure 2; cross-entropy is normalized by the number of entries of the matrix )n²
8

---

Under review as a conference paper at ICLR 2021
6.2 SIMILARITY TO GROUND-TRUES CLUSTERS
As way of assessing the interpretability of the clusters generated by our method, we evaluate the similarity the clusters to ground-truth communities, and we compare with results from other overlapping clustering algorithms. For all methods, set the number of communities to be detected as the number of ground-trutt communities. We report F1-Score as computed in Yang & Leskovec (2013). See Figure 4. The performance of method is competitive with SYMNMF, BIGCLAM, and vGraph (Sun et al., 2019).
0.5
F1 Soore
Method
0.3
vGraph
SymNMF
BigClam
0.1
0.0
YouTube
Dalaset
Figure 4: Similarity of recovered communities to ground truuh communities of worldw datasets. We were unable to run the authors' implementation of VGRAPH on BLOG with 16 GB of memory.
6.3 LINK PREDICTION
We assess the predictive power our generative model via the link prediction task on real-world networks. As discussed in Section 2, the link probabilities output by our model are interpretable in terms of clustering of nodes that it generates; we compare results with our method to those of other models which permit similar interpretation, namely BIGCLAM and SYMNMF. We randomly select 10% node pairs to hold out (i.e. 10% entries of the adjacency matrix), fit the models on the remaining 90%, then the trained models predict whether there are links between node pairs in the held out 10%. As baseline for comparison, we also show results for randomly predicting link or no link with equal probability. See Figure 5 for the results. The performance of our method is competitive with or exceeds that of the other methods in terms of Fl Score.
0.25
Score
0.20
Method
F1
SymNMF
BigCllm
0.05
0.00
Blog Dalasel
Figure 5: Accuracy of link prediction real-world datasets.
CONCLUSION
We introduce an interpretable, edge-independent graph generative model that highly expressive at representing both heterophily and overlapping communities. Our experimental results show its effectiveness on many important tasks. Further, our theoretical results demonstrate the expressiveness of our model in its ability to exactly reconstruct graph using number of clusters that is linear in the maximum degree, along with its ability to capture both heterophily and homophily in the data. In general, deeper understanding of the expressiveness of both nonnegative and arbitrary low-rank logit models for graphs, as well as convergence properties of training algorithms, is an interesting direction for future research.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Charu C Aggarwal and Haixun Wang. A survey of clustering algorithms for graph data. In Managing and Mining Graph Data, pp. 275 375-301. Springer, 2010.
Yong- Yeol Ahn, James P Bagrow, and Sune Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466(7307):761-764 2010.
Edoardo Maria Airoldi, David M Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 2008
Michael W Berry, Murray Browne, Amy N Langville, Paul Pauca, and Robert Plemmons. Algorithms and applications for approximate nonnegative matrix factorization. Computational Statistics & Data Analysis, 52(1))155-177 173, 2007.
Anthony Bonato. A survey of models of the web graph. In Workshop on Combinatorial and Algorithmic Aspects of Networking, pp. 159-172. Springer, 2004.
Bobby-Joe Breitkreutz, Chris Stark, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, Michael Livstone, Rose Oughtred, Daniel L.akknr, Jürg Bähler, Valerie Wood, et The biogrid interaction database: 2008 update. Nucleic acids research, 366supp 2007.
Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. Node embeddings and exact low-rank representations of complex networks. Advances in Neural Information Processing Systems, 33, 2020.
Chris Ding, Tao Li, and Michael Jordan. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching, and clique finding. In 2008 Eighth IEFE International Conference Data Mining, pp. 192. IEEE, 2008
David Donoho and Victoria Stodden. When does non-negan non-negative matrix factorization give a correct decomposition into parts? In Advances in Neural Information Processing Systems 16, pp. 1141- 1148. MIT Press, 2003.
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-pparraguiree, Rafael Gómez-Bombarelli Tim- othy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems 28, pp. 2224 2232, 2015.
Nicolas Gillis. Nonnegative Matrix Factorization. SIAM, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5()): 137, 1983.
Muhammad Aqib Javed, Muhammad Shahzad Younis, Siddique Latif, Junaid Qadir, and Adeel Baig. Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications, 108:87-111, 2018.
Samuel Johnson, Joaquín J Torres, Marro, and Miguel A Munoz. Entropic origin of disassortativity in complex networks. Physical Review Letters,
2010.
Eric Jones, Travis Oliphant, Pearu Peterson, al. SciPy: Open source scientific tools for Python, 2001. URL http: / www. http:wwwwwwpppppppp//t/ttttt.ttt peciiyy.orgg. org/.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Da Kuang, Chris Ding, and Haesun Park. Symmetric nonnegative matrix factorization for graph clustering. In Proceedings of the 2012 SIAM International Conference on Data Mining, pp- 106-117.00 SIAM, 2012.
10

---

Under review as a conference paper at ICLR 2021
Da Kuang, Sangwoon Yun, and Haesun Park. Symomf: nonnegative low-rank approximation of similarity matrix for graph clustering. Journal of Global Optimization, 62(3):545- 574, 2013.
Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factoriza- tion. Nature, 401(6755) 1999.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In 4th International Conference on Learning Representations, ICLR 2016, 2016.
Dong C Liu and Jorge Nocedal. On the limited memory BEGS method for large scale optimization. Mathematical Programming, 45(1-3):503-528, 1989.
Matt Mahoney, Large text compression benchmark. URL httt:::/www.matmmettt dc/textdata.
net/
Oliver Mason and Mark Verwoerd. Graph theory and networks in biology. IET Systems Biology, 1 (2):89-119, 2007.
Kurt T. Miller, Thomas Griffiths, and Michael Jordan. Nonparametric latent feature models for link prediction. In Advances in Neural Information Processing Systems 22, pp. 1276-1284. Curran Associates, Inc., 2009.
Maria CV Nascimento and Andre CPLF De Carvalho. Spectral methods for graph clustering survey. European Journal of Operational Research, 21 211())221123)
2011. 2011.
Mark EJ Newman, Assortative mixing in networks. Physical Review Letters, 89(20)208701, 2002. 2002.
Rogier Noldus and Piet Van Mieghem. Assortativity in complex networks. Journal of Complex Networks, 344):507-542, 2015.
Farshad Nourbakhsh, Samuel Rota Bulo, and Marcello Pelillo. matrix factorization approach to graph compression. In 2014 22nd International Conference Pattern Recognition, pp. 76-81.
IEEE, 2014.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: wrXhv:1905.095500 2019.
Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Viesek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814-888) 818, 2005.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
Fernando Pérez and Brian Granger. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 9(3):21-29, May 2007. ISSN 1521-9615. doi: 10.1 109/ MCSE.2007.53, URL https: /ttp:://ppttooooooooo org.
Alexander Peysakhovich and Leon Bottou. An attract-repel decomposition of undirected networks. arXiv preprint arXiv:2106.0966 2021.
Luca Rendsburg, Holger Heidrich, and Ulrike Von Luxburg. Netgan without gan: From random walks
to low-rank approximations. In International Conference on Machine Learning, pp. 8073 8073-8082. PMLR, 2020.
Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007.
John Scott. Social network analysis. Sociology, 22(1):109-127, 1988.

---

Under review as a conference paper at ICLR 2021
C Seshadhri, Aneesh Sharma, Andrew Stolman, and Ashish Goel. The impossibility of low-rank representations for triangle-rich complex networks. Proceedings of the National Academy of Sciences, 117(11):5631-5633 2020.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 2288))888-905, 2000.
Fan-Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wa Huang, and Jian Tang. vgraph: A generative model for joint community detection and node representation learning. In Advances in Neural Information Processing Systems 32, pp. 512-522, 2019.
Lei Tang and Huan Liu. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 817-826. ACM, 2009.
Yu-Xiong Wang and Yu-Jin Zhang. Nonnegative matrix factorization: A comprehensive review.
IEEE Transactions on Knowledge and Data Engineering, 25(6):1336-135,, 2012.
Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski. Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Comput. Surv., 45(4):43:1-43:33 2013.
Yujum Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462. 2021.
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.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181 223, 2015.
Zhirong Yang. Tele Hao, Onur Dikmen, Xi Chen, and Erkki Oja. Clustering by nonnegative matrix factorization using graph random walk. In Advances in Neural Information Processing Systems, pp. 1079-1087, 2012.
Kai Yu, Shipeng Yu, and Volker Tresp. Soft clustering on graphs. Advances Neural Information Processing Systems, pp. 1553-1560, 2005.
Yu Zhang and Yan Yeung. Overlapping community detection via bounded nonnegative matrix tri-factorization. In The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD) 12, pp. 606 614. ACM, 2012.
Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale hound-constrainee optimization. ACM Transactions on Mathematical Software (TOMS), 2345)5550-560 1997.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Thirty-Fifth AAAI Conference Artificial Intelligence, pp. 11 168-1617 11 1176. AAAI Press, 2021.
12


Reviews:
[{"review_id": "zgZMD97r35A", "reviewer": "Reviewer_gNYK", "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": "The model is a combination of three distinct features: a soft assignment matrix $V$, the use of a non-linearity $\\sigma$, and finally a link matrix $W$ with arbitrary weights allowing for the modelling of heterophily. Many combinations of those three features are present in the literature (with Millet et al. being the closest one), but to the best of my knowledge this is the first general model that includes all three.\n\nThe algorithm proposed is technically sound, although the justification for steps 1 and 2 is tenuous: is it useful apart from selecting the right values for $k_B$ and $k_C$ ? This is an especially interesting question since step 2 involves the eigendecomposition of an $n \\times n$ matrix, which implies an important computational cost. It is also further exacerbated by the fact that the supplementary material only implements step 3 of the algorithm, with $k_B$ and $k_C$ set to appropriate \"magic\" values and $B, C$ randomly initialized.\n\nI find the section on theoretical results to be kind of a mixed bag. On the one hand, Theorem 5.3 is an interesting result, as it shows that the proposed algorithm covers a larger selection of mixed-membership models, including thresholding the matrix $\\bar A$ instead of drawing Bernoulli variables. On the other hand, Theorem 5.2 seems to me more of a negative result: if any adjacency matrix can be simulated in the form of equation (1), even if there is no community structure, this casts a doubt on the interpretability of the algorithm output.\n\nFinally, the experimental results are quite convincing, although they lack computation time analysis to really allow comparing algorithms together. It should maybe be noted that the results of Figure 1 are simply a consequence of Theorem 5.2, and the real interest of those experiments is to show that this approximation still captures the group assignments.\n\nOverall, this article glossed quite quickly on a major interpretability problem: the model in equation (1) is invariant with respect to a lot of transformations (rotations, scalings...) the the matrices $V$ and $W$; this is used in the proof of Claim 4.3 and Theorems 5.2 and 5.3. I am unsure how all those transformations affect the community memberships, and whether the simpler model with $W$ diagonal has the same clustering effectiveness than the full model. Of course, this does not affect link prediction, but the main selling point of this article is its connection to clustering (else is it similar to e.g. Peysakhovich & Bottou) and it falls short on this part.\n\nI am of course willing to revise my judgement if there is a simple resolution to this problem that I've missed and that can be added easily to the paper.\n", "summary_of_the_paper": "This article deals with the task of community detection in the case of mixed membership networks, where a node can have multiple comunity assignments at once. It has been notice that in real-world networks, community overlaps tend to be much denser than the rest of the graph, which is a challenge to usual models (such as the stochastic block model).\n\nThe authors introduce a new mixed-membership graph model, where the expected adjacency matrix has the form\n\n$$ \\bar A = \\sigma( V W V^\\top), $$\n\nwith $\\sigma$ the logistic function. In this model, the matrix $V$ represents the soft community assignments, and $W$ the inter-community similarities. The negative entries of $W$ allow this model to represent the heterophily of the network, wherein vertices are less likely to be connected when they belong to the same community.\n\nThey provide a learning algorithm to approximate $V$ and $W$ given the adjacency matrix $A$ of a graph, and show some existence results about such approximations.\n\nIn a second part, the authors provide several numerical experiments on real-world datasets, studying both the reconstruction of the matrix $\\bar A$ and of the community membership matrix $V$.  They show that, in the chosen datasets, their algorithm outperforms or equals several others in the litterature.\n\n", "summary_of_the_review": "This paper introduces a general model for mixed-membership community detection, along with an approximation algorithm to recover its parameters. This algorithms shows promising results on real-world datasets; however, the model has some interpretability issues that undermine its main selling point, and reduce its novelty compraed to the existing literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rNrtD2w8G9G", "reviewer": "Reviewer_TiK2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper has a strong motivation over the generative graph model problem (GGM). It covers its use, and it explains some of the problems, especially the difficulty to capture heterophily. The paper also explains a type of GGMs and most importantly, it develops the training algorithm and some interesting theoretical results, which seems correct. So far, the paper is making an important contribution. \n\nUnfortunately, there are some problems that must be addressed before publication.\n\nFirst, the related work does not cover generative graph models (GGM). Instead, it focuses on node clustering, modeling heterophily, overlapping clustering. There are several works about GGMs that must be included in this paper. Especially, GGMs that are able to replicate the network structure and other characteristics, such as: Chung-lu, mKPGM, Bter, and others.\n\nSecond, it is difficult to figure out the main contribution inside the proposed generative graph model. Equation 1 is just one of the many ways to define the generative graph model. Then, the main contribution seems to be the training algorithm. However, this is based on a previous theory (Chanpuriya et al. (2020) and others). So it seems that the main contribution is the second stage, but it is not clear. \n\nThird, the paper should explain why this model is able to model heterophily. The training process minimizes the sum of binary cross-entropies of the link predictions over all pairs of nodes. So, why does this minimization can model heterophily? How are they linked?\n\nForth, the implementation of this model is quite complicated and details are avoided. In line 6 from algorithm 1, where it is just mentioned \"Calculate ∂X,Y R via differentiation through Steps 3 to 5\". Please give more details about this step.\n\nFifth, add a time complexity analysis of the model, including the training and sampling process. While most generative graph models are able to reduce the time of the sampling process, as it is, the time complexity of the proposition is O(N^2), which is prohibitive for medium-size networks. \n\nSixth, given the low Frobenius error, it seems that the model suffers from the degenerative problem. This means that the model will generate almost the same network every time that is used to generate a network. \n\nHowever, the main problem is the evaluation of the model. The paper proposes a generative graph model (GGM) and the evaluation is based on node clustering. The main purpose of GGMs is to replicate the characteristics and structure of the network. This is not evaluated in this paper. To do this, you have to sample multiple networks from your model and figure out if they can actually replicate some global and local network characteristics from the original network, such as clustering coefficient, geodesic distance, and others. Most importantly, the paper does not evaluate if the model is able to replicate heterophily, one of their main contribution. ", "summary_of_the_paper": "The paper proposes an edge-independent graph generative model. Besides the model, the paper also proposes the training process of the model and some theoretical contributions. Unfortunately, the evaluation of the model is based on another problem, clustering. This makes the paper complicate to evaluate. While the main contributions could be important, its evaluation does not guarantee that is able to replicate real networks. Most importantly, given its current results, it must suffer from the degeneracy problem.", "summary_of_the_review": "While all contributions are very interesting, the evaluation of the paper is focused on another completely different problem. So, it is impossible to evaluate if the graph generative model is able to replicate the global and local characteristics of real networks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0gbsShpnCix", "reviewer": "Reviewer_Fdty", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths :-\n1) The paper discusses an important problem of modeling heterophily and overlapping communities in graph based generative models. Subsequently proposes an interesting approach to solving the same. \n2) Via usage of non-negative matrix factorization (NMF), the approach in the paper can supposedly output link probabilities which are interpretable in terms of the detected communities.\n\nWeaknesses :-\n1) The approach proposed in the paper lacks motivation. Specifically, i) why did the authors choose to solve the problem using the three stage process, ii) what does each stage achieve, iii) can the approach be simplified from its complicated current form ? \n2) I found the notation and descriptions in the paper to be confusing and wrong in several cases. Specifically I found the example demonstrated in Figures 1 and 2 to be confusing and not clear at all. In addition to this, it has typos - In figure 2, (right) and (left) in the captions are interchanged. Furthermore equation 1) is incorrect, i.e., how did the authors evaluate V.T * W * V when W is a k-by-k matrix and V is a n-by-k matrix is beyond me. I found parts of Section 4 to be unclear and confusing. To be more clear, the authors should have added more details about their training procedure and how they exactly achieve the different steps. I did not quite understand which part of their framework/approach or training procedure helps them capture/model the heterophily. \n3) Building on weakness 1), I did not like the authors complicated three stage approximation procedure. Using NMF on top of that, builds in more error in the expressions. I am curious as to how much approximation error they incorporate during the entire process. Additionally I am not sure if one requires non-negativity of embeddings for interpretability.\n4) There is no discussion of time/space complexity of their approach. I would like to see this detail in the paper.\n5) The experiments are limited and use small datasets. I would have liked to see more analysis and discussion of the results. Also the authors should have compared their results against other more recent methodologies to demonstrate the clear superiority of their approach which is lacking in the paper. Via using small datasets, it adds more doubts to 4) above. Will their approach work on larger datasets ?\n", "summary_of_the_paper": "In this work, the authors claim to propose the first edge-independent graph based generative model that can capture heterophily and via producing non-negative embeddings, it allows link predictions to be interpreted in terms of communities. The authors demonstrate the efficacy of their approach via empirical results in multi-label clustering and link prediction based tasks.", "summary_of_the_review": "The current version of the draft needs some work. The paper lacks motivation and novelty in terms of its approach. The paper also needs i) more empirical results both with larger datasets, ii)comparison with more recent state-of-the-art approaches and iii) some discussion/analysis. Many parts of the paper are unclear and missing important details.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an edge-independent graph generative model that can capture heterophily. The authors propose a 3-stage process to obtain the node representations. The idea of factorization in the form of BB^T-CC^T is an interesting approach to model heterophily.

The paper can be improved in terms of writing to better motivate the need for a 3-stage algorithm and how these individual steps are related to the existing techniques in the literature. The authors should elaborate on the implications of the theorems and the concerns raised by the reviewers in the body of the paper.

The algorithm faces scalability challenges, which are not studied well in the experiments. The reviewers also have raised concerns about degeneracy in network reconstruction experiments. Overall, the paper needs further improvements for publication.
Decision: Reject