Loading Events

« All Events

  • This event has passed.

CIS/GRASP Seminar: Jean Gallier, University of Pennsylvania, “Clustering of Unsigned and signed Graphs Using Normalized Cuts (Normalized Cuts 15+ years later)” Part 1

September 29, 2015 @ 3:00 pm


Graph clustering using the method of normalized graph cuts is nowadays a standard technique in computer vision and other domains, owing to the seminal work of Shi and Malik. This method was extended to multiple clusters (K > 2) by  Yu and Shi. 

This talk will focus on Yu and Shi’s method, with clarification of certain details. The method proceeds in two stages. During the first stage, the clustering problem is formulated as an optimization problem which is translated in matrix form using a graph Laplacian.
This problem is NP-hard, so a relaxed continuous version is considered; I will show that this reduces to an eigenvalue problem.  The second stage consists of obtaining a discrete solution which approximates the continuous solution.

In the first part of this talk, I will describe how to set up and solve stage 1 of the clustering problem. I conclude by sketching a generalization of normalized cuts to graphs with negative edges. This part assumes no prior knowledge.

Slides may be found here…


- Learn More

Jean Gallier is a Professor of Computer and Information Science at the University of Pennsylvania, with a secondary appointment in Mathematics. He obtained his Ph.D in Computer Science at UCLA in 1978. Gallier has done research in a number of areas of CS, including program correctness, incremental parsing and error recovery, logic programming, unification, term-rewriting and equational logic, polymorphic lambda calculi, and linear logic. For the past twenty two years, he has focused on geometric modeling, surfaces splines, surface reconstruction from meshes, and recently on optimization problems arising in computer vision, robotics, and machine learning. Generally, he is interested in applying geometric tools (in particular, differential geometry) to problems in computer science. He is the author of seven books, the next to the last one with Dianna Xu, “A Guide to the Classification theorem for compact surfaces,” and the last one, “Logic For Computer Science” (second edition).Jean Gallier


September 29, 2015
3:00 pm
Event Category: