  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 $\sim$ 0.1\% of the number of parameters compared
to previous GNN baseline models.
