CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
News and Events
Related Activities
Related Links
Outreach Roadshow

Workshop on Graph Partitioning in Vision and Machine Learning

January 9-11, 2003, Carnegie Mellon University
OPEN PROBLEMS (add more!)
PHOTOS (presentations, dinner at Danny Sleator's house)

Graph cuts and separators of various forms have a long history in Algorithms. More recently, they have been used in Computer Vision for problems of image segmentation and data cleaning, among others. In Machine Learning, there has been increasing interest in problems of learning from labeled and unlabeled data, as well as probabilistic inference when data have pairwise relationships, that seem closely related to notions of graph partitioning. However, in each area, the objectives are subtly different, and it's not always clear how to best formalize them. The purpose of this workshop is to bring together researchers in Algorithms, Vision, and Machine Learning around the subject of graph partitioning and other graph algorithms, in order to discuss and better understand the connections between these problems and the techniques used to solve them. The workshop will be a combination of survey talks, new results and informal discussion. We intend to have all talk slides available on the web, as well as pointers to relevant papers and open problems.

Organizing committee: Avrim Blum, John Lafferty, Jon Kleinberg, Jianbo Shi, Eva Tardos, Ramin Zabih

NOTE: All events now in NSH 3305

Day 1: (January 9)
Hour Speaker Title
9:00 Bagels and coffee
9:30 Avrim Blum Introduction; graph partitioning for machine learning [ppt, html, pdf]
10:00 Ramin Zabih Recent Developments in Graph-Based Energy Minimization for Computer Vision
10:30 Break + DISCUSSION SESSION. Chair: Avrim Blum
11:30 Moses Charikar Compact Representation Schemes from Rounding Algorithms [pdf]
12:00 Shang-Hua Teng Spectral Methods, Graph Partitioning, and Clustering [pdf]
12:30 Lunch
2:00 Tom Mitchell Learning about WebSite-Specific Graph Structure [ppt, html]
2:30 Bob Murphy Location Proteomics: Determining an Optimal Partitioning of Proteins based on Subcellular Location
3:00 Break + DISCUSSION SESSION. Chair: Jon Kleinberg
4:00 Jianbo Shi Finding (Un)usual Events in Video [ppt] [papers]
4:30 Dan Huttenlocher Pictorial Structures for Object Recognition
5:00 Olga Veksler Compact Windows for Visual Correspondence via Minimum Ratio Cycle Algorithm [ppt, html]
5:30 DISCUSSION SESSION. Chair: Ramin Zabih


Day 2: (January 10)

Hour Speaker Title
9:00 Bagels and coffee
9:30 Christos Faloutsos Data mining large graphs [ppt, html, pdf]
10:00 Jon Kleinberg An Impossibility Theorem for Clustering
10:30 Break + DISCUSSION SESSION. Chair: Eva Tardos
11:30 David Karger Learning Markov Random Fields: Maximum Bounded-Treewidth Graphs
12:00 John Lafferty Random Walks, Random Fields, and Graph Kernels [ps, pdf]
12:30 Lunch
2:00 Yuri Boykov Cut Metrics and Geometry of Grid Graphs [ppt, html] [paper 1]
2:30 Henry Schneiderman Object Recognition using Graphical Models to Exploit Sparse Structuring of Statistical Dependency
3:00 Break + DISCUSSION SESSION. Chair: Jianbo Shi
4:00 Jerry Zhu Semi-Supervised Learning with Label Propagation [pdf]
4:30 Thorsten Joachims Transductive Learning, Leave-One-Out, and Cuts
5:00 John Langford Nonlinear dimensionality reduction [ps, pdf]
5:30 DISCUSSION SESSION. Chair: John Lafferty


Day 3: (January 11)

Hour Speaker Title
9:00 Bagels and coffee
9:30 Tom Dietterich Fitting Conditional Random Fields via Gradient Boosting [ps, pdf]
10:00 Short (15-min) Talks
Vladimir Kolmogorov What energy functions can be minimized by graph cuts?
Pedro Felzenszwalb Efficient graph-based image segmentation.
Zoubin Ghahramani Learning from Labeled and Unlabeled Data using Markov Random Fields [pdf]
Shuchi Chawla Learning using Graph Mincuts [ppt, html]
Stella Yu Cuts with Constraints [pdf]




This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation