AN INTERPRETABLE GRAPH GENERATIVE MODEL
Year: 2021

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 realworld 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.

text: 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 realworld 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.

heading: 1 INTRODUCTION
text: Graphs naturally arise in data from a 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 edge-independent 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 a cross-entropy loss. To choose among these models, one must consider whether the model is capable of expressing structures of interest in the graph, as well as the interpretability of the model.
Expressiveness As real-world graphs are high-dimensional objects, graph models generally compress 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 be 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 semi-definite, which prevents them from representing heterophilous structures in graphs; heterophilous structures are those wherein dissimilar nodes are linked.
Heterophily: 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 a recruiting website allows its members to contact each other; we construct a graph of these members, with an edge indicating that two members have been in contact. Members are either recruiters or non-recruiters, and each member comes from one 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 1 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 is 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.e., only the homophilous structure, and fails to capture the heterophilous distinction between recruiters and non-recruiters. We also plot the error of the reconstructions as the embedding length increases. There are 10 · 2 = 20 different kinds of nodes, meaning the expected adjacency matrix is rank-20, and our model maintains the lowest error up to this embedding length; by contrast, BIGCLAM is unable to decrease error after capturing location information with length-10 embeddings.
Interpretability Beyond being able to capture a given network accurately, it is often desirable for a 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 a node
represents the intensity with which the node participates in a community. Note that this allows the edge probabilities output by dot product models to be interpretable in terms of coparticipation in communities. Depending on the model, these vectors may have restrictions such as a sum-to-one requirement, meaning the node is assigned a categorical distribution over communities. The least restrictive and most expressive case is that of soft assignments to overlapping communities, where the entries can vary totally independently. In models for this case, the output of the dot product is often mapped through a nonlinear link function to produce a probability, i.e. to ensure the value lies in [0, 1]. This link function ideally also facilitates straightforward interpretation.
We propose the first edge-independent graph generative model that is 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 a graph generative model, based on nonnegative matrix factorization, which is able to 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 a graph which is represented exactly by LPCA can also be represented exactly by our model.
• We show theoretically that, with a small number of communities, our model can exactly represent a natural class of graphs which exhibits both heterophily and overlapping communities.
• In experiments, we show that our algorithm is competitive on real-world graphs in terms of representing the network, doing link prediction, and producing communities which align with ground-truth.

