Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings
Authors: Sudhanshu Chanpuriya
Ryan A. Rossi
Anup Rao
Tung Mai
Nedim Lipka
Zhao Song
Cameron N Musco
Venue: NeurIPS 2023 poster (2023)
Keywords: graph
network
embeddings
arboricity
factorization
model
community
nonnegative
TL;DR: We expand on previous bounds for exact factorization of undirected graphs and extend them to our proposed model, which is more interpretable.

Abstract: Graph models based on factorization of the adjacency matrix often fail to capture network structures related to links between dissimilar nodes (heterophily). We introduce a novel graph factorization model that leverages two nonnegative vectors per node to interpretably account for links between both similar and dissimilar nodes. We prove that our model can exactly represent any graph with low *arboricity*, a property that many real-world networks satisfy; our proof also applies to related models but has much greater scope than the closest prior bound, which is based on low *max degree*. Our factorization also has compelling properties besides expressiveness: due to its symmetric structure and nonnegativity, fitting the model inherently finds node communities, and the model's link predictions can be interpreted in terms of these communities. In experiments on real-world networks, we demonstrate our factorization's effectiveness on a variety of tasks, including community detection and link prediction.

Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings
Sudhanshu Chanpuriya', Ryan A, Rossi', Anup Rao², Tung Mai?, Nedim Lipka', Zhao Song', and Cameron Musco
"University Illinois Chrmma-Champaign, schariya@illinois edu com 3 University of Massachusetts Amherst, cmuscolcs, umass. edu
2 Adobe Research, fryrossi, anuprao,
Abstract
Graph models based on factorization of the adjacency matrix often fail to capture network structures related to links between dissimilar nodes (heterophily). We introduce novel graph factorization model that leverages two nonnegative vectors per node to interpretably account for links between both similar and dissimilar nodes. We prove that our model can exactly represent any graph with low arboric- ity, a property that many real-world networks satisfy; related models but has much greater scope than the closest prior bound, which is based low max degree. Our factorization also has compelling properties besides expressiveness: due to its symmetric structure and nonnegativity, fitting the model inherently finds node communities, and the model's link predictions can be interpreted in terms of these communities. In experiments on real-world networks, we demonstrate our factorization's ''s effectiveness a variety of tasks, including community detection and link prediction.
proof also applies
Introduction
Graphs data naturally arises in a variety of fields including sociology (Mason & Verwoerd, 2007), biology (Scott, 1988), and computer networking (Bonato, 2004). A key task in machine learning for graph data is forming models of graphs that can predict edges between nodes, form useful representations of nodes, and reveal interpretable structure in the graph, such detecting clusters of nodes. Many graph models fall under the framework edge-independent graph generative models, which 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, i.e., by minimizing predictive loss. To choose among these models, one must consider two criteria: 1) whether the model can express structures of interest in the graph, 2) whether the model expresses these structures in interpretable way.
Expressiveness of low-dimensional embeddings As real-world graphs are high-dimensional objects, graph models generally compress information about the graph. For example, dot product models associate each node with a real-valued "embedding" vector; the predicted probability a link between two nodes increases with the similarity of their embeddings. These models can alternatively be seen as factorizing the graph's 's adjacency matrix to approximate it with a low-rank matrix. Recent work of Seshadhri et al. (2020) has shown that dot product models limited in their ability to model common structures in real-world graphs, such as triangles incident only on low-degree nodes. In response, Chanpuriya al. (2020) showed that with the logistic principal components analysis (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
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

max degree of the graph. There are two keys to this result. First is the presence of a nonlinear linking function in LPCA; since adjacency matrices are generally not low-rank, exact low-rank factorization is impossible without a linking function. Second is that having two embeddings rather than one allows for expression of non-positive semidefinite (PSD) matrices. As discussed in Peysakhovich & Bottou (2021), that the single-embedding models can only represent PSD matrices precludes representation of "heterophilous" structures in graphs; heterophilous structures are those wherein dissimilar nodes are linked, in contrast to more intuitive "homophilous" linking between similar nodes.
Interpretability and node clustering Beyond being able to capture 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). 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 community. 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 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 such models, which include the BIGCLAM model of Yang & Leskovec (2013), the output of the dot product may be mapped through a nonlinear link function (as in LPCA) to produce probability for each edge, i.e., to ensure the values lie in [0, 1].
Summary of contributions
The key contributions of this work are as follows:
We prove that LPCA admits exact low-rank factorizations of grappss with bounded arboricity. which is the minimum number of forests into which a graph's 's edges can be partitioned. By the Mash-WWlliams theorem, arboricity a measure of a graph's 's density in that, letting S denote an induced subgraph and nig and ms denote the number of nodes and edges in S, arboricity is the maximum over all of ng- n 1. Our result is more applicable to world graphs than the prior result of Champuriya et al. (2020) for graphs with bounded max degree, since sparsity is a common feature of real networks, whereas low max degree is not.
me
We introduce a graph model that extends LPCA and is both highly expressive and inter- pretable. Our model incorporates two embeddings per node and a nonlinear linking function, and hence is able to express both heterophily and overlapping communities. At the same time, our model based on symmetric nonnegative matrix factorization, so outputs link probabilities that are interpretable in terms of the communities it detects. While prior graph factorizations incorporate some aspects of nonnegativity, heterophily, and/or nonlinearity, our proposed model lies at the intersection of all three.
We show how any graph with a low-rank factorization in the LPCA model also admits a low-rank factorization in our community-bass model. This means that the guarantees on low-rank representation for bounded max degree and arboricity also apply to our model.
In experiments, we show that our method is competitive with and often outperforms other comparable models on real-world graphs in terms of representing the network, doing interpretable link prediction, and detecting communities that align with ground-truth.
2 Motivating Example
To demonstrate how heterophily can manifest in networks, as well how models which assume homophily can fail to represent such networks, we provide a simple synthetic example involving a graph of matches between users of a dating app. Suppose that users of this app are generally seeking partners of a different gender (to simplify this example, we assume that each user of the app is either a man or a woman), and suppose that each user comes from one of ten cities. Members from the same city are likely to match with each other; this typifies homophily, wherein links occur between similar nodes. Furthermore, users having the same gender are unlikely to match with each other; this typifies heterophily. Figure shows an instantiation of such an adjacency matrix with 1000 nodes, which are randomly assigned to man or woman and to one of the ten cities. We recreate this network with proposed embedding model and with BIGCLAM which explicitly assumes

---

homophily. We also compare with the SVD of the adjacency matrix, which outputs the best (lowest Frobenius error) low-rank approximation that is possible without a nonlinear linking function. Since SVD lacks nonnegativity constraints on the factors, we do not expect intepretability. In Figure 2, we show how BIGCLAM captures only the ten communities based on city, i.e., only the homophilous structure, and fails to capture the heterophilous distinction between men and women. 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 city information with length- 10 embeddings. In Figure 3, we visualize the features generated by the three methods, ie., the factors returned by each factorization. Our model's factors capture the relevant latent structure in an interpretable way. By contrast, SVD's factors are harder to interpret. and BIGCLAM does not represent the heterophilous structure.
Expected Adjacency
Sampled Adjacency
200 403 e20 #20
200 420 so0 so0
400
400
05
500
0.4
200
02
Figure 1: The motivating synthetic graph. The expected adjacency matrix (left) and the sampled matrix (right); the latter, which is passed to the training algorithms, is produced by treating the entries of the former as parameters of Bernoulli distributions and sampling. The network is approximately a union of ten bipartite graphs, each of which correspond to men and women in one of the ten cities.
SVD
BigClam
Ours
Frobenius Error
200 400 600 800
200 400 600 800
200 400 600 800
SVD
BiyClam
200
200
200
Ours
400-
800
800
Rno
R00
5
10 15 Embedsing Length
20
Figure 2: Left: Reconstructions of the motivating synthetic graph of Figure 1 with SVD, BIGCLAM, and our model, using 12 communities or 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 men and women. Right: Frobenius error when reconstructing the motivating synthetic graph of Figure I with SVD, BIGCLAM, and our model, as the embedding length is varied. The error is normalized by the sum of the true adjacency matrix (i.e., twice the number of edges).
SVD
BigClam
Ours
1.0
0.0
0.5
10
0.0
200
302
230
420
500
800
00
-0.5
Figure 3: Factors resulting from decomposition of the motivating synthetic graph of Figure I with the three models, using 12 communities singular vectors. The top/bottom rows represent the positive/negative cigenvalues corresponding to homophiloushherrpphiuuu communities (note that BIGCLAM does not include the latter). The homophilous factors from BIGCLAM and our model reflect the 10 cities, and the heterophilous factor from our model reflect men and women. The factors from SVD are harder to interpret. Note that the order of the communities in the factors is arbitrary.
3

