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

Christopher Morris

Abstract

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.

Introduction

Graph Neural Networks (GNNs) have become the standard architecture for learning from non-Euclidean data, finding success in domains as diverse as drug discovery, social network analysis, and logistics. However, the rapid empirical expansion of GNNs has historically outpaced our theoretical understanding. This research addresses the fundamental gap between GNN application and theory, focusing on two critical pillars: expressive power (what a GNN can distinguish) and generalization (why a GNN performs well on unseen data). Furthermore, it explores how these theoretical insights can be leveraged to solve NP-hard combinatorial optimization (CO) problems more efficiently.

The Expressive Power of GNNs

A central question in graph representation learning is whether a model can distinguish between different graph structures. This research utilizes the Weisfeiler-Leman (WL) Hierarchy—specifically the 1-WL or "color refinement" algorithm—as a benchmark for expressivity.

A key theoretical result established here is that standard Message-Passing Neural Networks (MPNNs) are fundamentally limited by the 1-WL test. Specifically, there exists a sequence of weights such that MPNNs have the exact same expressive power as 1-WL, meaning they cannot distinguish certain non-isomorphic graphs that 1-WL also fails to differentiate (such as certain cycles or cliques). To move beyond this "1-WL ceiling," the research suggests the necessity of higher-order GNNs ($k$-WL) or subgraph-based architectures that can "see" more complex structural features.

Generalization and the Margin Theory

In classical learning theory, a model's ability to generalize is often linked to its complexity, measured by the Vapnik-Chervonenkis (VC) dimension. Typically, higher expressivity suggests a higher risk of overfitting. However, GNNs often defy this expectation, where more expressive models continue to show improved performance on test sets.

To resolve this "Generalization Paradox," the author employs Margin Theory. This perspective suggests that more expressive models are capable of finding "wider" solutions—decision boundaries that are more robust to noise and structural perturbations. By shifting the focus from binary graph isomorphism to continuous pseudo-metrics like "tree distance," the research provides a more fine-grained understanding of how GNNs perceive similarity between graphs.

Applications in Combinatorial Optimization

Beyond pure theory, these insights are applied to the challenge of NP-hard Combinatorial Optimization. Traditional solvers for Mixed-Integer Programs (MIPs) are exact but often slow. This research proposes using GNNs as "neural heuristics" to guide these solvers.

Bipartite MIP Encoding

To process optimization problems, MIPs are encoded as bipartite graphs consisting of variable nodes and constraint nodes. This representation allows GNNs to capture the inherent structure of the optimization problem without manual feature engineering.

GNNs as Solver Proxies

GNNs can be trained to predict "variable biases," effectively guessing which variables are likely to be part of an optimal solution. When integrated into state-of-the-art solvers like CPLEX, GNNs have demonstrated significant speedups in node selection and warm-starting for binary MIPs.

Algorithmic Simulation

A significant breakthrough in this work is the demonstration that GNNs can simulate classical algorithms. Specifically, the research shows that an MPNN with $O(m)$ layers (where $m$ is the number of constraints) can successfully reproduce an iteration of an Interior Point Method (IPM) for linear programming. This explains why GNNs are remarkably effective at solving the linear programming relaxations that underpin hard CO problems.

Conclusion and Future Directions

While this research provides a robust framework for understanding GNNs, several challenges remain. Most current theory relies on the graph isomorphism perspective, which may not fully capture the nuances of real-world graph similarity. Additionally, current generalization bounds often involve large constants that do not yet reflect the practical realities of deep learning engineering. Future work will focus on scaling these GNN-based solvers to much larger problem instances and incorporating specific architectural "tricks" (like skip connections and normalization) into the theoretical models to better align theory with practice.

Summary updated

Abstract

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.
BibTeX
@inproceedings{morris2024towards,
  author = {Christopher Morris},
  title = {{Towards a Theory of Machine Learning on Graphs and its Applications in Combinatorial Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=rac9xtijbV},
}
Figure