Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?
This work addresses the maximum clique problem, a fundamental NP-hard challenge in graph theory, with potential applications in network analysis and optimization, though it appears incremental as it builds on existing GNN methods with a scattering transform to mitigate oversmoothing.
The authors tackled the NP-hard maximum clique problem by proposing a geometric scattering-based graph neural network that outputs node probabilities for clique membership, achieving higher solution accuracy and inference speed than GNN baselines and conventional solvers like Gurobi under time constraints, with only ~0.1% of the parameters of previous models.
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.