---

3 Community-Bane -Based Graph Factorization
Consider the set of undirected, unweighted graphs on n nodes, i.e., the set of graphs with symmetric adjacency matrices in {0, 1 jexn, We propose an edge-independent generative model for such graphs.
Given nonnegative parameter matrices B E 1 and C' E R we set the probability of an edge existing between nodes and j to be the (i, entry of matrix A:
Á == o ).
(I)
where a is the logistic function. Here kB. ke are the number of homophiloushhetrrpphiouuu clusters. Intuitively, if b; E _ is the i-th row of matrix B, then b, is the affinity of node i to each of the kn homophilous communities. Similarly, C2 E R4C is the affinity of node i to the kc heterophilous communities. As an equivalent statement, for each pair of nodes and j. A.,; == ob,,, c.e..) We will soon discuss the precise interpretation of this model, but the idea is roughly similar to the attract-repel framework of Peysakhovich "attractive' b embeddings, i.e., when b,b, is high, the likelihood of edge between them increases, hence why the B factor is homophilous. By contrast, the factor is 'repulsive'/hetee /heterophilous since, when c,c. is high, the likelihood of an edge between and j decreases.
Bottou (2021). When nodes and have similar
Alternate expression We note that the model above can also be expressed in form that normalizes cluster assignments and is more compact, in that it combines the homophilous and heterophilous cluster assignments. Instead of B and C, this form uses matrix V E [0, 1jm*k and diagonal matrix W E R*** where k kg + ke is the total number of clusters. In particular, let mg g and mc be the vectors containing the maximums of each column of B and C. By setting
= (B - diag (m C C C-diag (mz²))
(2)
W = diag (++mg: -m
the constraint on V satisfied. Further, VWV BBB CC A o==oBBB'
=
Here, v; E [o, 11ah is the i-th row of matrix V. then v, is the soft (normalized) assignment of node i to the & communities. The diagonal entries of W represent the strength of the homophily (if positive) or heterophily (if negative) of the communities. For each entry, Ai,j (v, We use these two forms interchangeably throughout this work.
Interpretation The edge probabilities output by this model have an intuitive interpretation. Recall that there are bijections between probability p [0, 1]. odds = - [0, o0), and logit e log(o) E (-o0, +oo). The logit of the link probability between nodes and j is v Wvj, which is summation of terms Via V W.r cz. over all communities e E [A:. If the nodes both fully participate in community c, that is, Vic Vjc-- 1, then the edge logit is changed by W.. starting from baseline of O, or equivalently, the odds of an edge is multiplied by exp( Woe) 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 clear interpretation in this model: homophilous communities. which are expressed in B, are those with W.c O, where two nodes both participating in the community increases the odds of a link, whereas communities with Wec < O, which are expressed in C, are heterophilous, and coparticipation decreases the odds of link.
4 Related Work
Community detection via interpretable factorizations There is extensive prior work on com- munity detection and node clustering (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), many of which can be seen integrating nonnegativity constraints into

---

the broader, well-studied random dot product graph (RDPG) model (Young & Scheinerman, 2007;
Scheinerman & Tucker, 2010; Athreya et al., 2017). One such algorithm that of Yu al. (2005). which approximately factors a graph's adjacency matrix A E {0, 1 into two positive matrices H. and A, where H E 1 is left-stochastic and A E _ is diagonal, such that HAH R A. Here H represents a soft clustering of the n 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 et al. (2015) (SYMNMF).
Modeling heterophily Much of the existing work on graph models has an underlying assumption of network homophily (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; Kipf & Welling, 2017: Hamilton et al., 2017) at addressing network heterophily (NT & Maehara, 2019; Zhu et al., 2020; Zheng al., 2022), well as proposed solutions (Pei et al., 2020; Yan et al., 2021), 1), but relatively less work for models applicable to 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 A 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. Another example is the model in Miller et al. (2009), which is similar to ours, 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 larger networks. More recently, Rubin-Delanchy et al. (2017) and Peysakhovich & Bottou (2021) propose simple decompositions which allow for representation of non-PSD) adjacency matrices. The model in the latter work is a factorization of the form A ~ + BB CC where D E guXa is diagonal and B, C' E Ra are low-rank; excluding the diagonal D term, the model in the former work is algebraically identical. The authors discuss how, interestingly, this model separates the homophilous and heterophilous structure into different factors, namely B and C, corresponding to positive and negative eigenvalues, respectively. Note that these decompositions do not include nonlinear linking function, which is crucial to our exact factorization results, and the respective works do not investigate constraining the factors to be nonnegative.
Overlapping communities and exact embeddings Many models discussed above focus on the single-label clustering task and thus involve highly-constraineed factorizations (e.g., sum-to-one conditions). 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), which involves less constrained, more expressive factorizations. The BIGCLAM algorithm of Yang & Leskovec (2013) uses the following generative model for this task: the probability of link between two nodes i and j is given by exp(-f; fJ), where f; E TR represent the intensities with which the nodes participate in each of the & communities. Note that BIGCLAM assumes strict homophily of the communities: two nodes participating in the same community always increases the probability of a link. However, this model allows for expression of very dense intersections of communities, which the authors observe is generally a characteristic of real-world networks. To ensure that output entries are probabilities, BIGCLAM'S factorization includes nonlinear linking function (namely, f(x) = 1 - e²), like our model and LPCA. Recent work outside clustering and community detection on graph generative models (Rendsburg al., 2020; Chanpuriya et al., 2020) suggests that incorporating a nonlinear linking function can greatly increase the expressiveness of factorization-bast based graph models. to the point of being able to exactly represent graph. This adds to a growing body of literature on expressiveness guarantees for embeddings on relational data (Sala et al., 2018; Bhattacharjee & Dasgupta, 2020; Boratko et al., 2021). Most relevant to work, as previously discussed, Chanpuriya et al. (2020) provide a guarantee for exact low-rank representation of graphs with bounded max degree when using the LPCA factorization model. In this work, we provide a new such guarantee, except for bounded arboricity, which is more applicable to real-world networks, and extend these guarantees to our community-bane factorization.
5 Theoretical Results
We first restate the main result from Chanpuriya et al. (2020) on exact representation of graphs with bounded max degree using the logistic principal components analysis (LPCA) model, which
5

---

reconstructs graph A E {0, 10.1)=xm xx using logit factors X, Y E R via
A == o=
Note that unlike our community-based factorization, the factors of the LPCA model are not nonnega- tive, and the factorization does not reflect the symmetry the undirected graph's adjacency matrix. Regardless of the model's ss interpretability, the following theorem provides significant guarantee on its expressiveness. We use the following notation: given a matrix M, let H (M) denote the matrix resulting from entrywise application of the Hcaviside step function to M, that is, setting all positive entries to I, negative entries to O, and zero entries to 1/2.
Theorem 5.1 (Exact LPCA Factorization for Bounded -Degree Graphs ). Ler A E {0, [0,1] be the adjacency matrix of a graph G with maximum degree c. Then there exist matrices X, Y E [2x(2e+1) such that A = (XY
This corresponds to arbitrarily small approximation error in the LPCA model (Equation 4) because, provided such factors X, Y for some graph A, we have that Iim a (sXY (+XYT)= H ((XYT) = A.
That is, we can scale the factors larger to reduce the error to an arbitrary extent.
We expand on this result in two ways. First, give a new bound for exact embedding in terms of arboricity, rather than max degree. This increases the applicability to real-world networks, which often are sparse (i.e., low arboricity) and have right-skewed degree distributions (i.e., high max degree). Second, we show that any rank-k LPCA factorization can be converted to our model's 's symmetric nonnegative factorization with (k) communities. This extends the guarantees on the LPCÅ model's power for exact representation of graphs, both the prior guarantee in terms of max degree and our model as well. In Appendix A.I, we also
new one terms of arboricity, to our community-bue introduce a natural family of graphs Community Overlap Threshold (COT) graphs for which our model's s community-base based factorization not only exactly represents the graph, but also must capture some latent structure to do so with sufficiently low embedding dimensionality.
Arboricity bound for exact representation We will use the following well-known fact: the rank of the entrywise product of two matrices is at most the product of their individual ranks, that is,
rank(X X Y) S rank X) rYnk(Y).
Theorem 5.2 (Exact LPCA Factorization for Bounded-Arboricn Graphs). Let A {0, 1]nxn be the adjacency matrix of an undirected graph G with arboricity Then there exist embeddings X, E (1x) such that A = H(XY)).
Proof. Let the undirected graph A have arboricity a; i.e., the edges can be partitioned into forests. We produce a directed graph B from A by orienting the edges in these forests so that each node's edges point towards its children. Now A = B + B and every node in B has in-degree at most
Let E 2 be the Vandermonde matrix with V., 0-11 For any e RR200 (Vc[(t)
EJs e()) - 1011 10-1,thae that is, Ve E "R"" is a degree-(2a) polynomial with coefficients e evaluated at the Let by be the 5th column of B. We seek to construct polynomial such that for with (t) = 1, c:](()
integers E [m] (1, (1,....,,) n).
O, and [Vci](t) < O elsewhere; that is, when inputting an index ł [ni] such that the jdh node an in-neighbor of the 7th node, we want the polynomial to output 0, and for all other indices in [n]. we want it to have a negative output. Letting N (1) denote the in-neigbbors of the 7th node, simple instantiation of such a polynomial in is -1 II ( (t j)?.
Note that since all nodes have in-degree at most a, this polynomial's degree most 2a, and hence there exists coefficient vector E 20 encoding this polynomial.
Let C E x be the matrix resulting from stacking such coefficient vectors for each of the nodes. Consider P = VC E Raxn; P.j is 0 if B., = 1 and negative otherwise. Then (P o P )
is O when either Btj = or (B )e. = 1 and positive otherwise; equivalently, since A = B +
(Po PT), = 0 iff A.j = 1. Take any positive e less than the smallest positive entry of P PT Letting J be an all-ones matrix, define M = =J - (P PT). Note that Mi, > 0 if A = 1 and
M,j if A 0, that is, M ((A) desired. Since rank(J)
and rank PP) $ 2a, by the
bound on the rank of entrywise products of matrices, the rank of M is at most (2a)² + 1.

---

Exact representation with community factorization LPCA factors X, Y E R can be pro- cessed into nonnegative factors B E 1R+ and C E R Baxke such that KB + lcc = 64 and
BB - CC = = (XYT
+YX")
(5)
As a rough outline of the argument that follows, we will need 6Δ columns in the new factors B, C, up from the & columns in X, Y, because accounting for the possible asymmetry in XY will double the required columns, and accounting for the nonnegativity of B, C' will triple the required columns. Observe that the left-hand side can only represent symmetric matrices, but XY is not necessarily symmetric even H (XY = A for a symmetric A. For this reason, we use a symmetrization: let L 2 (XY*) +YT)). Note that HL) representation of A that (IX = A. so too do both expressions for L in Equation Pscudocode for the procedure of constructing B, C' given X, Y is given in Algorithm 1. The concept of this algorithm is to first separate the logit matrix L into sum and difference of rank-1 components via cigendecomposition. Each of these components can be written +vv or -v with v E R", where the sign depends on the sign of the eigenvalue. Each component is then separated into sum and difference of three outer products of nonnegative vectors, via the following Lemma 5.3.
H (XXY)) so if XY constitutes an exact
Lemma 5.3. Let Φ IR + R denote the ReLU function, i.e. <(z) max 0}. For any vector v,
vv = 20(v)((v)) + 2-0( ( v)((-v)((-v) -vv|v]"
Proof. Take any v E R Then
Tv = (ō(v) - +0(-v)((-v)
)
= =+v(v))(v)) + =
- ((v))((v)) -b(-v)((v)
+(((v)) =+2((v)((v) + (oo(-v)((vv) - +
-(((v)
(0(v) + v(-v))
+ =+v(v))(vv) -2((-v) -v)((v)) -
where the first step follows from v = σ(v) - (0))-6(-1))) (vv)), and the last step from |v| =
Algorithm follows from Lemma 5.3 and constitutes constructive proof of the following theorem: Theorem 5.4 (Exact Community Factorization from Exact LPCA Factorization). Given a symmetric matrix A {0, 1} and X, Y jgnnk such that A H (X (XYT) T) there exist nonnegative matrices nxkg and E R gaxke such that kg + kg 6k and A H(BB" CC B E R
Algorithm 1 Converting LPCA Factors Community Factors
Input logit factors X, Y E B
Output B E Ruxks C E paxke such that kB + kc 6k
and BB CC =
(XYT YXT)
1: Set Q R222 and À E 22 by truncated eigendecomposition such that
Q x diag(A) x Q = (XY + +
2: B" + Q+ x diag( V V+*+). where X+ Q* the positive eigenvaluess/vectoss
3: C Q x diag( --X-), where x= Q the negative eigenvalues/vectors
4: B (v20(B*); V2Φ( /2Ø(-B"); C*) D Φ and | |are entrywise ReLU and absolute value
5: C < (V20(C"); /20(-C") B*)
6: return B,C
As stated in the introduction this section, Theorem 5.4 extends any upper bound the exact factorization dimensionality from the LPCA model to our community-based model. That is, up to constant factor, the bound in terms of max degree from Theorem 5.1 and the bound in terms of arboricity from Theorem 5.2 also apply to our model; for brevity, we state just the latter here.
Corollary 5.5 (Exact Community Factorization for Gounded-Arboriche Graphs), Let A E (0, 1] be the adjacency matrix of an undirected graph G with arboricity a. Then there exist non- negative embeddings B Raxkg and C E Baxke such that kg + kc 6(4a² + 1) and
A H(BB - -CCT).
7

---

Note that Corollary 5.5 is purely statement about the capacity of our model; Theorem 5.2 stems from a constructive proof based on polynomial interpolation, and therefore so too does this corollary. We do not expect this factorization to be informative about the graph's latent structure. In the following Section 6, we will fit the model with an entirely different algorithm for downstream applications.
Experiments
We now present training algorithm to fit our model, then evaluate our method on a benchmark of five real-world networks.
6.1 Training Algorithm
Given an input graph A E {0. 1|mxn, we find low-rank nonnegative matrices B and C' such that the model produces Á = a (BB CCT) (0, 1)mx* as in Equation 1 which approximately matches A. In particular, we train the model to minimize the sum of binary cross-entropies of the link predictions over all pairs of nodes:
R= -., (Ais (Ag) + (1- A1)) log(1 log) -A:)))
(6)
We fit the parameters by gradient descent over this loss, as well as L2 regularization of the factors B and C. subject to the nonnegativity of B and C. This algorithm is fairly straightforward; pseudocode is given in Algorithm 2. This is quite similar to the training algorithm of Chanpuriya et al. (2020), but in contrast to that work, which only targets exact fit, explore the expression of graph structure in the factors and their utility in downstream tasks. Regularization of the factors is implemented to this end to avoid overfitting. Though the main paper we outline and evaluate a non-stochastic version of the training algorithm, it can generalize straightforwardly to a more scalable stochastic version, e.g., by sampling links and non-links for the loss function and using projected SGD. In Appendix A.2, we discuss an industry application of our model to tabular dataset completion, for which we employ such stochastic training. Here, we use the simpler non-stochastic training to isolate the impact of model capacity, which is the focus of this work, as opposed to optimization.
Algorithm 2 Fitting the Constrained Model
Input adjacency matrix A E {0, 1 } regularization weight 0, # of iterations I, # of homo/heterophilous communities kB/kt l/c
Output fitted factors B E R C E R_= such that a (BB CCT)
1: Initialize B, C' by setting entries to independent samples of Unif(0, 1/vE5), Unif(O, 1/vFG)
2: for + 1 to do
3:
A + aBBB' _
R Eij Ais log( A.)) + A1)) log(1 Aty))
4:
5:
R R+ BBB
|CI
6:
Calculate 0B, C Rt, the gradient At w.r.t B, C,C, via differentiation through Steps 2 to 4
7:
Update B, C' to minimize It using O,,R, subject to B, C
8: end for
9: return B,C
Implementation details Our implementation uses PyTorch (Paszke et al., 2019) for automatic differentiation and minimizes 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 max of 200 iterations of optimization. We set regularization weight À 10 as in Yang & Leskovec (2013). We include code in the form of a Jupyter notebook (Pérez. & Granger, 2007) demo.
Datasets
We use five fairly common mid-size datasets ranging from around 1K to 10K nodes. The selection of these five datasets is partly based on the presence of ground-truth multi-labels, which allows for evaluating the overlapping clustering methods. Statistics for these datasets, including the degeneracy

---

Table 1: Statistics of datasets used in our experiments. As in Sun (2019), for YOUTUBE and AMAZON, we take only nodes that participate in at least one of the largest 5 ground-truth communities.
Name
Reference
Nodes
Edges
Labels
Max Degree
Degeneracy
BLOG
Tang Liu (2009)
10,312
333,983
39
3,992
114
YOUTUBE
Yang & Leskovec (2015)
5,346
24,121
628
19
POS
Qiu et al. (2018)
4,777
92,406
40
3,644
49
PPI
Breitkreutz al. (2007)
3,852
76,546
50
593
29
AMAZON
Yang & Leskovec (2015)
794
2,109
29
of each network, are given in Table 1. Note that degeneracy is an upper bound on arboricity. We note that the mid-sized networks used in our empirical work actually underemphasize the significance of our theoretical arboricity bound: (2021), which have up to tens of millions nodes but still have degeneracies at most in the hundreds.
e.g., the real-world networks in Pashanasangi & Seshadhri
BLOG a social network of relationships between online bloggers; the node labels represent interests of the bloggers. Similarly. YOUTUBE is social network of YouTube users, and the labels represent groups that the users joined.
POS is word co-occurrence network: nodes represent words, and there edges between words which are frequently adjacent in a section of the Wikipedia corpus. Each node label represents the part-of-speech of the word. PPI is subgraph of the protein-proted interaction network for Homo Sapiens. Labels represent biological states. Finally, AMAZON a co-purchasing network: nodes represent products, and there are edges between products which frequently purchased together. Labels represent categories of products.
While social networks like the former two in this list generally dominated by homophily (McPher- son et al., 2001), the latter three should exhibit sigmificant heterophily. For co- co-purchasing networks like AMAZON, depending purchased, c.g., Pepsi and Coke, as discussed in Peysakhovich & Bottou (2021). Though less intuitively accessible, there is also prior discussion of disassortativity in word adjacencies (Foster et al., 2010; Zweig, 2016), as well as in PPI networks (Newman, 2002; Hase et al., 2010).
the product, two of the same kind of product
generally not co-
6.3 Results
Expressiveness First, we investigate the expressiveness of our generative model, that is, the fidelity with which it can reproduce an input network. Section 1, we used simple synthetic network to show that model is more expressive than others due to its ability represent heterophilous structures in addition to homophilous ones. We now evaluate the expressiveness our model on real- world networks. As with the synthetic graph, we fix the number of communities singular vectors, fit the model, then evaluate the reconstruction error. In Figure 4, we compare the results our model with those of SVD, BIGCLAM (which is discussed in detail in Section 4), and SYMNMF (Kuang et al., 2015). SYMNMF simply factors the adjacency matrix as A HH where H E Ra*k, note that, like SVD, S SYMNMF does not necessarily output a matrix whose entries are probabilities (i.e., bounded in (0, 1),, and hence is not natural graph generative model like and BIGCLAM.
2
Frabenias Enar
Croee-Eni Entropy K
Melhod
SVD
SymNMF
BigCtam
Ours
Blog
Blog
YouTube
Figure 4: Reconstruction error on real-world networks, relative to our model's error.

---

For each method, we fix the number of communities or singular vectors at the ground -oound-truth number. For this experiment only, we are not concerned with learning the latent structure of the graph: the only goal is accurate representation of the network with limited parameters. So, for fair comparison with SVD, we 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 6). We particularly highlight the improvement over BIGCLAM; the salient difference between these models, both of which are factorization-based, include nonlinear link function, and assign node communities using nonnegative factors, is the presence the heterophilous -CC term our model. Thus, the improvement directly reflects the value of incorporating heterophily into the model. Interestingly, find the most significant improvement exactly on the three datasets which have been noted to exhibit significant heterophily: POS, PPI, and AMAZON.
Similarity to ground-truth communities To assess the interpretability of clusters generated by method, we evaluate the similarity of these clusters to ground-truth communities (i.e., class labels), and we compare other methods for overlapping clustering. We additionally compare another recent but non-generative approach, the VGRAPII method of Sun et al. (2019), which is based on link clustering: the authors found their method to generally achieve state-of-the-art art results in this task. 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 & Leskovee (2013). See Figure (left): the performance of our method is competitive with SYMNMF, BIGCLAM, and vGraph.
Communily Delection
Link Prediction
0.8
0.5
Method
Method
vBraph
Spore
0.2
Random
0.3
SymNMF
SymNMF
BigClam
BigC/am
0.2
Ours
Ours
0.0
0.3
YouTube
YouTube
Figure 5: Left: Similarity of recovered communities to ground-truth labels of real-world datasets. (Note: VGRAPII is omitted on BLOG due memory limitations.) Right: Accuracy of link prediction.
Interpretable link prediction We assess the predictive power of our generative model on the link prediction task. As discussed in Section 3, 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 with other models which permit similar interpretation, namely BIGCLAM and SYMNMF. We randomly select 10% of node pairs to hold out, fit the models the remaining 90%, then use the trained models to predict links between node pairs in the held out 10%. As a baseline, we also show results for randomly predicting link no link with equal probability. See Figure (right). The performance of our method is competitive with or exceeds those of the other methods in terms F1 Score.
Conclusion
We introduce community-based graph generative model based symmetric nonnegative matrix factorization which can represent both homophily and heterophily. We add to prior guarantee of exact representation for bounded degree graphs with broader guarantee for bounded arboricity graphs, and we show that both of these guarantees apply to our more interpretable graph model. We illustrate our model's capabilities with experiments on synthetic motivating example. Experiments on real-world networks show its effectiveness on several key tasks. Broadly, our results suggest that incorporating heterophily into methods for networks can improve both theoretical grounding and empirical performance, while maintaining interpretability. Future directions include deeper understanding of the expressiveness of low-rank logit models and convergence of training algorithms.
10

---

Acknowledgments and Disclosure of Funding
This project was partially supported by an Adobe Research grant, along with NSF Grants 2046235 and 1763618.
References
Aggarwal, C. C. and Wang, H. A survey of clustering algorithms for graph data. In Managing and Mining Graph Data, pp. 275-301. Springer, 2010.
Athreya, A., Fishkind, D. E., Tang, M., Priebe, C. E., Park, Y., Vogelstein, J. T., Levin, K., Lyzinski, V., and Qin, Y. Statistical inference on random dot product graphs: a survey. The Journal of Machine Learning Research, 18(1):8393-4484 2017.
Berry, M. W., Browne, M., Langville, N., Pauca, V. P., and Plemmons, J. Algorithms and applications for approximate nonnegative matrix factorization. Computational Statistics & Data Analysis, 52(1):155-177 2007.
Bhattacharjee, R. and Dasgupta, S. What relations are reliably embeddable in euclidean space? In Algorithmic Learning Theory, pp. 174-195. PMLR, 2020.
Bonato, A. A survey of models the web graph. In Workshop on Combinatorial and Algorithmic Aspects of Networking, pp. 159- 199917722000 Springer, 2004.
Boratko, M., Zhang, D., Monath, N., Vilmis, L.,, Clarkson, K. L.,, and McCallum, A. Capacity and bias of learned geometric embeddings for directed graphs. Advances in Neural Information Processing Systems, 34:16423-16436, 2021.
Breitkreutz, B.-J., Stark, C., Reguly, T., Boucher, L., Breitkreutz, A., Livstone, M., Oughtred, R., Lackner, D. H., Bähler, J., Wood, et The biogrid interaction database: 2008 update. Nucleic acids research, 16611ppL_) 2007.
Chanpuriya. S., Musco, C., Sotiropoulos, K., and Tsourakakis, C. Node embeddings and exact low- rank representations of complex networks. Advances in Neural Information Processing Systems, 33, 2020.
Ding, C., Li, T., and Jordan, M. I. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching, and clique finding. In 2008 Eighth IEEE International Conference on Data Mining, pp. 183-192. IEEE, 2008
Donoho, D. L. and Stodden, V. When does non-negative matrix factorization give correct decompo- sition into parts? In Advances in Neural Information Processing Systems 16, pp. 1141-1148. MIT Press, 2003.
Duvenaud, D., Maclaurin, D., ggguieraa-parrrauirre J., Gómez- Bombbrell,, R., Hirzel, T., Aspuru- Guzik, A., and Adams, R. P. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems 28, pp. 2224-2232, 2015.
Foster, J. G., Foster, D. V., Grassberger, P., and Paczuski, M. Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107/24):10115-10820, 2010.
Gillis, N. Nonnegative Matrix Factorization. SIAM, 2020.
Hamilton, W., Ying, 7.,, and Leskovec, Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Hase, T., Niimura, Y., and Tanaka, H. Difference in gene duplicability may explain the difference in overall structure of protein-protent interaction networks among eukaryotes. BMC Evolutionary Biology, 10(1):1-15, 2010.
Javed, M. A., Younis, M. S., Latif, S., Qadir, J., and Baig, Community detection in networks: multidisciplinary review. Journal of Network and Applicttion,,, 108:87-111, 2018.

---

Johnson, S., Torres, J. J., Marro, J., and Munoz, M. A. Entropic origin of disassortativity in complex networks. Physical Review Letters, 104(10))108702, 2010.
Jones, E., Oliphant, T., Peterson, P., al. SciPy: Open source scientific tools for Python, 2001. URL http:// http://wwrr scipy secipy.org....
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Kuang, D., Ding, C., and Park, H. Symmetric nonnegative matrix factorization for graph clustering. In Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 106-117. SIAM, 2012.
Kuang, D., Yun, S., and Park, H. Symnmf: nonnegative low-rank approximation of a similarity matrix for graph clustering. Journal of Global Optimization, 62(3):545-577 2015.
Lee, D. D. and Seung. H. S. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788-777 791, 1999.
Liu, D. C. and Nocedal, J. On the limited memory BFGS method for large scale optimization. Mathematical Programming. 45(1-3):503-525 1989.
Mason, O. and Verwoerd, M. Graph theory and networks in biology. IET Systems Biology, 1(2): 89-119, 2007.
McPherson, M., Smith-Lovin, L., and Cook, J. M. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415 444, 2001.
Miller, K. T., Griffiths, L.,, and Jordan, M. I. Nonparametric latent feature models for link prediction. In Advances in Neural Information Processing Systems 22, pp. 1276-1284. Curran Associates, Inc., 2009.
Nascimento, M. C. and De Carvalho, A. C. Spectral methods for graph clustering-a a survey. European Journal of Operational Research, 211(2):221-231, 2011.
Newman, M. E. Assortative mixing in networks. Physical Review Letters, 89(20):00701, 2002.
Noldus, R. and Van Mieghem, P. Assortativity in complex networks. Journal of Complex Networks, 3(4):507-542, 2015.
Nourbakhsh, F., Bulo, S. R., and Pelillo, M. A matrix factorization approach to graph compression. In 2014 22nd International Conference Pattern Recognition, pp. 76-81. IEEE, 2014.
NT, H. and Machara, T. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.095500 2019.
Pashanasangi, N. and Seshadhri, C. Faster and generalized temporal triangle counting, via degeneracy ordering. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1319-1328, 2021.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., Vitooo, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035.
Curran Associates, Inc., 2019.
Pei, H., Wei, B., Chang, K. C., Lei, Y., and Yang, B. Geom-gen. Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020. 2020.
Pérez, and Granger, B. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 9(3):21-29, May 2007. ISSN 1521-9615. doi: 10.1 10.1109/MCSE.2007.555 URL https: https:///pptthon org.
Peysakhovich, A. and Bottou, L. An attract-repel decomposition of undirected networks. arXiv preprint (XXX:22106006771 2021.
12

---

Qiu, J., Dong, Y., Ma, H., J., Wang, K., and Tang. J. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459-467. ACM, 2018.
Rendsburg, L.,, Heidrich, H., and Von Luxburg, U. Netgan without gan: From random walks to low-rank approximations. In International Conference on Machine Learning, pp. 8073-8082. PMLR, 2020.
Rubin-Delanchy, P., Cape, J., Tang, M., and Priebe, C. E. A statistical interpretation of spectral embedding: the generalised random dot product graph. arXiv preprint arXiv: arXiv: 707.0550900500. 2017.
Sala, F., De Sa, C.. Gu, A., and Ré, C. Representation tradcoffs for hyperbolic embeddings. In International Conference Machine Learning, pp.
PMLR, 2018.
Schaeffer, E. Graph clustering. Computer Science Review, 1(1):27-44, 2007.
Scheinerman, E. R. and Tucker, K. Modeling graphs using dot product representations. Computational statistics, 25(1):1-16, 2010.
Scott, J. Social network analysis. Sociology, 22(1):109-127, 1988.
Seshadhri, C., Sharma, A., Stolman, A., and Goel, A. The impossibility of low-rank representations for triangle-rich complex networks. Proceedings of the National Academy of Sciences, 117(11): 5631-5631 2020.
Shi, and Malik, Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888- 2000.
Sun, F.. Qu M., Hoffmann, J., Huang, C., and Tang. J. vgraph: A generative model for joint community detection and node representation learning. In Advances in Neural Information Processing Systems 32, pp. 512-522, 2019.
Tang, L. and Liu, H. 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.
Wang, Y.-X. and Zhang, Y.-J. Nonnegative matrix factorization: A comprehensive review. IEEE Transactions on Knowledge and Data Engineering, 1336:1333-,,33, 2012.
Xie, J., Kelley, S., and Szymanski, B. K. Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Computing Surveys, 45(4):43:1-43:35, 2013.
Yan, Y., Hashemi, M., Swersky, K., Yang. Y., and Koutra, D. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint 1:X.x:2102.06444 2021.
Yang. J. and Leskovec, Overlapping community detection scale: nonnegative matrix factor- ization approach. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp. 587-596, 2013.
Yang. J. and Leskovec. J. Defining and evaluating network communities based on ground Knowledge and Information Systems, 42(1):181-213, 2015.
Yang, Z., Hao, T., Dikmen, O., Chen, X., and Oja, E. Clustering by nonnegative matrix factorization using graph random walk. In Advances in Neural Information Processing Systems, pp. 1079-1087, 2012.
Young, S. J. and Scheinerman, E. R. Random dot product graph models for social networks. In International Workshop on Algorithms and Models for the Web-Graph, pp. 138-149. Springer, 2007.
Yu, K., Yu, S., and Tresp, Soft clustering on graphs. In Advances Neural Information Processing Systems, pp. 1553-1560, 2005.
13

---

Zheng, X., Liu, Y., Pan, S., Zhang, M.. Jin, D., and Yu, P. Graph neural networks for graphs with heterophily: A survey, arXiv:2202.07082, 2022.
Zhu, C., Byrd, R. H., Lu, P., and Nocedal, Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions on Mathematical Software (TOMS), 23(4) 5600 1997.
Zhu, J., Yan, Y., Zhao, L.,, Heimann, M., Akoglu, L.,, and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
Zweig, K. A. Are word-adjacency networks networks? In Towards theoretical framework for analyzing complex linguistic networks, pp. 153-163. Springer, 2016.
14

---

A Appendix
A.1 COT Graph Exact Representation
As a theoretical demonstration of the capability of our model to learn latent structure, we additionally show that our model can exactly represent natural family of graphs, which exhibits both homophily and heterophily, with small & and interpretably. The family of graphs is specified below in Definition 1; roughly speaking, nodes in such graphs share an edge iff they coparticipate in some number of homophilous communities and don't t coparticipate in a number of heterophilous communities. For example, the motivating graph described in Section 2 would be an instance of such graph if an edge occurs between two users iff the two users are from the same city and have different genders.
Definition 1 (Community Overlap Threshold (COT) Graph), An unweighted, undirected graph whose edges are determined by an overlapping clustering and a "thresholding" " integer E as follows: for each vertex i, there are two latent binary vectors b, E {0, and C, E {0,1)" and there is an edge between vertices i and j iff b; b, C; Cj 2 t.
Theorem A.1 (Compact Representation of COT Graphs). Suppose A is the adjacency matrix of a n.. COT graph on n. nodes with latent vectors b; E {0, 1 and e E {0, [0,1)* for i E (1,2...... Let kg + ke. Then, for any > 0, there exist V E [0, (],1]xx(++1) and diagonal W E [[(++))((++) such that (loVVV - A <
Proof. Let t be the thresholding integer of the graph, and let the rows of B E {0, 1]nx and Ce {0. 1) 1 contain the vectors and e of all nodes. Via Equation 2, we can find V E [0, 1 1|nx and diagonal W E lg such that VWW.V+ =BB CCT, Now let
W
-1)
V 1) W
1
Then (VWVT) )aj = b, bj Cg + t. Hence (VWV Diy > O b. by c: c- which is true iff A.j = 1 by the assumption the graph. Similarly, (VWV 13 < 0 A,, O. follows that
lim (V(sW)VT) lim (sVWVT) =A. ++000
15

---

A.2 Application: Tabular Data Completion
We apply our link prediction algorithm to the task of data completion for categorical tabular data. We first transform such data to graph as follows: We create node for each row, as well as node for each unique category for each of the columns. For each entry of the table, a link occurs between the node for the row and the node for the value in the entry, which is one of the possible categories of the column (e.g., if Bob American, then a link occurs between the row node for 'Bob' and the category node for 'American") ). No links occur between two nodes for rows, or between two nodes for category values. For the negative samples, we select only edges between nodes for rows and nodes for category values; the negative samples would otherwise be dominated by pairs of nodes for rows.
We two proprietary company datasets datasets which we call COMPANY and COMPANY B. We use the same experimental setup as described in Section 6.3. Unlike in Section 6.3, we have restriction on the possible links: each row node must linked to exactly one of the value nodes for each of the categories. Hence, for each combination of row node and column, we predict link only with the value node with the highest predicted link probability. We set the number of communities for all methods to 20 and 50 for COMPANY A and COMPANY B, respectively. We employ the stochastic version of our algorithm, based on projected SGD, for which code is also provided. We generally use a batch size of 100; we find that the optimization of BIGCLAM often diverges on COMPANY B with this batch size, so we instead use batches of size 1000 for its optimization. The results are provided in Figure 6. Notably, our proposed approach outperforms comparable (community-bass -based factorization) methods in terms of accuracy. As a baseline, we also show the accuracy when completing the tables by simply selecting the most common categorical value for each column ("PLURALITY"). All methods outperform this baseline on both datasets.
0.6
RestAccuracy
Method
0.4
Plurality
SymNMF
BigGlam
Ours
Company A
Company
Dataset
Figure 6: Test accuracy tabular data completion on two proprictary company datasets (COMPANY A and COMPANY B).
16


Reviews:
[{"review_id": "UMMbQwNRs2", "reviewer": "Reviewer_gKGt", "summary": "This paper concerns several main results/themes: \n\n- the authors show a theoretical result on a prior model known as LPCA. Their result indicates that exact factorizations for graphs under the LPCA model is possible under a bounded arboricity assumption, which is more generally applicable than the prior degree-based assumption.\n\n- the authors propose a graph generative model  that uses two non-negative vectors (one for homophily, one for heterophily) per node as well as a non-linear linking function to embed a given graph in an interpretable manner. This models generalizes the prior LPCA model, and has nice properties such as having factorizations that are non-linear, captures heterophily in addition to homophily, and is non-negative. \n\n- they show that the theoretical results that are available for LPCA (including the one that they derived) is applicable to their more general model as well. \n\n- they show promising experimental results on datasets. ", "questions": "- See above section", "limitations": "The main limitations of these classes of methods is scalability and computational complexity. The authors briefly address this in the paper in A.3 for example by mentioning a stochastic training approach. I think the author's discussion of the limitations is sufficient but could be improved, for example, by discussing computational complexity (big Oh run time) in more explicit manners in both the deterministic and the stochastic case. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Originality: The two original contributions are mainly as follows. 1. the theoretical result on LPCA representations which uses a new arboricity criteria rather than a max degree criteria. 2. The proposed generative model (which is more general than LPCA). To the best of my knowledge, these two contributions have not been priorly proposed. I believe that the level of originality of this article, while not groundbreaking, is sufficient for publication at NeurIPS. \n\n- Quality: The quality of the experiments and the theoretical results are sound and technically solid, to the best of my knowledge. The results of the experiments supports the authors' claims that their proposed approach capture heterophily in an interpretable manner and that in specific cases it outperforms competitors. \n\n- Clarity: the paper is presented in a clear and easy to read manner, which is much appreciated. The authors motivated their results well. \n\n- Significance: Graph embeddings are certainly a relevant area of research nowadays. The authors' contributions have moderate impact, given their expressive, interpretable and more generally applicable model. It is significant enough for publication at NeurIPS. ", "weaknesses": "- The authors covered virtually all the bases. Overall, I do not see any obvious shortcomings/omissions in the paper. I do have some comments/questions below: \n\n-  From a theoretical and originality perspective, the advances that they make over the prior result (the arboricity vs degree assumption) appears rather marginal (similar to Chanpuriya 2020). Yet a new result is a new result. I do not find this to disqualify this article from being accepted. \n\n- I find a small disconnect between the theoretical results and the proposed methods. The theory says that exact representations exist. The methods provide one way to find a representation. But there seems to be little linking the two: there seems to be no guarantee that what the algorithm actually finds in practice is the exact representation. It is possible that I might be missing something here, and any clarifications from the authors would be appreciated. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review. We address some points you raise below.\n\n>From a theoretical and originality perspective, the advances that they make over the prior result (the arboricity vs degree assumption) appears rather marginal (similar to Chanpuriya 2020).\n\nWe believe that, while this work certainly builds on Chanpuriya et al., the combination of the arboricity-based bound with the non-negative component yields a new conceptual contribution. At a high level, the result in Chanpuriya et al. is that bounded-degree graphs admit exact low-rank factorization. In this work, we show that for sparse graphs in general (which covers a much wider range of real-world networks), you can exactly express the graph structure in terms of node communities, so long as you also allow for \"heterophilous\" communities. Both our theoretical and empirical work ground a core idea that could be integrated into larger and more performant models than the ones we test here, including deep models: the benefit of adding to nonnegative embedding models a second, heterophilous embedding in addition to the usual homophilous embedding. We see Chanpuriya et al. as being more abstracted from practical applications.\n\n>I find a small disconnect between the theoretical results and the proposed methods. The theory says that exact representations exist. The methods provide one way to find a representation. But there seems to be little linking the two: there seems to be no guarantee that what the algorithm actually finds in practice is the exact representation. It is possible that I might be missing something here, and any clarifications from the authors would be appreciated.\n\nIndeed, we provide no theoretical guarantee that our gradient-descent-based training algorithm in the empirical section will find an exact embedding. In some quick experiments in response to Reviewer SSbD (shown in Figure 1 of the rebuttal PDF), we did find that this algorithm can find an exact embedding, at least on the synthetic graph, but we do not focus on this for a few reasons. As we note around Line 290, exact factorization is not the goal of our empirical contribution. Our training algorithm is quite close to that of Chanpuriya et al., and essentially the whole of their empirical work concerns finding these exact embeddings with such a training algorithm. They report the embedding dimensionalities needed for exact factorization of various networks, among other related information, and we have little to add on that front. We instead use the empirical section to complement our theoretical contributions and highlight the core idea we discuss above. We also note that the proofs in our theoretical section are constructive and hence provide a totally different “fitting” algorithm that is guaranteed to give an exact factorization, though the resulting embeddings are unlikely to be of any practical use.\n\n>The main limitations of these classes of methods is scalability and computational complexity. The authors briefly address this in the paper in A.3 for example by mentioning a stochastic training approach. I think the author's discussion of the limitations is sufficient but could be improved, for example, by discussing computational complexity (big Oh run time) in more explicit manners in both the deterministic and the stochastic case.\n\nThis is a good point. We note why we focus on the less scalable non-stochastic version in the main paper, and we discuss and evaluate a more scalable stochastic version in the appendix, but we will also specifically note the computational complexities of these versions, which are quadratic and linear in the number of nodes, respectively."}, {"review_id": "4rYTxzLn94", "reviewer": "Reviewer_VwbN", "summary": "This paper proposes to use the logistic PCA model to represent. Paper's main contribution is theoretical – improving the embedding dimensionality bounds from maximum degree to the arboricity of a graph. Overall, I believe the contribution is significant, but currently the paper does not highlight why too much – see more in the weaknesses section. The evaluation is severely limited, which might be forgivable for a more theory-oriented paper.", "questions": "* Would node classification experiments on the datasets like POS/PPI/Blog (these are already present in the experimental section) strengthen the paper? Suggested comparison is some early neural embedding such as DeepWalk. This would open up interest from the subfield of more heuristic node embedding methods.\n\n* Can you detail the comparison with Chanpuriya et al., especially in terms of the proof?", "limitations": "Yes; although I would stress limited practicality of the proposed algorithm due to its time complexity.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Theoretical guarantees are interesting to (potentially) broader research community.\n* The methods offers grounded interpretability of node embeddings in terms of the community structure.\n* The paper is written clearly and should be easy to understand to the general audience.", "weaknesses": "* While the theoretical results are interesting, they are not well connected to the literature on either:\n ** Spanning trees and effective resistances and graph sparsification would be exciting to sparsification folks.\n ** Curvature (through bounds on Ollivier-Ricci curvature from effective resistance) would yield interesting connections to GNNs\n* The proposed algorithm is not really practical computationally speaking and does not scale to large graphs.\n* Experiments are not really indicative of real-world performance of the algorithm and rather focus on provide some free-form support for the theoretical claims of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and suggested directions for improvement. We address your criticisms and suggestions as follows.\n\n*On connections of our theoretical results to effective resistance, sparsification, curvature, and more*\n\nThank you for suggesting these connections. We will look into integrating and discussing them appropriately. We discuss some initial thoughts:\n\nWhile we focus on exact embeddings in the theoretical results, it would certainly be interesting to look at approximate embeddings, e.g., an embedding that produces a graph which is a spectral sparsifier or spanner of the input graph. Typically, spectral sparsifiers are produced by randomly sampling edges of a graph according to their effective resistances (see e.g. [Spielman, Srivastava 2008]). However, it is also known that a spectral sparsifier can be obtained by sampling $O(\\log n / \\epsilon^2)$ random spanning trees (see e.g., [Fung, Harvey 2010]). This result ensures that any graph has a spectral sparsifier with arboricity $O(\\log n / \\epsilon^2)$, and thus can be approximately embedded according to our results with dimension $O(\\log^2 n / \\epsilon^4)$. Observe that such a result was not possible with just the max degree bound of Chanpuriya et al. as there exist simple examples of graphs where all spectral sparsifiers must have high max degree (e.g., a star graph). It would be interesting to understand if the above approximate embedding bound could be improved via a more refined argument, or extended, e.g. to spanner constructions, many of which should also have low arboricity. It would also be interesting to find practically effective algorithms for finding such approximate embeddings.\n\nRelating to spanners, while our exact embedding does not directly constitute a spanner, it can be thought of as an exact distance oracle, which is a general data structure for approximating distances on graphs (see e.g., [Thorup, Zwick 2005]). However, while our embedding is very compressed, it is not clear if it is useful in this context, since there is no obvious way to *efficiently* calculate distances in the graph given just the embedding, faster than simply reconstructing the full graph. However this could be an interesting direction to pursue in future work.\n\nWe are less familiar with Olivier-Ricci curvature, but this also sounds like an interesting connection. Certainly, looking at, e.g., [Sia, Jonckheere, Bogdan 2019], curvature appears to be a powerful tool for detection of traditional, homophilous communities. Possible links to heterophilous community detection and exact embedding are less immediately clear, but are an interesting direction. Please do elaborate if you had some such links in mind.\n\n>The proposed algorithm is not really practical computationally speaking and does not scale to large graphs.\n\nThe algorithms we evaluate in the main paper indeed scale quadratically in $n$, and hence are not suitable for large graphs. However, as we note around Line 293, our loss function admits a natural stochastic approximation, so our method transforms straightforwardly to a stochastic version that scales linearly in $n$. We discuss this more in the appendix, where we also evaluate these more scalable algorithms for an industry task. As we state in Line 297, we use the simpler non-stochastic training in the main paper to isolate the impact of model capacity, which is the focus of this work, as opposed to optimization.\n\n>Experiments are not really indicative of real-world performance of the algorithm… Would node classification experiments on the datasets… strengthen the paper? Suggested comparison is some early neural embedding such as DeepWalk.\n\nIndeed, we focus in this work on experiments which complement our theoretical results, which concern non-negative / community-based embeddings. Relatively few methods generate such embeddings, and DeepWalk, node2vec, LINE, etc. are not among them. This is also why we do not evaluate on the node classification task. The concept and theory behind our model is relevant to community detection, which we do evaluate on, and which is an unsupervised analog of node classification. \n\nWe do this to keep a tight focus on one of our main goals with this paper, which is advancing a conceptual idea and putting it on solid theoretical and empirical footing. This core idea is the benefit of adding to nonnegative embedding models a second, heterophilous embedding in addition to the usual homophilous embedding. As we note in the response to Reviewer zLuj, this idea could be integrated into larger, more complex, and possibly more performant models, including deep models / GNNs, and including models more suitable for node classification.\n\n>Can you detail the comparison with Chanpuriya et al., especially in terms of the proof?\n\nWe start by comparing the proofs of the bounded degree/arboricity results. Both proofs involve polynomial interpolation arguments (this is a common technique for theory about sign rank in general), and we use similar notation where possible for accessibility, which emphasizes similarities. However, they are different in that 1) the central polynomials are different; 2) our proof involves a particular decomposition of $\\textbf{A}$ into $\\textbf{B}+\\textbf{B}^\\top$; and 3) the final part our proof involves an entrywise product of polynomial matrices. No analog of (2) or (3) appears in Chanpuriya et al.\n\nMore broadly, we think that, while this work certainly builds on Chanpuriya et al., the combination of the arboricity bound above with the non-negative component yields a new conceptual contribution. The result in Chanpuriya et al. is that bounded-degree graphs admit exact low-rank factorization; in this work, we show that for sparse graphs in general (which covers a much wider range of real-world networks), you can exactly express the graph structure in terms of node communities, so long as you also allow for \"heterophilous\" communities."}, {"review_id": "qa5KIF7Ccp", "reviewer": "Reviewer_SSbD", "summary": "This paper proposes and studies a community-based factorization model for exact representation of sparse networks. The authors extend a prior result on exact factorization which is based on logistic principal component analysis (LPCA), and show that an LPCA factorization can be converted to the proposed community-based graph factorization. The new factorization model explicitly captures both homophily and heterophily among nodes in the graph, and hence it is more interpretable. The authors carry out experiments using a different training algorithm to fit the model, and illustrate the advantage of the proposed decomposition method over existing ones for community detection and link prediction tasks.", "questions": "- For the synthetic experiment shown in Figure 2, what happens if you increase the embedding length further? Will SVD beat your method afterwards? Can you make your method has close to 0 error (since it is supposed to be exact)?\n\n- What happens if you don't regularize your training algorithm for the experiments in Section 6, and how would the methods compare in that case?", "limitations": "I cannot find where the authors discuss the limitations or potential negative societal impact of their work, but I think it is fine.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper provides an intuitive community-based graph factorization model that is able to explicitly capture both homophily and heterophily among nodes in the graph. The expressiveness of the new factorization is backed by a reduction from LPCA which is shown to be able to exactly represent any sparse graph with bounded arboricity. Although it may not be something of extremely high theoretical significance, I liked this aspect of technical development. It is an interesting result to have.", "weaknesses": "- There is a clear gap between the exact factorization studied up to Section 5 and the actual training algorithm evaluated in Section 6. Although the authors have mentioned the algorithmic gap explicitly at the end of Section 5. In order to well approximate the heavyside function which is used to achieve exact representation by LPCA, the input of the logit function should have entries that are arbitrarily large in magnitude. However, the training algorithm uses regularization to prevent this. The regularization does exactly the opposite of what is needed for exact representation. Therefore, there is a significant gap between theoretical development and empirical verifications.\n\n- Since the paper studies exact representation, there should be at least an experiment (e.g. the synthetic one) which shows that the reconstruction error goes to 0.\n\n- The overall writing and clarity can be improved. There are a few typos. For example, Line 32, principal components analysis -> principal component analysis. I also could not find where in the paper the term arboricity is clearly defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We appreciate the recognition of our conceptual and theoretical contribution. We are thankful for the suggestions on improving clarity – we will incorporate them. We address the criticisms, which mainly concern the empirical piece.\n\n>There is a clear gap between the exact factorization studied up to Section 5 and the actual training algorithm evaluated in Section 6… The regularization does exactly the opposite of what is needed for exact representation.\n\nWe discuss this a bit around Line 290, but exact factorization is not the goal of our empirical contribution. As we note, our training algorithm is quite close to that of Chanpuriya et al., and essentially the whole of their empirical work concerns finding these exact embeddings with such a training algorithm. They report the embedding dimensionalities needed for exact factorization of various networks, among other related information, and we have little to add on that front. We instead use the empirical section to complement our theoretical contributions, and highlight the benefit of adding to nonnegative embedding models a second, heterophilous embedding in addition to the usual homophilous embedding. Indeed, regularization does exactly the opposite of what is needed for exact representation, but it is crucial for our method (as well as the comparison methods) to yield good results on tasks like community detection and link prediction. We also note that the proofs in our theoretical section are constructive and hence provide a totally different “fitting” algorithm that is guaranteed to give an exact factorization, though the resulting embeddings are unlikely to be of practical use.\n\n>For the synthetic experiment shown in Figure 2, what happens if you increase the embedding length further? Will SVD beat your method afterwards? Can you make your method has close to 0 error (since it is supposed to be exact)?\n\nIt is quite likely that if we increase capacity by increasing the embedding length that SVD will have lower reconstruction error since it is unregularized. At your suggestion, we ran the training for our method without regularization, evaluated embeddings lengths from 20 to 60, and plotted the results in the PDF of rebuttal figures – see Figure 1. Our method has lower error at all embedding lengths. Further, the fit was essentially exact at length 60. SVD will not achieve zero error until the embedding length equals the number of nodes, 1000, since the adjacency matrix is generally full-rank. We do note that, related to our points above, this is of limited practical significance, since our regularized method captures all the “signal” in the data at embedding length 12, after which there is only noise to fit."}, {"review_id": "7YDKTctAGs", "reviewer": "Reviewer_zLuj", "summary": "This paper extends for by Chanpuriya et al (2020) for networks with homophilous and heterophilous edges. They show that their model is able to yield interesting results and they give theoretical underpinnings as well. ", "questions": "In the motivating example there are 10 cities but the model uses 12 communities. How is the number of communities chosen? \n\nEquation 4: what do the wriggly lines mean? \n\nTheorem 5.1: can it not happen that X Y^T has entries taking the value 0, in which case H would give the value 1/2 and not 0 or 1? \n\nProof of Theorem 5.2: In my understanding a forest is a collection of trees. What is a partition into forests? It would be good to give a worked example in the appendix. How are the children found? Are the trees supposed to be rooted, choosing a root at random, and then orienting the tree from there? The proof seems to be constructive but it is not clear what the resulting matrices X and Y would be; the final step in the proof seems to be missing. ", "limitations": "There is no mention of societal impact. For example when assessing credit risk by assigning customers to communities of different risk, would extra caution be advised? ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The model is straightforward but seems to work well. Due do its relative simplicity and its relationship to previous work it is possible to give theoretical guarantees. ", "weaknesses": "The paper seems to ignore relationships to multilayer and multiplex networks which are also able to capture different types of relationships through different layers. Mason Porter, Peter Mucha and others have written many papers on such networks. There is also a literature on spectral methods for signed networks which can also capture heterophily; Mihai Cucuringu comes to mind. These areas should be mentioned in the related works section. \n\nSome of the presentation is not clear:\nIn (4) it seems that A is a graph but the right hand side is a probability matrix. How is a 0-1 matrix reconstructed this way? \n\nThe overall method is competitive but does not outperform any of the other methods. The conclusion does not give any indication of how the performance could be improved. Is the issue related to independence assumptions? A discussion would be helpful. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and detailed questions, which we address piecewise.\n\n*On connections to multiplex networks and spectral methods for signed networks*\n\nThank you for bringing up these interesting connections. Indeed, in some sense, signed graphs seem to capture the idea of heterophilous communities more directly than standard graphs. It seems quite possible that one of the spectral methods you allude to, such as SPONGE, could be slightly altered to detect heterophilous communities instead of homophilous ones. Regarding multiplex networks, this is also an interesting area for connections. At a high level, one of our ideas with this paper is considering types of communities beyond the standard, homophilous ones, and this concept arises more readily when studying types of graphs beyond the standard. This includes multilayer/multiplex graphs, which can have many kinds of edges and thus give more freedom in defining a “community.” We will reconsider these topics and the suggested references, and look into integrating them appropriately into our text.\n\n>The overall method is competitive but does not outperform any of the other methods. The conclusion does not give any indication of how the performance could be improved. Is the issue related to independence assumptions? A discussion would be helpful.\n\nOur method does generally outperform the competitors on the three tasks in the main paper, as well as the one in the appendix; on some tasks and datasets, there is a significant outperformance. That being said, there is certainly room to improve on the numbers. Rather than maximizing empirical performance, one of our main goals with this paper is advancing a conceptual idea and putting it on solid theoretical and empirical footing. This core idea is the benefit of adding to nonnegative embedding models a second, heterophilous embedding in addition to the usual homophilous embedding. This idea could be integrated into larger, more complex, and possibly more performant models, such as deep nonnegative matrix factorization or deep clustering models.\n\n>In the motivating example there are 10 cities but the model uses 12 communities. How is the number of communities chosen?\n\nThere are 10 cities but also 2 genders, for a total of 12 (overlapping) communities. The goal with the unsupervised task here is, by detecting both the city and gender communities, to retrieve a 12-dimensional vector for each node/person which is very positive for that person’s city and gender, and roughly 0 for the 10 other entries. In Figure 3, it is shown that our method achieves this, whereas SVD and BigClam have some shortcomings.\n\n>In (4) it seems that A is a graph but the right hand side is a probability matrix. How is a 0-1 matrix reconstructed this way?\n\n> Equation 4: what do the wriggly lines mean?\n\n$\\mathbf{A} \\approx \\sigma(\\mathbf{X} \\mathbf{Y}^\\top)$ denotes approximate equality, as opposed to exact equality as in $\\mathbf{A} = \\sigma(\\mathbf{X} \\mathbf{Y}^\\top)$. Equation 4 is informally expressing that the goal of LPCA is for $\\sigma(\\mathbf{X} \\mathbf{Y}^\\top)$ to be a high probability (near $1$) where $\\mathbf{A}$ is $1$ and a low probability (near $0$) where $\\mathbf{A}$ is $0$.\n\n>Theorem 5.1: can it not happen that X Y^T has entries taking the value 0, in which case H would give the value 1/2 and not 0 or 1?\n\nIndeed, $H(0) = 1/2$, but the theorem is asserting that there exist $\\mathbf{X}$ and $\\mathbf{Y}$ such that their product is positive where $\\mathbf{A}$ is $1$ and negative where $\\mathbf{A}$ is $0$; the theorem is asserting the existence of such $\\mathbf{X}$,$\\mathbf{Y}$ whose product has no zero entries.\n\n>Proof of Theorem 5.2: In my understanding a forest is a collection of trees. What is a partition into forests? It would be good to give a worked example in the appendix. How are the children found? Are the trees supposed to be rooted, choosing a root at random, and then orienting the tree from there?\n\nIndeed, a forest is a union of disjoint trees. Equivalently, it is an acyclic undirected graph. For our purposes, an undirected graph being a forest means that its edges can be made directed such that each node has at most one incoming edge. This is because each node in a forest participates in a single tree and is either that tree’s root or has a single parent, so orienting each edge towards the parent achieves the desired outcome. A partition into $\\alpha$ forests is a partition of the graph’s edges into $\\alpha$ undirected acyclic graphs. For our purposes, this means the graph’s edges can be oriented such that each node has at most $\\alpha$ incoming edges. We have provided a diagram of an example (see Figure 2 in the PDF of rebuttal figures), and we hope it will help clarify this.\n\n>The proof seems to be constructive but it is not clear what the resulting matrices X and Y would be; the final step in the proof seems to be missing.\n\nWe show how to construct a matrix $\\mathbf{M} \\in \\mathbb{R}^{n \\times n}$ that exactly encodes the graph in the signs of its entries. We also prove that this matrix is low-rank, specifically that $\\text{rank}(\\mathbf{M}) = O(\\alpha^2)$. By definition of rank, this means there exists a factorization $\\mathbf{M} = \\mathbf{X} \\mathbf{Y}^\\top$ for some matrices $\\mathbf{X},\\mathbf{Y} \\in \\mathbb{R}^{n \\times O(\\alpha^2)}$. Constructively, this factorization could be retrieved in many ways, e.g., by eigendecomposition of $\\mathbf{M}$. We will add a mention of this to clarify the constructive nature of the proof."}]

Author rebuttal:
We would like to thank the reviewers for their time and helpful suggestions. We address each reviewer with an individual reply. Here, we post the PDF of rebuttal figures that are referenced in these replies.

Meta-review: 3/4 reviewers recommend accepting the paper with average score 6. One reviewer rejected it with score 4. I would like to accept this paper as a poster.
Decision: Accept (poster)