A sharp NMF result with applications in network modeling  
Authors: Jiashun Jin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Non-negative matrix factorization (NMF)
social networks
degree-corrected block model
mixed-membership
low-rank model

Abstract: Given an $n \times n$  non-negative rank-$K$ matrix $\Omega$ where $m$ eigenvalues are negative, when can we write $\Omega = Z P Z'$ for non-negative matrices $Z \in \mathbb{R}^{n, K}$ and $P \in \mathbb{R}^{K, K}$?  While most existing works focused on the case of $m = 0$, our primary interest is on the case of  general $m$. With new proof ideas we develop, we present sharp results on when the NMF problem is solvable, which significantly extend existing results on this topic. The NMF problem is partially motivated by applications in network modeling.   For a network with $K$ communities,  rank-$K$ models are popular, with many proposals. The DCMM model is 
a recent rank-$K$ model which is especially useful and interpretable in practice. To enjoy such properties,  it is of interest to study 
when a rank-$K$ model can be rewritten as a DCMM model. Using our NMF results, we show that for a rank-$K$ model with parameters in the most interesting range, we can always rewrite it as a DCMM model.  

A sharp NMF result with applications in network modeling
Jiashun Jin
Department of Statistics & Data Science Carnegie Mellon University Pittsburgh, PA 15213 j jashun@stat. cmu edu
Abstract
Given an n n non-negative rank- K matrix Q where m eigenvalues are negative, when can we write f = ZPZ' for non-negative matrices Z E Ra.K and P e KKK.? While most existing works focused on the case of m = O, our primary interest is the case of general m. With new proof ideas, present sharp results on when the NMF problem is solvable, which significantly extend existing results on this topic. The NMF problem is partially motivated by applications in network modeling. For a network with K communities, rank-K models are especially popular. The rank-K model which is especially useful and interpretable in practice. To enjoy such properties, it is of interest study when rank-K model can be rewritten a DCMM model. Using our NMF results, we show that for a rank- model in the most interesting parameter ranges, we can always rewrite it DCMM model.
(DCMM) model is recent
Introduction
Fix (n, m) where n 2 2 and 0 S m S K 1. We are interested in the following Non-negative Matrix Factorization (NMF) problem.
The NMF problem: given an n X n symmetric non-negative irreuccbble matrix Ω with rank K where exactly m of the K nonzero eigenvalues are negative, when can we find (1.1)
non non-negative matrices Z E R.,K and P E K. such that Ω ZPZ"
We say a matrix Ω non-negative if all of its entries are non-negative, and we say it positive if all of its entries are (strictly) positive. We say the NMF problem is solvable for Q is can find non-negative matrices (2, P) as above such that Ω = ZPZ'.
Definition 1.1
We assume 2 for the case K 1 trivial and we assume m < K 1 for an irreducible non-negative matrix has at least one positive eigenvalue (c.g., by Perron's 's theorem (9).
NMF is a fundamental problem and has applications in areas such image processing 5 2 text learning (11, hyper-spectral unmixing, and social network analysis [3]. Our setting is special case of NMF where both l and P symmetric,
may call it symmetric NMF. In the literature, symmetric NMF was widely used in clustering of nonlinearly separable data from a similarity matrix where for non-negative symmetric matrix Ω, it aims to find non-negative matrix Z such that
Ω = ZZ'. where Z R. and N 2 K.
(1.2)
Note that, first, this implicitly requires that Ω is positive semi-definite. Second, it is understood that for many non-negative and positive semi-definite matrices Ω the smallest N can find in the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

factorization of (1. is strictly larger than K (the rank of f2). See the 2021 book by Shaked- Monderer and Berman 226 The book is 551 pages and summarizes nicely most existing results on NMF.
Unfortunately, our setting in (1.1) is significantly different from that in (1.2). so existing results on NMF do not directly apply. Especially, our NMF setting is motivated applications of social network modeling, where we must (a) allow S2 to have negative cigenvalues, (b) require that Z has exactly K
columns (K~ rank( and (c) have factorization of S Z ZP'' instead of 52 ZZ' (we will soon see that both (P, 2) have practical meanings in our setting).
Below, in Section L1 introduce several recent network models. In Section 1.2 we explain why
the NMF problem is important and relevant in social network modeling.
1.1 Several recent rank-K network models, and especially the DCMM model
Consider a symmetric connected network with n nodes and let A be the adjacency matrix, where A(i.5) = if there is an edge connecting nodes and j and A(i.j) = O otherwise. As convention, we do not allow self edges, so all diagonal entries of A are O. We assume the network has K perceivable communities (communities are scientifically meaningful but mathematically hard to define; intuitively, they are clusters of nodes that have more edges "within" than "across" [12] 30)): C2,C, C,....., ,.2....,C.:: CK.
many network models, we assume that the upper triangular entries of A are independent Bernoulli random variables, and that there is an
non-negative matrix s such that ((i.j) = ((A(i)) j) = 1) for all S # j S n. Let (iag(1)) E R be the diagonal matrix where the i-th diagonal entry is ((i, 2) and let W E IR"." be the matrix where W (ii.j) = A(i, 2(i, j) if * j and (i. = otherwise. The matrix W is known as the generalized Wigner matrix. With these notations,
A = diag(?) + W.
(1.3)
We call Ω the Bernoulli probability matrix. Frequently, we assume r model for Q:
Ω is an irreducible non-negative matrix where the rank is K.
(1.4)
Note that K is the number of communities and has important practical meanings. Also, irreuuibiliity is natural assumption as we assume the network is connected (otherwise, we can study each connected component of the network separately). Below are some examples of rank-K models.
Example 1 (RDPG Model). In a Random Dot Product Graph (RDPG) model 288) we fix a K-
dimensional distribution F", generate yi iid F. and let Mii,j = (yis VÚ) (inner product), 1 S i,j S n. If we write Y = [V1, 3/2, .... Ynl' (which is an n x K matrix), then S = YY'. The model is well- known in network and graph modeling. However, noteworthy issue that, the matrix 12 defined in this way is always positive semi- cemineefnite. This makes the model relatively restrictive (e.g., (25
Example (GRDPG Model). To address the issue above, Rubin-Delanchy el al 25 proposed the generalized RDPG (GRDPG). Fix K and 0 < m < K. Let Jk.m = (faag(1,1 1, 1,.... be the K K diagonal matrix where the first (K m) diagonal entries are 1 and the remaining diagonal entries are 1. With a similar Y matrix as in RDPG, GRDPG assumes Q = YJKmm Y'. An Ω defined in this way has negative eigenvalues, but we have to choose (K,), carefully to make sure that Ω is non-negative; this problem is not immediately clear.
1)
Example 3. It was argued (e.g., [4) that the Bernoulli probability matrix Ω in a graphon model can be appo-appro by a low-rank matrix provided with some regularity conditions.
In all these examples above, the parameters do not have explicit practical meanings (at least not directly or not sufficiently), so a real application example, it remains unclear how to interpret the estimates of these parameters. Therefore, it is desirable to have models where the parameters have more explicit meanings in practice and so are easier to interpret.
The Degree-Corrected Meeee-sembership (DCMM) model is one of such models. Proposed by 15] (see also 22 the model is motivated by the observation that natural networks usually have severe degree heterogeneity and
To accommodate both features, for each node i, 1 s S n, we use a (strictly positive) parameter 9: to model the degree heterogeneity and weight vector πV E IR K to model the memberships, where ny (k) weight node i puts in Ck 1 < & < K. We call node pure if πं is degenerate (i.e., only one entry is nonzero) and mixed otherwise. We also model the community structure by symmetric and non-negative matrix P E KR
P(k, E) = bascline probability where node in Cj and node in Ct have edge, 1 k, k, K.

---

DCMM assumes that for all 1 S 1,j S 2((,)) = 7. If we let 0 = (01..... 0n), II K Tnl' and è be the n diagonal matrix where O(i, 8,. 1 s S n. then we have
= O11PIIO,
(1.5)
Conventionally, assume ra) rank K, DCMM is also rank- K model.
Remark 1. The DCMM model can viewed as the extension of several models, including the classical block model. In fact, (a) DCMM reduces to Degree-Correctee Block Model (DCBM) [201 if all nodes are pure, (b) DCMM reduces to the Tixed-Memberstie 2 24 if all 0; are equal, and (c) DCMM reduces to the classical Stochastic Block Model (SBM) if all nodes are pure and all 0, are equal (as above, node is pure if TT is degenerate).
Stochastic Block Model (MMSBM)
1.2 When is rank-K network model also a DCMM model?
A DCMM model is a rank-K model, but compared to other rank- K models, all parameter matrices (9, II, P) in the DCMM model have practical meanings and are easy to interpret. These make the
DCMM model especially appealing in practice, and motivate the following problem:
When is a rank- K network model also a DCMM model?
(1.6)
To explain why this is important, we use the dynamic co-citation networks in [[]] (see also [10] as an example. The paper presented 21 co-citation networks for the same set of nodes (i.e., authors) in statistics, each for a different time window. We are interested in (a) how many research areas in statisties, (b) what are baseline citation exchanges between different research areas, and (c) how the research interests of individual authors evolve over time. Here, co-citation network is symmetrized citation network where each node is an author, and two nodes have an edge if they have been co-cited for at least N times (for N they picked) in the corresponding time window. The paper suggested that there are primary research areas in statistics (which was interpreted as "Bayes", "Biostatistics", and "Non-pare parametrie") and handful of sub-areas, and that it is convenient model each co- co-citation network by a DCMM model with K = 3. In detail, for each author and time window I, S S n, 1 S l S T, they used a K K matrix p(() to model the baseline citation exchanges between the primary research areas, positive number 0se to model the relative influence (in citations) of author i, and a weight vector Ret to model the research interest of author i. If we similarly let (t)) = diag(01e; B2., .2,,...,,.... One)
and IT(t) = [Ti+ T2t...... Knel', then the Bernoulli probability matrix of the DCMM model at time t is ( = ((t) (I
Using the DCMM model, they discovered a research triangle of statisticians (reminiscent of Efron's 's triangle for statistical philosophy (6), and used it to visualize the trajectories of research interests of a handful of individual authors.
Imagine that, if we use differrnt rank-K model (e.g., GRDPG) to model these networks, say, with 200 = (()))(())))))))) (y for some matrices citation exchanges, research interests and relative influence of individual authors. This explains why (166) is of interest: given rank-K K network model, we wish know when we can rewrite it as DCMM model, and so we can enjoy the properties and interpretability of the DCMM model.
It is unclear how to relate ( baseline
We now come back to (L.6). Seemingly, NMF is to key answer this question. Consider positive matrix with rank K and suppose that has an NMF as in (I.I) for two non-negative matrices Z E lR,.K and P E J.K.K. Ω ZPZ'. Write Z = [21, 22.... .2...,,,,)) 2nl so 2 is the i- th row. Without loss of generality, assume all 2; are nonzero vectors. Let O(i, = || and T; 2/11eil1.
< i < n. It is seen that O i) > 0, that each म; is weight vector, and that Q= ZPZ' = θHРI''.. Therefore, we can always rewrite rank- K model as a DCMM model Ω has an NMF in (I.I). This explains our motivation underline the NMF problem (I.I).
Note that to answer the question in [I. a study on the NMF problem in (.2) would be not be relevant. For example, in DCMM model, K is the number of communities, so NMF in (1.2
with an N K would not be useful. For this reason, we have to focus on the NMF problem in
1.3 Results and contributions
Write Ω YJ Y' as in Example 2, where JKm diag(1,.... ..... -1...... -1. is K x K diagonal matrix and Y [y1, V2....,..................
yyl'' I' IR",K, Let ds be the k-th eigenvalue of Ω and let Ex
3

---

be the corresponding eigenvector. For 1 S i S n, define r; E R RK by (k) = fx+1 (1). 1 S k < K For any unit-norm vector yo R let c(yn) = (isii)) (1) yo) //:::l): }. In Section 2 we show that the NMF problem for Ω is solvable if m & K/2 and c(yo) 2 -/K for some yo: let us call this the main condition. We show that, in order for the NMF problem to be solvable, the constant v1- 1/K can not be further reduced. Therefore, in this sense, our results are sharp. Using this, we deduce several other results. Especially, we show that the NMF problem is solvable for Q if =k=1 ([)++1l (R)) < //1/(KK 1) for all I <i S n. We also extend our results to the case of m > K/2, and explain why we need a different proof in this case.
In Section we apply our results on NMF to network modeling. We argue that for parameters in the most interesting range, we have (A) all ||r:]| are bounded, and (B) max254-5 {Ae/Ail] - 0, and so the condition just mentioned holds. This implies that can alway rewrite a rank-K network model as a DCMM model if the parameters are in the most interesting range. We also discuss how to check the main condition in practice where Q2 is unknown. We tackle this by proposing an approach to estimating Q, and support our results by some real networks.
Our contributions are two fold. First, we develop several new results on symmetric NMF (a problem of interest many applications [5]). Existing works on symmetric NMF have been focused on the case of m = 0 (so ? is positive semi-definite; m is the number of negative eigenvalues of Ω?). In this case, the best result is seen to be 226 Theorem 3.1.7, which can be viewed as a special case of our results; see Remark 2. This suggests that our results are sharp, for they are hard to improve even in the special case of m O. Note that our case allows m to take any possible values, so it is clearly harder to study. For example, to show the results for the case of m 0, it suffices if we can find K X K orthogonal matrix Q such that YQ' is non-negative, since J is the identity matrix in this case. For our case, we must find Q such that YQ' and QJk.m m Q' are simultaneously non-negative. Clearly, this requires new ideas. We tackle this by constructing a special class of matrices Q; see our proofs for details. Our approach is quite different from that of [26 Theorem 3.137] and is new
Second, we shed interesting new light on different rank- K network models. In the literature, it not unusual that many similar models are proposed for the same type of data sets. But in the end, we need to understand the advantages and disadvantages of different models, and pick the most suitable one. Our study recommends DCMM model, for it offers desired practical interpretability which other rank-K models do not have, and points out that a general rank- K model is also a DCMM model if the parameters are in the most interesting range. Such findings are valuable for they can help us identify the most suitable models in real applications.
Notations. We denote 61, e2...., CK by the standard basis vectors of K K-dimensional Euclidean space and en = (e1 + e2 +... + ex). ). For any > and vector x. ||>|| denotes the no-m (when q = 2, we drop the subscript and write ||=|]). For any two vectors x and y of the same dimension, (zz, y) denotes the inner product. For a vector E R", diag(a) denotes the n X n diagonal matrix where the i-th diagonal entry is ag 1 S S n. When is an n n matrix, diag({?) denotes the n X n diagonal matrix where the i-th entry is S2 i), 1 < i S n.
2 Main results on NMF
This section presents our results on NMF, Results on network modeling are in Section 3 Consider an n X n irreducible non-negative matrix Ω with rank K, where n is usually much larger than K. By Perron's theorem (9, least one eigenvalue of Z is positive. Fix m K- and suppose f2 has m negative eigenvalues. Let Jk.m = diag(1...... -1. -1) be the K x K diagonal matrix as in Example 2. By basic algebra, we can always write
= YJJ.m'''
for a full rank matrix Y e R...K
(2.7)
We can also show (e.g., an exercise with the Weyl's theorem (9) that for any matrix as in 2.. the numbers of positive and negative eigenvalues are (K m) and m. respectively. Write
Y [/1 1/2 ywJ',
so that y/ is row of Y. 1 S i n.
(2.8)
Define the subset of K -ddimensional vectors that live on the unit-sphere where the last mn entries are 0:
Sk.m= {2= (a (s......... .xk) R ||ا||| = 1, 1,zk-m+t = ... = IK = 0}.
When m = 0, Sm is the unit sphere of K The following theorem is proved in the supplement.

---

Theorem 2.1 Fix K 2 2. n 2 K. and S m S K/2. Consider the NMF problem
1.7 where
Q = J mn Y' and Y are as in 2.7 Suppose there is a vector yo E Sk.m such that
(/30,:))l/lbe 1/bbal 2 VI-
for all sisn.
(2.9)
There exists a K K orthogonal matrix Q such that both YQ' and QJk.m O are non-negative. As a result, the NMF problem for Q is solvable: Q2 = 7P7' with 7 = =YQ' and P = Q.
We have several comments. First, Theorem 2.1 assumes two conditions: m I K22 and (.9 When K I 2, both conditions hold automatically, so the NMF problem is always solvable in this case; see Section 2.1 As far we know, our proof is different from existing approaches. Second, in Theorem 2.1 we require Yo E Sm- This may seem restrictive, but is not. This is because yo is a vector we choose for our own convenience. In fact, one of the most interesting settings for NMF seems to be that in Section 2.3] where we choose y/o OI,0...., 0)', so the requirement is satisfied automatically, Also, when the last m entries of yo are nonzero but sufficiently small, Theorem 2.1 continues to hold if we modify the term /1 -1-1/Kk slightly. Third, from a practical view point, the condition of m S K/2 is mild: we rarely see rank-K K network model with m > K/2 (note here m can be estimated using the eigenvalues of the adjacency matrix A). For theoretical completeness, the case of m > K/2 is also interesting, but there does not exist an orthogonal matrix Q such that QJ Q' non-negative. This is because for any such Q, tracc (aeccQuJ,mmm Q)) = K 2m O. Therefore, we must find a different way to solve the NMF problem in this case. We discuss this in Section 2.4 Last, an interesting question is whether our idea is extendable to asymmetric NMF or complex NMF [19]. As simple extension to asymmetric NME, consider an n X P positive matrix Ω of rank-K. By SVD, Ω = YZ for an n X K matrix Y and a p x K matrix Z. Let s/. be i-th row of and z/J be the j-th row of Z, respectively. If there is a yo Sk.m such that for all and j. (yv,, bo)) /lb//lllll 2 /1 1/K ||2l||1||| 2 /1 15-1, 1/K, then we can find K x K orthogonal matrix Q which rotates all and [e, /o)l
rows of Y and Z to the first orthant simultaneously. In this case, the asymmetric NMF problem is solvable for Q. For reasons of space, we leave further study along this line to the future.
Our result is sharp for the constant / -- in (2.9) can not be further reduced. While we can show this for general K. we illustrate with the case of K = 2 for instruction purpose. In this case, we can rotate n unit-norm vectors y1, .2.... Vn in R²2 simultaneously to the first orthant and only if there is a unit-norm vector yo such that (3)o 3/)] 2 /I 1/2 (i.e., the angle between them is I I r/4) for all 1 < i < n. See Section 2.1 and Remark 3 for more discussion. Another way to see the sharpness is to consider the case of m 0 (so Q positive semi-definite). In this case, condition 2.9 is hard to improve and is the weakest we have so far in the literature; see Remark 2.
2.1 The case of K =
In this case, the NMF problem is always solvable, as the two conditions of Theorem 2.1 m S K/2 and (2.9). hold automatically. In fact, first, since 5 has at least one positive eigenvalues and K = 2, we have either m
m 1, and so m < K/2. Second, we can always find yo E Sm such that (2.9h is satisfied. In detail, let 0 < 02 < 2 be the angle from e1 (e1 = O)) to ye counterclockwise, and let mmmn and fmaz be the smallest and largest values of all 9g. Now, when m 0, let yo be the unit vector where the angle from e1 to yo is (Omaz + mmmn)) 1/2, counterclockwise, When m = 1, take yo 01. The following theorem is proved in the supplement.
Theorem 2.2 Fix K = 05 m < K - 1, n 2 K, and let yo be as above. In this case, m S K/2 and 2.9 holds for the yo above, so the NMF problem is always solvable for Q
2.2
When yo is scaled weighted average of y:'s
For the yo in (.9). an interesting choice is to let it be proportional to a weighted average of yı 's. Call E R weight vector if all of its entries are non-negative with sum of 1. Recall that Introduce y y(u) E R and g(w) E R." by y = Σn Weyls = Y'u and g(w) = Sww. Since Y is full rank,
Ω Y Y'..Y',. Define a proxy of Ω by Q YY'. Note that ÿ Ω if m
y (())) * 0. Take yo = yy(") /lg/"// Condition 2.9 reduces to
10(")// (1 () 2 1/K,
for all 1 isis n.
(2.10)
5

---

Theorem 2.3 Fix K 2 3. 0 m < K/2, and n 2 K. The NMF problem
1.1 is solvable for S2 if
the last m entries of 7()) are and 2.10 holds.
Theorem 2.3 follows from Theorem 2.1 by direct calculations, so the proof is omitted. We require that the last entries of y ((w) are 0, for need you E Sm in Theorem 2.1 As explained before, this may seem restrictive, but is not, as in the most interesting case to be discussed in Section we
take y = (1, .,,,,....,, 0), so the requirement is satisfied automatically. See details therein.
When m = 0, 52 = S2 and g(w) Qw. In this case, condition 20 reduces to
1 I/v (ww'ww 2 31-11 11-1/K.
(2.11)
We have the following corollary, the proof of which is straightforwards so is omitted.
Corollary 2.1 Fix n 2 K 2 The NMF problem is solvable for Q if m = and 2.11 holds.
(1,,51), 2 V 1/K Remark 2. If we take w n nn--n then 2. 10 reduces to | Rii, i)
with 3 = ,, and Corollary 2.1 reduces to 26 Theorem 3.137], where m = 0 and Ω is positive semi-definite. Our setting is more general as 52 may have m negative eigenvalues for any m S K/2. For the case of m = 0. [26] Theorem 3.137] (see also ( is by far the best results we can have. The book (26) presents several other results on this topic, but they need some conditions which are less intuitive or harder to check. Recall that the constant / - 1/K in (2.9 can not be further reduced. These suggest that Theorem 2.1 is hard to improve and our results are sharp.
Remark 3. (When can we rotate n vectors the first orthant?) As stylized application, con- sider the following problem. Let T2,,,,.... ..,,............................ .n be unit-norm vectors in RK 2 K, and let og (I'1, T2...... ................................ Z..) minigi.jsw [11,, x2))] }- For what values of ox (Z1 22,,22... T2,.... ........,, Fn) can we rotate all n points simultaneously to the first orthant? Let X = [21, ................................ .nnl
and assume X is full rank without loss of generality. The matrix Ω X X' is symmetric and positive semi-definite, Let o = if K that when ag 1 22.... Fn) ag we can rotate all n points to the first orthant. Note that we can not do so if ak (Z), 22,..... xn) < 0.
and o²x / 1/K if K 2 3. Applying Theorem 2.1 with m O, it follows
2.3 When Y is constructed by the spectral decomposition of !
So far, we have tried to keep our results as general as we can, and Y can be any matrix satisfying Q Y JK.m Y'. An interesting special case is when Y constructed using the spectral decomposition of Ω. which we now discuss. For 1 < k < K, let X be the k-th largest eigenvalue of Ω, and let & be the corresponding (unit-norm) eigenvector. In the literature A and & are called the Perron root and Perron vector, respectively, where we can always assume all entries of & are positive since Ω irreducible and non-negative (e.g., (26)). Write = (2..............................
........EE Ex] and define the n x (K 1) so-called matrix of entry-wise ratio R by R(i, k) = (1+)())/E1 < k & K 1, S i n 12 16]. Introduce
D= diia((/A/llMM)))
(kk))
Do = diag(I>)) ..... (ax)),
(2.12)
and write
R= r2, rnn'. == E2 = [yn, y2. "/,...,,,,''
(2.13)
By spectral decomposition, Ω ED1/2JK,, 11/2 = YJK.m Y' Now, in Section 2.2 if we take w = cτ1 where = 1/1 then by basic algebra and definitions, it is seen (w)) = cv /1 and so
Vo e₁ and especially yo E Smn Moreover, ,.!') (i), w/ww c² An and 50 = sDy Combining these, condition (0.10) reduces to
K
r:Dor
(P ( (A))) S |AII((K 1),
for all 1 Si n.
(2.14)
1=1
The following theorem is proved the supplement.
Theorem 2.4 Fix K 3, m < K and n 2 K. The NMF problem 1.1 is solvable if (.114) holds.
Note that as in most works on NMF (e . 26) the main goal to find easy-to-check conditions under which the NMF is solvable. Such conditions sufficient but are not necessary.

---

2.4 The case of m > K/2
So far, we have been focused on the case of m I K/2, which is the case that is most frequently found in real networks. For completeness, we now consider the case where m > K/2. Since S m S K --1, such a case only exists when K 2 3. In Theorem2.1] we show that when m I K/2. we can find an orthogonal matrix Q such that QJ Q' is non-negative. When m > K/2, we can not do this, as for any such Q, trace trace(QJK..n (QJK.mQ = (K' 2m) < 0. Therefore, we need a new approach. A convenient approach is to redefine Jm.m where we select subset of the positive diagonal entries of Jmm and add a positive number for each of them. Success has been shown in a related setting (e.g.. BD. Using such a trick, we can extend all our main results to the case of > K/2. For reasons of space, we only consider an extension of Theorem 2.4 as the claim of the theorem is probably the most explicit. Also for reasons of space, we only consider the case where we add number to the first diagonal entry of J JK. Note that the idea is readily extendable to more general cases.
Let Q be the set of all orthogonal matrices where the first column is K-1//211, (1.1,...,,1) ,, Fix where :(K-m)) and Q(m are
1 S m S K 1. For any Q E 2, write Q = =Q(K=m),Q') the sub-matrix of Q consisting the first (K m) columns and the other columns, respectively. Introduce a constant by (m = 1 + K inf maxisujs (i. (i. H = (0(mm) (Q( - Tx [(x: K K identity matrix). Theorem 2.5 extends Theorem 2.4 and is proved in the supplement.
Theorem 2.5 Fix K 2 3, 0 < m S (K 1),, and n 2 K. We have am = 1 if m < K/2 and Om = (K 1) if m K -1
1. Also, the NMF problem is solvable for if r =
K-1 1e+ (k)) < 1/[am (K - 1)] for all 1 sis sin. n.
When m S K/2, a... 1. In this case, the claim here is the same as that in Theorem 2.4
Remark When the NMF problem for Q is solvable, the solution is usually not unique without a proper regularity condition (e.g.. (5). In our setting, once we can write s = OITPI'' for some non-negative matrices (θ, IT, P) as in (1.5), the factorization is unique if (a) for each S < K, there is at least one such that ,,- Cgg, where eq is the k-th standard Fuclidean basis vector of R.K
and (b) all diagonal entries of P are 1 (see [15 16
for a proof).
Remark 5. When condition (.9) of Theorem 2.1 holds for some vectors you how to find such a go and the orthogonal matrix Q in Theorem 2.1 numerically? This is an interesting question and we discuss it in Section F of the supplement.
3 When is a rank- K network model also a DCMM model
So far, we focus on general NMF settings where we show that the NMF problem 1.1 solvable when, for example, (2.14) holds. We now apply the results to networks and study when we can rewrite a rank-K network model as a DCMM model. Network analysis (e.g., community detection, membership estimation, link prediction) is a well-studied area, where we have lot of knowledge on what is the regime of major interest and what conditions are reasonable [16 15 18 29,. In fact, in network analysis, we usually use an asymptotic framework where - co, K is fixed, and other parameters may vary with n, where it is quite acceptable to assume
(A) all |r:|]| are bounded
and
(B) max2gagk (AtAal) + 0:
the notations are the same as those in Theorem 2.4 In fact, (A)-(B) model the most interesting regime
in network analysis. In Theorem 2.4 the main condition (e.g.. 2. 14) is r S |Ail/(K - 1) for all < iis < n. Once (A)-(B) hold, Du 0 and (..4) holds, we can always rewrite rank-K K network model as DCMM model when (A)-(B) hold.
The remaining question is then, why (A)-(B) are reasonable assumptions in network analysis, and why they model the most interesting regime in network analysis. We now explain these in details.
Let Q be the Bernoulli probability matrix as in 1.3). Suppose S2 = YPY', where Y E R and is full rank, P E TR. K. and (Y, P) are not necessarily non-negative. Denote G Y'Y. Note that G is a K x K symmetric and positive definite matrix. Let G1/2 be the (unique) square root of Y'Y. We usually assume Y is balanced in that (a) the (2-norm of all K columns are in the same order, and (b) no severe linearity between the K columns 15 18] As a result, all eigenvalues of are at the same
order. By basic algebra, there is a K x K orthogonal matrix Q such that = [E, E2........ {x] YB,
7

---

where B = G- Write B = [b1. be..... bx] and let 0 - a; < 2T be the angle between b and
y: (counterclockwise). Let M (92) max [1/] cos (a:)] and define matrix V R Kg by
1 1 S K, 1 S 1. Write V = [U1, U2,..... "x] so o/ is row-k of V, denotes the k-th largest eigenvalue; to be consistent with earlier notations, we simply write A (22) as AR. Lemma 3.1 is proved in the supplement.
Vi,, k) bx+1 (1))
(3.15)
< k S K. For any symmetrical matrix P. {x.
Lemma 3.1 We have B diag(bi [ KK VJ. P Bdiag(>1...... B by is an eigenvec- for of PG, and P(k, k) = (() + di... Ax), S k S K. Moreover, if as n 7 00, (G) S Go)R(G) for constant co > O, then condition (B) holds if and only if (ORNSSSSR((MMM(PPAMMPPP
+ O, and maxiin)) Ullil S (M).
is seen that conditions (A)-(B) hold if M(2) S C and max ( (PP)A)))())))))) first one is mild: it only requires that no yo is nearly orthogonal to bj. To boil these conditions down to a more explicit and vivid form, we consider the DCMM model. It is fine to consider the DCMM model here for (a) we only use the model to explain why conditions (A)-(B) are reasonable, and (b) the argument below is extendable beyond the DCMM model. In the DCMM model, Q = IIIPII' Therefore, can write Ω Y PY" if we let Y = III, where we note that (Y, P) are non-negative. Recall that G = Y'Y (a positive definite K x K matrix). Lemma 3.2 is proved in the supplement.
0. The
Lemma 3.2 If (Y, P) are non-negative, then first, PG is an irreducible non-negative matrix and by is the Perron vector, so all entries of by are strictly positive. Second, all rows ofr; r. lives with simplex with un, 02,..., .UK being the vertices, maxiin [[]r=ll] S max K) [[lvel]]- Last, (G) S codx (G), then max [llra]]3 S CM) S C C'maxisss' (alabl/l
Now, first, in a DCMM model, the matrix P(k, E) measures the baseline probability where there is an edge between a node in community k and node in community L. Therefore, the most difficult or most interesting case is where all P(k, E) have similar values. In this case, P close to rank-1, or in other words, max K A1 (P)/11 (P)I} + 0, and so max k < /1al - O. See for example [LS] 18] where it was further pointed out that the most difficult case for network analysis )k { < Ln Vd1 for multi-log(n)
factor L,, Therefore, condition (A) models the most difficult case of network analysis and so is of major interest. Moreover, by Lemma 3.2 max(i y (Irrsl]) < C if all entries of dj are the same order. This is only a mild condition for b is the Perron vector of PG. Last, by Lemma 3.2 we also have max {||a=l]> < C if
is when
we alternatively assume m [1l S C. Recall that = G-1/2Q = [6,, b2.,b..... bg..b...0.0. bk] and t/i v/, .,,,,,,, U'K are rows of V formed by dividing 62. bz..... bx by bj entry-wise, where bj is the Perron vector. Since G is positive definite where all eigenvalues are at the same order, Q is orthogonal, and V is properly scaled (and all of them have small-sizes), is only a mild condition to assume max [ [|]u~]]] < C. These explain why conditions (A)-(B) are mild condition and they model the most challenging regime for network analysis.
4 Real data examples, and especially how to check condition (2.14)
Let a; = (rdAAiD,DDrra 1 S i S n. Condition 2.144 can be rewritten as a, S 1/(K - 1). for all i S In applications, Ω unknown, so it is unclear how to obtain a, A straightforward approach is to estimate a; with the eigenvalues and eigenvectors of the adjacency matrix A, but the estimates may be too noisy. We propose the following approach, which is inspired by Lemmas 3.1 3.2 and the recent Mixed-SCORE approach [16]. Let (Y,V) ) be as above. Mixed-SCORE suggests an interesting idea for estimating V and (a normalized version of) Y. denoted by II; see details therein. Let ÅS be the le-th eigenvalue of A and let & be the corresponding eigenvector. Write E = [6,, .........r, Exl = [21, $2.... 2nl' so 2/ is row-i E. Our approach runs as follows.
Apply Mixed-SCORE and obtain an estimate (V, ii) for (V, Let 6r be row & or V and let ii be row i of fi. S S K, iissn
Estimate by by b2 where b, (k)
1u + Ek diag Ak)Or] 112 Let
B = diag(E;) [1,, Vj. and estimate P by P = Bdiag(A) A2, , B'. Let g =
Ax)
(| R1 R 1 S < n, and let Y 101, .2..... Vnr''
8

---

Let fi be the k-th eigenvalue of the matrix Ωi "PÝ" and let îJ be the corresponding eigenvector. In the definition of a, (see above and (2.14). replace (Ax. {x) by (pk, f))) and denote the resultant quantity d;, I S These are our estimates for dg.
The approach can be shown to be consistent for Ω under some regularity conditions. We skip the study for it is beyond the scope of this paper. In this algorithm, (Y, P)) are not automatically non-negative, and check whether NMF solvable for Q we can check
à; S 1//KK - 1),
for all 1 ssisn.
(4.16)
Remark 6. Condition (2.14) of Theorem 2.4 2.45 is only sufficient condition for NMF; they not necessary conditions. It could happen that an NMF is solvable for an Ω but (2.14) does not hold.
We now consider some real examples. The weblog is well-known data set 22 where with some light preprocessing, the network has 1, 222 node (each a blog) and 16, 714 edges (each a two-way hyperlink). The network has two communities: democratic and republican. For this data set, rank-2 model appropriate, so we have (n, K) = (1, 1222 2) (e.g., [30 I2 18). Let Ω be the Bernoulli probability matrix as in (I3) By Theorem 2.2 when K 2, we can always decompose Ω as non-negative matrix P. Now, by
YPY" for non-negative n x 2 matrix and paragraph right above Remark 1, we rewrite fi АIIIIO in [.3). Ω satisfies DCMM model. Same claim can be drawn for the karate data set 30 12). where we similarly have K = 2.
As another example, we consider the UKFaculty network (e.g., see [7 Table IJ). It is reasonable model the network with rank-K K model with (n, K) (81,3) and m I K/2. By Theorem 2.4 the model can be rewritten as DCMM model if 46 holds. Following the discussion above, first obtain estimate Ω for Ω. We then use Ω to obtain à; and check if (4.16) holds. The results are in Figure (left) below, where the maximum of â 02,.... ān is slightly smaller than 0.5 (1/(K 1) 0.5 K 3), suggesting that (4.16) holds. Moreover, let Ae be the k-th eigenvector of á and let îię be the corresponding eigenvector. Let D diag(A1..... ,x) .m Y'. Let Q be the 3 x 3 matrix where the three rows are (1/v3, 1/ /6, 1/v2), (1/ (1/V3.11 1/v6, - 1/ and (1/V3, -2/V6, 0), respectively. Define 2 YQ'. It is seen Ω JK Y ZmQ Q')Z'', where QJK. Q' is seen to be non-negative. Moreover, for < S n, let 2; the smallest entry in row-i of Z. Figure (right) plots the histogram for { The results suggest that all è; are non-negative, so the matrix YQ' is non-negative. Therefore, 5 has an NFM by Ω Z(QJK,n 2' These suggest that for the UKFaculty data set, (4. holds and is reasonable to model the UKFaculty with DCMM model. In summary, in many recent works on network analysis, we frequently assume that a DCMM model holds for the settings at hand, but we rarely checked if such an assumption is valid. Our NMF results provide approach to checking whether the network satisfies DCMM model.
and y = [fn...., iiK] 11/2_ We have Ω = Y Jk.m
0.0
0.5
Figure 1: Histograms of {ā, (left) and (2. __ (right). The results suggest that all â are smaller than 0.5 (note that 1/(K - 1) 55 K 3) condition (4.16) is satisfied, and that all é, non-negative so the matrix 2 is non-negative. See above for definitions of à; and E,

---

5 Discussion
We derive sharp NMF result and apply it to network modeling. Both NMF and network analysis are important areas in machine learning, with applications in image processing, social media, NLP, and cancer study [5 23 21. In comparison, NMF is more theoretically oriented and network analysis is more application oriented. Our paper makes interesting connection of the two areas. On one hand, we find a new application of NMF theory. This may open the door for a line of research where we find new applications of NMF in areas such text learning [2]] and tensor analysis [14]. On the other hand, we gain valuable insight on what are the most suitable network models in applications. This is crucial, for suitable model is the starting point for methods and theory. Our study may help researchers identify the right network models and so can channel their strengths to the right direction. Our work may also help develop new methods. For example, compared to the general rank-K model, the DCMM model has more structures which we can exploit (see [16] [8] where they discovered a simplex structure in the spectral domain, using some specific features which the DCMM model has but a general rank-K model does not). Our approach is useful for it ensures us that in certain settings, we can use a more specific model and exploit the structures the model provides.
Another point is that, existing NMF theory usually requires some crucial conditions. However, whether such conditions
reasonable in real applications remains unclear, especially when the conditions are on matrices that are not directly observable. In Section 3 4
we tackle this problem reasonable in network analysis and (b) new ideas for checking the NMF conditions in real applications when the NMF conditions are matrices that not directly observable. We hope our efforts many spark some new research along this line.
by providing (a) detailed explanation for why our NMF assumptions
Acknowledgements. The research was supported in part by NSF Grant would like to thank Naomi Shaked-Monderen Helena Smigoe, and Changqing Xu for helpful pointers, and Zheng Tracy Ke and Jiajun Tang for very helpful comments.
The author
References
[1] Edoardo M. Airoldi, David M. Blei, Stephen E, Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodels. J. Mach. Learn. Res., 9:1981-2014, 2008.
[2] Animashree Anandkuma, Rong Ge, Daniel Hsu, and Sham Kakade. A tensor approach to learning mixed membership community labels. J. Mach. Learn. Res., 15(1), 2014.
[3] Damjana Kokol Bukovsek and Smigoc Helena. Symmetric non-negative matrix trifactorization. arXiv.2106. 20w.2100..1437v2. 2022.
[4] Sourav Chatterjee. Matrix estimation by universal singular value thresholding. Ann. Statist., 43(1):177-214, 2015.
[5] David L. Donoho and Victoria Stodden. When does non-negative matrix factorization give correct decomposition into parts? Advances in Neural Information Processing Systems 16, 2003.
[6] Bradley Efron. Fisher in the 21 century. Statist. Sci., 13(2):95-114, 1998.
[7] Zhaoshui He, Shengli Xie, Rafal Zdunek, Guoxu Zhou, and Andrzej Cichocki. Symmetric nonnegative matrix factorization: Algorithms and applications to probabilistic clustering. IEFE Transactions on Neural Networks, 2212):2117-2133 2011.
[8] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Soc. Netw, 5(2):109 137, 1983.
[9] Roger A. Horn and Charles Johnson. Matrix Analysis. Cambridge University Press, 2nd edition, 2013.
[10] Pengsheng Ji and Jiashun Jin. Coauthorship and citation networks for statisticians (with discussions). Ann. Appl. Stat., (0(4):177--188) 2016.
[11] Pengsheng Ji, Jiashun Jin, Zheng Tracy Ke, and Wanshan Li. Co-citation and co-authorship networks for statisticians (with discussions). J. Bus. Econ. Statist., 40(2)469 2022.
[12] Jiashun Jin. Fast community detection by SCORE. Ann. Statist., 43(1):57-89, 2015.
10

---

[13] Jiashun Jin and Zheng Tracy Ke. The score normalization. especially for heterogeneous network and text data, Stat, apper.
[14] Jiashun Jin, Zheng Tracy Ke, and Jiajun Liang. Sharp impossibillty results for hypergraph testing. Advances in Neural Information Processing Systems 34, 2021.
[15] Jiashun Jin, Zheng Tracy Ke, and S. Luo. Optimal adaptivity of signed-polygon statistics for network testing. Ann. Statist., 4966)33408-3333, 2021.
[16] Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Estimating network memberships by simplex vertex hunting, arXiv: 07852 2017.
[17] Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Improvements score: especially for weak signals. Sankhya pages 1-36, 2021.
[18] Jiashun Jin, Zheng Tracy Ke, Shengming Luo, and Minzhe Wang. Optimal estimation of the number of network communities. Amer. Statist. Assoc., pages 1-16, 2022.
[19] H. Kameoka, N. Ono, K. Kashino, and S. Sagayama. Complex nmf: new sparse representation for acoustic signals. Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019.
[20] Brian Karrer and Mark E. Newman. Stochastic blockmodels and community structure in networks. Phys. Rev. E, 83:016107, 2011.
[21] Zheng Tracy Ke and Minzhe Wang. Using svd for topie modeling. J. Amer: Statist, Assoc., to appear.
[22] Adamic L.. and Glance N. The political blogosphere and the 2004 election: Divided htey blog. Proceeding of the 3rd International Workshop on Link Discovery, pages 36-43, 2005.
[23] Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(67555)788-791 1999.
[24] X Mao, Sarkar P. and D Chakrabarti. On mixed memberships and symmetric nonnegative matrix factoriza- tions. International conference on machine learning, pages 2324-2333, 2017.
[25] Patrick Kubin-Delande Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. arXiv. 770.00560,, 2021.
[26] Naomi Shaked-Mondente and Abraham Berman. Composite and completely positive matrices. World Scientific, 2021.
[27] Wasin So and Changqing Xu. When does ep-rank equal rank? arXiv. 13X8x.338..319 2013.
[28] S. Young and E. Scheinerman. Random dot product graph models for social networks. Proceddings of the 5th international conference algorithms and models for web-graph, pages 138 149, 2007.
[29] Yuan Zhang, Elizaveta Levina, and Ji Zhu, Detecting overlapping communities in networks using spectral methods. SIAM J. Math. Data Sci., 2(2):265-22)) 283, 2020.
[30] Yunpeng Zhao, Elizaveta Levina, and Ji Zhu. Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist,, 40(4):2266 2000222666222,,,,2.2 2012.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...

---

(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or URL)? [No] The data
well- (h) Did you specify all the training details (e.g.. data splits, hyper-parameters, how they chosen)? [Yes]
known public data sets. The algorithm details are given Section 4.
Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type resources used (e.g., type GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g.. code, data, models) curating/releasing assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The data sets we use are well-know public data sets.
(h) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're us-
ing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "kQPkeApL8ek", "reviewer": "Reviewer_61UN", "summary": "The paper deals with the problem of symmetric non-negative matrix factorization (NMF) for a low-rank matrix, when some of the eigenvalues of the matrix are negative. The paper provides conditions under which a symmetric NMF solution exists for a matrix of rank K with negative eigenvalues. The main theoretical results are divided into two main theorems, one for m<K/2 and another for general K. The paper also provides an algorithm for symmetric NMF for degree-corrected mixed-membership block model (DCMM).", "questions": "Suggestion:\n1. Regarding section 4, it would be better to either put in Supplementary or give the theoretical support behind the estimated conditions.", "limitations": "None noted.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The theoretical results (Theorem 2.1-2.5) on the conditions under which a symmetric NMF solution exists for a matrix of rank K with negative eigenvalues are the main strengths of the paper, as the results need some technical innovation.\nWeakness:\n1. The algorithm of NMF for DCMM is provided a bit lightly and without theoretical support, thus section 4 becomes quite antithetical to the tone of the rest of the paper.\n2. The paper also misses some relevant references, like,\n(i) Anandkumar, Animashree, Ge, Rong, Hsu, Daniel J, and Kakade, Sham M. A tensor approach to learning mixed membership community models. Journal of Machine Learning Research, 15(1):2239–2312, 2014.\n(ii) Mao, X., Sarkar, P. and Chakrabarti, D., 2017, July. On mixed memberships and symmetric nonnegative matrix factorizations. In International Conference on Machine Learning (pp. 2324-2333). PMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dTOCN0eFmHP", "reviewer": "Reviewer_h5Vj", "summary": "This paper considers a particular case of the NMF problem, along with its application to network modelling.\nThe main contributions of the paper is two-fold. On one hand, the authors put forth several new results on the symmetric case of the NMF problem, further generalizing previous lines of work that considered special cases of the current formulation from the paper. On the other hand, as a secondary contribution, the authors provide a both quantitative and qualitative discussion on use-cases of different rank-K network models.\n", "questions": "Perhaps not a good idea to use acronyms in the abstract without first explaining them - most readers of the abstract would not be familiar with DCMM, so a brief comment would be appropriate.\n\nWhat about the asymetric case? Can a brief comment be made on it, in light of the results in this paper?\n\nCould clarify what are “pure” nodes in Remark 1, line 82 - as it might not be clear to everyone outside of the SBM community.\n\nWhat about extension to a directed stochastic block model? (say, where the input adjacency matrix is a skew symmetric matrix). And somewhat related to this, what about the complex NMF?\n\nWhy exactly is the case m < K/2 - “probably the most interesting case in practice”?\n\nThe notation J_{K,m} is a bit cumbersome to follow at places, perhaps a notation can be used without the use of subscripts throughout, to improve readability. \n\nIn Section 3, the authors repeatedly refer to “network analysis” applications as if it was a particular problem/task - but it should be made clear at the beginning what is the exact problem to be adressed. \n\nAre there any implications of the results concerning the ability to derive guarantees of SBM/community detection models in the very sparse regime? (one where the edge density in the graph is required to be above (log n) / n and extra effort is required for regularize appropriately before procedding with a spectral approach).\n\nThe authors could comment more on the converse of Thm 2.4 when first mentioned. \n\nThe Figure in page 9 should have a bare minimum to axis labeling and sub/captions. \n\nSection 4 could make it clear what type of insights one can obtain with the NMF-based approach which perhaps it cannot otherwise. \n\n\nTypos: \n314: all rows of r_i lives with \n357 (n,K) = (1,222, 2) - confusing at first ", "limitations": "none", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is fairly original in its inception, and provides a generation of previous results, with previous results being recovered from the current formulation. It provided a very good motivation for why one might care to consider an NMF approach to analyze network problems. The paper is quite dense, and a bit difficult to follow at places, also due to several omitted proofs and results called upon from other works, and not always with enough context. The authors could consider improving this aspect. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "80roWzmJ6S5", "reviewer": "Reviewer_1VWq", "summary": "In this paper, the authors discuss when a square symmetric non-negative matrix with $m$ negative eigenvalues allows a non-negative factorization of the form $ZPZ'$. The authors' main result is Theorem 2.1 where they show a set of sufficient conditions under which the NMF problem is solvable. The authors also extend the results for some special cases.  ", "questions": "1) Here, the paper discusses the solvability of the NMF problem. However, of equal importance is the question of when the solution is unique and can be recovered by an algorithm. The paper does not answer these questions for problem 1.1 when the problem is known to be solvable.\n\n2) How did J_{k,m} still come up in the spectral decomposition of \\Omega? \\lambda and \\Zeta are eigenvalues and eigenvectors of the symmetric matrix \\Omega; so \\Omega should just be \\Zeta D\\Zeta' , right?\n\nMinor:\n\n1) Why use such an uncommon notation for the inner product that is so confusing?\n2) How is the matrix of entry-wise ratio relevant (L246) and what do its entries correspond to? Also, what is R in 2.13?\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and also provides nice examples to motivate the problem. However, I feel that there are several questions that are not answered properly and are mentioned below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept