Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis

Thank you for your helpful comments. We are glad that you think our paper has a "novel and theoretically sound contribution" and our optimization-free estimation is "elegant and well-justified." Please find below our point-to-point response to your questions.

1. Runtime analysis.

Following your suggestion, we documented the runtime of our method as $K$ increases: Fix $n=1000$. For a grid of $K$, we ran our algorithm for 20 repetitions and divided the total runtime by 20. This gives the average runtime per iteration. For comparison, we have also included the runtime of successive projection (SP) for all $K$ and the runtime of minimum volume transformation (MVT, a classical unsupervised method) for $K=3$. All three methods are implemented on R.

Our method is super fast, and the runtime is insensitive to $K$. SP is also very fast, but its runtime increases considerably as $K$ increases. MVT requires solving a non-convex optimization via iterations. We used the CVRX package, via a convex relaxation of the objective, to implement MVT. It is much slower than our method and SP.

The complexity of our method is as follows: $O(N^3)$ for finding $\alpha$; $O(NK^2+K^3)$ for estimating $b$; and $O(nKd + K^3)$ for obtaining $\widehat{V}$ from $b$, where $N$ is the number of labeled points and $d$ is the dimensionality of all points. When $K\leq N\ll n$, the total complexity is $O(NK^2+nKd)$.

2. Selection of $\alpha$.

"Section 2.2 proposes two methods to select α, but the empirical section always uses the first approach. Could the authors provide a comparison between the two choices to validate whether one is clearly preferable or whether both are robust?"

This is a great point. We first answer your questions using a simulation experiment. We fix $n=1000$, $K=3$, $d=2$, $\sigma=0.2$ (noise standard deviation), and set the labeling ratio to 5%. We implement our method with three choices of $\alpha$: Approach 1 and Approach 2 in the paper, and a randomly perturbed version of Approach 1by adding $0.1\cdot \mathrm{Unif}(0, 1/\sqrt{N})$ noise to each entry of $\alpha$ (since the original $\alpha$ is a unit-norm vector with $N$ entries, such a perturbation is significant). The media errors over 20 repetitions are as follows:

In this example, there is no big difference between the two approaches. Additionally, the results are robust to perturbation of $\alpha$.

Second, we explain why we presented two approaches. Approach 2 was inspired by our theoretical insight for the special case of $N=K+1$. In this case, we can explicitly find an optimal $\alpha$. Such an $\alpha$ is not defined for $N>K+1$, but we hope to mimic the case of $N=K+1$ by grouping labeled points into $(K+1)$ groups. Although this idea was clear, we found that its performance relied on that labeled points were well-clustered. To deal with the case that labeled points are scattered, we designed Approach 1, which is more ad-hoc but works for broader cases.

As for practice, our recommendation is to first run k-means on the labeled points and check whether they are well-clustered (e.g., by checking the Rayleigh quotient) . If yes, apply Approach 2; otherwise, always use Approach 1.

3. The impact of noisy or imperfect side information.

Yes, our theory can incorporate this. Let $\Pi_S$ and $\widehat{\Pi}_S$ be the true and noisy (or imperfect) label matrices for those labeled points. There will be an extra term in the error bound (the norm below is the spectral norm): $N^{-1/2}\| \widehat{\Pi}_S-\Pi_S \|.$

Notably, this term will not explode as $N$ increases, so our method still enjoys a good error rate.

4. Comparison with modern NMF-based VH variants.

We added two competitors: minimum volume transformation (MVT, Craig, 1994) and the archetypal analysis (AA) algorithm in Javadi and Montanari (2020). MVT is the prototype of most recent anchor-free approaches, and AA is a recent optimization approach. The results for $K=3$, $n=1000$ and 5% of labeling ratio, along with five different values of $\sigma$ (noise standard deviation), are presented in the table below. We have also included our method and SP.

We found that the optimization approaches (such as AA) were less stable; and the error rate could be really large under a high-noise level (in this case, the algorithm may be hard to converge). Our method outperforms these competitors.

5. Combination with optimization-based VH.

"The paper mentions that the SSVH method can be combined with optimization-based VH, but this idea is left as future work. A small experiment on this combination would strengthen the practical value."

We mentioned two ways of combination: (1) Using our method as the initialization. (2) Using the $b$ estimated from our method to modify the constraints in an optimization-based method. Due to the short time, we only implemented the first idea.

