Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis
Authors: Yicong Jiang
Tracy Ke
Venue: NeurIPS 2025 poster ()
Keywords: Eigenvalue problem
successive projection
mixed membership estimation
topic modeling
Primary area: general_machine_learning
TL;DR: We propose a novel semi-supervised vertex hunting (SSVH) algorithm that has a theoretical guarantee. We use SSVH to develop semi-supervised learning algorithms for network and text analysis.

Abstract: Vertex hunting (VH) is the task of estimating a simplex from noisy data points and has many applications in areas such as network and text analysis. We introduce a new variant, semi-supervised vertex hunting (SSVH), in which partial information is available in the form of barycentric coordinates for some data points, known only up to an unknown transformation. To address this problem, we develop a method that leverages properties of orthogonal projection matrices, drawing on novel insights from linear algebra. We establish theoretical error bounds for our method and demonstrate that it achieves a faster convergence rate than existing unsupervised VH algorithms. Finally, we apply SSVH to two practical settings---semi-supervised network mixed membership estimation and semi-supervised topic modeling---resulting in efficient and scalable algorithms.

Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis
Yicong Jiang
Zheng Tracy Ke Department of Statistics Harvard University zke@fas. hww.ard. edu
Department of Statistics Harvard University
yicong-jiame jinggg. harvard.
Abstract
Vertex humting (VH) is the task of estimating a simplex from noisy data points and has many applications in areas such network and text analysis. We introduce new variant, semi supervsee vertex hunting (SSVH), in which partial information is available in the form of barycentric coordinates for some data points, known only up to an unknown transformation. To address this problem, we develop a method that leverages properties of orthogonal projection matrices, drawing on novel insights from linear algebra. We establish theoretical error bounds for our method and demonstrate that it achieves a faster convergence rate than existing unsupervised VH algorithms. Finally, we apply SSVH to two practical settings- semi-supervised network mixed membership estimation and semi-supervised topic nesuting-eesulting in efficient and scalable algorithms.
1 Introduction
Semi-supervised learning has been widely studied in the classification settings with discrete-valued la- bels. In contrast, continuous-valued labels (e.g., soft labels) also play crucial role in applications. One example is network mixed membership estimation (2). Suppose a network contains K communities, and each node has mixed membership over K communities. The mixed membership vectors take arbitrary values in the probability simplex of R Another example is topic modeling (7]. Suppose text corpus contains K topics. Each word has /<-dimensional topic loading vector representing its relevance to K topics. These topic loading vectors can also be regarded as soft labels of the words.
We are interested in semi-supervised learning for soft labels, where small fraction of them known. In the previous network estimation example, we may know the mixed membership vectors for some nodes (for example, this happens in dynamic networks with both long-existing and newly emerging nodes, where the mixed membership a long-existing node can be inferred from historical data). In topic modeling,
may have knowledge of the topic relevance of certain words, such as anchor words ( or seed words [15] for some topics, which can be leveraged for model estimation.
Vertex hunting (VH), also called linear unmixing archetypical analysis, is important tool used in the above problems for unsupervised learning. Fix > 2 and a simplex S Rd that has K vertices Ug- Let W1, ........ ... W1, E IRKK be weight vectors (a weight vector is such that all entries are non-negative and sum to 1). Suppose we observe 21, F2, In E Rd satisfying
U1 ..,..... .....
K
where r; r;= E we workk) and 6 's are i.i.d. noise.
34 +i
Here, each r; is contained in the simplex S, and wy is called the barycentric coordinate of r;- The goal of VH is to estimate the vertices U1, UK from the noisy data cloud {x; { In both unsupervised mixed membership estimation and topic modeling, the spectral-projettes data exhibit such simplex
structure, so that VH is frequently used as a plug-in step in parameter estimation
21 25
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we introduce the semi-supervised vertex hunting (SSVH) problem, as a new tool for semi supervised learning in the above problems. Suppose for a subset S {1. ..,,,..,] we observe Ty E TR& for each i E S, where Ti is related to the barycentric coordinate w; as follows:
n).
Wi- (b o /t/// b Till,, for an unknown positive vector E B
(2)
Here o is the Hadamard (entrywise) product. In this expression, if we multiply b by any positive scalar, the equality continues to hold. Therefore, we assume |]6]] without loss of generality. SSVH aims to estimate , UK from {zi and the additional information {Ti)EEs.
Model (2) was discovered in the literature of unsupervised learning. such as 21 for mixed member- ship estimation and [25) for topic modeling. In these problems, the mean of data matrix admits a nonnegative factorization structure. Under such structures. for any low-dimensional linear projection of data (including the spectral projection), the projected points are contained in a simplicial cone subject to noise corruption. To enable downstream estimation procedures, we must first normalize this simplicial cone to a simplex (e.g., for spectral projections, the SCORE normalization [20] is convenient choice), and Model (2) is direct consequence of such normalizations (24.. See Section
for details, where we validate (2) for the two applications of interest. It is worth noting that Model (2)
was often hidden in the proofs of the previous works but not explicitly presented there, due to that an
unsupervised VH algorithm does not need any knowledge of how the barycentric coordinate w; is related to the true тΙ, contrast, for semi-supervised VH, the connection between m, and wy directly explicitly here.
affects how we design the algorithm, so must present Model 2
Many algorithms have been developed for unsupervised VH. such as minimum volume transformation (MVT) 8 N-FINDR (32), and successive projection (SP) 4 Based on MVT, [4] developed a delicate anchor-free topic model estimation approach, which can also be applied to the VH problem. Recently, (22 provided refinement of SP to strengthen its robustness against noise; 64 estimated the vertices in unsupervised overlapping community detection via K-median clustering under certain asympiotic regime: [16] adopted a regularized negative matrix factorization (NMF) for vertex hunting (archetypal analysis); and (30) proposed a theoretical framework for interpretation and guidance on spectral methods for network membership estimation and algorithms for vertex hunting such as MVT. However, is unclear how to modify these methods to incorporate the information within { (T. hes. The difficulty stems from that b is barycentric coordinate of ri inside the simplex. One may consider a joint-optimization approach, where we optimize over b and U,,..., UK together using a loss function, but it is unclear how to design a loss function that both facilitates computation and comes with a theoretical guarantee.
the knowledge of ग. does not directly imply the
We overcome the difficulty by proposing an optimization-free estimate of b: For any vector a E RISI satisfying mild conditions, we construct a K x K matrix M (a) and let be the eigenvector of this matrix associated with its smallest eigenvalue. This estimator is easy to implement and enjoys nice theoretical properties. Our method is inspired by non-trivial insight in linear algebra: the construction of M (a) carefully utilizes properties of orthogonal projection matrices.
Once b is obtained, we can derive the barycentric coordinate w; for i E S at ease. It provides the locations of these r; inside the simplex, and we can utilize such information to enhance an existing unsupervised VH algorithm. In fact, given b, we can even use a simple regression to get ê1...., θg- This gives final SSVH algorithm.
We show that SSVH has several benefits compared to unsupervised VH: First, unsupervised VH needs strong identification conditions. For instance, SP requires that at least one r; is placed at each vertex, and MVT requires that the minimum-volume simplex containing r' ri,...: I' is unique. When such conditions are violated, unsupervised VH may fail. Second, the error rate of unsupervised VH does not decay with n (1222,, so it is unable to take advantage of having more data points. Third, the signal-to-nois. ratio of unsupervised VH depends on the (K- 1)th singular value of the vertex matrix (22). When K is large, this singular value can be small, indicating that the simplex is 'thin' in some direction and vulnerable to noise corruption; hence, unsupervised VH may have unsatisfactory performance for large K. SSVH can address these issues- as we will demonstrate, it requires weaker identification conditions, enjoys fast-decaying error rate, and can handle large values of K.
We apply SSVH to semi-supervised lixeddmembership estimation and semi-supervised topic model- ing and develop new methods for these two problems. For the first problem, despite of many methods for sumi-super community detection 26 19 33
G 17 28 35), they are hard to generalize to
allow for mixed membership. For example, one strategy in such methods (c.g., see [19 is to group

---

labeled nodes according to their true communities and compute the "similarity' between an unlabeled node and each group. When there mixed membership. is unclear how to define groups and com- pute the similarity metrics. For the second problem, seeded topic modeling [15] and keyword-assister topic modeling [10] can be regarded as -upesssueee learning methods. However, they add prior information as Dirichlet priors, not permitting specification of topic relevance for individual words. Additionally, these Bayesian approaches are computationally intensive for large corpora, while our SS SSVH-powered algorithms can run much faster in some settings.
In summary, we introduce the SSVH problem and make the following contributions:
Methodology: We propose an SSVH algorithm, the core idea of which is an optimization-free approach to estimating 6. Our method is inspired by delicate insight in linear algebra. Theory: We prove an explicit error bound for SSVH under that the error bound decreases fast as the size of S increases.
noise. We show
Application: We apply SSVH network mixed membership estimation and topic modeling, obtaining new semi-supervised learning algorithms for these two problems.
Notations: Write N |S]. Let Ws, IIs E RNNK R.s E RNxd and Xg R-Nxd be the matrices of stacking together the ws, Ri. and 2; for i E 8, respectively. Let V R be the matrix whose kth row is equal 1/g. With these notations, model ( can be re-written as Rs = WsV. By elementary linear algebra, eigenvector of matrix is defined up to any scalar multiplication. Throughout this paper, when we compute the eigenvector a matrix, the default scalar multiplication is chosen such that the eigenvector has unit -o-morm and that the sum of its entries is positive.
2
Method for Semi-supervised Vertex Hunting
2.1 The oracle case
In the oracle case, we observe r; [B(xs]] and aim to recover V from Tı, .2,..., In and t. for E S. The key is to find an approach for recovering b. Once b is known, we can immediately use (2) to recover the barycentric coordinate wy for E S, and the problem becomes relatively easy.
We tackle the estimation of b by an interesting discovery in linear algebra. We introduce an N N matrix, which is the projection matrix to the orthogonal complement of the column space of lls:
= H()) = IN - IIs (I'sIls))))
For any vector v, let diag(u) denote the diagonal matrix whose diagonal entries are from v. Given any a E R.,, we construct a K x K matrix:
M(a) = ((;; S) = I''diag( Rs Rgdiag( HHx:
(4)
Our design of (a) is based on a novel idea of leveraging properties of projection matrices. In the following theorem, we show that ((a) has nice property:
Theorem 2.1 (Main discovery). For any a E IR" M(a)b = 0g. Therefore, is an eigenvector of M(a) associated with the zero egienvalue.
Proof of this theorem: Let [a) = RdddiggHa)lls,, Then, ((a) ((a) It suffices to show
J(a) = 0g. First, model [[] implies Rg = WsV. It follows that J(a)b V'W diag(Ho ggg.. Second, model (2) implies w; (T; b)/[[T; bll1; in the matrix form, this can be expressed as Ws = [diag(II b (b) We plug Ws into J(a:}b to obtain:
J(a)b d'di (i,
Is
H [dag (switching diagonal matrices)
(because diag(v)-lg = 1 for a vector v)
V'diag(b)
(because diag(e:1 = for vector v)
(5)
We recall that H is the projection matrix to the orthogonal complement of IIg Hence, II's H is zero matrix. It follows that the right hand side of (5) is zero vector.
Theorem 2.1 states that is an eigenvector associated with the zero eigenvalue of M(a). However, does not imply that b is the unique eigenvector associated with the zero eigenvalue. The uniqueness holds only if the null space of (aa) a oie-dimeniional subspace. The next theorem provides sufficient condition for the uniqueness to hold:
3

---

Theorem 2.2 (Uniqueness). Let wi = Ñ EiEs wi and define a K x K matrix by
Σ(a)= E)a, I ((H)) (w, - (w,-w.)(ue w.)(w; -w.).
(6)
iES
When rank([((a)) - the null space of M() a one-dimensional subspace. Consequently, the eigenvector associated with the zero eigenvalue of M(a) is unique and must be equal to b.
To when the condition rank(E(())) = K holds, we consider simple case where b 1 k and Ha = 1 and give Two examples. In the first example, there are K + labeled points, with one point each vertex and the last point located in the interior of the simplex (not on any vertex/eegeefface) When the simplex is non-degenerate [{a) has rank K - 1. In the second example, the T 's of labeled nodes are i.i.d. sampled from Dirichlet distribution, with the Dirichlet parameters being all positive constants. As N + oo, (a)) has a rank K - with an overwhelming probability.
Inspired by Theorems 2.1 2.2 obtain method for recovering b from the eigenvector of M()). Once b is known, by 2 W0 18 known for i E S. We then have many options for recovering V. A simple method is the following regression approach. Recalling that Rs- WsV, we recover V from
=
Another option is a penalized optimization approach. Let L(V; be a loss function that quantifies how well the simplex spanned by V fits the data points. Such loss functions exist in many unsupervised VH algorithms (c.g.. [6). We propose the following optimization:
min L(V Tn)
ΣΣ
||, Vwull
(8)
EES
When À oc, it reduces the estimator in which is the main version will use. Meanwhile, one can always use a finite A. Then, (8) and our method of estimating together offer an approach for extending any apptimization-basedd unsupervised VH method to the sumi-super setting.
Remark 1: Unsupervised VH requires identification conditions to uniquely determine the simplex from F1, 72.... ... T'- For example, SP 4 requires that there is at least one ri locating at each vertex, and MVT [8] and anchor-free approaches such as [4] require that among all simplexes that contain T1, 72.72....... T'n there is unique one that minimizes the volume. When such conditions are violated, unsupervised VH may fail (see Figure T and more details in Appendix G). SSVH addresses this issue by leveraging the additional information in (isss
True simplex
simplex sclutions tialy
Another simplex that aboo contains the data cloud
Figure I: The identification issue for SP (left) and MVT (right). The grey area is the area covered by rl...ry Fre (the noiseless point cloud). Left: There exists on the vertices of the true simplex; consequently, there are multiple simplexes containing the point cloud, and the SP solution not necessarily the simplex. Right: the point cloud is ball, and the MVT solution (the minimum-volume simplex that contains this hall) not unique and does not include the true simplex.
2.2 The real case
In the real case, we observe 24 instead of rs. The oracle method can be extended: First, we construct M (a) by replacing R.s 4 by Xs. Due to noise corruption, this matrix often doesn't have zero eigenvalue; but we can estimate b by the eigenvector associated with the smallest eigenvalue. Second, we plug 6 into 7 and replace Rs by Xs there. This gives V. See Algorithm
Choice of a: Algorithm the only remaining question is how to choose a. In the oracle case, as long as the matrix Σ(a) denned in (6) has rank K - any choice of yields the precise recovery of V. the real case, we still have a wide range of choice of a, as long as the the signal-to-non ratio (SNR) in M(x) is properly large. We offer two recommended approaches, both being closed-form.
Since re-scaling a doesn't it alter we set ||||| = 1. Note that and are the eigenvector of M (a) and M (a) associated with the smallest cigenvalue, respectively, By sin-theta theorem (9) the eigen-gap,

---

Algorithm 1: Semi-supervised Vertex Hunting (SSVH)
Input: K, Xs. and ITs-
1. Compute
R. from Tl using the closed-form solution of either (9) 10
2. Construet M (a) d'g (Ha) dasai"gdHHHHH
where H is in ① cigenvector of M (a) corresponding to the smallest eigenvalue.
Let b be the
3. Obtain úh (6 o m Fi I, and let Wss be the matrix of stacking together the úū for
E S. Compute V (W' W
Output: V (its rows the estimated vertices).
(M plays a key role in determining the signal strength. With ||a|] = 1, we empirically observe that Ax-1 (MM (a)) often increases with (a)]l. It inspires us to maximize [IM subject to ||a|| = This optimization still does not have an explicit solution. However, when the volume of the simplex is lower bounded (which means that the simplex is not 'super thin' in any direction), it holds approximately that [a)]l 2 w diag Ha)ls Il where w a quantity that depends on model parameters but not (this derivation is technical thus contained in the supplement). Therefore, we solve the following optimization:
max |[I'ddiag (Ha)diagHHaasss333
s.t.|aa|| = 1
Without much effort, we can show that has a close-form solution: Let I's IIsll's. and let f(T's) be the matrix of applying a univariate function f(c) c² on Iss entry-wisely. The solution a" is the eigenvector of H (T
9) H corresponding to the largest eigenvalue.
Another option of choosing a uses dimension reduction. We divide S into K + non-overlapping clusters .i..... CR++1. by running k-means clustering on {Te)iEs. Let ा. ex (the kth standard basis vector of RK+ for E Cg. Let IT Nx++((+11 be the matrix of stacking together x; for
all i S. Define U I ([Tgg) - ( the projection matrix into the column space of Tg (which is a subspace with dimension < + 1). We solve the optimization:
max [|
s.t.||a|| 1.
(10)
At first glance, this problem is not easier than maximizing || [a:]] directly. What makes a difference that when IT's has a full rank K, HTJe projects all vectors into 1-dimensional subspace. In this case, maximizing [U is equivalent to maximizing || || and the problem has a closed-form solution: a* is the right eigenvector of H associated with the largest eigenvalue of HU We remark that even when the column space of H is not I-dimensional, we can still compute this closed-form a", though it is no longer the solution of (TO).
Remark 2: It is important to note that, although these choices of a are motivated by optimizations involving M (a),, their closed-form solutions are only functions of IIs. In other words, these a neither use noisy data nor depend on unknown model parameters. This why we can legitimately impose regularity conditions a in the theoretical analysis to be presented in Section 3
3 Theoretical Results
In this section, we derive the error bound for our estimator in Algorithm [ As we have mentioned, the scaling of b and doesn't i matter. We assume ||6|| 1 and ||a|| = without loss of generality.
Assumption 3.1. There exist constants C1, C22 e1 VVIl (b) Amin (Is)) 2 C2 Amar (Ts)) and (c) ming by 2 C3 max; by- Assumption 3.2 (Sub-Gaussian noise). There exists a 0 (which may depend n) such that E[exp(ted) < exp(tto" 2)) S,j E [K] & E IR.
O, such that (a) [|V]| 2 and Xx-1 2
Assumption 3.3. There exists a constant C4 such that Xx-1(E(o)) 2 c2/ ca((VKN), where E(a) is the matrix defined in Theorem 2.2
Assumption 3.2 assumes that the noise within the data sub-Gaussian, and the noise level or may grow as n Dc. Regarding Assumption 3.1 since the volume of the simplex is related to Ax-1 (V), item (a) imposes a lower bound on the volume after re-scaling, which prevents the simplex to be too thin in some direction. Item (b) states that the labeled points are well spread-out in the simplex.
5

---

For instance, they can't 't concentrate in a small region, in which case the conditioning number of IIs large. Item (c) implies that म; retains enough information of each coordinate of w; (e.g., when some by is much smaller than the others, information of (r(k) is nearly lost in T²). Assumption 3.3 about the matrix E(a)). In Theorem 2.2 we assume that its (K - 1)tth singular value is nonzero; and here we put slightly stronger condition.
Our first result a non-stochastic bound, which drops Assumption 3.2 and treats e, as non-stochastic:
Lemma 3.1 (Non-stochastic bound). Suppose Models [ 2 and Assumptions 3.7 3.3 hold. Define erT1 == [['ddiag (Xs Rs)llF, eTT2 := (Xs - -Rs) le, erTs == Xxs -
There exist constants Cs C6 > 0 that only depend on c1, Ca. such that when err < cs /N/K,
|I VII < | Ca + e + ert//N + err//N].
(11)
We use matrix spectral norm as the loss metric. The row-wise norm | - |I is more frequently used in the literature [1
Our bound implies the row-wise bound because max | - uall S II VII-
The three error terms defined in Lemma result provides high- hrgh-probability bounds for them under sub- Gaussian noise.
[.ImmaB.Jjam Jare functions of the 'noise' matrix Xs- - Rss. Our next
Lemma 3.2 (Noise terms). Suppose Models (T(2) and Assumptions 3.7 3.2 hold. Suppose Z
K. There exists universal constant Cen (which does not depend on any other constant in the assumptions) such that with probability at least 1 - -2/n= = 11=11-111 ((1/n))
err; S on / K + C K log(n), err S Cen V NVK log(n), erry S Ceer Vlog)))
(12)
Here the absolute constant Cen depends on the absolute constants of Hanson -rrigtt inequality B1 Theorem 1.1]. [29] provides an evaluation of Hanson Wright inequality's 's constants, based on which a rough estimate of Cerr is 2.8042. See Appendix D.4 for more details. Combining Lemma 3. and Lemma 3.2 we have the main theorem:
Theorem 3.1. Suppose Models ① 12) and Assumptions 3.1 3.3 hold. Suppose N > (1/c))-o
Co Co,, K:15 log(n)), where cg is as in Lemma 3.7 and Cer is as in Lemma 3.2 There exists a constant
Ö₂ >> 0 only depending on c1.... ........ Ct, and Cerv. such that with probability least 1 - ((1nn,
| VII S [[V|| C,,N-1/2 21.25 on Vlo(())( + log(n))).5.
(13)
In Theorem 3.1
we require the number of labeled nodes N to be at least of order o (K2 2
K 1.5 log(n)). This condition is mild. First, when K and on are constants, it only requires O (log of labeled nodes, which much smaller than n. Second, in many applications (see Section 4 on decreases fast with n. In such settings, even a finite number of labeled nodes are sufficient.
We focus on comparing with the results for successive projection (SP). 11 derived a non-stochastic bound in terms of [1/Ax (V) maxigign ||c/]]: and [22] derived an improved bound where Ax (V) is replaced by Ax --1 (VV). Their bounds are for the loss max; 0
Faster rate than unsupervised VH:
va Translating their results to our loss and using concentration inequalities for sub-Gaussian variables, have (see [22] and (G.43) in Appendix for details):
VII < ||V||- CKo. Vlo(n))
(14)
Comparing (44 with 13). we observe that the error rate of SSVH has an additional factor of N- 1/2 (ignoring K K- and logarithmic terms), which converges faster than the error of unsupervised VH.
Tightness of the error bound: We consider an ideal situation where b is given. It follows by 2 that Ws is immediately known. Define a regression estimator (under Gaussian noise, this the ML.E):
4 -W
(15)
If the error rate in (13 matches with the rate of this estimator, then we believe that the rate is already sharp. The lemmas below shows that the error rate in (13) matches the ideal estimator's error rate only up to a (VK- + jog( factor, suggesting the tightness of our rate.
Lemma 3.3 (Ideal estimator). Under the assumptions of Theorem 3.1 the ideal estimator satisfies that with probability at least - O11/n), -iv - VII < ||V]| N- K1.25 o,, / /log(n).
Remark 3 (Noisy labels): Our theory can be extended to the case with incorrect or noisy labels. Let Is and HIs be the true and noisy label matrices, respectively. In this case, there will be an extra term in the error bound, N | 11s []. Notably, this term will not explode as N increases.

---

Applications to Network Analysis and Text Analysis
4.1 Semi-supervised mixed membership estimation
Mixed membership estimation (MME) 2 is problem of interest in network analysis. Let A E R be the adjacency matrix of undirected network with nodes. The network has K communities. Each node i has a mixed membership vector गं E R2 where Tz(k) (k) is this node's s fractional weight on community k. The degree-corrected mixed membership (DCMM) model [2] has been introduced:
Definition 4.1 (DCMM model). The upper triangle of A contains independent Bernoulli variables, with P(,, = 1) = 0.03- T. PT where Ti E RK* is the mixed membership vector, 02 > is the degree parumeter, and P E B-XK is a symmetric nonnegative matrix that has unit diagonal entries. n.. subset of [1, . Given A and T; for E S, we aim to estimate all T. for i S.
x.
Definition 4.2 (Semi-supervised MME). Suppose the network followss a DCMM model. Let S be
We propose the following algorithm. It first uses full-rank matrix U project each column of A to a K k-diiensional vector x; Ae;, and then uses a vector to normalize it: x, ( When U consists of the first K eigenvectors of A and when 7) C1, the vectors 2; coincide with the spectral projections in (21]. However, our approach permits a general choice of U and 1). For example, we may apply a community detection algorithm on get an estimated community membership matrix fist E _ where each row takes values in FI....,E, Then, we can take U = [N and rj = 1g- Under mild regularity conditions on (U, n), we can show that up to noise corruption, 21, .......... Fn are contained in a simplex with K vertices (see Theorem beloo). Therefore, we apply SSVH to x; 's.
Algorithm 2: Semi- supervise Mixed Membership Estimation
Input: K, A, and Ils, Algorithm parameters: matrix U R=*X and vector 1) E RR Tn,] E 1. Compute 2; U' Ae;/ An: Ae;) for < i S Let X = [I,
B and let
Xs E IR NxX be the matrix stacking the x; for E S.
2. (SSVH). Apply Algorithm to (K, Xs, {T) 3) to obtain V and the intermediate quantity
3. Let = diag(b)V. For each i & S, compute मे = (BBBBBB")) Let â be the vector by setting the negative entries in Tig to zero and re-normalizing to have unit -orm.
Output: R, for i $ S.
We justify this algorithm using the following theorem. Under the DCMM model, E[A] = Qi-diag(!!). where Ω is matrix with Piy- 0.0,- n² Pmr. We call Ω the 'signal' matrix.
Theorem 4.1 (Validity of the algorithm). Suppose that the rank of is K, and (U, m)) satisfies that rank(U)= = K and 1f U'e 0 for all i. The following statements are true:
(a) Let ri vector E RKK such that each r; = KK we(k)uk, where w; = (b / R
(T'Dea/r'UUQee for 1 S i < There exist u1,- UKK--.,UK E R and positive
(b) we plug (K, Ils) into Algorithm 2 then क.; = for all $
The first statement in Theorem 4.1 justifies that Models - hold for x; 's, so that our SSVH framework is applicable. (Here, the noise is E; = x; - T; x shown sub-Gaussian as (A R)e; contains independent centered Bernoulli variables.) The second statement says that the proposed algorithm can exactly recover unknown Tú in the noiseless case.
-)e: (r)e(() which can be
Compared with the unsupervised MME methods such as MSCORE 21 or [34], major benefit of the above algorithm is that doesn't 't require existence of pure nodes for each community. Additionally, Algorithm 2 is also a new unsupervised MME algorithm, if we replace SSVH by unsupervised VH in Step 2. The resulting algorithm different from MSCORE 21 in the unsupervised setting.
Semi-supervised topic modeling
Topic modeling (TM) 7 is a widely used tool for text analysis. Suppose we have a corpus with
documents written on a vocabulary of words. Let Y = [Y,...., ......,. Y.. E RR be such that Y,() is the count of word in document i. Topic modeling aims to estimate K topics from the corpus, where each topic a distribution over vocabulary words, represented by a probability mass function (PMF) A Rº. The probabilistic Latent Semantic Indexing (pLSI) model [12] is common topic model:
7

---

Definition 4.3 (pLSI model). The word count vectors Yi...., Yn are independent of each other, with Y Multinomial(N, Q2), where N, is the length of document i, and S2 E R2 a PMF satisfying that 92 = >x T%: (k) with (kk()) being the fractional weight that document i puts on topic k.
The unsupervised topic modeling aims to estimate A = [AI....,Ax from the data matrix Y, and is addressed various algorithms via optimization or spectral methods [14] (5). We now formulate the semi-supervised problem by discussing what "additional information means in practice. For each 1 J S p, let a; = (Ai()).... A....,Ax( E IRK. This vector contains word j's frequencies in different topies. The topic loading vector for word j is defined as aj = a;/|laşlı, Since the effect of word frequency heterogeneity has been removed in az, this vector purely captures word topic relevance. For example, when j is anchor word S [5] of topic k. az is equal to eg. When a = (0.5, 0.5, 0, ...'. )/, it means that word j is only related to the first two topics. Motivated by these observations, we formulate the semi-supervised problem as follows:
Definition 4.4 (Semi-supervise) TM). Suppose the word count matrix Y follows the plSI model. Let S be a subset of (1,2.....P)) .p]. Given Y and a; for j E S, we aim to estimate A.
There literature on incorporating prior knowledge or human input into topic modeling
10]
A common assumption [15 I0 is that a set of keywords is given for each topic, and the topic vector is modeled as A₁ A +11 TT) where Aş and A are the keyword- and standard topics, respectively, and the support of Ag is restricted on the keyword set. All parameters (TTE, Ag, AT) are estimated in a Bayesian framework using beta and Dirichlet priors. In comparison, our problem in Definition 4.4 permits a more flexible way of specifying the topic relevance of each keyword. If in az we put equal weight on each topic word serves as a keyword, then our framework is similar to those in the literature. But we can also put unequal weights, to incorporate more human knowledge on keywords. Another benefit of our framework is that we can leverage SSVH to get a fast algorithm, without relying on the sampling procedure in the Bayesian framework.
We now propose our algorithm for semi-supervised TM. The strategy is similar to that in Section We first turn the counts to frequencies: D = [d1, U E R to project each row of D and a vector 77 E R K for normalization, and apply SSVH. After V is obtained, how to estimate A requires some derivation. We relegate details to the supplement and only present the algorithm (A² is the N x K matrix of stacking together those az for j E S):
dn],, with d; N, We use a matrix
Algorithm 3: Semi Semi-super Topic Modeling
Input: K, D, and A Algorithm parameters: a matrix U E RRPX and a vector v) E IK
1. Compute 2j = U' D'Dee D'ez//n/U''D'' for 1 S j S p. Let X [Ti, [r,, uppl' E R and
let X N be the matrix of stacking the x; for i E S.
2. (SSVH). Apply Algorithm
| to (K, Xs, Aš) to obtain V and the intermediate quantity b. 3. Let B = ddiag()) ( Estimate A by Ā = DU DUB (BB'
Output: Å (its columns are the estimated topic vectors).
Theorem 4.2 (Validity of the algorithm). In the plStt model, write I = (n...., 7nl and Do = AA. Suppose the rank of Al' is K, and (U, is such that rank(U)= = K and J'U > 0.oor S S p. If we plug (K, Do: Ag) into Algorithm 3 then A = A.
5 Empirical Study
We evaluate the performance of our method, compare it with the unsupervised SP algorithm, and apply our method to the problems in Section 4
By default, we choose in our algorithm using the first PPV V|l K, where minimum is over row permutations.
approach there. We use the loss minp
Simulations: We fix n = 1000 and generate by first sampling its K entries independently from Uniform(0.9) 1.1) and then normalizing it so that [|b] 1. The diagonal elements of V are 1, and the off-diagonal entries are independently generated from Uniform(O, //) (we make the off-diagonal elements of V less than 1/K is to guarantee Ax-i(V) of 5 experiments by varying the label ratio |S|/n, noise level a, and dimension K, and 2 additional experiments comparing with unsupervised VH and studying the runtime.
O(1) when K is large). We consider total
8

---

Balanced Dirichlet
Dirichlet w/ Pure Points
Balanced Dirichlet
Dirichlet w/ P Pure Points
Growing K w/ P Pure Points
6gination
1.2
62
0.8
SP
2001
3.2
13
Rati
104
2.5
032
0.22
Label
0.23
0.54
0.23
0.22
0.23
Noss Levelo
0.23
0.54
0.25
1.05
Noise Level
2.04
5.5
Dimension
Figure 2: The influence of label ratio N/n, noise level o, and dimension K on error IV - VII "Balanced Dirichlet" and "Dirichlet w/ Pure Points" correspond to setting (1) and (2) respectively.
0.2) and con- sider two different settings for W: (1) all the rows of W are generated independently from Dirichlet(1/3, (3, 1/3, 1/3); (2) with k 1.2.... K, generate rows of Ws independently from the transformed Dirichlet distribution 0. 1/1 1/3. 1/3) + 0.9eg so that they are almost pure, set 30 rows of Wee to be C₁ so that they are pure, and finally generate all the other rows of W independently from D1richlet 1/3, 1/3). Setting (1) is more natural, but it does not guarantee the existence of pure points (i.e., T2 is equal to one vertex). In setting (2). we purposely add pure points. Once W is generated, we generate x, 's following Models ( In these two experiments, we vary the label ratio SS|/n from 1% to 5%. The results based on 100 repetitions are given in Figure [ In both experiments, with only very low label ratio, algorithm can greatly outperform the unsupervised VH algorithm, successive projection (SP).
Experiments 1-2, influence of data points distribution. We (K
Experiments 3-5, influence of noise level and data dimension. In experiment 3 and 4, we fix (K, [|/n)) (3, 0.03) and vary the noise level a. We still consider the two ways of generating W as in Experiments 1-2. As seen in Figure 2 as the noise level increases, the error of our method grows much slower than that of SP. In experiment 5, we study the influence of K. Fix a 0.2. As K increases, the number of vertices grows and it is reasonable to require more labeled points. We set |S] = 4K (e.g., when K = 3, the label ratio [S|/n = 0.012). For large K, it is likely that some vertices are far from all the observed points, rendering difficulty in identifying them. To prevent this, we generate W in the following way. With & = 1, 2.... K, we generate rows of Wss independently from the transformed Dirichlet distribution 0. 0.1irrichlet(1. (1x) rows of Ws independently from 0. D.Dirricheet (1x) ) 0.91 x/ K, set 10 rows of Wse to be cx. and finally generate all the other rows of W independently from Dirichlet (1x)). As in Figure 2 despite the high dimensionality, our method outperforms SP with only very few labeled points.
0.9eg, generate
Experiments 6, comparison with MVT and AA. In this experiment, with two NMF-based unsupervised methods: the minimum volume transformation (MVT, (8) and the archetypal analysis (AA) algorithm [16]. Different from SP, both approaches are anchor- free: MVT can leverage the data points on the boundary to locate the monimum-volune simplex, and AA focus the convex hull of the data cloud, minimizing the well-constructed distance between it and the estimated vertices. However, the two methods are restricted to utilizing only the convex hull information and rely on the assumption that the data points are scattered widely enough for the convex hull to cover most of the underlying simplex. Our method, conversely, can appropriately extract information from both the inner and boundary points. In this experiment, (K, S\/n) = (3, 0.03) and vary the noise level σr. Because both MVT and AA are anchor free, we adopt the same generation process of W in Experiment 1 so that there may not exist no pure nodes. The results based on 100 repetitions are exhibited in Table [ It illustrates that without leveraging the pure nodes, our method can outperform both of MVT and AA under various noise level.
compared our method
fix
Table 1: The median estimation error for SP, MVT, AA, and our method over 100 repetitions.
0.2
0.4
0.6
0.8
Ours
0.053
0.064
0.231
0.297
0.416
SP
0.319
1.712
4.438
8.404
13.37
MVT
0.191
0,38
0.39
0.427
0.522
AA
1.863
4.095
7.8
12.521
18.925
Experiments 7, runtime analysis. In this experiment, we study the runtime of SP, MVT, and our method as the dimension K grows. We adopt the same setting in experiment 5. The results aggregated from 100 repetitions are shown in Table 2] From the table, one can see that our method very computationally efficient compared to unsupervised approaches such as SP or MVT. Additionally,

---

Table 2: The mean runtime (in milliseconds) of SP, MVT, and our method over 100 repetitions. MVT is very cinemconuuming for large K, so the results are omitted.
K
3
9
12
15
18
21
24
27
30
Ours
3.22
3.22
3,45
3.81
3.71
3.98
4.1
5.44
4.92
4.52
SP 5.11
9.62
10.44
17.67
24.44
32.58
35.93
44.67
46.11
53.55
MVT 8489
>le4 >le4
>le4
>le4
>le4
>le4
>le4
>le4
>le4
as K scales up, the time complexity of unsupervised methods grows rapid, while our method maintains a low computation cost.
Network mixed-membershig estimation. We use a co-authorship network for statisticians [T8] with 2831 nodes and 71432 edges.
The node degrees range from 2 to 853, showing with severe hetero- geneity. Since there is no ground-truth membership, we conduct a semi-synthetic experiment where we first apply Mixed-SCORE [21) to cablirate the parameters K, P. 0 for DCMM and then generate synthetic networks with the estimated parameters. We set the label ratio N/n 0.05 and compare our algorithm with two unsupervised algorithm, SP and a de-noised variant of SP called SVS [21] (it has tuning parameter L, which is set L 10 x K). The median loss on estimating V over 100 repetitions is given in Table B] and the estimated simplexes by different methods in one repetition are shown in Figure (the points 2:.3s ' are obtained using the spectral projections in (I)). Additionally, we also evaluated the excess error of plugging in different VH algorithms into A estimating the mixed membership vectors compared with the ideal case where the vertices are known (the loss is the Frobenius error ||N TTll//VnK) In Table 3. we report the Excess Error: the loss by plugging in our SSVH estimate minus the loss by plugging in the true simplex.
Dracle
SP
SvS
Figure 3: Comparison of the true simplex (orange). SSVH estimate (blue), SP estimate (pink), and SVS estimate (red). The green points are the la- beled ones.
The median estimation error of the vertices for SP, SVS, and our method over 100 repetitions. The numbers in parentheses denote median absolute deviation [13] a robust statistics for variability.
Table 3:
Error in
Excess Error of II or
SP
SVS
Ours
SP
SVS 0.08 (0.0083)
Ours
Network
2.37 (0.26)
1.05 (0.14)
0.16 (0.04)
0.15 (0.024)
0.02 (0.0035)
Text Analysis
1.77 (0.12)
1.64 (0.II)
1.22 (0.46)
0.052 (0.014)
0.033 (0.0025)
0.031 (0.0047)
The processed word count provided by authors use a vocabulary of 2106 words. We further restrict to those abstracts whose total count on these 2106 words is at least 100. This results in 4 4129 documents. We fix K = 11 (following (23) and apply the algorithm in [25) calibrate model parameters (A, W). We then generate synthetic corpus matrices. We set the label ratio N/n = 0.05 and compare our algorithm with two unsupervised algorithms, SP and SVS. Since K is large, we set I. K + 5 SVS (the time complexity of the algorithm scales with (K)). We perform 100 repetition of the semi-synthetic experiments, and
Topic modeling, We use the academic abstracts in MADStat [23
compares the average estimation error of the vertices V|V V|l>/K K (up to permutation) for the three different methods. The results are displayed in Table 3 It can be seen that with only a small proportion of the label information, our method can greatly outperform the unsupervised methods. We also computed the Excess Error of plugging these algorithms into Algorithm 3 for estimating A (the loss is Frobenius error Á AlLF/ / K), and the results are in Table 3
Besides SP ans SVS, we also compare our method with novel unsupervised topic model estimation approach [1.. We use the same synthetic dateset and setting as the previous empirical study except setting the number of labeled nodes N = K + 1. The prior information within this scenario is extremely weak, barely equipping us with any knowledge above the unsupervised setting. Remarkably, over 100 repetitions, our method's 's median estimation error in V is 0.023, while the corresponding error of [14 is 0.030, which 30.4% higher than us. This illustrates the efficiency of our algorithm even with exceedingly low signal. We also implemented Seededl. DA [5), but the resulting error in A is very large (about 40 times larger than our method). The main reason is that seeded LDA assumes different model and is less valid in our scenario.
10

---

References
[1] Joshua Agterberg and Anru Zhang. Estimating higher-order mixed memberships via the 2-to- infinity tensor perturbation bound. (rXiv:2212.086422 2022.
[2] Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. Advances in neural information processing systems, 21, 2008.
[3] David Andrzejewski, Xiaojin Zhu, and Mark Craven. Incorporating domain knowledge into topic modeling via dirichlet forest priors. In Proceedings of the 26th annual international conference on machine learning, pages 25-32, 2009.
[4] Mário César Ugulino Araújo, Teresa Cristina Bezerra Saldanha, Roberto Kawakami Harrop Galvao, Takashi Yoneyama, Henrique Caldas Chame, and Valeria Visani. The successive projec- tions algorithm for variable selection in spectroscopic multicomponent analysis. Chemometries and intelligent laboratory systems, 57 2001.
[5] Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models-going beyond svd. In 2012 IEEE 53rd annual symposium on foundations of computer science, pages 1-10. IEEE, 2012.
[6] Richard F Betzel, Maxwell A Bertolero, and Danielle S Bassett. Non-assortative community structure in resting and task-evoked functional brain networks. bioRxiv, page 355016, 2018.
[7] David M Blei, Andrew Y Ng, and Michael Jordan. Latent dirichlet allocation. Journal of machine Learning research, (tti)):993--122220 2003.
[8] Maurice D Craig. Minimum-volume transforms for remotely sensed data. IEEE Transactions on Geoscience and Remote Sensing, 32(3):542-553 1994.
[9] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[10] Shusei Eshima, Kosuke Imai, and Tomoya Sasaki. Keyword-assisted topic models. American Journal of Political Science, 68(2):730-750, 2024.
[11] Nicolas Gillis and Stephen A Vavasis. Fast and robust recursive algorithms for separable non- negative matrix factorization. IEEE transactions on pattern analysis and machine intelligence. 36(4):698-714 -714, 2013.
[12] Thomas Hofmann. Probabilistic latent semantic indexing. In Proceedings of the 22nd annual international ACM SIGIR conference on Research and development information retrieval, pages 50-57, 1999.
[13] David C Howell. Median absolute deviation. Encyclopedia of statistics in behavioral science, 2005.
[14] Kejun Huang, Xiao Fu, and Nikolaos Sidiropoulos. Anchor-free correlated topic modeling: Identifiability and algorithm. Advances in Neural Information Processing Systems, 29, 2016.
[15] Jagadeesh Jagarlamudi, Hal Daumé III, and Rughavendra Udupa. Incorporating lexical priors into topic models. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 204-213, 2012.
[16] Hamid Javadi and Andrea Montanari. Nonnegative matrix factorization via archetypal analysis. Journal of the American Statistical Association, 116(530):896-907, 2020.
[17] Min Ji, Dawei Zhang, Fuding Xie, Ying Zhang, Yong Zhang, and Jun Yang. Semisupervised community detection by voltage drops. Mathematical Problems in Engineering, 2016, 2016.
[18] Pengsheng Ji and Jiashun Jin. Coauthorship and eitation networks for statisticians. The Annals of Applied Statistics, 10(4), December 2016.
[19] Yicong Jiang and Zheng Tracy Ke. Semi-supervised community detection via structural similarity metrics. The Eleventh International Conference on Learning Representations, 2022.

---

[20] Jiashun Jin. Fast community detection by SCORE. The Annals of Statistics, 43(1):57-89, 2015.
[21]
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Mixed membership estimation for social networks. Journal of Econometrics, 2023.
[22] Jiashun Jin, Gabriel Moryoussef, Zheng Tracy Ke, Jiajun Tang, and Jingming Wang. Improved algorithm and bounds for successive projection. International Conference on learning and representations, 2024.
[23] Zheng Tracy Ke, Pengsheng Ji, Jiashun Jin, and Wanshan Li, Recent advances in text analysis. Annual Review of Statistics and Its Application, 11(1):347-372, April 2024.
[24] Zheng Tracy Ke and Jiashun Jin. Special invited paper: The SCORE normalization, especially for heterogeneous network and text data. Star, 12(1):e545, 2023.
[25] Zheng Tracy Ke and Minzhe Wang. Using SVD for topic modeling. Journal of the American Statistical Association, 1196545):444449, 2024.
[26] Mingwei Leng and Tao Ma. Semi-supervised community detection: A survey. In Proceedings of the 2019 7th International Conference on Information Technology: loT and Smart City, pages 137-140, 2019.
[27] Chenliang Li, Shiqian Chen, Jian Xing, Aixin Sun, and Zongyang Ma. Seed-guided topic model for document filtering and classification. ACM Transactions on Information Systems (TOIS), 37(1):1-37, 2018.
(28) Dong Liu, Xiao Liu, Wenjun Wang, and Hongyu Bai. Semi-supervised community detection based on discrete potential theory. Physica Statistical Mechanics and its Applications, 416:173-182, 2014.
[29] Kamyar Moshksar. On the absolute constant in hanson- hanson-wright wright inequality, 2024.
[30] Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpreta- tion of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(4):1446-144) 2022.
[31] Mark Rudelson and Roman Vershynin. Hanson-Wrääs inequality and sub-gaussian concentra- tion. arXiv e-prints, page urXiv:1306.228 June 2013.
[32] Michael E Winter. N-FINDR: An algorithm for fast autonomous spectral end-member determi- nation hyperspectral data. In Imaging spectrometry V, volume 3753, pages 266-275. SPIE, 1999.
[33] Liang Yang, Xiaochun Cao, Di Jin, Xiao Wang, and Dan Meng. A unified semi-supervised community detection framework using latent space graph regularization. IEEE Transactions on Cybermetics, ():25)5):22258 2015.
[34] Yuan Zhang, Elizaveta Levina, and Ji Zhu. Detecting overlapping communities in networks using spectral methods. SIAM Journal on Mathematics of Data Science, 2(2):265-283, 2020.
[35] Kuang Zhou, Arnaud Martin, Quan Pan, and Zhunga Liu. Selp: Semi-supervised evidential label propagation algorithm for graph data clustering. International Journal of Approximate Reasoning, 92:139- 154, 2018
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly explained the contributions of the paper in Section T using bullets points. We also presented detailed related work review and emphasize the gap in the current literature.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We summarize our novel semi-supervised vertex hunting algorithm; also, we discuss the limitations and future extensions of our work in Appendix H
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: We provide full set of assumptions, Assumption 3.3 in Section 3 We provide complete proof of all the theorems and lemmas in the supplemental material. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We disclose all the information needed to reproduce our experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
The data and code for our experiments are available in the supplementary materials.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: the experiment details, such as the parameters/simulation settings we choose, available in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the error bars of our result in Tjile the form of median absolute deviation (MAD) (13). We use this robust statisties for error bar alleviate the effect of extreme cases in the experiments where all of or most of the methods perform very poorly.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Our experiments do not require any computer resources. All the experiments in paper be implemented personal computer.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppppp//.aaapppp..cpppppbbeeac
Answer: [Yes]
Justification: We strictly conform the NeurlPS Code of Ethics, without any form of plagia- rism or the use LLM models.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: As illustrated in Section 4 our method can be applied to both network and text analysis, providing positive social impact. We discuss the possible social impact of our algorithm in Appendix [
16

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper proposes a vertex hunting problem, which we do not think has any risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have cite the sources of the data we use, 18
23 in Section 5
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
17

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The details of our method is well explained in Section 2 and the code for our algorithm is available in the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our paper does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurd) auttep://eearrppcccc///ooeeeeeer /ct//////oeeeeeece/22////..... for what should or should not be described.
19


Reviews:
[{"review_id": "aXOuCQzrYL", "reviewer": "Reviewer_GfMr", "summary": "This paper introduces semi-supervised vertex hunting (SSVH), an extension of the classical vertex hunting problem that incorporates partial label information. The key technical contribution is establishing an interesting connection between the eigenvector of zero eigenvalue for a constructed matrix and the unknown parameter $b$, leading to a clean optimization-free approach for estimating $b$. The paper provides theoretical guarantees showing improved convergence rates compared to unsupervised methods and demonstrates applications in network mixed membership estimation and topic modeling. The method is validated on both synthetic and real datasets, with empirical results showing consistent improvement over baseline methods.", "questions": "1. 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.\n\n2. 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?\n\n3. The paper should compare with state-of-the-art anchor-free approaches that don't require pure nodes. While the NeurIPS 2016 paper is one example, there are more recent developments in this area that should be considered.\n\n4. The sub-gaussian noise assumption needs justification in the context of specific applications. What is the nature of noise in network mixed membership estimation and topic modeling? Is this assumption reasonable in these settings?\n\n5. In real-world applications, there is likely to be noise in the labels or known membership vectors themselves. How does label noise affect the theoretical guarantees?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n- The paper is technically sound with complete proofs and clear assumptions.\n- The connection between the eigenvector of zero eigenvalue for the constructed matrix $M(\\alpha)$ and the unknown transformation vector $b$ is interesting, leading to a clean optimization-free approach.\n- The paper provides good reproducibility with code provided.\n\n### Weaknesses:\n\n- For vertex hunting problems, having information about the position/membership of even a few points naturally makes the identification problem much easier, so the improved performance is not surprising.\n- The theoretical analysis focuses on the entire $V$ matrix, while recent literature emphasizes row-wise bounds.\n- The literature review is insufficient and misses critical prior work. For example, \"Anchor-free Correlated Topic Modeling: Identifiability and Algorithm\" in NeurIPS 2016 and its follow-ups are not discussed, despite being highly relevant as they solve similar problems without requiring pure nodes.\n- The paper lacks theoretical guarantees specific to the applications (network mixed membership and topic modeling)\n- The notations are messy and sometimes confusing, making it difficult to follow the transitions between different problem settings.\n- The empirical evaluation could be more comprehensive with additional modern baselines, and some experimental results need to be clarified or simplified for better interpretation (will raise in Questions session).", "was_revised": true, "final_justification": "After careful consideration of the paper, reviews, and author rebuttal, I revise my recommendation to borderline accept.\n\nIssues Resolved:\n1. Theoretical framework and proofs were clarified and strengthened with noise assumptions\n2. Additional baselines (MVT, AA) were added for comparison\n\nIssues Remaining Unresolved:\n1. While a faster rate than unsupervised methods is shown, there's no proof of optimality or lower bound for semi-supervised setting, making it hard to justify the claimed difficulty of achieving such rates\n2. Despite adding comparisons with anchor-free methods, the possibility of adapting these methods to leverage labeled points is not thoroughly addressed\n3. Limited real-world validation as experiments rely heavily on synthetic/semi-synthetic data", "rebuttal": "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. \n\n**1. Comparison with the literature, especially the anchor-free approach.**\n\nSince 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:  \n- *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. \n- *Different methods*: The anchor-free approach solves a non-convex optimization and requires an iterative algorithm to solve, while our approach is optimization-free. \n- *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. \n\nIn 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.\n\n**2. Additional baselines.**\n\nWe 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. \n\nThe 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. \n\n| Method | Ours | SP | MVT | AA |\n| --- | --- | --- | --- | --- | \n| $\\sigma=0.2$ | 0.053  | 0.319 |   0.191 | 1.863 |\n| $\\sigma=0.4$ |  0.064 |  1.712 | 0.380  | 4.095 |\n| $\\sigma=0.6$ | 0.231  | 4.438 |  0.390 | 7.800 |\n| $\\sigma=0.8$ | 0.297 | 8.404 | 0.427  |  12.521 |\n| $\\sigma=1$ |  0.416 | 13.37 |  0.522 | 18.925  |\n\nWe 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. \n\n**3. Numerical comparison with the 2016 NeurIPS paper.**\n\nThanks for pointing out this interesting reference. Before presenting the numerical results, we'd like to clarify two points:\n - *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. \n- *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). \n\nSince 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. \n\n| Method | Ours  | Anchor-free |\n| ------ | ------ | ----- |\n| **Error**  | 0.023 (0.005)  | 0.030 (0.001) |   \n\n**4. Labeling ratio.**\n\n*\"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?\"*\n\nWe 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: \n- 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. \n- In our newly added topic modeling experiment (see Point 3 above), we only pick $N=12(=K+1)$ labeled points. \n\n**5. Justification of the sub-Gaussian noise assumption in applications.**\n\nThis 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,$$\n\nwhere $\\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. \n\n**6. How does label noise affect the theoretical guarantees?**\n\nYes, 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$$N^{-1/2}\\| \\widehat{\\Pi}_S-\\Pi_S \\|.$$ \n\nNotably, this term will not explode as $N$ increases, so our method still enjoys a good error rate. \n\n**7. Row-wise bounds.**\n\n *\"The theoretical analysis focuses on the entire $V$ matrix, while recent literature emphasizes row-wise bounds.\"*\n\nOur 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$,  \n\n$$\\| \\hat{v}_k-v_k \\| = \\|(\\widehat{V}-V) e_k\\| \\leq  \\text{SpectralNorm}(\\widehat{V}-V).$$\n\nSince our theory bounds the spectral norm of $\\widehat{V}-V$, it automatically implies the row-wise bounds.   \n\n\n**8. Why SP has a worse performance even with pure points.**\n\n*\"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.\"*\n\nAs 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. \n\nYes, we will add error bars in the revision. Thanks for this suggestion.  \n\n**9. Other clarifications.**\n\n*\"Having information ... makes the identification problem much easier, so the improved performance is not surprising.\"*  \n\nAlthough 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.  \n\n*\"The paper lacks theoretical guarantees specific to the applications\"*\n\nWe did provide theorems for both applications. Please see Theorem 4.1 and Theorem 4.2."}, {"review_id": "lLhAvehFmu", "reviewer": "Reviewer_qLyi", "summary": "The paper proposes a vertex hunting algorithm in semi-supervised setting where the membership information of a few number of data points/nodes are known. This is an extension to unsupervised vertex hunting algorithms which typically rely on stringent conditions to work. The idea stems from utilizing the projection matrices derived from the membership vectors and hence proposing an optimization-free estimation of the vertices. This also allows them to provide nice theoretical support to their approach. Synthetic and semi-synthetic experiments in community detection and topic modeling are presented to evaluate the proposed approach.", "questions": "Questions/Comments:\n\n1.\tVertex hunting has close connections to structured matrix factorization (SMF) and nonnegative matrix factorization (NMF).  \n\n2.\tModel 2 is the backbone of the proposed framework. But, in my opinion, a solid justification for this model is not presented. Why is Model 2 is intuitive in real settings?\n\n3.\tThe uniqueness result in Theorem 2.2 looks very stringent. Under what settings $M(\\alpha)$ is a one-dimensional subspace? The identifiability (uniqueness) conditions of SP algorithm, for instance, can have nice practical interpretation in community detection and topic modeling. But, here, such interpretation is missing.\n\n4.\tAlso, $\\Sigma(\\alpha)$ needs to be $K-1$-dimensional. Under what conditions, it can be satisfied or violated in practical settings. Some discussion and intuitions might help to understand the strictness of these conditions.\n\n5.\tTheorem 4.1 and Theorem 4.2 demand an exact recovery. Do these theorems require the uniqueness conditions in Theorem 2.2 to be satisfied?\n\n6.\tIn 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.\n\n7.\tSome minor comments:\n\na.\tV is not introduced in line 68\n\nb.\t$\\Pi_S$ is not explicitly defined in Eq. (3) \n\nc.\tin line 147, bing -> “being”", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper is well-written with nice theoretical support of the proposed framework.\n\n2.\tThe work can inspire follow up research in the field of structured matrix factorization and nonnegative matrix factorization in semi-supervised, noisy settings.\n\nWeaknesses:\n\n1.\tLimited empirical evaluation and comparison. There are many recent community detection and topic modeling methods. Only SP and SVS are employed in the study.", "was_revised": true, "final_justification": "The authors have addressed my concerns over some of the theoretical claims and questions over initializing the algorithm in practically feasible way. Overall, I liked the idea and how the work promotes the structured matrix factorization for weekly supervised settings. Hence, I keep my score on accepting the paper.", "rebuttal": "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. \n\n**1. Empirical evaluation and comparison.**\n\n*\"There are many recent community detection and topic modeling methods. Only SP and SVS are employed in the study.\"* \n\nIn 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). \n\nAdditionally, 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. \n\n| Method | Ours | SP | MVT | AA |\n| --- | --- | --- | --- | --- | \n| $\\sigma=0.2$ | 0.053  | 0.319 |   0.191 | 1.863 |\n| $\\sigma=0.4$ |  0.064 |  1.712 | 0.380  | 4.095 |\n| $\\sigma=0.6$ | 0.231  | 4.438 |  0.390 | 7.800 |\n| $\\sigma=0.8$ | 0.297 | 8.404 | 0.427  |  12.521 |\n| $\\sigma=1$ |  0.416 | 13.37 |  0.522 | 18.925  |\n\nWe 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. \n\n**2. Justification of Model (2).**\n\nFor 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:\n$$\\hat{r}_i = U'Ae_i/\\eta'U'Ae_i, \\qquad 1\\leq i\\leq n.$$\n\nHere, $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\n$$r_i = U'\\Omega e_i/\\eta'U'\\Omega e_i, \\qquad 1\\leq i\\leq n.$$\n\nIn 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 \n$$r_i = Vw_i, \\quad \\mbox{with}\\quad w_i = (b\\circ \\pi_i)/\\|b\\circ \\pi_i\\|_1.$$ \n\nThis is exactly Model (2).  \n\nFor 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). \n\nWe 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. \n\n**3. The uniqueness result in Theorem 2.2 and the conditions on $\\Sigma(\\alpha)$.** \n\n*\"Under what settings $M(\\alpha)$ is a one-dimensional subspace?\"*\n\nBy our Theorem 2.2, $M(\\alpha)$ has a one-dimensional null space if $\\Sigma(\\alpha)$ has a rank $(K-1)$. \n\n*\"$\\Sigma(\\alpha)$ needs to be $(K-1)$-dimensional. Under what conditions, it can be satisfied or violated in practical settings.\"*\n\nIn 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)$:\n- $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)$. \n- 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).\n\n**4. Using our method to initialize other algorithms**\n\n*\"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.\"*\n\nSP 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. \n\n| Method | Error |\n| --- | -- |\n|Ours | 0.053 |\nMVT (constant initialization + 4 iterations) | 0.255 |\nMVT (constant initialization + 8 iterations) | 0.177 |\nMVT (our initialization + 4 iterations) | 0.114 |\nMVT (our initialization + 8 iterations) | 0.223 |\n\nWhen 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."}, {"review_id": "qM7YXFVg4z", "reviewer": "Reviewer_EEzx", "summary": "The paper addresses the \"vertex hunting\" problem. This is the problem of identifying the corners of a simplex, given observations consisting of points in the simplex. The particular variant studied in the paper is a semi-supervised version of the problem, where coordinates are provided for a subset of the observations, however, the observed coordinates are given in a different format. The problem formulation also allows for noise in the observations. The main contribution of the paper is the novel problem formulation and a method for solving the problem. It is also shown how to use the formulation in applications of community detection in network analysis and in topic modeling for document analysis.", "questions": "I would like to see further justification about the motivation of the problem, in particular about the exact formulation of the semi-supervised setting, involving the unknown vector b.", "limitations": "There is a minimal discussion on limitations on Appendix H which is rather discussion on future work.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The main strengths of the paper are the following: \nS1. A new interesting problem formulation is introduced for vertex hunting in a semi-supervised setting.\nS2. The problem is solved using a tools from linear algebra. The error-free as well as the noisy version of the problems are analyzed and closed-form solutions are given. \nS3. The proposed algorithm is analyzed theoretically, error bounds are provided, and sensible assumptions on the input data are identified for which the theoretical results hold.\nS4. Interesting use cases are identified and tested empirically in network analysis and document analysis.\nThe main weakness of the paper is that: \nW1. the problem is not so well motivated. In particular, the problem of connecting the observed coordinates \\pi_i with the barycentric coordinates w_i, via the vector b, seems quite artificial. In some sense the problem seem a bit reversed engineered to fir the solution, rather than the other way around.", "was_revised": true, "final_justification": "My main question was about the motivation of the problem, and the authors provide a satisfactory answer in the rebuttal. I upgrade my score to borderline accept, but my confidence is low, and I am not willing to champion the paper in the discussion.", "rebuttal": "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. \n\n**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. \n\nModel (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. \n\n**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. \n\nIn summary, Model (2) was not proposed by us. It was already discovered in the previous literature, although not highlighted there."}, {"review_id": "OSgdxrtDLB", "reviewer": "Reviewer_AVSi", "summary": "This paper introduces a novel problem formulation called Semi-supervised Vertex Hunting (SSVH), a variant of the classical vertex hunting (VH) problem, which seeks to estimate the vertices of a simplex from noisy data points. In SSVH, the semi-supervised setting assumes partial side-information about some points' barycentric coordinates, though only up to an unknown element-wise scaling (Hadamard product with an unknown positive vector b).\n\nThe authors propose an optimization-free method for estimating b, based on a clever construction of an eigenvalue problem leveraging projection matrix properties. Once b is estimated, existing VH methods can be enhanced by incorporating the supervised points.\n\nTheoretical contributions include an explicit error bound for SSVH under sub-Gaussian noise, showing faster convergence compared to existing unsupervised VH approaches. Practical applications to semi-supervised mixed-membership estimation in networks and semi-supervised topic modeling are demonstrated, with empirical results on synthetic and semi-synthetic datasets showing significant improvements over baselines.", "questions": "The method is claimed to handle large K better than SP and MVT, but no wall-clock time comparisons or runtime analysis is provided. Could the authors report the computational cost (both theoretically and empirically) as K increases?\n\nSection 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?\n\nIn applications, the quality of the semi-supervised labels may vary — especially if derived heuristically. Could the authors study the impact of noisy or imperfect side information on SSVH's performance?\n\nThe paper focuses on networks and text analysis. Are there other promising domains where SSVH could be applied? A discussion of potential broader applicability would be appreciated.\n\nThe experimental comparison mainly uses SP and SVS. Could the authors also compare against modern NMF-based VH variants to further demonstrate superiority?", "limitations": "The authors explicitly discuss limitations in Appendix. Moreover, the theoretical analysis clarifies conditions under which the method works well (Assumptions 3.1–3.3), and the empirical results demonstrate that the method is not brittle. Some points that could be highlighted even more explicitly:\n\nThe method depends on the spread and coverage of the labeled set S. If S is highly unbalanced or missing key regions of the simplex, performance may degrade.\n\nAssumes the model of barycentric coordinate transformation (Eq. 2) holds; when this model is violated, behavior is not analyzed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is technically strong, with a novel and theoretically sound contribution. The idea of using an optimization-free estimation of b via properties of projection matrices is elegant and well-justified. Proofs are complete and provided in the supplementary material.\n\nThe paper is very clearly written. The introduction does an excellent job motivating the problem and situating it within both VH literature and applications in network and text analysis. The key technical insights are well-explained.\n\nThe proposed SSVH method addresses key limitations of existing VH methods—sensitivity to identification conditions, inability to leverage semi-supervised labels, and poor scaling in K. The paper shows strong potential impact for network community analysis and topic modeling — two high-visibility applications.\n\nThe work is original in both its problem formulation (semi-supervised vertex hunting with transformed barycentric coordinates) and its methodological solution (optimization-free eigen-based estimation). To my knowledge, no prior work provides this perspective on integrating side information into VH.\n\nWeaknesses:\n\nThe empirical section, while providing clear gains, could be strengthened by including more real-world datasets. Both network and text experiments rely on semi-synthetic settings where the ground truth is known through re-simulation; it would be valuable to show performance on unmodified real datasets where only partial labels are available.\n\nThe 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.\n\nThe dependence of the error bound on the choice of α is somewhat under-explored empirically. While two closed-form solutions are proposed, it would help to see how sensitive performance is to these choices.", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n**1. Runtime analysis.**\n\nFollowing 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. \n\n| K  | 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 | 30 |\n| -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |\n| Ours (millisecond) | 3.22 | 3.22 | 3.45 |  3.81 | 3.71 | 3.98 | 4.10 | 5.44 |  4.92 | 4.52 |\n| SP (millisecond) | 5.11 | 9.62 | 10.44 |  17.67 | 24.44 | 32.58 | 35.93 | 44.67 |  46.11 | 53.55 |\n| MVT (millisecond) | 8489 |\n\nOur 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.\n\nThe 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)$. \n\n\n**2. Selection of $\\alpha$.**\n\n*\"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?\"*\n\nThis 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:  \n\n| $\\alpha$-choice | Approach 1 | Approach 2 | Approach 1(perturbed) | \n| -- | -- | -- | -- |\n| Error | 0.0260 | 0.0229 | 0.0265 |\n\nIn this example, there is no big difference between the two approaches. Additionally, the results are robust to perturbation of $\\alpha$. \n\nSecond, we explain why we presented two approaches. \nApproach 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. \n\nAs 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.  \n\n**3. The impact of noisy or imperfect side information.**\n\nYes, 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$$N^{-1/2}\\| \\widehat{\\Pi}_S-\\Pi_S \\|.$$ \n\nNotably, this term will not explode as $N$ increases, so our method still enjoys a good error rate.\n\n**4. Comparison with modern NMF-based VH variants.**\n\nWe 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. \n\n| Method | Ours | SP | MVT | AA |\n| --- | --- | --- | --- | --- | \n| $\\sigma=0.2$ | 0.053  | 0.319 |   0.191 | 1.863 |\n| $\\sigma=0.4$ |  0.064 |  1.712 | 0.380  | 4.095 |\n| $\\sigma=0.6$ | 0.231  | 4.438 |  0.390 | 7.800 |\n| $\\sigma=0.8$ | 0.297 | 8.404 | 0.427  |  12.521 |\n| $\\sigma=1$ |  0.416 | 13.37 |  0.522 | 18.925  |\n\nWe 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.\n\n**5. Combination with optimization-based VH.**\n\n*\"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.\"*\n\nWe 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. \n\n\nWe 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:  \n\n| Method | Error |\n| --- | -- |\n|Ours | 0.053 |\nMVT (constant initialization + 4 iterations) | 0.255 |\nMVT (constant initialization + 8 iterations) | 0.177 |\nMVT (our initialization + 4 iterations) | 0.114 |\nMVT (our initialization + 8 iterations) | 0.223 |\n\nWhen 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.\n\n**6. Other promising domains where SSVH could be applied.**\n\nOur 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. \n\n**7. Unmodified real datasets.**\n\n*\"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.\"*\n\nWe 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."}]

Author rebuttal:

Meta-review: The paper introduces semi-supervised vertex hunting (SSVH), where some data points come with barycentric coordinates known only up to an unknown transformation. It proposes a linear-algebraic method with provable guarantees built on properties of orthogonal projection matrices to estimate the underlying simplex. The authors present practical, scalable algorithms for mixed-membership networks and topic modeling. The reviewers appreciated the solid theoretical guarantees and the clear exposition. For the camera-ready, the authors should incorporate the rebuttal clarifications and added experiments, and expand the unsupervised VH literature review. I am including some references from my discussion with some of the reviewers here - 
1. “Detecting overlapping communities in networks using spectral method”, SIAM Journal of Mathematics of Data Science, 2020 (see citations 3, 30, 31, 33, 39–41 in the journal version);
2. “Anchor-Free Correlated Topic Modeling: Identifiability and Algorithm,” NeurIPS 2016;
3. “A statistical interpretation of spectral embedding: the generalized random dot product graph,” JRSS-B, 2022.
Decision: Accept (poster)