mlsanityData to 7 Oct 2026

Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?

arXiv 2206.01506 ↗First posted 3 Jun 2022cs.LGcited by 25

Not on the map. Why?

Abstract (arXiv)

We propose a geometric scattering-based graph neural network (GNN) for approximating solutions of the NP-hard maximum clique (MC) problem. We construct a loss function with two terms, one which encourages the network to find highly connected nodes and the other which acts as a surrogate for the constraint that the nodes form a clique. We then use this loss to train an efficient GNN architecture that outputs a vector representing the probability for each node to be part of the MC and apply a rule-based decoder to make our final prediction. The incorporation of the scattering transform alleviates the so-called oversmoothing problem that is often encountered in GNNs and would degrade the performance of our proposed setup. Our empirical results demonstrate that our method outperforms representative GNN baselines in terms of solution accuracy and inference speed as well as conventional solvers like Gurobi with limited time budgets. Furthermore, our scattering model is very parameter efficient with only ~ 0.1% of the number of parameters compared to previous GNN baseline models.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 3 Jun 2022.

Builds on

17 of 39 references.

References · 17

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  7. 2021How Attentive are Graph Attention Networks?cited by 818
  8. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  9. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  10. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  11. 2020Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networkscited by 57
  12. 2018Geometric Scattering for Graph Data Analysiscited by 49
5 more
  1. 2018Graph Convolutional Neural Networks via Scatteringcited by 46
  2. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  3. 2018Diffusion Scattering Transforms on Graphscited by 43
  4. 2013Vertex-Frequency Analysis on Graphscited by 24
  5. 2022Overcoming Oversmoothness in Graph Convolutional Networks via Hybrid Scattering Networkscited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 6; 2025: 9; 2026: 4.

25 papers.

Sort:

By area:

  1. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  2. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  3. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  4. 2022Geometric Scattering on Measure Spacescited by 17
  5. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  6. 2022The Manifold Scattering Transform for High-Dimensional Point Cloud Datacited by 9
  7. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  8. 2025Learning for routing: A guided review of recent developments and future directionscited by 6
  9. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  10. 2023BLIS-Net: Classifying and Analyzing Signals on Graphscited by 3
  11. 2025Structure As Search: Unsupervised Permutation Learning for Combinatorial Optimizationcited by 2
  12. 2024IDEQ -- Improving Diffusion Models for the Traveling Salesman Problem (TSP) by Leveraging the Structure of the Solution Spacecited by 1
13 more
  1. 2025Unsupervised Ordering for Maximum Cliquecited by 1
  2. 2025VDW-GNNs: Vector diffusion wavelets for geometric graph neural networkscited by 1
  3. 2026Graph Neural Networks are Heuristicscited by 1
  4. 2024A short review on the maximum clique problem algorithms with classical, AI, and quantum methodscited by 0
  5. 2024An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problemcited by 0
  6. 2024Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networkscited by 0
  7. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  8. 2025ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule miningcited by 0
  9. 2025Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysiscited by 0
  10. 2025Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Miningcited by 0
  11. 2026GraIP: A Benchmarking Framework For Neural Graph Inverse Problemscited by 0
  12. 2026Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?cited by 0
  13. 2026Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfecited by 0