We focus on the MVT algorithm and consider two initializations: (1) Constant initialization: Set the barycentric coordinate for each point to be $w_i=(1/K){\bf 1}_K$. (2) Using our estimated vertices as the initialization. In the same simulation settings as in Point 4 above with $\sigma=0.2$, we obtain the following results:

When we only run 4 iterations, our initialization is better than the constant initialization. However, as the number of iterations increases to 8, the performance becomes worse. It seems that the true $V$ is not a local minimum of MVT: Even if we start from a very good initialization, the algorithm still deviates from it in just a few iterations. We should probably try a different optimization-based method other than MVT, and we will continue to explore this direction.

6. Other promising domains where SSVH could be applied.

Our method can be potentially applied to semi-supervised NMF problems. Suppose we have an NMF problem and know a few rows of one of the two factors. We can apply spectral decomposition and then apply the SCORE normalization (Jin, 2015) to eigenvectors. This will create a simplex structure, in which the barycentric coordinates and the original rows are connected as in Model (2). This is where our SSVH can be useful.

7. Unmodified real datasets.

"The empirical section could be strengthened by including more real-world datasets ... it would be valuable to show performance on unmodified real datasets where only partial labels are available."

We absolutely agree with you, but it is hard to find such real data sets. Take the network problem for example. It is not hard to find data sets where partial labels are available (e.g., based on our prior knowledge on those high-degree nodes). However, in order to evaluate the error rates of different methods, we need to know the true labels of all nodes. Available data sets only provide categorial labels for all nodes, so we can only use them for evaluating community detection, but not mixed membership estimation. This is why we chose to do semi-synthetic experiments.

Thank you for a nice summary of the four strengths of our paper. There is only one weakness you raised: how to motivate Model (2). We clarify that this model naturally arises from applications and has been known in the literature.

Where this model came from: Both mixed-membership estimation and topic modeling essentially assume a nonnegative factorization structure on the expectation of the data matrix. Under such structures, for any low-dimensional linear projection of data (including the spectral projection), the resulting points are contained in a simplicial cone, subject to noise corruption. To enable downstream estimation procedures for these applications, we must first normalize this simplicial cone to a simplex (e.g., for spectral projections, the SCORE normalization (Jin, 2015) is a convenient choice). Model (2) is a direct consequence of such normalizations. For details, please see the proofs of Theorem 4.2 and Theorem 4.3, in which we verify that Model (2) indeed holds for these two applications.

Model (2) was already discovered in the literature of unsupervised learning, such as Jin et al. (2024) for mixed membership estimation and Ke and Wang (2024) for topic modeling.

Why this model was not highlighted in the previous literature: For unsupervised VH, as long as each point is contained in the simplex, we don't care how its barycentric coordinate is related to the true $\pi_i$. This is why the previous literature didn't highlight Model (2). However, for semi-supervised VH, since we need to incorporate the known $\pi_i$'s, the connection between $\pi_i$ and $w_i$ does matter and needs to be highlighted.

In summary, Model (2) was not proposed by us. It was already discovered in the previous literature, although not highlighted there.

Thank you for your insightful comments and positive evaluation! We are especially glad that you think our work can "inspire follow-up research in the field of structured matrix factorization and nonnegative matrix factorization." Please find below our point-to-point response.

1. Empirical evaluation and comparison.

"There are many recent community detection and topic modeling methods. Only SP and SVS are employed in the study."

In these applications, VH is used as one plug-in step. Although there are different methods, many of them actually use SP in their VH step. For this reason, we hope to find methods that don't use SP in the VH step. Inspired by the comment of another reviewer, we found that Huang et al. (2016) "Anchor-free correlated topic modeling: Identifiability and algorithm" gave such an algorithm. We implemented it on the semi-synthetic data with calibrated paraders from the paper abstracts in MADStat, where we added $12$ labeled words. The $L_1$-estimation error on the topic matrix is $0.023$ for our method and $0.030$ for the method in Huang et al. (2016).

Additionally, we compared with other NMF-based unsupervised methods in the sub-Gaussian-noise setting. This includes the minimum volume transformation (MVT, Craig, 1994) and the archetypal analysis (AA) algorithm in Javadi and Montanari (2020). The results for $K=3$, $n=1000$ and 5% of labeling ratio, along with five different values of $\sigma$ (noise standard deviation), are presented in the table below. We have also included our method and SP.

We found that the optimization approaches (such as AA) were less stable; and the error rate could be really large under a high-noise level (in this case, the algorithm may be hard to converge). Our method outperforms these competitors.

