Research map / Learning theory and algorithms / Matrix and tensor methods
Semi-supervised Vertex Hunting, with Applications in Network and Text Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces semi-supervised vertex hunting (SSVH), estimating simplex vertices from noisy data plus partial barycentric coordinates via an optimization-free eigenvector estimate of an unknown weight vector b, and applies it to semi-supervised mixed membership estimation and topic modeling.
Problem
Vertex hunting (estimating simplex vertices from noisy points) becomes hard to extend when partial soft-label information is available only up to an unknown positive transformation b; existing unsupervised VH methods cannot use it and have non-decaying error rates.
Approach
Estimate the unknown transformation b as the smallest eigenvector of a K x K matrix built from orthogonal projections of the labeled points' pi-vectors, avoiding optimization; then recover barycentric coordinates and vertices by regression, yielding error that decays with the number of labeled points.
Key results
- In simulations with 5 percent labeled points and noise sigma=0.2 to 1, SSVH median vertex error is 0.053 to 0.416 versus 0.319 to 13.37 for SP, and beats MVT and AA at all noise levels.
- On semi-synthetic network data (label ratio 0.05), SSVH vertex error is 0.16 versus 1.05 for SVS and 2.37 for SP.
- Runtime at K=30 is about 4.5 ms for SSVH versus 53.6 ms for SP, while MVT exceeds 10 seconds for K>=6.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SSVH instead of SP for vertex hunting | Synthetic VH with varying noise σ · Synthetic VH (σ=0.2, 0.4, 0.6, 0.8, 1) | median estimation error: 0.319 -> 0.053; 1.712 -> 0.064; 4.438 -> 0.231; 8.404 -> 0.297; 13.37 -> 0.416 | Helped |
| Use SSVH instead of MVT for vertex hunting | Synthetic VH with varying noise σ · Synthetic VH (σ=0.2, 0.4, 0.6, 0.8, 1) | median estimation error: 0.191 -> 0.053; 0.38 -> 0.064; 0.39 -> 0.231; 0.427 -> 0.297; 0.522 -> 0.416 | Helped |
| Use SSVH instead of AA for vertex hunting | Synthetic VH with varying noise σ · Synthetic VH (σ=0.2, 0.4, 0.6, 0.8, 1) | median estimation error: 1.863 -> 0.053; 4.095 -> 0.064; 7.8 -> 0.231; 12.521 -> 0.297; 18.925 -> 0.416 | Helped |
| Use SSVH instead of the strongest baseline, SVS, for vertex hunting | Semi-supervised network mixed-membership estimation · Network mixed-membership estimation | vertex estimation error: 1.05 (0.14) -> 0.16 (0.04) | Helped |
| Use SSVH instead of the strongest baseline, SVS, for membership estimation | Semi-supervised network mixed-membership estimation · Network mixed-membership estimation | excess membership error: 0.08 (0.0083) -> 0.02 (0.0035) | Helped |
| Use SSVH instead of the strongest baseline, SVS, for vertex estimation | Semi-supervised topic modeling · Text analysis | vertex estimation error: 1.64 (0.11) -> 1.22 (0.46) | Helped |
| Use SSVH instead of the strongest baseline, SVS, for topic estimation | Semi-supervised topic modeling · Text analysis | excess topic error: 0.033 (0.0025) -> 0.031 (0.0047) | Helped |
| Use the proposed method instead of the unsupervised topic model baseline | Semi-supervised topic modeling with N = K + 1 · Synthetic topic modeling | median estimation error in V: 0.030 -> 0.023 | Helped |
| Use SSVH instead of SeededLDA | Semi-supervised topic modeling · Synthetic topic modeling | error in A: about 40 times larger than our method | Helped |
Surprising findings
- With only K+1 labeled nodes, SSVH still improves on a recent unsupervised topic model estimator (vertex error 0.023 vs 0.030).
Limitations
- Theory relies on sub-Gaussian noise and on assumptions on the spread of labeled points and the matrix Sigma(alpha) rank.
- Semi-supervised topic modeling and network results are on semi-synthetic data calibrated from real datasets rather than real labels.
Experimental setup
Datasets: co-authorship network of statisticians (2831 nodes, 71432 edges) MADStat academic abstracts
Benchmarks: simulated vertex hunting semi-synthetic network mixed membership semi-synthetic topic modeling
Metrics: estimation error of vertices (Frobenius/K, permutation-minim excess error of membership or topic estimates runtime in milliseconds
Baselines: successive projection (SP) SVS minimum volume transformation (MVT) archetypal analysis (AA) SeededLDA
Builds on: successive projection minimum volume transformation Mixed-SCORE degree-corrected mixed membership model pLSI
Closest papers by meaning
- A Flexible Generative Framework for Graph-based Semi-supervised Learning (NeurIPS 2019 · similarity 0.83)
- Improved algorithm and bounds for successive projection (ICLR 2024 · similarity 0.83)
- Exact Combinatorial Multi-Class Graph Cuts for Semi-Supervised Learning (AAAI 2026 · similarity 0.83)
- Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks (ICML 2024 · similarity 0.82)
- Fast Algorithms for Hypergraph PageRank with Applications to Semi-Supervised Learning (ICML 2024 · similarity 0.82)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.