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: Submitted to ICLR 2023 (2023)
Keywords: graph
network
embeddings
arboricity
factorization
model
community
nonnegative

Abstract: Many models for undirected graphs are based on factorizing the graph's adjacency matrix; these models find a vector representation of each node such that the predicted probability of a link between two nodes increases with the similarity (dot product) of their associated vectors. 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. In contrast, a factorization with two vectors per node, based on logistic principal components analysis (LPCA), has been proven not only to represent such structures, but also to provide exact low-rank factorization of any graph with bounded max degree. However, this bound has limited applicability to real-world networks, which often have power law degree distributions with high max degree. Further, the LPCA model lacks interpretability since its asymmetric factorization does not reflect the undirectedness of the graph. We address the above issues in two ways. First, we prove a new bound for the LPCA model in terms of arboricity rather than max degree; this greatly increases the bound's applicability to many sparse real-world networks. Second, we propose an alternative graph model whose factorization is symmetric and nonnegative, which allows for link predictions to be interpreted in terms of node clusters. We show that the bounds for exact representation in the LPCA model extend to our new model. On the empirical side, our model is optimized effectively on real-world graphs with gradient descent on a cross-entropy loss. We demonstrate its effectiveness on a variety of foundational tasks, such as community detection and link prediction.

Under review as a conference paper at ICLR 2023
EXACT REPRESENTATION OF SPARSE NETWORKS WITH SYMMETRIC NONNEGATIVE EMBEDDINGS
Anonymous authors Paper under double-blind review
ABSTRACT
Many models for undirected graphs are based on factorizing the graph's adjacency matrix; these models find a vector representation of each node such that the predicted probability of a link between two nodes increases with the similarity (dot product) of their associated vectors. 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. contrast, factorization with two vectors per node, based on logistic principal components analysis (LPCA), has been proven not only to represent such structures, but also to provide exact low- rank factorization of any graph with bounded max degree. However, this bound has limited applicability to real-world networks, which often have power law degree distributions with high max degree. Further, the LPCA model lacks interpretability since its asymmetric factorization does not reflect the undirectedness of the graph. We address the above issues in two ways. First, we prove new bound for the LPCA model in terms of arboricity rather than max degree; this greatly increases the bound's applicability to many sparse real- weal-world networks. Second, we propose an alternative graph model whose factorization is symmetric and nonnegative, which allows for link predictions to interpreted in terms of node clusters. We show that the bounds for exact representation in the LPCA model extend to our new model. On the empirical side, our model is optimized effectively on real- well-world graphs with gradient descent on cross-entropy loss. We demonstrate its effectiveness variety of foundational tasks, such as community detection and link prediction.
INTRODUCTION
Graphs naturally arise in data from variety of fields including sociology (Mason & Verwoerd, 2007), biology (Scott, 1988), and computer networking (Bonato, 2004). A key underlying task in machine learning for graph data is forming models of graphs which can predict edges between nodes, form useful representations of nodes, and reveal interpretable structure in the graph, such as detecting clusters of nodes. Many graph models fall under the framework of seggeindependent 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 network which is known, in the link prediction task, i.c., 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 structure in interpretable way.
Expressiveness of low-dimensional embeddings 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 link between two nodes increases with the similarity of their embedding vectors. These models can alternatively be seen as factorizing the graph's 'sss adjacency matrix to approximate it with a low-rank matrix. Recent work of 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 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 such structures be represented, but further, any graph be exactly represented

---

Under review as a conference paper at ICLR 2023
with embedding vectors whose lengths are linear in the max degree of the graph. There are two keys to this result. First is the presence of a nonlinear linking function in the LPCA model; since adjacency matrices generally not low-rank, exact low-rank factorization is generally impossible without 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 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. 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 the model, these vectors may have restrictions such as 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 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 nonlinear link function (as in LPCA) to produce a probability for each edge, i.e., to ensure the values lie in [0, 1].
particular, each entry of the nonnegative embedding
Heterophily: Motivating example To demonstrate how heterophily can manifest in networks, as well as how models which assume homophily can fail represent such networks, we provide simple synthetic example. Suppose we have a graph of matches between users of a mostly heterosexual dating app, and the users each come 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 are unlikely to match with each other; this typifies heterophily. (Note that a mostly homosexual dating app would not exhibit heterophily in this sense.) 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 our proposed embedding model and with BIGCLAM, which explicitly assumes homophily. (It is far from alone in this assumption; see Li et al. (2018) 8) for recent example. along with more examples and further discussion in Section 3.) We also compare with the SVD of the adjacency matrix, which outputs the best (lowest Frobenius error) low-rank approximation that is possible without nonlinear linking function. Since SVD lacks nonnegativity constraints on the factors, we do not expect intepretability. In Figure I, 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 10 2 = 20 different kinds of nodes, meaning the expected adjacency matrix is r2n and our model maintains the lowest error up to this embedding length; by contrast, BIGCLAM is unable decrease error after capturing city information with length-10 embeddings. In Figure 3, we visualize the features generated by the three methods, i.e., the factors returned by each factorization. Our model's 's factors captures 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.
Summary of main contributions The key contributions of this work are as follows:
We prove that the LPCA model admits exact low-rank factorizations of graphs with bounded arboricity, which is the minimum number of forests into which graph's 's edges can be partitioned. By the Nash- Williams theorem, arboricity is a measure of a graph's 's density in that, letting S denote an induced subgraph and ng and m. denote the number of nodes and edges in S. arboricity is the maximum over all subgraphs S of m Our result is more applicable to real-world graphs than the prior one for graphs with bounded max degree, since sparsity is a common feature of real networks, whereas low max degree is not.
2