2. Justification of Model (2).

For the network application, we justify Model (2) in Theorem 4.1. In detail, let $U$ be an arbitrary $n\times K$ projection matrix, and let $\eta\in\mathbb{R}^K$ be an arbitrary vector. We construct the following $K$-dimensional points: $\hat{r}_i = U'Ae_i/\eta'U'Ae_i, \qquad 1\leq i\leq n.$

Here, $Ae_i$ is the $i$th column of $A$, and $U'Ae_i$ is a projection of this column into low dimensionality, and the denominator $\eta'U'Ae_i$ serves as a normalization. In a special case where $U$ consists of the first $K$ eigenvectors of $A$ and $\eta=(1,0, \ldots, 0)'$, the points $\hat{r}_i$ are called the SCORE projections (Jin, 2015) in the literature, and these points are used for the downstream estimation procedure. In Theorem 4.1, we consider a population counterpart of $\hat{r}_i$ as follows: Let $\Omega=\mathbb{E}A$ be the Bernoulli probability matrix. Consider $r_i = U'\Omega e_i/\eta'U'\Omega e_i, \qquad 1\leq i\leq n.$

In Theorem 4.1 Bullet Point (a), we show that if $\Omega$ satisfies the degree-corrected mixed membership (DCMM) model, then there exists a matrix $V$ and a vector $b$ such that $r_i = Vw_i, \quad \mbox{with}\quad w_i = (b\circ \pi_i)/\|b\circ \pi_i\|_1.$

This is exactly Model (2).

