Sharp results for NIEP and NMF

Response to your main point. We thank you for a very positive feedback for our paper. We are especially glad that you think we have made a significant advancement for the NIEP problem, particularly in challenging cases where the size of the matrix is large. You have raised the following main point.

• I apologize for my limited familiarity with the solvability of the NIEP and NMF problems. I have a straightforward question: Based on my understanding of Schur decomposition, it seems that a nonnegative matrix with a given spectrum can be expressed as $A = U (\\Lambda + V) U'$, where $U$ is orthogonal, and $V$ is upper triangular. If this is the case, does the solvability of the nonlinear system $U (\\Lambda + V) U' \\geq 0$ offer a potential approach to address the NIEP problem from an optimization perspective?

Here is our response. Yes, you are right, but this is a non-convex problem: the set of $K \times K$ orthogonal matrices (which is called the Stiefel manifold in the literature) is non-convex, and the optimization problem is also non-convex, so computationally, this is a challenging problem. For example, we may put an $\\epsilon$-net on the Stiefel manifold (so that for any point on the Stiefel manifold, there is a point in the net within a distance of $\\epsilon$) and only check your inequality when $U$ is a net-point. However, such an $\\epsilon$-net will have at least $C(1/\\epsilon)^{O(K^2)}$ points, so this approach is computationally infeasible for relatively large $K$.

Response to your main points. Thanks for your valuable comments. You have raised two major points.

• What is the connection between the NMF problem and the NIEP problem?
• What is the result that this paper shows and what are already known results?

Response to your main point 1. Thanks for your valuable comments. To clarify, the whole section of Section 1.1 is for explaining the relationship between NMF and NIEP. In detail, if the NIEP is solvable for $(K, m)$, then the NMF is solvable if Condition (A) is satisfied with $a \geq a_{K, m}$, and Condition (A) cannot be further relaxed in the sense that $a_{K, m}$ is the smallest possible value of $a$ there. When the NIEP is not solvable, then the NMF is solvable if Condition (A) is satisfied with an $a \geq \tilde{a}\_{K, m}$ where $\tilde{a}\_{K, m} > a_{K,m}$ is given explicitly in Section 4. In this case, we are not sure if $\tilde{a}_{K, m}$ is the smallest possible $a$ there. Additionally, we have also added Section L in the supplement to explain the relationship between the NMF problem and network modeling.

Response to your main point 2. Thanks for your valuable comment. We have revised several places in Section 1 to improve literature review, overview of our results, and comparison with existing literature. To further clarify, our main results are as follows.

• The orthodox NIEP concerns the following problem: given $K$ numbers $\sigma_1,\sigma_2,\ldots, \sigma_K$, when do we have a $K \times K$ non-negative matrix $M$ with $\sigma_1, \sigma_2, \ldots, \sigma_K$ as its eigenvalues?
  The existing literature on the NIEP have been largely focused on general $(\sigma_1, \sigma_2 \ldots, \sigma_K)$ but small $K$ (e.g., $K \leq 4$) (e.g., see the two survey papers we added in the first paragraph of the introduction). Especially, the orthodox NIEP and all of the subproblems we mentioned in the first paragraph of our paper remain unsolved for $K \geq 5$. See Page 1 of the paper for details.
• Since the orthodox NIEP is too hard (and people can only crack the case for $K \leq 4$ in the past 70 years), it is of interest to focus on some special cases (especially those motivated by real applications), where the results may be more fruitful.
• Motivated by the NMF problem and network modeling, we focus on a special case where $(\sigma_1,\sigma_2, \ldots, \sigma_K) = (1 + a_{K, m}, 1, \ldots, 1, -1, \ldots, -1)$ but $K$ is arbitrary. Here, $1 \leq m \leq (K-1)$, and $a_{K,m} = \max\{0, 2m-K\}$. We show that for $9$ different cases (S1)-(S9), the NIEP is solvable. For example, one of these cases is $K$ is a multiple of $4$ and $m$ is arbitrary; we show that in this case the NIEP is always solvable. We also identify two cases (N1)-(N2) and proved that the NIEP is not solvable in these cases. Table 1 in Section 3 summarizes our results for all pairs of $(K, m)$ with $K \leq 20$ (but our theorems are for general $(K, m)$).
• Moreover, using the results on NIEP and the connection between NMF and NIEP in Section 1.1, we derive sharp results for NMF in Section 4. There is a rich literature on solving general NMF problems of the form $V \approx W H$, e.g. [1] and the ensuing work, but they cannot be directly applied to our NMF problem (2), which has a more constrained factorization. We will add these discussion to the paper.

