Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers a particular case of the NMF problem, along with its application to network modelling.
The 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.

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

What about the asymetric case? Can a brief comment be made on it, in light of the results in this paper?

Could clarify what are “pure” nodes in Remark 1, line 82 - as it might not be clear to everyone outside of the SBM community.

What 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?

Why exactly is the case m < K/2 - “probably the most interesting case in practice”?

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

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

Are 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).

The authors could comment more on the converse of Thm 2.4 when first mentioned. 

The Figure in page 9 should have a bare minimum to axis labeling and sub/captions. 

Section 4 could make it clear what type of insights one can obtain with the NMF-based approach which perhaps it cannot otherwise. 


Typos: 
314: all rows of r_i lives with 
357 (n,K) = (1,222, 2) - confusing at first 
limitations: none
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).
strengths_and_weaknesses: Strength:
1. 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.
Weakness:
1. 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.
2. The paper also misses some relevant references, like,
(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.
(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.
questions: Suggestion:
1. Regarding section 4, it would be better to either put in Supplementary or give the theoretical support behind the estimated conditions.
limitations: None noted.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.  
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. 
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.

2) 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?

Minor:

1) Why use such an uncommon notation for the inner product that is so confusing?
2) How is the matrix of entry-wise ratio relevant (L246) and what do its entries correspond to? Also, what is R in 2.13?

limitations: Yes
review_title: null

Meta-review: metareview: This was a borderline paper, which fell just above the bar for acceptance. The reviewers felt the work was interesting and original, although perhaps the problem studied is a bit niche for NeurIPS.
confidence: Less certain
Decision: Accept