For the topic modeling problem, we have a similar justification in the proof of Theorem 4.2 (due to the very tight space constraint, we didn't state this explicitly in Theorem 4.2, but it was indeed in the proof).

We also clarify that Model (2) is not new. It has been discovered in the previous literature. However, since the connection between $\pi_i$ and $w_i$ does not matter for unsupervised VH, this model was not highlighted in the previous literature.

3. The uniqueness result in Theorem 2.2 and the conditions on $\Sigma(\alpha)$.

"Under what settings $M(\alpha)$ is a one-dimensional subspace?"

By our Theorem 2.2, $M(\alpha)$ has a one-dimensional null space if $\Sigma(\alpha)$ has a rank $(K-1)$.

"$\Sigma(\alpha)$ needs to be $(K-1)$-dimensional. Under what conditions, it can be satisfied or violated in practical settings."

In Line 123, we mentioned that $\Sigma(\alpha)$ is a weighted sample covariance matrix of $w_i$'s for $i\in S$. Since $w_i$'s live in a $(K-1)$-dimensional hyperplane, it is reasonable to assume that the sample covariance matrix has a rank $(K-1)$. For illustration, let's tentatively assume that $b={\bf 1}_K$ and $H\alpha={\bf 1}_n$. Below are two examples for which $\Sigma(\alpha)$ has a rank $(K-1)$:

• $S$ only contains $(K+1)$ points, with one point at each vertex and the last point located at the center of the simplex (defined as $K^{-1}\sum_{k=1}^K v_k$). We can theoretically show that $\Sigma(\alpha)$ has a rank $(K-1)$.
• For the labeled points, their $\pi_i$'s are i.i.d. sampled from a Dirichlet distribution, with the Dirichlet parameters being all positive constants (in this case, as $N\to\infty$, $\Sigma(\alpha)$ has a rank $(K-1)$ with an overwhelming probability).

4. Using our method to initialize other algorithms

"In the experiments, do the algorithms SP and SVS utilize the labeled information using some sort of initialization? It may also be worthwhile to initialize the SP/SVS algorithms or other NMF algorithms using volume minimization to initialize with your approach and observe the empirical performance."

SP and SVS do not need initializations. Using our method to initialize MVT is an interesting idea. With the same simulation settings as in Point 1 above with $\sigma=0.2$, we compared two ways of initializing MVT: (1) Constant initialization: Set the barycentric coordinate for each point to be $w_i=(1/K){\bf 1}_K$. (2) Using our estimated vertices as the initialization.

When we only run 4 iterations, our initialization is better than the constant initialization. However, as the number of iterations increases to 8, the performance becomes worse. It seems to suggest that the true $V$ is not a local minimum of MVT: Even if we start from a very good initialization, the algorithm still deviates from it in just a few iterations.

Thank you for your comments. We are glad that you think our discovery of the optimization-free approach is interesting and that our paper is technically solid.

1. Comparison with the literature, especially the anchor-free approach.

Since several of your critical comments are related to this, we hope to clarify this point first. Thanks for pointing out the anchor-free paper, and we will add a nice citation. However, our work is significantly different from it:

• Different settings: The anchor-free approach is for the unsupervised setting, but our focus is the semi-supervised setting. The anchor-free approach is not able to leverage the partial label information.
• Different methods: The anchor-free approach solves a non-convex optimization and requires an iterative algorithm to solve, while our approach is optimization-free.
• Different error rates: All unsupervised methods, including the anchor-free approach, can only achieve an error rate of $\widetilde{O}(1)$. However, our semi-supervised method is able to achieve a faster rate of $\widetilde{O}(N^{-1/2})$, where $N$ is the number of labeled points.

In summary, although anchor-free is one advantage of our method, it is not our main goal. Our main goal is to leverage the labeled points to achieve a "faster" error rate than all unsupervised methods. Our contribution is orthogonal to those of the anchor-free approaches.

2. Additional baselines.

We added two NMF-based unsupervised methods: the minimum volume transformation (MVT, Craig, 1994) and the archetypal analysis (AA) algorithm in Javadi and Montanari (2020). They are both anchor-free approaches: MVT bypasses the anchor-point condition by minimizing the volume of the simple, and AA bypasses it by minimizing the distance from vertices to the convex hull of data points.

The results for $K=3$, $n=1000$ and 5% of labeling ratio, along with five different values of $\sigma$ (noise standard deviation), are presented in the table below. We have also included our method and SP.

We found that the optimization approaches (such as AA) were less stable; and the error rate could be really large under a high-noise level (in this case, the algorithm may be hard to converge). Our method outperforms these competitors.

3. Numerical comparison with the 2016 NeurIPS paper.

Thanks for pointing out this interesting reference. Before presenting the numerical results, we'd like to clarify two points:

• Their method is not for a general VH setting: In their Equation (7), the constraints are that each column of the topic matrix is nonnegative and self-normalized. These constraints do not hold for a general VH problem.
• An adaptation of their method to a general VH setting reduces to Minimum Volume Transformation (MVT): In a general VH setting, we may adapt their method by keeping the same objective but removing those problem-specific constraints. Their objective is maximizing the determinant of $M=V^{-1}$, which is equivalent to minimizing the volume of the simplex spanned by $V$. This becomes the classical MVT algorithm (which has already been discussed in our Remark 1 and Figure 1).

Since this paper didn't propose a general VH algorithm, we can only compare it in the topic model setting. We use the MADStat data set to calibrate a true topic model and then simulate data from it. We pick only $N=12$ labeled points (words). The mean and standard deviation of the L1-error of topic modeling over 100 repetitions are reported below.

4. Labeling ratio.

"In line 344, the paper claims that 5% labels is a 'small proportion.' However, in many semi-supervised learning contexts, 5% is not typically considered small. Can the authors justify why they consider this a small proportion?"

We will edit the text not to claim 5% as a 'small proportion.' In theory, our method can work with as few as $(K+1)$ labeled points. Our numerical results also contain low-labeling-ratio cases:

• In the left two plots of of Figure~2, the x-axis is the labeling ratio, ranging from 1% to 5% on a fine grid. Our method outperforms SP in this whole range. Since $n=1000$ in these experiments, a 1% labeling ratio means there are only $N=10$ labeled points.
• In our newly added topic modeling experiment (see Point 3 above), we only pick $N=12(=K+1)$ labeled points.

5. Justification of the sub-Gaussian noise assumption in applications.

This is a great point. We recall that in these applications, VH algorithms are applied to leading eigenvectors of data matrices. Recent results have shown that the entries of leading eigenvectors are approximately normal. To see the rationale, we take the network setting for example. We quote the result in Abbe et al. (2020) "Entrywise eigenvector analysis of random matrices with low expected rank". Let $A$ be the n-by-n network adjacency matrix, and let $\hat{\xi}_k$ and $\xi_k$ be the respective $k$th eigenvector of $A$ and $\mathbb{E}A$. Under the stochastic block model (SBM), Abbe et al. (2020) showed that $\hat{\xi}_k= A\xi_k + \delta_k,$

where $\delta_k$ is an entry-wise negligible vector, and $A\xi_k$ is called the first-order proxy of $\hat{\xi}_k$. Each entry of $A\xi_k$ is a weighted linear combination of $n$ entries of $A$ (these are independent Bernoulli variables), hence being sub-Gaussian. Since the entries of $\delta_k$ are at a smaller order, each entry of $\hat{\xi}_k$ is also approximately sub-Gaussian.

6. How does label noise affect the theoretical guarantees?

Yes, our theory can be modified for this setting. Let $\Pi_S$ and $\widehat{\Pi}_S$ be the true and noisy label matrices for those labeled points. There will be an extra term in the error bound (the norm below is the spectral norm): $N^{-1/2}\| \widehat{\Pi}_S-\Pi_S \|.$

Notably, this term will not explode as $N$ increases, so our method still enjoys a good error rate.

7. Row-wise bounds.

"The theoretical analysis focuses on the entire $V$ matrix, while recent literature emphasizes row-wise bounds."

Our results are in fact stronger than row-wise bounds. Recall that $V=[v_1, v_2,\ldots,v_K]$. Let $e_k$ denote the $k$ th standard basis of $\mathbb{R}^K$. It is seen that for each $1\leq k\leq K$,

$\| \hat{v}_k-v_k \| = \|(\widehat{V}-V) e_k\| \leq \text{SpectralNorm}(\widehat{V}-V).$

Since our theory bounds the spectral norm of $\widehat{V}-V$, it automatically implies the row-wise bounds.

8. Why SP has a worse performance even with pure points.

"For Figure 2, why does SP perform equally poorly even in the case with pure points? Also, error bars should be added since results are based on 100 repetitions."

As we mentioned in Point 1 above, anchor-free is only one of the advantages of our method. Another advantage is the improved error rate by a factor of $1/\sqrt{N}$. In the pure-point case of Figure 2, the x-axis is the labeling ratio. Even with 1% (corresponding to $N=10$) of labeled points, the theoretical error rate is only $1/\sqrt{10}\approx 0.32$ times the theoretical error rate of SP. This explains the results in Figure 2. The error rate is indeed a fundamental difference between unsupervised and semi-supervise settings.

Yes, we will add error bars in the revision. Thanks for this suggestion.

9. Other clarifications.

"Having information ... makes the identification problem much easier, so the improved performance is not surprising."

Although people expect the semi-supervised setting to be easier than the unsupervised setting, how to design an algorithm that indeed achieves a faster rate is not easy. Both our method and theory are non-trivial. For example, we explicitly show that leveraging the labeled points will strictly improve the error rate, which has never been discovered before.

"The paper lacks theoretical guarantees specific to the applications"

We did provide theorems for both applications. Please see Theorem 4.1 and Theorem 4.2.

Thank you for your response. We are glad to hear that our rebuttal addressed some of the issues you raised, and we sincerely appreciate your decision to raise the score.

Below please find our quick answers to your "Issues Remaining Unresolved":

Optimality of the Rate: In the paper, we considered an Ideal Estimator which assumes that $b$ is known. In this case, we can solve the vertex matrix by a simple least-squares, and its rate is presented in Lemma 3.3. We showed that our rate matches with this rate of the Ideal Estimator up to a $\sqrt{\log(n)}$ factor. While this is not a lower bound, it provides some evidence that our rate is hard to improve (because when noise is Gaussian, least-squares is hard to improve).

Adapting anchor-free methods to semi-supervised settings: As discussed in the paper, we are not aware of any semi-supervised variant of these methods. Instead, our work provides such a solution: We can either (1) use our $\widehat{V}$ to initialize another method, or (2) use our $\hat{b}$ to modify the constraints/objectives of another method. In both approaches, information of labeled nodes is incorporated.

During the rebuttal period, we were only able to experiment on Approach (1). The results were included in our rebuttal to other reviewers, in which we used our estimator to initialize MVT.

After a second thought, we realize that Approach (2) should be the more promising one, as a modified constraint/objective will impact all iterations, not just the initialization. In detail, let $\hat{w}_i = (\hat{b}\circ \pi_i)/\|\hat{b}\circ \pi_i\|_1$ for all labeled nodes $i$, where $\hat{b}$ is our estimator of $b$. We hope to enforce the constraint that $x_i\approx V\hat{w}_i$. This can be done by adding a penalty in the objective: Let $L(V)$ be the original loss. The new loss is defined by

$L(V) + \lambda \sum_{i \in S} (x_i - V\hat{w}_i)^2.$

We'd be glad to explore this idea. However, a thorough study of this will demand significant empirical/theoretical efforts, and we prefer to defer it to future work.