In response, we will make the following changes.

• We have revised the first paragraph of Section 1 to clarify the difference between orthodox NIEP and our NIEP. Especially, we have added more references to the literature on the NIEP.
  On Page 1, we have revised the first paragraph and added several references. Existing approaches on NIEP include the Fiedler's approach and Soules' approach, but these approaches focus on the orthodox NIEP and are very different from ours.
  We focus on a special NIEP, where the results are new (especially as the NIEP remain unsolved for $K \geq 5$ while our $K$ is arbitrary). See the two NIEP survey papers we added on Page 1 for details.
• We have revised Section 1.1 slightly to clarify the relationship between NMF and NIEP.
• We will revise our results summary in Section 1.2
• We have added Section L in the supplement to explain the relationship between the NMF problem and network modeling. We have also discussed the modeling of $5$ real networks.

[1] Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization.Nature, 401(6755):788–791, 1999

Response to your main points. Many thanks for your very positive feedback on our paper. We are especially glad that you think our approaches are novel, our proofs are solid, and our paper is well written. You have raised the following main points.

• This paper is very technical and it would be better if it could introduce more related work in the introduction section about NIEP and NMF, etc.
• This paper analyzes the solvability of the special NIEP and provides the algorithms for NMF, but does not give the time complexity of the proposed method, which lacks comparisons with some prior methods with respect to time efficiency.
• Although this paper presents the application of the proposed problem in NMF and network modeling in Section 4, it is still not very clear the specific applications in NMF and DCMM. It would be better if some specific experiments were implemented for NMF and network analysis.

Response to your main point 1. Thanks for your comments. In response, first, in the last few lines of the first paragraph of the introduction, we have add a couple of sentences and four references to orthodox NIEP, including two survey papers on NIEP. Second, we have added a long discussion on how the NMF problem in equation (2) is motivated by social network modeling. Due to space limit, we have put it in the Section L of the supplement.

Response to your main point 2. Time efficiency of the proposed algorithm: with explicit construction of the $Q$ matrix, the dominating computation in both Algorithms 1 and 2 are computing the top $K$ Eigen value and vector pairs of a $n$-by-$n$ real symmetric matrix, which can be solved in O($Kn^2$) time by the Lanczos method or power iteration, and there exist quite a few numerically stable and well optimized software implementations. Standard methods for NMF such as the multiplicative update method of [1] are iterative optimization, and usually run in $O(T K n^2)$ time, where $T$ is the number of iterations. Hence our proposed method with explicit construction of the $Q$ matrix has similar time complexity to existing methods. However, [1] and other optimization-based NMF methods yield factorizations of the form $V \approx W H$, where $W$ and $H$ are allowed to be different. To solve our NMF problem in (2), these techniques need to be modified to enforce extra constraints and may run slower. When constructing $Q$ via numerical optimization as in Lemma 13, the time complexity can be significantly higher. We will add these discussions to the paper.

Response to your main point 3. Thanks and this is a very interesting point. In Section L of the supplement, we have added a section explaining how the NMF problem is related to network modeling. Consider a network with $K$ communities. The rank-$K$ model is one of the most frequently used model for social works, including block models, random dot product graph (RDGP) models, and generalized RDGP models as special cases. The Degree-Corrected Mixed-Membership model is also a rank-$K$ model, but where the parameters all have explicit meanings and are more interpretable in practice. An interesting question is therefore when a rank-$K$ model is also a DCMM model. We show that

• When $K = 2$, a rank-$K$ model is always a DCMM model. For the frequently seen networks weblog, dolphin, karate, polbooks for example. In the literature, we usually assume they have $2$ communities, and so a rank-$2$ model are appropriate. Using our results, whenever a rank-$2$ model is appropriate for these networks, a DCMM model is also appropriate for them.
• For networks with $K \geq 3$ communities, we may similarly model them with a rank-$K$ model. And to check if we can write them as a DCMM model, all we need is to check whether Condition (B*) in Section 4 is satisfied; we can check this by estimating $\Omega$ first. See Section 4 of (Jin, 2022) for example, where it was argued that UKFaculty network satisfies Condition (B*) with $K = 3$ and so we can model it with a DCMM model with $K = 3$. See the table below and Section L of the supplement.

Response to your minor points. We thank you for pointing out these typos, and we have fixed them in the revision.

[1] Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization.Nature, 401(6755):788–791, 1999

Response to your main point. You have made the following main point.

• The paper contains ton of information and is written in such a way that is not easy to follow. It would be great if the authors could make more efforts in organizing and presenting the technical in a way more accessible to general ML/AI audience.

Thanks for a very valuable comment. To respond, we have made the following changes.

