Subgraph-GNNs: Theorie vs Praxis bei MILP-Branching

Graph Neural Networks (GNNs) haben sich als vielversprechende Methode für das „Learning to Branch“ in Mixed‑Integer Linear Programming (MILP) etabliert. Während klassische Message‑Passing GNNs (MPNNs) effizient arbeiten, fehlt ihnen theoretisch die Ausdruckskraft, um die komplexen Strukturen von MILP vollständig abzubilden. Auf der anderen Seite bieten höhere‑Ordnung‑GNNs wie 2‑FGNNs die nötige Expressivität, sind jedoch in der Praxis zu rechenintensiv.

In dieser Arbeit wird die Klasse der Subgraph‑GNNs als theoretische Zwischenlösung untersucht. Die Autoren zeigen, dass node‑anchored Subgraph‑GNNs – deren Ausdruckskraft strikt unterhalb der 3‑WL‑Stufe liegt – bereits ausreichen, um die Strong‑Branching‑Scores zu approximieren. Damit wird ein schärferes theoretisches Ergebnis als in früheren Studien erzielt.

Die umfangreiche Evaluation an vier Benchmark‑Datensätzen offenbart jedoch einen deutlichen Kontrast zwischen Theorie und Praxis. Obwohl node‑anchored Subgraph‑GNNs theoretisch bessere Branching‑Entscheidungen liefern, führt ihre O(n)-Komplexität zu erheblichen Speicherengpässen und längeren Löstimes als bei MPNNs und klassischen Heuristiken.

Die Ergebnisse legen nahe, dass die derzeitigen Rechenkosten für expressive GNNs die potenziellen Qualitätsgewinne bei MILP‑Branching übersteigen. Zukünftige Forschung sollte daher darauf abzielen, Ausdruckskraft mit Effizienz zu verbinden, um die praktische Anwendbarkeit von GNN‑basierten Branching‑Strategien zu erhöhen.