📖 Beyond results, we include:

🔹 Theoretical analysis on why GCON works.
🔹 Ablations on efficiency and generalizability — GCON is surprisingly transferable 🚀

Check out the paper for more, or even better, catch us at our @logconference.bsky.social oral at 14:30 EST/19:30 GMT! 🧵[10/10]

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]

🔧 GCON overcomes these by:

1️⃣ Hybrid filter bank: Combines GNN aggregation with wavelet filters to capture intricate graph geometry.
2️⃣ Localized attention: Dynamically weights filters per node for flexibility.
3️⃣ Self-supervised losses: Circumvent the need for labels 🧵[5/n]

1️⃣ GNNs treat smoothness as an inductive bias. This isn't always suitable for CO problems, which often require high-frequency info.
2️⃣ CO graphs usually lack informative node features.
3️⃣ NP-hardness limits labeled data availability, making supervised learning infeasible. 🧵[4/n]

✨ Deep learning enables finding rapid approximate solutions, which are practical for most real-world CO tasks. Since many CO problems are graph-based, GNNs are a natural fit, but they face some challenges of their own: 🧵[3/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]