Finding Maximum Common Subgraphs

PhD Qualifying Examination


Title: "Finding Maximum Common Subgraphs"

by

Mr. Yicheng HU


Abstract:

Finding the maximum common subgraph (MCS) between two graphs is a common 
operation in practice, for example, in measuring graph similarity. Existing MCS 
solutions can be exact or inexact.  Exact algorithms fall into three 
categories, including (1) reducing the problem to finding the maximum clique, 
(2) solving the problem with constraint programming, and (3) performing an 
exhaustive search through branch and bound. Among these three, the branch and 
bound approach is the winner in terms of time and space efficiency, with 
effective heuristics for vertex selection in the search. We particularly focus 
on the several algorithms that belong to the branch and bound approach and 
contrast them with clique-based and constraint programming approaches.

In contrast, inexact MCS solutions are produced by machine learning approaches 
based on the Graph Neural Networks (GNN), with a given time limit. Some of 
these machine learning approaches do not output MCS solutions but only an 
affinity matrix that predicts node-to-node correspondence or a single 
similarity value between the two input graphs. As a result, they are typically 
less expensive than exact algorithms.

Additionally, we also consider issues in finding MCS in molecular matching, 
such as the finding MCS between more than two molecules; a constraint between 
each pair of mapped atoms; the elimination of equivalent atoms and bonds due to 
the structural symmetry and equivalence in molecules.


Date:                   Wednesday, 26 June 2024

Time:                   6:00pm - 8:00pm

Venue:                  Room 3494
                        Lifts 25/26

Committee Members:      Prof. Qiong Luo (Supervisor)
                        Prof. Ke Yi (Chairperson)
                        Prof. Pedro Sander
                        Prof. Raymond Wong