Research map / Graph learning / Graph algorithms and clustering
Clustering from General Pairwise Observations with Applications to Time-varying Graphs
Shiau Hong Lim, Yudong Chen, Huan Xu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MLE weights instead of linear or uniform weights (ablation) | convex clustering (Algorithm 1) · Sparse planted partition graphs (n=200, n=1000) | full recovery rate | Improved |
| use linear weights instead of MLE weights (ablation) | convex clustering (Algorithm 1) · Dense planted partition graphs | full recovery rate | Mixed |
| use negative (conservative) deviation of weights from the MLE mean (ablation) | convex clustering with inexact weights · Gaussian labels (n=200, 8 clusters, mu=2 and 1.5) | full recovery rate | Improved |
| add random noise in [-Delta, Delta] to the MLE weights (ablation) | convex clustering · Gaussian labels (n=200, 8 clusters) | full recovery rate | Hurt |
| increase cluster size K with total nodes fixed (ablation) | convex clustering · Planted partition (n=400) | full recovery rate | Improved |
| make observations highly certain instead of 0.7-reliable (ablation) | convex clustering · Partial observations, n=600 to 2400, K=150 | fraction of observed entries for 90% recovery: 0.7 reliable: linear in n; certain: sub-linear in n | Improved |
| add more snapshots T (ablation) | convex clustering on time-varying graphs · Independent and Markov snapshots (n=200, 8 clusters) | full recovery rate | Improved |
| replace evolutionary spectral clustering with the convex program | time-varying graph clustering (T=1,2,3) · Synthetic time-varying graphs (fully observed) | pairwise error rate: higher computational cost | Improved |
| use Markov snapshot model instead of independent or union models (ablation) | convex clustering · Reality Mining (n=85, 14 weekly snapshots) | pair accuracy | Improved |
| replace Markov convex method with evolutionary spectral clustering | Reality Mining clustering · Reality Mining (n=85) | pair accuracy | Improved |
Closest papers by meaning
- Generalized Probabilistic Graphical Modeling for Multi-View Bipartite Graph Clustering (TPAMI 2025 · similarity 0.91)
- Multi-View Stochastic Block Models (ICML 2024 · similarity 0.89)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.88)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.88)
- Local Graph Clustering with Noisy Labels (ICLR 2024 · similarity 0.87)
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.
