Constrained Rank Aggregation and Correlation Clustering

on YouTube ↗25m

" summary

Proposes a correlation‑clustering variant that lets negative edge weights be arbitrarily large to enforce mutual exclusivity, adds per‑vertex penalties to enforce soft size bounds, and uses an LP relaxation plus a thresholded rounding step (alpha solved from a cubic) to get constant‑factor approximations (practical ratios around 6). Applies methods to TCGA breast cancer data (after filtering ~9,000→~600 genes) and recovers subtype‑specific modules (e.g., kinase vs CDH1 groups) from 504 patients, while greedy CCpivot performs poorly.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 1:57Mathematical Collaboration Communities
3. 2:12New Functional Community Detection Paradigm
4. 4:31Community Detection via Correlation Clustering?
5. 6:10Correlation Clustering: Basics
6. 7:27Extensions of the Basic Model: Edge Weights
7. 9:10Is Correlation Clustering Suitable for Cancer Genomics?
8. 10:59Correlation Clustering: Our Contributions
9. 11:31CGW Algorithm - Step 1: LP Relaxation
10. 14:31CGW Algorithm - Step 2: Rounding Up
11. 15:44Extensions: Size Constraints and New Weights
12. 16:53The New Algorithm: LP Part
13. 17:20The New Algorithm: Rounding Up Part
14. 18:49What is the Approximation Ratio?
15. 19:40Changing the Rounding Up Procedure
16. 20:12Other Extensions: Randomized Algorithms a la C-PIVOT
17. 20:23Proof Techniques
18. 20:34Some Results on Cancer Modules

" related talks

• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 37mPower to the Points: Local Certificates for ClusteringsSuresh Venkatasubramanian · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 40mTesting Correlation of Unlabeled Random GraphsJiaming Xu · Computational Phase Transitions (Simons Institute, 2020)
• 38mMixed and Covariate-Dependent Graphical ModelsLiza Levina · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 46mEliciting and Enforcing Subjective Individual FairnessAaron Roth · Recent Developments in Research on Fairness 2019
• 38mThe Impact of Regularization in Spectral ClusteringBin Yu · Spectral Algorithms: From Theory to Practice 2014