heading: 2 GRAPH GENERATIVE MODEL
text: Consider the set of undirected, unweighted graphs on n nodes, i.e., the set of graphs with symmetric adjacency matrices in {0, 1}n×n. We propose an edge-independent, generative model for such graphs. Given a diagonal matrixW ∈ Rk×k and a matrix V ∈ [0, 1]n×k, we set the probability of an edge existing between nodes i and j to be the (i, j)-th entry of matrix Ã:
Ã := σ(V >WV ), (1)
where σ is the logistic function. k represents the number of clusters; intuitively, if vi ∈ Rk is the i-th row of matrix V , then vi is soft assignment of node i to the k communities. W can be viewed as a cluster affinity matrix. An equivalent alternative formulation is
Ãi,j = σ(viWv > j ). (2)
Interpretation The edge probabilities output by this model have an 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 = p1−p ∈ [0,∞), and logit ` = log(o) ∈ (−∞,+∞). The logit of the link probability between nodes i and j is v>i Wvj , which is a summation of terms vicvjcWcc over all communities c ∈ [k]. If the nodes both fully participate in community c, that is, vic = vjc = 1, then the edge logit is changed by Wcc starting from a baseline of 0, or equivalently the odds of an edge is multiplied by exp(Wcc) starting from a 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 a clear interpretaion in this model: homophilous communities are those withWcc > 0, where two nodes both participating in the community increases the odds of a link, whereas communities withWcc < 0 are heterophilous, and coparticipation decreases the odds of a link.

heading: 3 RELATED WORK
text: Node clustering There is extensive prior work on the node clustering problem (Schaeffer, 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 adjacency matrix A ∈ {0, 1}n×n into two positive matrices H and Λ, where H ∈ Rn×k+ is left-stochastic (i.e. each of its columns sums to 1) and Λ ∈ Rk×k+ is diagonal, such that HΛH> ≈ A. Here H represents a soft clustering of the n nodes into k clusters, while the diagonal entries of Λ represent the prevalence of edges within clusters. Note the similarity of the factorization to our model, save for the lack of a nonlinearity. Other NMF approaches include those of Ding et al. (2008), Yang et al. (2012), Kuang et al. (2012), and Kuang et al. (2015) (SYMNMF).
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 et 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 et 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. (2014), for example, is similar to that of Yu et al. (2005), but allows the cluster affinity matrix Λ to be non-diagonal; this allows for inter-cluster edge affinity to exceed intra-cluster edge affinity, so heterophily can arise in this model, though it is not a focus of their work. Further, the model of Miller et al. (2009) is similar to 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 to large networks. More recently, Peysakhovich & Bottou (2021) propose a decomposition of the form A ≈ D + BB> − CC>, where D ∈ Rn×n 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, namelyB andC. However, this work does not pursue a clustering interpretation or investigate setting the factorsB andC 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 i and j is given by 1 − exp(−fi · fj), where fi,fj ∈ Rk+ represent the intensities with which the nodes participate in each of the k communities. This model allows for intersections of communities to 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-membership 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 semi-supervised 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 a 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 a nonlinear linking function, specifically softmax and logistic nonlinearities as in our
model, can make matrix factorization-based graph models more expressive. Lastly, a recent approach is the VGRAPH model of Sun et al. (2019), which also lacks a final nonlinear linking function, but, interestingly, has an 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 a softmax linking function. Their algorithm ultimately determines overlapping communities as in link clustering approaches, and they find that it generally achieves state-of-the-art results in matching ground-truth communities; as discussed in Section 6.2, we find that our algorithm’s performance on this task compares favorably to VGRAPH.

heading: 4 TRAINING ALGORITHM
text: Given an input graph A ∈ {0, 1}n×n, we find V and W such that the model produces Ã = σ(VWV >) ∈ (0, 1)n×n as in Eq. (1) which approximately matchesA. In particular, we train the model to minimize the sum of binary cross-entropies of the link predictions over all pairs of nodes:
R = − ∑( A log(Ã) ) − ∑( (1−A) log(1− Ã) ) , (3)
where ∑
denotes the scalar summation of all entries in the matrix. Rather than optimizing the model of Equation 1 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 to a 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 as in Chanpuriya et al. (2020). This model reconstructs a graph Ã ∈ {0, 1}n×n using logit factorsX,Y ∈ Rn×k via the model
Ã = σ(XY >). (4)
FactorsX and Y are initialized randomly, then trained via gradient descent on the loss of Equation 3 so that Ã ≈ A. Note that entries of the factorsX 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 findX,Y such that Ã = A, and does not explore the graph structure which is recovered in the factors, we employ L2 regularization of the factors to avoid overfitting. See Algorithm 1 for pseudocode of this stage.
Second stage The factors X and Y from the first stage are processed into nonnegative factors B ∈ Rn×kB+ and C ∈ R n×kC + such that kB + kC = 3k and
BB> −CC> ≈ 12 ( XY > + Y X> ) .
Note that the left-hand side can only represent symmetric matrices. Let L = 12 ( XY > + Y X> ) . L is a symmetrization ofXY >; if σ(XY >) closely approximates the symmetric matrixA 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 L into a sum and difference of rank-1 components via eigendecomposition. Each of these components can be written as +vv> or −vv> with v ∈ Rn, where the sign depends on the sign of the eigenvalue. Each component is then separated into a sum or difference of three outer products of nonnegative vectors, via the claim below. Claim 4.1. Let φ : R → R denote the ReLU activation function, i.e., φ(z) = max{z, 0}. For any vector v,
vv> = 2φ(v)φ(v)> + 2φ(−v)φ(−v)> − |v||v|>
Proof. Take any v ∈ Rk. Then vv> = (φ(v)− φ(−v)) · (φ(v)> − φ(−v)>)
= φ(v)φ(v)> + φ(−v)φ(−v)> − φ(v)φ(−v)> − φ(−v)φ(v)>
= 2φ(v)φ(v)> + 2φ(−v)φ(−v)> − (φ(v) + φ(−v)) · (φ(v) + φ(−v))>
= 2φ(v)φ(v)> + 2φ(−v)φ(−v)> − |v||v|>,
where the first step follows from v = φ(v)− φ(−v), and the last step follows from |v| = φ(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 ∈ Rn×n, there exist nonnegative matricesB ∈ Rn×kB+ and C ∈ R n×kC + such that kB + kC = 3k andBB> −CC> = L.
Third stage The factorsB and C from the previous stage serve as initialization for the final stage of optimization. Of the 3k communities generated by the previous stage, we keep the top k which are most impactful on the edge logits, as ranked by the L2 norms of the columns ofB and C. Now B ∈ Rn×kB+ and C ∈ R n×kC + such that kB + kC = k.
These remaining k communities are then directly optimized by minimizing the cross-entropy loss of Equation 3 on the following graph model:
Ã = σ ( BB> −CC> ) . (5)
This stage proceeds exactly as the first stage, i.e. as in Algorithm 1, except with Equation 5 as the generative model rather than Equation 4. Additionally, the optimized parametersB and C are constrained to be nonnegative.
The model in Equation 5 is exactly equivalent to that of Equation 1, whereW is constrained to be diagonal (i.e. diag(w)), and parameters can be transformed to that form with a small manipulation.
Claim 4.3. Given nonnegative matrices B ∈ Rn×kB+ and C ∈ R n×kC + , letting k = kB + kC , there exist a matrix V ∈ [0, 1]n×k and a diagonal matrix W ∈ Rk×k such that VWV > = BB> −CC>.
Proof. Let mB and mC be the vectors containing the maximums of each column of B and C, respectively. The equality and the constraints on V andW are satisfied by setting
V = ( B × diag ( m−1B ) ; C × diag ( m−1C )) W = diag (( +m2B ; −m2C )) .
Algorithm 1 Fitting the Unconstrained LPCA Model input adjacency matrixA ∈ {0, 1}n×n, rank k < n, regularization weight λ ≥ 0, number of iters. I output factorsX,Y ∈ Rn×k such that σ(XY >) ≈ A
1: Initialize elements ofX,Y ∈ Rn×k randomly 2: for i← 1 to I do 3: Ã← σ(XY >) . reconstructed adjacency matrix 4: R← − ∑( A log(Ã) ) − ∑( (1−A) log(1− Ã) ) . cross-entropy loss
5: R← R+ λ ( ‖X‖2F + ‖Y ‖2F ) . regularization loss 6: Calculate ∂X,Y R via differentiation through Steps 3 to 5 7: UpdateX,Y to minimize R using ∂X,Y R 8: end for 9: returnX,Y
Implementation details Our implementation uses PyTorch (Paszke et al., 2019) for automatic differentiation and minimizes the loss using the SciPy (Jones et 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 in the form of a Jupyter notebook (Pérez & Granger, 2007) demo in the supplemental material.
Algorithm 2 Initializing the Constrained Model from LPCA Logits input logit factorsX,Y ∈ Rn×k outputB,C ∈ [0,∞)n×3k such thatBB> −CC> ≈ 12 ( XY > + Y X> ) 1: SetQ ∈ Rn×k and λ ∈ Rk by truncated eigendecomposition
such thatQ× diag(λ)×Q> ≈ 12 (XY > + Y X>)
2: B∗ ← Q+ × diag( √
+λ+), where λ+,Q+ are the positive eigenvalues/vectors 3: C∗ ← Q− × diag( √ −λ−), where λ−,Q− are the negative eigenvalues/vectors
4: B ← (√ 2φ(B∗); √ 2φ(−B∗); |C∗| ) . φ and | · | are entrywise ReLU and absolute value
5: C ← (√ 2φ(C∗); √ 2φ(−C∗); |B∗| ) 6: returnB,C

heading: 5 THEORETICAL RESULTS
text: 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 is 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, Chanpuriya et al. (2020)). Let A ∈ {0, 1}n×n be the adjacency matrix of a graph G with maximum degree c. Then there exist matricesX,Y ∈ Rn×(2c+1) such that (XY >)ij > 0 ifAij = 1 and (XY >)ij < 0 ifAij = 0. Theorem 5.2 (Interpretable Exact Reconstruction for Bounded-Degree Graphs). LetA ∈ {0, 1}n×n be the adjacency matrix of a graph G with maximum degree c. Let k = 12c+ 6. For any > 0, there exist mV ∈ [0, 1]n×k and diagonalW ∈ Rk×k such that
∥∥σ(VWV >)−A∥∥F < . Proof. Lemma 5.1 guarantees the existence of matricesX,Y ∈ Rn×(2c+1) such that (XY >)ij > 0 if Aij = 1 and (XY >)ij < 0 if Aij = 0. Let L = 12 (XY
> + Y X>), the symmetrization of XY >. Since A is symmetric, it still holds that Lij > 0 if Aij = 1 and Lij < 0 if Aij = 0; further, as the sum of two rank-(2c+ 1) matrices, the rank of L is at most 2 · (2c+ 1). Finally, by Claim 4.2 and Theorem 4.3, with k = 3 · 2 · (2c+ 1) = 12c+ 6, there exist matrices V ∈ [0, 1]n×k and diagonalW ∈ Rk×k such that VWV > = L, meaning still (VWV >)ij > 0 ifAij = 1 and (VWV >)ij < 0 ifAij = 0. Since limz→−∞ σ(z) = 0 and limz→+∞ σ(z) = 1, it follows that
lim s→∞
σ ( V (sW )V > ) = lim s→∞ σ ( sVWV > ) = A,
that is,W can be scaled larger to matchA arbitrarily closely.
The above bound on the number of communities k required for exact representation can 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 coparticipate in a 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 a non-recruiter). Theorem 5.3. Suppose there is an undirected, unweighted graph on n nodes with adjacency matrix A ∈ {0, 1}n×n whose edges are determined by an overlapping clustering and a “thresholding” integer t ∈ Z in the following way: for each vertex i, there are two binary vectors bi ∈ {0, 1}kb and ci ∈ {0, 1}kc , and there is an edge between vertices i and j iff bi ·bj−ci ·cj ≥ t. Then, for any > 0, there exist V ∈ [0, 1]n×(k+1) and diagonalW ∈ R(k+1)×(k+1) such that
∥∥σ(VWV >)−A∥∥F < .
Proof. Let the rows ofB ∈ {0, 1}n×kb andC ∈ {0, 1}n×kc contain the vectors b and c of all nodes. By Claim 4.3, we can find V ∗ ∈ [0, 1]n×k and diagonal W ∗ ∈ Rk×k such that V ∗W ∗V ∗> =
BB> −CC>. Now let
V = (V ∗ 1) W =
( W ∗ 0
0 12 − t
) .
Then (VWV >)ij = bi · bj − ci · cj + 12 − t. Hence (VWV >)ij > 0 iff bi · bj − ci · cj > t− 12 , which is true iffAij = 1 by the assumption on the graph. Similarly, (VWV >)ij < 0 iffAij = 0. It follows that
lim s→∞
σ ( V (sW )V > ) = lim s→∞ σ ( sVWV > ) = A.

heading: 6 EXPERIMENTS

heading: 6.1 EXPRESSIVENESS
text: We investigate the expressiveness of our generative model, that is, the fidelity with which it can reproduce an input network. In Section 1, we used a simple synthetic network to show that our model is able to represent heterophilous structures in addition to homophilous structure. We now evaluate the expressiveness of our model on a benchmark of real-world 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 3, 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. SYMNMF simply factors the adjacency matrix as A ≈ HH>, where H ∈ Rn×k+ ; note that, like SVD, SYMNMF does not necessarily output a matrix whose entries are probabilities (i.e., bounded in [0, 1]), and hence it is not a graph generative model like ours and BIGCLAM.
For each method, we fix the number of communities or singular vectors at the number of ground-truth communities of 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).

heading: 6.2 SIMILARITY TO GROUND-TRUTH CLUSTERS
text: As a way of assessing the interpretability of the clusters generated by our method, we evaluate the similarity of the clusters to ground-truth communities, and we compare with results from other overlapping clustering algorithms. For all methods, we set the number of communities to be detected as the number of ground-truth communities. We report F1-Score as computed in Yang & Leskovec (2013). See Figure 4. The performance of our method is competitive with SYMNMF, BIGCLAM, and vGraph (Sun et al., 2019).

heading: 6.3 LINK PREDICTION
text: We assess the predictive power of 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 a 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% of node pairs to hold out (i.e. 10% of entries of the adjacency matrix), fit the models on the remaining 90%, then use the trained models to predict whether there are links between node pairs in the held out 10%. As a 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 F1 Score.

heading: 7 CONCLUSION
text: We introduce an interpretable, edge-independent graph generative model that is 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 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. In general, a 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.

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

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).  The authors introduce a new mixed-membership graph model, where the expected adjacency matrix has the form  $$ \bar A = \sigma( V W V^\top), $$  with $\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.  They 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.  In 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.