---

Under review as a conference paper at ICLR 2023
We introduce graph model which is both highly expressive and interpretable. 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, model is based on symmetric nonnegative matrix factorization, so it outputs link probabilities which are interpretable in terms of the communities it detects.
We show how any graph with low-rank factorization in the LPCA model also admits low-rank factorization in our community-basse 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.
Expected Adjacency
Samp Adjacency 420 to soo
203 403 e20
08
400
05
100
0.4
02
0.0
Figure 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 and women in of the ten cities.
SVD
BigClam
Ours
Frobenius Error
400
800
200 400 600
200 600
SVD
0.9
BtyCtam
200
200
200
600
600
600
Embaddiing Length
Figure 2: Left: Reconstructions of the motivating synthetic graph of Figure 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 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).
BigClam
Ours
200 400
600
803
202 400 600
800
220 400 500 500
0.5
0.5
-05
0.0
200
400
800
203
200
400
D0D
200
2-
-05
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 eigenvalues corresponding to homophiloushhhetrrphiiouu 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

---

Under review as a conference paper at ICLR 2023
2 COMMUNIT-BASED GRAPH FACTORIZATION MODEL
Consider the set of undirected, unweighted graphs on n nodes, i.e., the set of graphs with symmetric adjacency matrices in {0, 1 We propose edge-independent generative model for such graphs. Given nonnegative parameter matrices B E IR " and C RT* we set the probability of an edge existing between nodes and j to be the (i, entry of matrix A:
Á == o
(BB CC
where a is the logistic function. Here kB. ke are the number hommohiioushheerrpphiouu clusters. Intuitively, b, E T is the i-th row of matrix B, then b, is the affinity of node i to each of the ky homophilous communities. Similarly, C; E R is the affinity of node i to the kc heterophilous communities. As an equivalent statement, for each pair of nodes and j. A., == obbbb c.c, ). We will soon discuss the precise interpretation of this model, but the idea is roughly similar to the attract-repel framework of Peysakhovich & Bottou (2021). When nodes and have similar "attractive' b embeddings, i.e., when b,b, is high, the likelihood of an edge between them increases, hence why the B factor homophilous. By contrast, the C factor is 'repulsive' /heterophilous since, when e.c. is high, the likelihood of an edge between and j decreases.
Alternate expression We note that the model above can also be expressed in a form which 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 a matrix V E [0, 1|m** and a diagonal matrix W E B where k = kn + ke is the total number of clusters. In particular, let mn and mc be the vectors containing the maximums of each column of B and C. By setting
V = (B x diag (m C x diag (mz!))
W = diag ((+m); )m
the constraint on V is satisfied. Further, VWV BB - CC
À = o (BB
(3)
Here, v; E (0, 1] is the i-th row of matrix V. then v; is the soft (normalized) assignment of node i to the ie communities. The diagonal entries of W represent the strength of the homophily (if positive) or heterophily (if negative) of the communities. For each entry, A.j Vv,, ). 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 log(o) E (-00, +.)). The logit of the link probability between nodes and j is v. Wvj. which is a summation of terms Vie Wee cc over all communities c [k]. If the nodes both fully participate in community c, that is, Vie Vie- 1, then the edge logit is changed by Woe starting from baseline of O, or equivalently, the odds of an edge is multiplied by exp( Wee) 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 accordingly prorated. Homophily and heterophily also have clear interpretation in this model: homophilous communities, which are expressed in B, are those with W.. O, where two nodes both participating in the community increases the odds of a link, whereas communities with W.. < O, which are expressed in C, are heterophilous, and coparticipation decreases the odds of link.
1-p [0, oo), and logit e
3 RELATED WORK
Community detection via interpretable factorizations There is extensive prior work on the com- munity detection 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 work are those based on non- -egnaeete matrix factorization (NMF) (Lee & Scung, 1999; Berry et al., 2007; Wang & Zhang, 2012; Gillis, 2020), many of which can be seen integrating nonnegativity constraints into
4

---

Under review as a conference paper at ICLR 2023
the broader, well-studied random dot product graph (RDPG) model (Young & Scheinerman, 2007; Scheinerman & Tucker, 2010; Athreya et al., 2017; Gallagher et al., 2021; Marenco et al., 2022). One such algorithm is that of Yu et al. (2005), which approximately factors a graph's 's adjacency matrix A E (0, 1)mxn into two positive matrices H and A, where H E R is left-stochastic (i.e. each of its columns sums to 1) and A E R is diagonal, such that HAH RS A. Here H represents a soft clustering of the nodes into & clusters, while the diagonal entries of A represent the prevalence of edges within clusters. Note the similarity of the factorization to our model, save for the lack of 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 (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), as well as proposed solutions (Pei et al., 2020; 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. For example, the Generalized RDPG (Rubin-Delanchy et al., 2017) allows for the representation of non-PSD adjacency matrices by using a "ti-faactorization" " like that of Yu et al. (2005), but removing the constraint that the central diagonal matrix must be nonnegative. The model of Nourbakhsh et al. (2014) goes further, removing all constraints on this matrix. Another example is the model in Miller al. (2009), which is similar 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 to larger networks. More recently, Peysakhovich & Bottou (2021) propose a decomposition of the form A R D + BB - CC where D E R='* is diagonal and B, C E Rnnk are low-rank. Note that their decomposition does not include a nonlinear linking function, and their work does not pursue clustering interpretation or investigate setting the factors B and C to be nonnegative.
Overlapping communities and exact embeddings Many models discussed above focus on the single-label clustering task and thus involve highly-constrained factorizations (e.g., sum-to-one conditions). We are interested in the closely related but distinct task of multi-label clustering, also known 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 1 ff fy), where f. f, E 14 represent the intensities with which the nodes participate in each of the k 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 a 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 et al., 2020; Chanpuriya et al., 2020) suggests that incorporating nonlincar linking function can greatly increase the expressiveness of factorization-bant based graph models, to the point of being able to exactly represent graph. This adds to growing body of literature expressiveness guarantees for embeddings on relational data (Sala et al., 2018; Bhattacharjee & Dasgupta, 2020; Boratko et al., 2021). Most relevant to our work, as previously discussed, Chanpuriya et al. (2020) provide guarantee for exact low-rank representation of graphs with bounded max degree when using the LPCA factorization model. In this work, we provide new such guarantee, except for bounded arboricity, which is more applicable to real- world networks, and extend these guarantees to our community -basdd factorization.
4 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 reconstructs graph A E (0, (0.1)ax using logit factors X, Y E R via
A A Axo(XTT)
5

---

Under review as a conference paper at ICLR 2023
Note that unlike our commmnity-basee factorization, the factors of the LPCA model are not nonnega- tive, and the factorization does not reflect the symmetry of the undirected graph's 's adjacency matrix. Regardless of the model's 's 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 Heaviside step function to M, that is, setting all positive entries to I,, negative entries to O, and zero entries to 1/2.
Theorem 4.1 (Exact LPCA Factorization for Bounded-Degree Graphs, Chanpuriya et al. (2020)). Let A E {0, 1] jun=n be the adjacency matrix of a graph G with maximum degree c. Then there exist matrices X, Y E [ex((2++1) such that A- = H.
This corresponds arbitrarily small approximation error in the LPCA model (Equation 4) because, provided such factors X, Y for some graph A, we have that lim (sXXT)== ((Y = 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 (kk) communities. This extends the guarantees power for exact representation of graphs, both the prior guarantee in terms of max degree and our new one in terms of arboricity, to our community-base based model as well. In Appendix A.I, also introduce a natural family of graphs Community Overlap Threshold (COT) graphs for which our model's 's community-band based factorization not only exactly represents the graph, but also must capture some latent structure to do so with sufficiently low embedding dimensionality.
the LPCA model's
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 Y) S rank rYn
Theorem 4.2 (Exact LPCA Factorization for Bounded-Arboricity Arboricity Graphs). Let A E {0, 10,1) be the adjacency matrix of an undirected graph G with arboricity a. Then there exist embeddings
X,Y Y E R=x((aa=1)) such that A = H
Proof. Let the undirected graph have arboricity a, i.e., the edges can be partitioned into a forests. We produce directed graph B from A by orienting the edges in these forests so that each node's 's B + B and every node in B has in-degree at most a.
edges point towards its children. Now
Let V E R be the Vandermonde matrix with V., g For any c R (Vc(())
Σe=1 e(j)- 1--1, that is, Ve TR" is degree-(2a) polynomial with coefficients e evaluated the integers E [n] = .n............ Let b, be the 8h column of B. We seek to construct a polynomial such that for with (t) 1, [V,, (t) O, and [Vc, (t) < 0 elsewhere; that is, when inputting an index / E [n]] such that the 1th node is an in-neighbor of the 7th node, we want the polynomial to output and for all other indices in [n). we want it have negative output. Letting (i) denote the in-neighbors of the nd node, simple instantiation of such polynomial in t is -1 II (t - -
Note that since all nodes have in-degree at most a, this polynomial's degree is at most 2o, and hence there exists coefficient vector e; E 20 encoding this polynomial.
Let C E 2 be the matrix resulting from stacking such coefficient vectors for each of the nodes. Consider P VC Raxa, P., is 0 B,, = 1 and negative otherwise. Then (P o P )ay 0 when either Btj
or (B ) )r. = 1 and positive otherwise; equivalently, since A B + B
(Po PT),, )c,, = iff A., = Take any positive e less than the smallest positive entry of P PT Letting J be an all-ones matrix, define M eJ (P PT). Note that Mr, > 0 if A = 1 and
M.j, < 0 if A = 0, that is, M = H (A) as desired. Since rank(J) = and rank (P) < 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 B can be pro- cessed into nonnegative factors B E Ra and C E R Raxke such that kB + kc = 6k and
BB CC XY + vXT).
(5)
6

---

Under review as a conference paper at ICLR 2023
Observe that the left-hand side can only represent symmetric matrices, but XY is not necessarily symmetric even if (XX = A for a symmetric A. For this reason, we use a symmetrization. let L 2 (XY + +Y Note that H() H(XY)), so if XYT constitutes an exact representation of A in that H(XYT) = A. so too do both expressions for L in Equation 5. Pseudocode 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 a sum and difference of rank-1 components via eigendecomposition. Each of these components can be written as +vv or -v with v E R", where the sign depends on the sign of the eigenvalue. Each component is then separated into sum and difference of three outer products of nonnegative vectors, via Lemma 4.3 below.
Lemma 4.3. Let Φ - R denote the ReLU function, iee, ((2) (2, 0}. For any vector v,
vv = - +
|v/|vl
Proof. Take any Rt Then
vv T = - ((-v)) -(1 )
=d(v)((v) + ((-v)((vv)) ((v))(-v)) -
=20(v)d(v) + 20( (()((v)((vv) vv ((((v) -((-)) (d(v) v(v))
=V(())(v)) + 22 (v)((( -v) - -|vvvllv"
where the first step follows from v = =<(v)= ((v))((vv), and the last step from |v| = x(v)+
Algorithm follows from Lemma 4.3 and constitutes constructive proof of the following theorem: Theorem 4.4 (Exact Community Factorization from Exact LPCA Factorization). Given symmetric Y E i such that A H (XY T) there exist nonnegative matrices
matrix E {0, }} and X,Y
B E 1 mxxk and C E Rixke such that kB + kc = 6k and A = H(BB CC
Algorithm Converting LPCA Factorization to Community Factorization input logit factors X, Y Ra
output B E T ga and C E R Ruxke such that kB + kc = 6k and
BB CC
(XYT + +YXT)
1: Set Q E R and À E 2 by truncated eigendecomposition such that Q x diag(A) A) Q 1 (XY +YX")
2: B + Q+ x diag( V /+++), ) where Xt, Q+ are the positive eigenvalues//vcctos
3: C < Q x diag(v
V- x where \= Q are the negative eigenvalues/vectors
4: B+ (V);(B");
V20( -B"); C*) P @ and - | are entrywise ReLU and absolute value
5: C+ (2(((*))
V20( V2"(-C"); B*))
6: return B.C
As stated in the introduction this section, Theorem 4.4 extends any upper bound the exact factorization dimensionality from the LPCA model to our community-basse model. That is, to a constant factor, the bound in terms of max degree from Theorem 4.1 and the bound in terms of arboricity from Theorem 4.2 also apply to our model; for brevity, we state just the latter here.
Corollary 4.5 (Exact Community Factorization for Bounded-Aren Bounded-Arborrcity Graphs). Let A E (0, 1 be the adjacency matrix of an undirected graph with arboricity a. Then there exist non- negative embeddings B Raxke and C E Ruxke such that kB + kc = 6(4a² + 1) and A H(BB CC
Note that Corollary 4.5 is purely a statement about the capacity of our model; Theorem 4.2 stems from constructive proof based polynomial interpolation, and therefore too does this corollary. We do not expect this factorization to be informative about the graph's 's latent structure. In the following Section 5, we will fit the model with entirely different algorithm for downstream applications.
7

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTS
We now present training algorithm to fit model, then evaluate method benchmark of five real-world networks. These are fairly common small to mid-size datasets ranging from around 1K to 10K nodes; for brevity, defer the statistics and discussion of these datasets, including how some of them exhibit heterophily, to Appendix A.2.
5.1 TRAINING ALGORITHM
Given an input graph E (0. 1)mxn, we find low-rank nonnegative matrices B and C' such that the model produces Á = a (BB )CT) E (0,1) as in Equation 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 Σ A log( () + (1 ()-A) log(1 A))
where Σ denotes the scalar summation of all entries in the matrix. 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 an exact fit, we 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 we outline a non-stochastic version of the training algorithm, it generalizes straightforwardly to stochastic version, i.e., by sampling links and non-links for the loss function.
Algorithm 2 Fitting the Constrained Model
input adjacency matrix A {0, _ regularization weight À 2 0. number of iterations I, number of hhntepiiooushhettrpphiluuuuu communities kB/ /kc output fitted factors B E x and C E R such that o (BB CC ~ A
1: Initialize B, C' by setting entries to independent samples of Unif(0, 1/Vkn), Unif(O, 1/Vkc)
2: for +- do
3:
Á + cBB CCT))
- (:AA A log A) + (1 A) log(1- 10--] -A)
4:
5:
R+ R B (IC1))+
6:
Calculate 0B, OB.olt R via differentiation through Steps to 4
7: Update B, C' to minimize R using Ôn,RR, subject to B, C20
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 et al., 2001) implementation of the L- BFGS (Liu & Nocedal, 1989; Zhu et al., 1997) algorithm with default hyperparameters and up to max of 200 iterations of optimization. We set regularization weight À = 10 as in Yang & Leskovec (2013). We include code the form of Jupyter notebook (Pérez & Granger, 2007) demo. The code also contains stochastic (i.e., more scalable) versions of the optimization functions.
5.2 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 our 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 of our model with those of SVD, BIGCLAM (which is discussed in detail in Section 3), and SYMNMF (Kuang et al., 2015). SYMNMF simply factors the adjacency matrix as A HH where H E Baxk, 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 graph generative model like ours and BIGCLAM.
8

---

Under review as a conference paper at ICLR 2023
Frobentu Entr
Croas Entopr w
Method
SVD
SymNMF
BgCam
Qura
POB
FPI
Blog
Amazon
YouTube
POS
PPI
Blog
Amazon
YouTube
Figure 4: Reconstruction on real-world networks, relative our model's error.
For each method, we fix the number of communities or singular vectors at the ground -oound-truth 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 a fair comparison with SVD, we do not regularize the training the other methods. Our method consistently lowest reconstruction error, both in terms of Frobenius emrr and entrywise cross-entropy (Equation 6). Interestingly, we find the most significant improvement exactly on the three datasets which have been noted exhibit significant heterophily: POS, PPI, and AMAZON.
the
Similarity to ground-truth communities To assess the interpretability of clusters generated by our 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 to another recent but non-generative approach, the VGRAPH method of Sun al. (2019), which based on link clustering; the authors found their method to generally achieve mate-of-the-an results in this task. For all methods, we set the number communities to detected as the number ground-truth communities. We report FI-Score computed in Yang & Leskovee (2013). See Figure (left): the performance of our method competitive with SYMNMF, BIGCLAM, and vGraph.
Community Delecton
Link Prediction
0.6
0.5
Method
Methed
vGraph
F1 Score
0.3
SymNMF
SymMMF
BigClam
BigCamm
0.2
0.1
0.0
0.0
Blg
Figure 5: Left: Similarity of recovered communities to ground-truth labels of real-world datasets. We are unable to run the authors' implementation of vGRAPH on BLOG with limited memory. Right: Accuracy of link prediction on real-world datasets.
Interpretable link prediction We assess the predictive power of our generative model on the link prediction task. As discussed in Section 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 on 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 that of the other methods in terms F1 Score.
CONCLUSION
We introduce community-basse based graph generative model based on symmetric nonnegative matrix factorization which is capable of representing both homophily and heterophily. We expand on prior work guaranteeing exact representation of bounded max degree graphs with new, more applicable guarantee for bounded arboricity graphs, and we show that both the prior bound and our new one 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. More broadly, our results suggest that incorporating heterophily into models and methods for networks improve both theoretical grounding and overall empirical performance. while maintaining simplicity and interpretability. deeper understanding of the expressiveness of both nonnegative and arbitrary low-rank logit models for graphs is interesting future direction.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Charu C Aggarwal and Haixun Wang. A survey of clustering algorithms for graph data. In Managing and Mining Graph Data, pp. 275-301. Springer, 2010.
Avanti Athreya, Donniell Fishkind, Minh Tang, Carey E Priebe, Youngser Park, Joshua T Vogelstein, Keith Levin, Vince Lyzinski, and Yichen Qin. Statistical inference on random dot product graphs: a survey, The Journal of Machine Learning Research, 18(1):8393-8484 2017.
Michael W Berry, Murray Browne, Amy N Langville, Paul Pauca, and Robert Plemmons. Algorithms and applications for approximate nonnegative matrix factorization. Computational Statistics & Data Analysis, 52(1): (0(1))155-11 155-173, 2007.
Robi Bhattacharjee and Sanjoy Dasgupta. What relations are reliably embeddable in euclidean space? In Algorithmic Learning Theory, pp. 174-195. PMLR, 2020.
Anthony Bonato. A survey of models of the web graph. In Workshop on Combinatorial and Algorithmic Aspects of Networking, pp. 159-172. Springer, 2004.
Michael Boratko, Dongxu Zhang, Nicholas Monath, Luke Vilnis, Kenneth L Clarkson, and Andrew McCallum. Capacity and bias of learned geometric embeddings for directed graphs. Advances in 2021.
Neural Information Processing Systems,
Bobby-Joe Breitkreutz, Chris Stark. Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz. Michael Livstone, Rose Oughtred, Daniel H Lackner, Jürg Bähler, Valerie Wood, et al. The biogrid interaction database: 2008 update. Nucleic acids research, 1)) 2007.
Sudhanshu Chanpuriya, Cameron Museo, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. Node embeddings and exact low-rank representations of complex networks. Advances in Neural Information Processing Systems, 33, 2020.
Chris Ding, Tao Li, and Michael Jordan. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching, and clique finding. In 2008 Eighth IEEE International Conference on Data Mining, pp. 183-192. IEEE, 2008.
David L. Donoho and Victoria Stodden. When does non negative matrix factorization give a correct decomposition into parts? In Advances in Neural Information Processing Systems 16, pp. 1141- 1148. MIT Press, 2003.
David Duvenaud, Dougal Maclaurin, Jorge aguilera-Iparraguirre Rafael Gómez-Bombarelli, Tim- othy Hirzel, Alán Sapuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems 28, pp. 2224-2232, 2015.
Jacob G Foster, David V Foster, Peter Grassberger, and Maya Paczuski. Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107(24):00115-10220, 2010.
Ian Gallagher, Andrew Jones, and Patrick Rubin-Delanchy. Spectral embedding for dynamic networks with stability guarantees. Advances in Neural Information Processing Systems, 34:10158-10170, 2021.
Nicolas Gillis. Nonnegative Matrix Factorization. SIAM, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Takeshi Hase, Yoshihito Nimura,, and Hiroshi Tanaka. Difference in gene duplicability may explain the difference in overall structure of protein-protein interaction networks among eukaryotes. BMC Exolutionnary Biology, 10(1):1-15, 2010.
Muhammad Aqib Javed, Muhammad Shahzad Younis, Siddique Latif, Junaid Qadir, and Adeel Baig. Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications, 108:87-111, 2018.
10

---

Under review as a conference paper at ICLR 2023
Samuel Johnson, Joaquín J Torres, Marro, and Miguel A Munoz. Entropic origin of disassortativity in complex networks. Physical Review Letters, 104(10):108702, 2010.
Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python, 2001. URL http: www. .ww.l/y..or......o
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Da Kuang, Chris Ding, and Haesun Park. Symmetric nonnegative matrix factorization for graph clustering. In Proceedings of the 2012 SIAM International Conference Data Mining, pp. 106-117. SIAM, 2012.
Da Kuang, Sangwoon Yun, and Haesun Park. Symnmf: nonnegative low-rank approximation of similarity matrix for graph clustering. Journal of Global Optimization, 62(3):545-57) 2015.
Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factoriza- tion. Nature, 401(6755);788-79,, 1999.
Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. Community detection attributed graphs: An embedding approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Dong Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1-3):503-55 1989.
Bernardo Marenco, Paola Bermolen, Marcelo Fiori, Federico Larroca, and Gonzalo Mateos. Online change point detection for weighted and directed random dot product graphs. IEEE Transactions on Signal and Information Processing over Networks, 8:144-155 159, 2022.
Oliver Mason and Mark Verwoerd. Graph theory and networks in biology. IET Systems Biology, 1 (2):99-119, 2007.
Miller McPherson, Lynn Smith-Lovin, and James Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-4444 2001.
Kurt T. Miller, Thomas L. Griffiths, and Michael I. Jordan. Nonparametric latent feature models for link prediction. In Advances in Neural Information Processing Systems 22, pp. 1276-1284. Curran Associates, Inc., 2009.
Maria CV Nascimento and Andre CPLF De Carvalho. Spectral methods for graph clustering-a survey, European Journal of Operational Research, 211(2)221--311 2011.
Mark EJ Newman. Assortative mixing in networks. Physical Review Letters, 89(20), 2002.
Rogier Noldus and Piet Van Mieghem. Assortativity in complex networks. Journal of Complex Networks, 344):507-542, 2015.
Farshad Nourbakhsh, Samuel Rota Bulo, and Marcello Pelillo. A matrix factorization approach to graph compression. In 2014 22nd International Conference on Pattern Recognition, pp. 76-81.
IEEE, 2014.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 0ttt::/995.000... 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-80888 8035. Curran Associates, Inc., 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
11

---

Under review as a conference paper at ICLR 2023
Fernando Pérez and Brian E. Granger. IPython: system for interactive scientific computing. Computing in Science and Engineering, 9()):11-2,, May 2007. ISSN 1521-9615. doi: 10.1109/
MCSE.2007.53, URL https: htttthotttooooooooo org.
Alexander Peysakhovich and Leon Bottou. An attract-repel decomposition of undirected networks. arXiv preprint 0tth::2006096677. 2021.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459-467, ACM, 2018.
Luca Rendsburg, Holger Heidrich, and Ulrike Von Luxburg. Netgan without gan: From random walks to low-rank approximations. In International Conference Machine Learning, pp. 8073-8082. PMLR, 2020.
Patrick Rubin- Delnn-eeench, Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. arXiv preprint arXiv: 1709.05566, 2017.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoff' for hyperbolic embeddings. In International Conference on Machine Learning, pp. 4460-4469, PMLR, 2018.
Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007.
Edward R Scheinerman and Kimberly Tucker. Modeling graphs using dot product representations. Computational statistics, 25(1):1-16, 2010.
John Scott. Social network analysis. Sociology, 22(1):109-127, 1988.
Seshadhri, Aneesh Sharma, Andrew Stolman, and Ashish Goel. The impossibility of low-rank representations for triangle-rich complex networks. Proceedings of the National Academy of Sciences, 117(11))5631-5633 2020.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-99) 905, 2000.
Fan-Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wei Huang, and Jian Tang. vgraph: A generative model for joint community detection and node representation learning. In Advances in Neural Information Processing Systems 32, pp. 512-522, 2019.
Lei Tang and Huan Liu. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 817-826. ACM, 2009.
Yu-Xiong Wang and Yu-Jin Zhang. Nonnegative matrix factorization: A comprehensive review.
IEEE Transactions on Knowledge and Data Engineering, 2336)11336 2012.
Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski. Overlapping community detection in networks: The -tate-of-the-arr and comparative study. ACM Computing Surveys, 45(4):43:1 13:335, 2013.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.064422 2021.
Jaewon Yang and Jure Leskovec. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp. 587-596, 2013.
Jaewon Yang and Jure Leskovec, Defining and evaluating network communities based on ground-truth Knowledge and Information Systems, 42(1):181-213 2015.
Zhirong Yang, Tele Hao, Onur Dikmen, Xi Chen, and Erkki Oja. Clustering by nonnegative matrix factorization using graph random walk. Advances in Neural Information Processing Systems, pp. 1079-1087, 2012.
12

---

Under review as a conference paper at ICLR 2023
Stephen J Young and Edward R Scheinerman. Random dot product graph models for social networks. In International Workshop on Algorithms and Models for the Web-Graph, pp. 138-149. Springer, 2007.
Kai Yu, Shipeng Yu, and Volker Tresp. Soft clustering graphs. In Advances in Neural Information Processing Systems, pp. 1553-1560, 2005.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv:2202.07082 2022.
Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-BFGS-B BB Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions on Mathematical Software (TOMS), 23(4):550-50) 1997.
Jiong Zhu. Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
Katharina Anna Zweig. Are word-adjacency networks networks? In Towards a theoretical framework framewwnk for analyzing complex linguistic networks, pp. 153-163. Springer, 2016.
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A. COT GRAPH EXACT REPRESENTATION
As theoretical demonstration of the capability our model 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 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 heterophilous communities. For example, the motivating graph described in Section I would be 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 (Community Overlap Threshold (COT) Graph), An unweighted, undirected graph whose edges are determined by overlapping clustering and a "thresholding" " integer I, E 2. as follows: for each vertex i, there are two latent binary vectors b, E {0, 10, and C; E (0,1) and there an edge between vertices i and iff b; bj C; Cj 2 t.
Theorem A.1 (Compact Representation of COT Graphs). Suppose A is the adjacency matrix of COT graph on n nodes with latent vectors b, E {0, 13 and C₁ E {0, 13 for i E [1,2, ...,............ Let kGs ke. Then, for any > there exist V E [0, 1]mx(k+1) and diagonal W E [[(+1)x(+++) such that (VVVVVV) A <.
.n).
Proof. Let t be the thresholding integer of the graph, and let the rows of B E {0, 1j and Ce {0, 1]"xk] contain the vectors and e of all nodes. Via Equation 2, we can find V E [0, 1 1jnxk and diagonal W E kk such that V V*W*** = =BB' CCT, Now let
V 1)
W =
W
1 -11)
Then (VWV )iy b; bj c: Cg + I. Hence (VWV )ay > 0ff b, by C: -0.--11- which is iff A.j 1 by the assumption the graph. Similarly, (VWV )is < < A, 0. It follows that
lim o (V(sW)VT) lim (SVWVT) = +0000
++000
14

---

Under review as a conference paper at ICLR 2023
A.2 DATASET DESCRIPTIONS
As stated in Section 5, we now briefly describe the five real-world datasets. datasets given in Table 1.
Statistics for these
Table 1: Statistics of datasets used in our experiments. As in Sun al. (2019). for YOUTUBE
and AMAZON, we take only nodes which participate in at least one of the largest 5 ground-truth communities. Note that degeneracy is an upper bound on arboricity.
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 et al. (2007)
3,852
76,546
50
593
29
AMAZON
Yang & Leskovec (2015)
794
2,109
29
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 are 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-protedd 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 are firquuenly purchased together. Labels represent categories products.
While social networks like the former two in this list are generally dominated by homophily (McPher- son et al., 2001), the latter three should exhibit significant heterophily. For co- co-purchasing networks like AMAZON, depending purchased, e.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-
15


Reviews:
[{"review_id": "ouBkM0E9Nh", "reviewer": "Reviewer_s4Ez", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the issue with representing (esp. heterophilic, power law) graphs by factorising the adjacency matrix into a combination of homophilic and heterophilic factors that are interpretable. Lower bounds based on logisitic principal components analysis (LPCA) is improved removing assumptions on the max degree and replacing with the arboricity of the graph. A new graph model is proposed with symmetric and non-negative factorisations based on the decomposition mentioned and a simple gradient descent alogirthm is proposed to optimise the paramters. The method is compared to a baseline SVD decomposition and recent work using a similar method, BigClam. Results on synthetic and real-world data are reported with promising results.\n", "summary_of_the_review": "A very good model, with a new lower bound and a simple optimisation approach. The achilles heel seems to be selecting the number of homophilic factors and number of heterophilic factors. This is not explored in the experiments nor discussed in the paper. Clearing this up would make a strong paper.\n\n[Post Review Updates]\n\nMy questions were clearly answered and I feel that this is a novel and sginificant contribution to a growing are of interest: working with heterophily in graphs.\n\nI have raised my review to an accept as I see this work as ready for publication.\n\n[Post Reviewer-Discussion]\nDuring the reviewer discussion the similarity to the work on Generalized RDPG was brought up and this area of work is not compared in enough detail considering the similarity with the work on homopholic and heterophilic relations in [1]. There was also some questions about the bound, to be clarified. Therefore I have slightly lowered my review recommendation as I felt these were genuine concerns.\n\nI want to emphasize that in my opinion this is an area of growing interest, namely modelling heterophilic and homophilic relations. I feel this paper is well written and shows promising results. I believe this will be a very strong paper with the additions of addressing more closely the GRDPG and related literature, clarifying questions on the bound and ensuring that the real-data experiments are strongly supporting the claims (datasets are those which have heterophilic and homophilic relations, and the comparable methods are state-of-the-art).\n\n1. P. Rubin-Delanchy, J. Cape, M. Tang, and C. E. Priebe, \"A statistical interpretation of spectral embedding: The generalized random dot product graph,\" 2017\n", "strength_and_weaknesses": "\nThis paper addresses the issue of modelling graphs with both homophily and heterophily in a elegent decomposition that is both simple and effective. The new lower bound is novel and seems valid to the best of my knowledge but I could not follow all steps in detail due to time constraints and lack of deep knowledge in the area. The algorithm to optimise the model is simple and results looked promising. This is very relevant work, and a hot topic in graph related domains including GNNs for example.\n\nI do wonder about the comparison with the other methods, as in the comparison with synthetic data, the BigClam method was limited to 12 factors, when I think using 20 factors would be interesting, and may lead to improved fitting of the BiClam method. Although the model is elegant, the selection of the hyper-parameters (how many homophilic and how many heterophilic factors) is left open but does not seem trivial is it is vital to the good fitting of the model. With the synthetic data, the exact number of homophilic factors was known (10 towns) and number of heterophilic were known (2 genders), leading to an over simplified problem, as this knoweldge is unknown for a real problem. Exporing this would strengthen the work, like showing the behaviour of the model if choosing 9 homophilic and 3 heterpholic features for example, or how to find those from the data maybe? Some more details about how many features and other parameter tuning of the comparison models in the results would also be important to understand if these seem optimal. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OVMZYkHiZbR", "reviewer": "Reviewer_pv1p", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a representation model in the framework of describing an adjacency matrix through matrix factorization. They also prove a result regarding exact matrix representation, where the needed size of the embeddings can be described in terms of the arboricity of the graph. This improves previous results in terms of applicability to real graphs.\nFinally, the authors propose an alternative learning method for the factorization based on gradient descent, which is then used for downstream tasks in the experimental section.", "summary_of_the_review": "The paper proposes interesting ideas, but the (unintentional) lack of references to very similar works makes it very hard to accept it in this first version.\nI'm sure the authors will take into account these (and maybe other) related papers and will come up with a new version, which would be a very nice paper.", "strength_and_weaknesses": "The strength of the paper is the result regarding arboricity and the factorization of the adjacency matrix.\n\nHowever, I find a significant weakness. There is a quite big community working in graph models via factorization, or \"dot product graphs\", which is not acknowledged in the paper. I'm sure this is not intentional, but the amount of work of these groups is quite large, and published in journals and conferences very related to this one (meaning that this is not a case of similar work but in a very different community) like NeurIPS or PAMI.\nNamely, the RDPG model is widely studied and not mentioned in the paper. The model is almost exactly like the ones described in this work, and moreover, there is a version called Generalized RDPG which takes into account heterophily and homophily, and its formulation is very related to the one proposed in this paper (in equation 3).\n\nI think the Generalized RDPG model is described in this paper:\nP. Rubin-Delanchy, J. Cape, M. Tang, and C. E. Priebe, \"A statistical interpretation of spectral embedding: The generalized random dot product graph,\" 2017\n\nand some other papers on the subject are:\n - E. Scheinerman and K. Tucker, \"Modeling graphs using dot product representations,\" Comput. Stat.\n - A. Athreya, D. E. Fishkind, M. Tang, C. E. Priebe, Y. Park, J. T.\nVogelstein, K. Levin, V. Lyzinski, and Y. Qin, \"Statistical inference on random dot product graphs: A survey,\"\n - I. Gallagher, A. Jones, and P. Rubin-Delanchy, \"Spectral embedding\nfor dynamic networks with stability guarantees,\" Advances in Neural\nInformation Processing Systems 34, NeurIPS, 2021.\n - B. Marenco et. al, Online change-point detection for weighted and directed random dot product graphs. IEEE Transactions on Signal and Information Processing over Networks, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "68GnuFfN8GQ", "reviewer": "Reviewer_N53t", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an exact nonnegative matrix factorization method that provides interpretable node embeddings (interpretation as the cluster/community assignment). The authors prove that under the constraint of embedding dimensionality, the embeddings can reconstruct adjacency matrix exactly. A training algorithm is provided and shown to be effective in community detection and interpretable link prediction.", "summary_of_the_review": "To further justify the weaknesses:\n- It's not clear whether 4 * \\alpha^2 is a smaller number than 2c (where c is the max degree). In appendix, the authors provide the value of degeneracy, but based on that number, 4 * \\alpha^2 is definitely much larger than 2c. In this way, I don't think the bound based on arboricit has a wider applicability.  \n- Regarding the heterophily of the datasets, though the authors illustrate the heterophily intuitively, it's not quantified. Thus, it's unable to justify whether the proposed method can model heterophily in practice.", "strength_and_weaknesses": "Strengths:\n- The proposed model is interpretable to provide node embeddings that can be interpreted as cluster assignments.\n- The paper theoretically proves under certain embedding dimensionality, the node embeddings can be used to perfectly reconstruct the input adjacency matrix.\n- The graph model can explicitly capture the homophily and heterophily of the graph.\n- An illustrative example is provided in the introduction to help understand the motivations of this work.\n\nWeaknesses:\n- It's not clear whether the embedding dimension condition on arboricit is tighter than the existing degree-based theorem.\n- The proposed algorithm has a high complexity given that it computes the reconstructed dense adjacency matrix in each iteration (BB^T-CC^T).\n- Interpretable link prediction is not a new application, but in the experiments only few methods are compared. \n- The heterophily of the datasets is not clearly justified.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject