# Algorithms and Machine Learning on Graphs

## People

### Supervisor

### External Member

## Description

**Project #1 Graph Neural Networks - Theory and Practice**

**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:*

- A New Perspective on “How Graph Neural Networks Go Beyond Weisfeiler-Lehman?”, A. Wijesinghe and Q. Wang, International Conference on Learning Representations (ICLR) 2022
- Theory of Graph Neural Networks: Representation and Learning, Stefanie Jegelka, 2022

**Project #2 Constrained Shortest-Path Problem**

**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:*

- BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale, M. Farhan, Q. Wang, and H. Koehler, ACM SIGMOD International Conference on Management of Data (SIGMOD), 2022
- Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks, Y. Wang, Q. Wang, H. Koehler, and Y. Lin, ACM SIGMOD International Conference on Management of Data (SIGMOD), 2021
- A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks, M. Farhan, Q. Wang, Y. Lin, and B. Mckay, The 22nd International Conference on Extending Database Technology (EDBT), 2019

**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:*

- Coverings of bipartite graphs, Dulmage, Andrew L and Mendelsohn, Nathan S, Canadian Journal of Mathematics, vol(10), pages 517--534, 1958
- Graph partitioning with natural cuts, Delling, D., Goldberg, A.V., Razenshteyn, I. and Werneck, R.F., IEEE International Parallel & Distributed Processing Symposium, 2011
- https://www.cs.princeton.edu/courses/archive/sprin...

## Keywords

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