• We have greatly revised Section 2 (Page 4 and Page 5-6, marked in blue) to discuss the key ideas underlying our proofs.
• We have added Section L in the supplement to explain the connection between the NMF problem and the social network modeling problem. Especially, we discuss the impact our results on modeling $5$ well-known networks: weblog, dolphin, karate, polbooks, and UKFacutly.

Response to your other points. You have made the following other points.

• Section 1.2: We also show that in 2 two different cases, (N1)-(N2), Problem (1) is not solvable: redundancy here?
• Section 2: Theorems 2-4 are proved in the supplement perhaps say also in which specific section of the supplement?
• After Theorem 9: For Case (d))
• After Lemma 13: This motivates the following algorithm, could the algorithm be put into an algorithm environment here? or is it just not necessary?
• More generally, the authors propose to tackle Problem (1) using a construction approach by exploiting Haar and DFT basis. To me this choice of basis may not be unique, could the authors comment on the possible extension of the proposed construction?

Thanks for your very careful read and valuable comments. For 1-3: we have revised as suggested. For 4: we can but we didn't do it due to the space constraint. We will try to revise the paper to accommodate that. For 5: this is a very interesting point and for some of the cases, we have indeed proposed different approaches. For example, consider the case of $K = 2^d$, where $d \geq 1$ is an integer. In this case, we can use the Haar construction as in Theorem 6, and we can also use the Haar-DFT combined construction as in Theorem 10. How to extend and combine the proposed approach to broader cases is a very interesting research problem for the future work.

Response to your summary. Thanks and we are especially glad that you think

• (a) we study an interesting question using novel constructions, (b) there is a lot of care and precision we put into characterizing the $Q$ matrix, and (c) people heard about our problem and know why it matters.
• the relationship between NMF and our problem (NIEP) is nice and crisp.
• the writing of our paper is clear, and the practice side of the paper is appreciated.
• the paper could be published in a good venue.

We thank you for many very positive comments, which we very much appreciate. We are also a little surprised to see that you gave our paper a very low rating. We have revised our papers (especially in Section 2, marked in blue). We hope these changes have satisfactorily addressed your concern.

Response to your main points. In particular, you have raised the following points.

• Main point 1. The paper lacks a clear discussion in its own right that the NIEP and NMF problems are well motivated ...
• Main point 2 The body of the paper contains many constructions for $Q$ matrices that solve the NIEP for various $(K, m)$ pairs. It does not, however, justify at all why these constructions should work, or any intuition at all ....
• Main point 3. A lesser issue is that I do not understand if this paper is a good fit for ICLR, or really any other ML conference.

For your main point 1, it seems that there is a major misunderstanding. The NIEP problem is motivated by an NMF problem in equation (2), and the NMF problem is motivated by the problem of social network modeling:

Network modeling --> The NMF problem in equation (2) --> NIEP,

In Section 1.1, we have used a whole page to explain how the NIEP is motivated by the NMF problem in equation (2). The two sentences you mentioned is for explaining how the NMF problem in equation (2) is motivated by network modeling. For the latter, we have now added a more detailed explanation, but for space limit, we put it in the appendix (Section L, the last page), where we also discuss modeling for $5$ real social networks.

For your main point 2: thanks and your comments have greatly helped us in revising our paper. In particular,

• we have rewritten the first part of Section 2 (marked in blue) on page 4, explaining a key idea in our proofs. We also used the key idea to explain the proof for Theorem 2.
• we have rewritten Section 2.2 (marked in blue) on Page 5-6, explaining the key idea underlying Lemma 7 and Theorem 8 there.

We encourage you to read the changes. We hope these changes have explained some of the key ideas in our proofs and assure you that our proofs are correct and rigorous.

For your main point (3), we think being diverse, inclusive, and interdisciplinary is one of the main reasons why ML conferences become so successful in the past decades.

• It is a win-win to publish papers of this kind in ML conferences: on one hand, we can attract talented mathematicians to tackle ML problems in areas such as NMF and network analysis, and on the other hand, we can enrich mathematics by providing mathematicians with new ideas and new problems.
• Both NMF and network analysis are important ML research topics, and in the past decades, ML conferences have published many interesting papers in these areas. We have spent almost a whole page (Page 2) explaining how the problem (i.e., NIEP) grows out from NMF problem in equation (2), and in the appendix (Section L), we have added discussion on how the NMF problem (2) is motivated by network modeling. See our response to your main point (1) above.

Response to your other points and minor points. Thanks. For your other point: we think they are already addressed in our response to your main points. For the minor points: thanks, and we will revise as suggested if not already.