SCHEDULE: NOV 10-16, 2012
When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.
A Multithreaded Algorithm for Network Alignment via Approximate Matching
SESSION: Graph Algorithms
EVENT TYPE: Papers
TIME: 4:30PM - 5:00PM
SESSION CHAIR: Esmond G. Ng
AUTHOR(S):Arif Khan, David Gleich, Mahantesh Halappanavar, Alex Pothen
ROOM:355-EF
ABSTRACT:
Network alignment is an optimization problem to find the best one-to-one
map between the vertices of a pair of graphs that overlaps in as many edges
as possible.
It is a relaxation of the graph isomorphism
problem and is closely related to the subgraph isomorphism problem.
The best current approaches are entirely heuristic and iterative in nature.
They generate real-valued heuristic weights that must be rounded to
find integer solutions. This rounding requires solving a bipartite maximum weight
matching problem at each iteration in order to avoid missing
high quality solutions.
We investigate substituting a parallel, half-approximation for maximum
weight matching instead of an exact computation. Our experiments show
that the resulting difference in solution quality is negligible.
We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor
Intel Xeon E7-8870 system and now solve real-world problems in 36 seconds instead of
10 minutes.
Chair/Author Details:
Esmond G. Ng (Chair) - Lawrence Berkeley National Laboratory
Arif Khan - Purdue University
David Gleich - Purdue University
Mahantesh Halappanavar - Pacific Northwest National Laboratory
Alex Pothen - Purdue University
Click here to download .ics calendar file
Click here to download .vcs calendar file
Click here to add event to your Google Calendar
A Multithreaded Algorithm for Network Alignment via Approximate Matching
SESSION: Graph Algorithms
EVENT TYPE:
TIME: 4:30PM - 5:00PM
SESSION CHAIR: Esmond G. Ng
AUTHOR(S):Arif Khan, David Gleich, Mahantesh Halappanavar, Alex Pothen
ROOM:355-EF
ABSTRACT:
Network alignment is an optimization problem to find the best one-to-one
map between the vertices of a pair of graphs that overlaps in as many edges
as possible.
It is a relaxation of the graph isomorphism
problem and is closely related to the subgraph isomorphism problem.
The best current approaches are entirely heuristic and iterative in nature.
They generate real-valued heuristic weights that must be rounded to
find integer solutions. This rounding requires solving a bipartite maximum weight
matching problem at each iteration in order to avoid missing
high quality solutions.
We investigate substituting a parallel, half-approximation for maximum
weight matching instead of an exact computation. Our experiments show
that the resulting difference in solution quality is negligible.
We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor
Intel Xeon E7-8870 system and now solve real-world problems in 36 seconds instead of
10 minutes.
Chair/Author Details:
Esmond G. Ng (Chair) - Lawrence Berkeley National Laboratory
Arif Khan - Purdue University
David Gleich - Purdue University
Mahantesh Halappanavar - Pacific Northwest National Laboratory
Alex Pothen - Purdue University
Click here to download .ics calendar file