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

arXiv: https://arxiv.org/abs/2206.01506 · HTML: https://mlsanity.com/paper/2206.01506/

## Key facts

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

## Builds on (most cited first, 17 of 17)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks](https://mlsanity.com/paper/2003.08414/) (2020)
- [Geometric Scattering for Graph Data Analysis](https://mlsanity.com/paper/1810.03068/) (2018)
- [Graph Convolutional Neural Networks via Scattering](https://mlsanity.com/paper/1804.00099/) (2018)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [Diffusion Scattering Transforms on Graphs](https://mlsanity.com/paper/1806.08829/) (2018)
- [Vertex-Frequency Analysis on Graphs](https://mlsanity.com/paper/1307.5708/) (2013)
- [Overcoming Oversmoothness in Graph Convolutional Networks via Hybrid Scattering Networks](https://mlsanity.com/paper/2201.08932/) (2022)

## Built on by (most cited first, 25 of 25)

- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems](https://mlsanity.com/paper/2406.03503/) (2024)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Geometric Scattering on Measure Spaces](https://mlsanity.com/paper/2208.08561/) (2022)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [The Manifold Scattering Transform for High-Dimensional Point Cloud Data](https://mlsanity.com/paper/2206.10078/) (2022)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [BLIS-Net: Classifying and Analyzing Signals on Graphs](https://mlsanity.com/paper/2310.17579/) (2023)
- [Structure As Search: Unsupervised Permutation Learning for Combinatorial Optimization](https://mlsanity.com/paper/2507.04164/) (2025)
- [IDEQ -- Improving Diffusion Models for the Traveling Salesman Problem (TSP) by Leveraging the Structure of the Solution Space](https://mlsanity.com/paper/2412.13858/) (2024)
- [Unsupervised Ordering for Maximum Clique](https://mlsanity.com/paper/2503.21814/) (2025)
- [VDW-GNNs: Vector diffusion wavelets for geometric graph neural networks](https://mlsanity.com/paper/2510.01022/) (2025)
- [Graph Neural Networks are Heuristics](https://mlsanity.com/paper/2601.13465/) (2026)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem](https://mlsanity.com/paper/2408.08484/) (2024)
- [Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks](https://mlsanity.com/paper/2412.11205/) (2024)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)
- [ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining](https://mlsanity.com/paper/2511.22866/) (2025)
- [Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis](https://mlsanity.com/paper/2512.03419/) (2025)
- [Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Mining](https://mlsanity.com/paper/2512.20915/) (2025)
- [GraIP: A Benchmarking Framework For Neural Graph Inverse Problems](https://mlsanity.com/paper/2601.18917/) (2026)
- [Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?](https://mlsanity.com/paper/2603.02462/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)

## 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.