Navigation menu menu

Algorithms and Machine Learning on Graphs

People

Supervisor

External Member

Dr Henning Koehler

Description

Research Projects with Graph Research Lab (https://graphlabanu.github.io/website/)
 
Graph algorithms provide fundamental and powerful ways of exploiting the structure of graphs. Recent advances in machine learning, particularly deep learning, are also achieving remarkable progress in a wide variety of application domains. Graph Research Lab aims to investigate graph-related problems by marrying the best of two worlds: traditional graph algorithms and new machine learning techniques to bridge the gap between combinatorial generalization and deep learning.
 

Project #1 Graph Neural Networks - Theory and Practice

Graph neural networks (GNNs) have become a popular machine learning model for graph prediction tasks. Considerable progress has been made to characterize the connection between the representation power of GNNs and the Weisfeiler-Leman (WL) Algorithm (and accordingly the k-WL hierarchy). Through this connection, a beautiful relation between GNNs and finite-variable logics has also been established. Nonetheless, some interesting questions still remain underexplored, such as the locality of GNNs and first-order logic/finite model theory, the generalization ability, and the interpretability of GNNs. In this project, one specific issue relating to graph neural networks will be explored.

Prerequisites: This project requires students to have a solid background in machine learning, algorithms (and logic if working on logic-related topics). ANU students are expected to have finished COMP4670 or have an equivalent experience.

Background literature:

 

Project #2 Constrained Shortest-Path Problem

The shortest-path problem is a fundamental problem in graph theory which has many applications that require quick interaction (e.g., travel, communicate or search) between any two points in a network. However, in practice we are often not only interested in computing a quickest path but rather in a path satisfying a combination of different constraints. The problem of finding such a path is called constrained shortest-path problem (CSP). A constraint could be fuel consumption or toll fee in road networks; end-to-end delay or minimum bandwidth guarantees in communication networks, etc. Whereas the shortest-path problem can be solved in polynomial time, the CSP is known to be NP-hard. Existing work on CSP does not scale well on large networks and are slow. In this project, we will investigate the limitations of the existing work and develop nice properties to pre-compute a compressed data structure to efficiently answer CSP queries.

Prerequisites: This project requires students to have a strong background in data structure and algorithms and excellent programming skills C/C++/Java. ANU students are expected to have finished COMP3600 or have an equivalent experience.

Background literature:

 

Project #3 Balanced Minimal S-T Cuts

An S-T cut of a graph is a set of vertices (or edges) whose removal separates the graph into two disconnected components containing vertices S and T respectively. Minimum S-T cuts can be found in polynomial time, but offer no guarantees that the components found are balances (i.e., of similar size), which is an important property for many applications. Worse, the classical approach for finding minimal S-T cuts based on maximum flows tends to return extreme solutions amongst the set of minimal S-T cuts, often leading to maximal imbalance. In this project we investigate the space of minimal S-T cuts, and how more balanced minimal S-T cuts can be found.

Prerequisites: This project requires students to have a strong background in data structure and algorithms and excellent programming skills C/C++/Java. ANU students are expected to have finished COMP3600 or have an equivalent experience.

Background literature:

 
For further information about our team, visit https://graphlabanu.github.io/website/team/

 

Keywords

graph algorithms, machine learning, graph neural networks, graph kernels

Updated:  10 August 2021/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing