We test GCON on Max Cut, Min Dominating Set, & Max Clique tasks.

🔹 GCON beats other GNNs & GFlowNet-based solvers
🔹 Outperforms (time-budgeted) Gurobi optimizer on Max Cut by 45+ edges!
🔹 Much faster inference than GFlowNet & Gurobi

GCON is both versatile & powerful. 🧵[9/n]

✨ Attention then re-weights the multi-scale features on a node-by-node basis, which are then passed through MLP + softmax to predict node probabilities (p).

p is then used for:
(a) Self-supervised loss computation
(b) Task-specific decoding to satisfy task constraints
🧵[8/n]

🌐 High-frequency signals are vital for CO, helping capture subsets that are not always local & distinguish clear boundaries for vertex sets.

[L]: High-frequency features capture the true clique.
[R]: Low-pass filters diffuse boundaries to nodes not part of the clique. 🧵[7/n]

🔍 The GCON pipeline starts with generating node features from graph statistics.

We then apply GCON blocks with multi-scale filters derived from geometric scattering alongside conventional GNN aggregation for low-pass filtering

Why the multi-scale filters? 🧵[6/n]

🔍 Combinatorial Optimization (CO) problems require finding the optimal subset of objects from a finite set. Most CO problems are NP-hard, making exact solutions (e.g., via MIP) infeasible as set instances become larger. 🧵[2/n]

Excited to present our paper "Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs" as a Spotlight at @logconference.bsky.social 2024! 🎉

We propose GCON, a novel GNN framework for tackling CO problems.

📜 arxiv.org/abs/2405.20543
🛠 github.com/WenkelF/copt
🧵[1/n]