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.
Day 1: (January 9) |
Hour |
Speaker |
Title |
9:00 Bagels and coffee |
9:30 |
Avrim Blum |
Introduction; graph partitioning for machine learning [ppt,
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] |
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] |
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,
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] [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] |
|
Stella Yu |
Cuts with Constraints [pdf]
|
11:45 GENERAL DISCUSSION, SUMMARY
AND CONCLUSIONS. |