Towards a Theory of Machine Learning on Graphs and its Applications in Combinatorial Optimization

Towards a Theory of Machine Learning on Graphs and its Applications in Combinatorial Optimization

Christopher Morris

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Early Career. Pages 8553-8558. https://doi.org/10.24963/ijcai.2024/981

Machine learning on graphs, especially using graph neural networks (GNNs), has seen a surge in interest due to the wide availability of graph data across many disciplines, from life and physical to social and engineering sciences. Despite their practical success, our theoretical understanding of the properties of GNNs remains incomplete. Here, we survey the author's and his collaborators' progress in developing a deeper theoretical understanding of GNNs' expressive power and generalization abilities. In addition, we overview recent progress in using GNNs to speed up solvers for hard combinatorial optimization tasks.
Keywords:
Machine Learning: ML: Representation learning
Machine Learning: ML: Learning theory
Machine Learning: ML: Theory of deep learning
Constraint Satisfaction and Optimization: CSO: Constraint optimization problems