BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Globally Optimizing Graph Partitioning Problems Using Message Pass
 ing - Elad Mezuman\, Hebrew University
DTSTART:20140326T100000Z
DTEND:20140326T110000Z
UID:TALK51361@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Graph partitioning algorithms play a central role in data anal
 ysis and machine learning. Most useful graph partitioning criteria corresp
 ond to optimizing a ratio between the cut and the size of the partitions\,
  this ratio leads to an NP-hard problem that is only solved approximately.
  This makes it difficult to know whether failures of the algorithm are due
  to failures of the optimization or to the criterion being optimized.\n\nI
 n this work we present a framework that seeks and finds the optimal soluti
 on of several NP-hard graph partitioning problems. We use a classical appr
 oach to ratio problems where we repeatedly ask whether the optimal solutio
 n is greater than or less than some constant - \\lambda . Our main insight
  is the equivalence between this “\\lambda  question” and performing i
 nference in a graphical model with many local potentials and one high-orde
 r potential. We show that this specific form of the high-order potential i
 s amenable to message-passing algorithms and how to obtain a bound on the 
 optimal solution from the messages. Our experiments show that in many case
 s our approach yields the global optimum and improves the popular spectral
  solution.\n\nJoint work with Yair Weiss.\n
LOCATION:Auditorium\, Microsoft Research Ltd\, 21 Station Road\, Cambridge
 \, CB1 2FB
END:VEVENT
END:VCALENDAR