Student: Anthony Kim
School: Massachusetts Institute of Technology
Email:tonyekim [@] dimax.rutgers.edu
Research Area(s): Semidefinite Programming, Computer Science
Project Name: Finding Isomorphic Substructures, and Its Applications to Analyzing Interaction Graphs (Project #: DDD2008-24 in this list )
Faculty Advisor: Alantha Newman, DIMACS

Project Description

Here is the project description from the list of projects website:

Graph or subgraph isomorphism problems are that of determining if two graphs have the same structure or substructures. We can think of the following graph optimization problem: Given two graphs G and H, we would like to find the largest subgraph that is isomorphic to some subgraph of both G and H. A recent technique that has been applied to graph optimization problems is semidefinite programming. This project involves (a) developing semidefinite programming based methods and code for finding isomorphic subgraphs, and (b) exploring applications in specific "interaction graphs". For example, if we let the nodes of the graph represent people or objects and we let the edges represent the relationships between pairs of people or between a person and an object, then the problem of finding isomorphic substructures could be used to detect similar behavior patterns.

Project Summary

We applied semidefinite programming methods on the graph isomorphism problem and studied how it can be used efficiently. There were two parts to the project; for the first part of the project we studied false positives given by our original semidefinite program for the graph isomorphim problem and for the second part we experiemented with various methods, for example alternative semidefinite programs, to make isomorphism testing fast. The graph isomorphism problem still remains to be solved and we hoped to learn more about the problem by applying semidefinite programming methods. We made some progress on the first part and did experiements with several heuristics for the second part.

For a quick overview of the project, the powerpoint used for my final presentation will be provided upon request.