Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?
Authors: Yimeng Min
Frederik Wenkel
Michael Perlmutter
Guy Wolf
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Geometric Scattering
Combinatorial Optimization

Abstract: 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.

Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?
Yimeng Min'
Frederik Wenkel"
Department of Computer Science
Department of Mathematics and Statistics
Cornell University Ithaca, NY, USA
Université Montréal
Mila Quebec Al Institute
min@cs. cornell......o..ooo edu
Montreal, QC, Canada
frederik wenkel @umontreal.................. ca
Michael A. Perlmutter
Guy Wolf
Department of Mathematics University of California Los Angeles, CA, USA perlmutter&ucla.c edu
Department of Mathematics and Statistics
Université de Montréal
Mila Quebec Al Institute
Montreal, QC, Canada guy wol wwwneuueeaaale.n.ooeeaaaa
Abstract
We propose geometric scattering baaseringg-baeed graph neural network (GNN) for approxi- mating 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 the constraint that the
connected nodes and the other which acts as surrogate nodes form 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 rule-based decoder to make final prediction. The incorporation 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 represen- tative 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.
Introduction
The success of Graph Neural Networks (GNNs) for a variety of machine learning tasks [Scarselli
al. 2008 Gori al. 2005 Kipf and Welling 2016 Gilmer et al.) 2017 has sparked interests in using GNNs to solve graph combinatorial optimization (CO) problems [Li et al, 8018a| Karalias and
Loukas
2020
For example,Josti et al. 2019 introduces GNN-based method for approximately
solving the travelling salesman problem (TSP), while Karalias and Loukas 20200) approximate
solutions of the maximum clique (MC) problem. Solving such problems in end-to-ent fashion via
GNNs is challenging for several reasons. First of all, many CO problems are provably either NP-hard or NP-complete. Therefore, learning CO solvers in a supervised or semi-supervised fashion can be computationally infeasible since the cost of generating the ground truth labels grows exponentially with the problem size. Second, the solution the CO problems must satisfy a number of constraints
Equal contribution; order determined alphabetically
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Scattering- GNN
Maximum Clique Decoder
Intrinsic Signals
Output Signals
Maximum Clique
Figure I: Illustration of our model pipeline. We use scattering-based GNN to learn a discriminative node representation and use a decoder to extract the MC from the learned representation.
or limitations (e.g. belonging to a clique). Although these constraints can be imposed during training time, there is still guarantee that these constraints still satisfied test time. Furthermore, solving graph combinatorial problems largely depends on the expressive power of GNNs. Many smoothing operation. This degrades the expressive power of GNNs and results in the so-called oversmoothing problem [Li al. 80] where neighboring nodes have similar representations and are difficult to distinguish from each other. This is problematic if a node that is not in the solution set borders many points that in the solution
GNNs aggregate information via local averaging. which can be interpreted
The purpose of this paper is to use a geometric scattering- based GNN to fast approximate the solution of the maximum clique (MC) problem, that is to find the largest complete subgraph contained within a large graph G. This problem has many applications including pattern recognition and knowledge discovery. For instance, finding the maximum elique of the related connection graphs be used to handle object recognition tasks [Horaud and Skordas 1989). It is also tightly related to biological applications, such helping solve genome-scale elucidation of biological networks (Zhang et al., 2005). Our use of geometric scattering, rather than more traditional GNN is motivated by recent work [Wenkel et al. 2022) showing that the geometric scattering transform can help overcome the oversmoothing problem via the use of band-pass wavelet filters in conjunction with GCN-type filters. This is particularly important in the context of the MC problem because is critical to distinguish point which connects to many members of the clique from an actual member of the clique. As we shall show, our method, which utilizes band-pass wavelet filters is able to better detect the border between the MC and the rest of the graph. This parallels the traditional use of wavelets as edge detectors in image processing [Grossmann) 1988).
Our method uses a two-phase strategy shown in Figure 1 model generate an efficient representation of how likely each node is to be part of the maximum clique. Then, this representations is fed into a constraint-pp constraint-preserving decoder to generate the maximum clique. Ideally, given graph G with n nodes, nodes in the maximum clique are assigned the value 1 (True) while all other nodes are assigned 0 (False), so that we can 'cut' the MC from the graph via O(n) operations. representation which assigns large probabilities to the maximum clique nodes and small probabilities the other nodes. This will allow to extract the maximum clique by choosing the vertices where p
We first use an unsupervised learning
would build a representation p E [0, 1]" where the
practice, we will build
(a)
(b)
4
4
7
0.0
0.5
0.0
0.5
1.0
Figure 2: Illustration of the oversmoothing problem. Left: A discriminative representation, which can be interpreted as a probability for each node belong to the maximum clique or not. Right: Due to the oversmoothing problem, the GNN generates smooth representation, making MC and non-MC nodes difficult to discriminate.

---

is large. As illustrated in Figure 2 this approach works best if p is not excessively smooth. However, so-called oversmoothing is known limitation of many GNN models [Li et al. 2018b]. Figure (a) presents situation where oversmoothing does not occur. The signal p is much larger on the nodes (1, 2,3, 4, 6), which form the maximum clique, than on the other nodes (5, 7, 8). Therefore, the decoder can easily find the MC by, e.g., setting threshold. Figure (b). on the other hand, illustrates a situation which oversmoothing occurs and exhibits less variability, Indeed, there are no blue colored nodes all. In this setting, is nearly impossible to distinguish node 7, which does not belong to the maximum clique, from the nodes 1, 6, and therefore extracting the MC from p is difficult if not impossible.
(a)
Background and Related Work
2.1 Graph Signal Processing
Consider graph G EV,E) with set of nodes (or vertices) V {ui...., Un and set of undirected edges c. x V. For a function x V + R defined on V, we will, in minor abuse of notation, identify with the vector where x|i] zxux). We let W E g=*x denote the adjacency matrix of G and define the symmetric normalized graph Laplacian by : 1/2 WDD 1/2 where d; = Σラ= W [[,,, 2yy is the degree of the node 2 and D = fiag(d1....,.6 dn) ) E R"** X is the degree matrix. We will let q, and A denote the (normalized) cigenvectors and eigenvalues of L with Lg X, and make use of the eigendecomposition L = Q Q where Q is the orthogonal matrix whose i-th column is the normalized eigenvector q:- and
diag(A1. ..., An). Notably, the eigenvectors 9I.... 4n can be seen as generalization of Fourier modes in the context of graph domains with the corresponding eigenvalues representing the increasing frequencies À S
An < 2. This link may be established by viewing frequency as a measure of variation, in particular Fourier modes across edges, i.e.,
the variation of
A = q. Lq: = Σ (ā.lu) q [b])
{u,D)E
for q, D-22 q. The graph Fourier transform of a signal vector x then defined as by x|1] (x, q:) and the inverse Fourier is given by x D x[[] q. Compactly written, we have a = Q x
and x Q+.
In the Euclidean setting. it is known that convolution the spatial domain corresponds to multiplica- tion in the Fourier domain. This fact has motivated work such as [Shuman et al. [2016), which defines the convolution of a signal x with filter g to the unique vector verifying (g * x [1] = [1] which implies that
g*x Σ g
Σ kli x) q. = Q&Q x,
where G = (g) diag(g íml)). When incorporating this notion of convolution into
graph neural network, a common choice [e.g.. Defferrard et al., 2016] is to require the coefficients
g be polynomials of the eigenvalues A [m]. i.e., [ E. A. in which case have
G= Σ. A This allows one to implement convolution the spatial domain by verifying that g * x = Σx Ch x. In particular, the entire method may be implemented without the need to diagonalize matrix which is extremely expensive for large graphs.
2.2 Graph Convolutional Networks
In Kipf and Welling 2016 the authors set g = 0(2 Ax). where 0 is real number, which yields
go * x 02IL, - -) I, + D 1/2 W D D-12)))
(1)
As the eigenvalues of the above convolutional filter lie in [0,2] and could lead to vanishing or exploding gradients, the authors then apply renormalization trick which replaces I,, + +DD11/ W D -1/2 with

---

= (D + ( 1/2, 112 The layer-wise propagation rule of GCN is then defined by
N
x 0
Σ
0 A A
where x R is the i-th feature vector in layer e - 1, fiy are a trainable parameters, xf the j-th feature activation vector in layer and a(-) a nonlinear activation function. We can summarize this in matrix notation as
x =²=o (=xx
(2)
where Oº N is the weight-matie of layer l and X' RR*NN contains the activations output by layer f. The GCN model updates node features at every node by averaging over the node features the node itself and its neighbors, which enforces similarity throughout node neighborhoods. This makes nodes increasingly difficult to discriminate for 'deeper' models and is widely referred to the oversmoothing problem (Li al. [01 From graph spectral theory perspective, oversmoothing is related to low-pass filtering the filter in Eq. [ puts larger weights on the low- frequency spectrum (as 0 S A S 2). This motivates the idea of using GCN-type low-pass filters in conjunction with band-pass pass filters, that can be implemented, for example, using graph scattering [Min ct al. 2020]. which we discuss in the following.
2.3
Graph Scattering
The graph scattering transform [Gama et al. 2019 Zou and Lerman 2019 Gao et al. 2019 is wavelet-based model for machine learning on graphs. Unlike the one-hop localized low-pass filters used in GCN, which aim to promote smoothness between neighboring nodes, these wavelets are band-pass filters, which in turn incorporate long-range dependencies through the large spatial support of the used aggregations. The scattering transform is based upon raising the lazy random walk matrix
1 p= (I. (L.+WD-))
to different powers in order to capture the diffusion geometry of the graph G at various time scales. In particular, subtracting such powers allows detect changes in these diffusion geometries. Following the lead of Coifman and Maggioni (0066). for & E No. we define a wavelet matrix V Roxx scale 2 by
D - 2 121
(3)
Intuitively, at every node, these diffusion wavelets can be seen as comparison operation that calculates the difference of the averaged features of two neighborhoods of different sizes (namely sizes 2k-1 and 2*). The geometric scattering transform is constructed through an alternating cascade on wavelet filters and pointwise nonlinearities that outputs
+ IR, a so-called scattering path p == (ki,... km)
Up =
km 0 o km-1 of kg 0. V VK
(4)
Model
Our method is centered around three main components, (i) hybrid scattering-GCh model M (Sec.
that transforms a small set of simple node-level statistics represented by the matrix E IR to a probability vector E [0, 1]" representing the probabilities that each node is part of the maximum clique, (ii) an easy-to-optimize unsupervised loss function L (Sec. (344) that is small for "good"' probability vectors p": and (iii) rule-based decoder D (Sec. 3.5) that maps the probability vector the maximum clique C* C of G.
3.1 3.3
X
M
M D2 o*
I.
X
3.1 Embedding Module
The input of our model is a node feature matrix X E nxd containing features for each node. In experiments, set d and let the features be the eccentricity, the clustering coefficient, and

---

the logarithm of the degree of each node. The encoder transforms the node features to d di-ddmmnnsional embeddings HD using multi-layer perceptron (MLP) Memb IR" - TR i.e., H == Memb (X),
which will be used as the input to the diffusion module introduced in the next subsection.
3.2 Diffusion Module
The diffusion module consists of a cascade of E N aggregation (or diffusion) layers with operations that are chosen for each node via attention mechanism. Our network is based upon the framework introduced in Wenkel et al. 2022]. However, an important deviation is to store the initial node representation H and every intermediate node representation H S & < K, in list of readouts.
In each layer L, every node has access to node representations from set of filters F that contains selection of low-pass and band-pass filters. Similar Wenkel al. [022] our band-pass filters flow,r are modified GCN filters that have the form
frow (H* (H²-1) = A A
(5)
and are parameterized by the power r 2 1 of the matrix A. Similarly, we define the scattering filter f of order according to
I HH (H² V H
Next, we want to obtain data-driven scores sT( that determine the importance of filter f E for node E V. We set H == f(H(-1) and calculate the scores via an attention mechanism, setting
sf a H H " a²,
(7)
where || denotes the concatenation operation. The attention mechanism, at every node, calculates dot product learned attention vector af R2ds with the filtered node representation of node concatenated to its previous representation. We further deviate from the model in Wenkel et al. [2022] by rewiring the nonlinearity (-)) in Eq. 7 They apply it after the multiplication with the attention vector a similar to the traditional graph attention mechanism Vellčković al. 2018)] In contrast, we apply it before the multiplication with the attention vector following the lead of Brody al. [222]) who showed this constitutes an even more expressive attention mechanism. The i-th entry of s IR" then contains the importance score of filter for node Us. We normalize the scores across the filters using the softmax function, i.e., a (v) softmax= (s (v)), and store the resulting scores in attention vectors a' E IR", f E F. We then update node representations via
H
Σ
Eaje OH JEF
(8)
where O is the element-wise multiplication (applied separately to each column of H Notably, the softmax function enforces that every node is likely to focus mostly on one single filter. We note that the method is compatible with multi-head attention but omit further details as not necessary for the present experiments. Finally, we transform the aggregated node representations via an MLP mf dh + de. i.c., H = m m (H g We repeat the above process for K E N iterations (or layers) and store the intermediate representations list of readouts R = (H') 1z=0-
3.3 Output Module
In the output module, we combine the information from the list of readouts R. We first concatenate the readouts horizontally
H
H
where Ham. E ggxxd(K+1) and then transform Hea to a vector h E R" using an MLP Mout (k++) + R, i.e,, h h Momt H.m)). Finally, to obtain vector of probabilities, apply min-max normalization, i.e., p = (h - min(h) 1x)/(maxx (h) - min(h)), and interpret the i-th entry of p as the probability that node is part of the maximum clique.
5

---

3.4
Training Loss
We now derive an unsupervised training loss for the maximum clique problem, which was also obtained by different derivation in the work of Karalias and Loukas [2020]. Letting S denote the set of cliques of a graph G EV, we note that the task of finding the maximum clique equivalent to identifying the clique C' E S that contains the most edges, i.e., maximizes the objective function
(C) =
Σ
Wa
where Wa, = 1 if node u. and are connected otherwise O. Our approach relies on producing vector p such that P, = 1 if in the maximum clique and P, otherwise. We consider the vector x E R" where X, as a Bernoulli random variable where P(x, = 1) Pp. Our goal then becomes to maximize expectation
if is in the maximum clique and x, 0 otherwise. We then model
[ E
Σ (a,e)EE
Way Na Xe
=
Σ (u,N)EE
Wue Pu Ps =p WP.
(9)
Maximizing Eq. encourages p to be large on highly connected nodes. However, we also want the support of p to be concentrated within clique. This naturally motivates the constrained optimization problem of minimizing
(p) = - P Wp subject to: supp(p) is contained clique.
However, the constraint that p is contained construct surrogate, consider the complement graph G (V,E), The vertices of G are taken to be the same G. i.c., V V. while the edges are defined by the rule that for & there is edge between u and in G if and only if there is not edge between them in G, i.e. E. We denote the adjacency matrix of G by W (Wa.v).vVV,
clique is hard enforce directly. In order to
E = {(u, v) E V x V : u + E. and note that
{1
if (u, & E and + 4 otherwise.
W a,P
0
In particular, W has zeros on the diagonal and can be computed from W via W 1nxn - (I W). The following Lemma indicates that a second loss term L2 (p)) == P W p can be used to ensure that mass is primarily concentrated a set nodes that form a clique.
Lemma 1. Consider graph G = (V, E), a signal p 2 0 and define supp(p) = V P. > 0}. Then, (2(p) p W p = 0 if and only if there exists clique C C V such that the support of is
contained in C.
Proof. We first assume p T W p 0 and suppose for the sake of a contradiction that there exists no clique C' V with (p) C. Then, there exist at least two nodes uy Up E supp(p) with {ug, P0 & E. Now. pT W Wp=/ Σ E( Pu P. 2 Puo Pro 0, which contradiction.
For the opposite direction, we assume that there exists clique C V such that supp(p) C C. Hence, every pair of distinct nodes in supp(p) is connected by an edge and consequently Wa,r 0 for all U supp(p). Thus, W p En,vev W., Pa P. Ex.vesupo(p) Wu,v P P 0.
In light of Eq. 9 and d Lemma D we now define our training loss
L(p) == (p(p) + 3L2(p) pp" Wp+3p' Wp.
(10)
We note that the loss function decomposes into two terms. The first term, L1, encourages the allocation of mass highly connected nodes, while the second term L- encourages most of the mass of p to be contained in clique. Moreover, is hyper-parameter which is used to balance the contributions of the two terms. As mentioned, an almost identical loss function was already used in Karalias and Loukas (2020) with further details discussed in Appendix C.
desirable to use the sparsity of the graph G and hence also W. We note that, although sparse W signifies dense W, we efficiently evaluate the second loss term as p" W p ( ( p2)² -pp W Σ 20=1 p
Similar to many other GNN applications

---

Algorithm Maximum Clique Decoder
1: Input: Probability vector p. graph G with nodes, number of samplers K, sample length 7.
2: Output: Predicted maximum elique C' of size IC).
3: Order nodes via permutation π + [rx] such that Px Px-1(1) 2 Px (() 2 ... 2 P ((n)"
4: for j = to λ. do
5:
- ()+(r=(())
6:
for 2
Ko
7:
UCT ( forms a clique then
C
8:
9: end if
10: end for
11: end for
12: Q <
13: Ö t- arg cea CC
3.5 Decoder
In order to extract the maximum clique from p, we use greedy decoder detailed in in Algorithm Our algorithm creates set Ω {C of cliques and then selects the C3 with largest cardinality. To construct each Cj, we first create a sorting function т + {I,...,/M [VD which puts the nodes in descending order, PT-'(1) 2 ... Px-1(n) Each Öÿ3 starts as a single node x "J). We then consider T j additional candidates, "(j 1)...... (T) and accept each candidate node Veanditate if Õ U {Vcandidane forms a clique. This tested by verifying that x W x = for 1, We remark that in order for our decoder predict the true maximum clique exactly, we must choose the parameters and such that there exists a j. S K, such that j S x (i) I r for all n in the MC. On simple datasets, such as IMDB, it suffices to set x: More complex datasets such as Twitter require larger values of K. Importantly, we note that the C2 can be computed in parallel, increasing the value of does not create major scalability issues. We note that setting the hyperparameters of the decoder requires some prior knowledge of the largest sizes of the maximum cliques present in the data, which we tune using the validation set.
: 2vvć,
Results
4.1 Baselines
We compare our hybrid scattering model against other neural network-based methods, an inte- ger programming-base solver and traditional heuristic. For the the neural networks, Erdös' GNN (Karalias and Loukas 2020) and RUN-CSP (Toenshoff et al. (02T]. the authors provide two implementations, one optimized towards computational speed (fast), and the other optimized for best approximation score (accurate). In order to highlight the contribution of our hybrid scattering model, we also provide results for pure low-pass model, which only uses GCN-type filters [Kipl) and Welling 2016) followed by our decoder module. We further report results for the integer- programming method Gurobi 9.0 (Gurobi Optimization, LLC, 2022]. Finally, we compare traditional heuristic [Grosso et al. 22088) local search procedure with 7/ random restarts, where an initial clique is continuously modified and possibly improved by neighbourhood search operations until some termination condition occurs. The heuristic is iterated for maximum of 1/2 iterations. We denote the method for different hyperparameter configurations as Heuristic 72).
4.2 Datasets
We evaluate our model on three popular real-world graph learning datasets, namely IMDB, COL- LAB [Yanardag and Vishwanathan, 2015) and TWITTER (Yan et al., 2008). To further explore how our model performs relative to other methods more challenging and larger graphs, we introduce two new datasets consisting of graphs generated according to the approach in Xu et al.) [2005). The
first dataset (SMALL) contains graphs of slightly larger size (~~100 nodes average) compared to the
7

---

Table I: Maximum clique test approximation score (mean + std.) and avg. prediction time measured in seconds per graph (in brackets) on real-world datasets compared to the different baselines. In our decoder, we set equal to I, 1 and 10 for IMDB, COLLAB and TWITTER, respectively. We provide results for Gurobi 9.0 with 4 different time budgets, and for the heuristic with different configurations.
Dataset
IMDB
COLLAB
TWITTER
Scatteringllique (ours)
1.000 + 0.000 (4e-3)
0.999 +: 0.014 (0.029)
0,952 + 0.059 (0.05)
GCN (low-pass)
0.956 + 0.109 (3e-3)
0.981 4: 0.085 (0.020)
0.887 + 0.111 (0.04)
Erdös (fast)
1.000 0.000 (0.08)
0.982 0.063 (0.10)
= 1.94400115
(0.17)
Erdös (accurate)
1.000 + 0.000 (0.10)
0.990 0.042 (0.15)
0.942 = 0.111 (0.42)
RUN-CSP (fast)
0,823 + 0.191 (0.11)
0.912 0.188 (0.14)
0.909 + 0.145 (0.21)
RUN-CSP (acc.)
0.957 + 0.089 (0.12)
0.987 + 0.074 (0.19)
0,987 + 0.063 (0.39)
Gurobi 9.0 (0.1s)
1.000 + 0.000 (1e-3)
0.982 + 0.101 (0.05)
0.803 = 0.258 (0.21)
Gurobi 9.0 (0.5s)
1.000 1: 0.000 (Ie-3)
0.997 1: 0.035 (0.06)
0.996 = 0.019 (0.34)
Gurobi 9.0 (1s)
1.000 0.000 (1c-3)
0.999 + 0.015 (0.06)
1.000 + 0.000 (0.34)
Gurobi 9.0 (5s)
1.000 0.000 (1c-3)
1.000 0.000 (0.06)
1.000 + 0.000 (0.35)
Heuristic(5, 10)
0.912 0.190
+ (0.09)
0.706 + 0.188 (0.08)
Heuristic(5, 20)
0.972 11 0.081 (1.5e-2)
0.466 0.27 (0.17)
(0.14)
Heuristic(S, 30)
0,998 0.015 (1.8e-2
0.620 1 0.299 (0.26)
0.910 1 0.094 (0.29)
Heuristic (20, 20)
0.973 1 (5.8e-2)
0.469 1 0.277 (0.70)
0,940 1 0.098 (0.61)
Heuristic(1, (1, 100)
0,919 = 0.133 (6.0e-3)
0.847 + 0.257 (0.16)
0.689 = 0.260 (0.07)
Heuristic(5, (5, 100)
0.997 = 0.021 (2.7e-2)
0.916 + 0.201 (0.77)
0.920 = 0.084 (0.36)
TWITTER dataset (~~132 nodes on average), which is the real-world dataset with the largest graphs. The second dataset (LARGE) contains significantly larger graphs (~ nodes on average), that are far more challenging. In each of the two datasets, we have three different classes of hardness (easy, medium and hard) that are retained for different hardness parameters (0.2, 0.5 and 0.8) following the approach in Xu et al. 2005]. More details on the datasets can be found in Table 3 in Appendix B.
4.3 Evaluation
To evaluate the different models, we use average test approximation score (mean 1 standard deviation across three runs) and the average time needed to approximate the MC across the graphs of a dataset (in brackets) measured in seconds per graph (s/G). We note that the time requirement of Gurobi 9.0 can exceed the indicated time limit as it only affects subroutine of the method. On the real- world datasets and the proposed SMALL dataset, the approximation score of a given graph is computed by dividing the size of the clique found by the algorithm by the size of the true MC, i.e., if the MC of graph has size 10 and the algorithm returns a clique of size 9, it would be given a score of 90%. We then average these scores across all graphs in each dataset. On the proposed LARGE dataset, the MC size is unknown because it is virtually impossible to specify. Instead, we use the predicted MC size from Gurobi 9.0 (s) as target. Notably, this allows for approximation scores larger than 100% to arise, which signifies that the model found a better (larger) clique than Gurobi 9.0 (0.1s).
4.4 Experiments
We first look at the three real-world datasets and provide results in Table [ In the decoder (Section 3.5 we set x equal to 1, and 10 for the IMDB, COLLAB and TWITTER dataset, respectively. For the IMDB dataset, our hybrid approach and most other methods (except RUN-CSP) solve the MC problem with a perfect (100%) approximation score. However, our model significantly outperforms the other neural network-bard based models (Erdös' GNN and RUN-CSP) with respect to computation time (although the highly optimized Gurobi solver slightly faster than our method on this dataset due to the small graph size). On COLLAB, our model almost reaches perfect performance (99.99) (99.9% in 0.029 s/G, outperforming the other neural network based methods in both speed and approximation score. Some versions of the Gurobi solver are able to achieve 99.9% and 100% approximation scores, however, they are slower than our method on this dataset. The TWITTER dataset the most challenging of the considered real-world datasets. Here, our method achieves the second highest accuracy among neural networks with 95.2% compared to 98.7% for RUN-CSP (accurate). However, our method is nearly seven times faster than RUN-CSP (0.05 s/G 0.34 s/G). Similarly, while
8

---

there are several versions of Gurobi which achieve higher accuracy, these require at least 0.34 s/G. In principle, one could utilize faster versions of Gurobi, but those methods would achieve lower accuracies. For example, Gurobi 9.0 (0.1s) requires four times the time per graph compared to our method (0.21 s/G vs 0.05 s/G) while achieving a much lower accuracy (80.3% vs 95.2%)
Figure 3 illustrates the differences between our hybrid scattering model and the low-pass GCN-based model performs better
model [Kipf and Welling 2016] and helps explain why the scattering- across all three datasets. It shows that the probability vector p generated by our approach is more discriminative than the one produced by the low-pass model. When using the low-pass model, most nodes are assigned high probabilities (marked in red). The decoder cannot tell which nodes have higher priorities given such smooth output. This leads to the decoder accepting nodes which are not part of the MC. If the new clique is not sub-clique of the MC, this in turn can lead to the decoder rejecting nodes which are part of the MC. The scattering model on the other hand produces a less smooth representation. The nodes outside the MC are assigned lower probabilities so that our decoder can successfully find the MC. This consistent with previous work [Wenkel et al. [022] showing that graph scattering helps to alleviate oversmoothing in node classification. We emphasize that both models are trained with the same loss function and the same rule-based decoder. Therefore, the differences illustrated in Figure 3 are the direct result of using a hybrid scattering model. More comparison between the scattering model and low-pass model can be found in Appendix E.
0.2
02
0.0
00
Figure 3: Comparison of the output probability vector p for our model (left) and the low-pass model (right) graph taken from TWITTER with ground truth MC of size 10. Our approach followed by our decoder yields the correct clique, while the low-pass model concludes with a clique of size 8.
To further explore how our model performs on harder graphs, we now look at the newly proposed datasets generated according to the methodology of Xu et al. [2005]. Each dataset contains three subclasses (easy, medium and hard) and our decoder (Section 3.5) uses different parameters k (1, and 10), respectively. Here, we present the results of the most challenging LARGE dataset, shown in Table 2 while the discussion of the results on the SMALL dataset can be found in Appendix D.
Our hybrid scattering model outperforms the other neural network approaches on all three subclasses (easy, medium and hard) in terms of approximation score and inference time. The gap in approxi- mation score is larger on medium and hard samples, highlighting the utility of our model for more complex graphs At the same time, our model is extremely efficient, exhibiting much lower inference times than the other neural networks (with the exception of GCN, which is a modified version of our hybrid model with band-pass filters removed), e.g., inferring the MC on LARGE-hard 12 times faster than RUN-CSP (accurate). the closest competing neural network. For sufficiently large time budgets, Gurobi and the hcuristic [Xu et al. 2005) can achieve higher accuracies, however at a significantly higher time cost. For example, LARGE-hard, only Gurobi 9.0 (50.0s) and Heuristic(5 (5, 100) are better, however taking on average 131 and 49 times longer to infer the MC, respectively.
Overall, across all considered datasets, we remark that our hybrid model provides considerable speedup compared to both the other neural networks and to Gurobi for large graphs. We also note that our model takes fewer parameters than the Erdös' GNN [Karalias and Loukas 2020). They use a multi-head GNN (8 heads, with 64 hidden units each) for each layer, whereas the MLPs used in our method have d, 8 hidden units on all three datasets, without using any multi-head attention mechanism. This in turn suggests that the use of both GCN filters and scattering filters combined yields powerful feature extractors that help learn informative node representations with relatively few

---

Table 2: MC test approx. score (mean + std.) and avg. prediction time measured in seconds per graph (in brackets) on LARGE dataset for our model compared to the different baselines. In our decoder, we set is equal to 1, and 10 for the easy, medium and hard graphs, respectively. As ground truth sizes cannot be estimated for such large graphs, we compare to the cliques found by Gurobi 9.0 (0. Is). As explained in Sec. 4.3 the inference time of Gurobi can exceed the indicated time budget.
Datasct
LARGE-casy
LARGE-hard
Scattering (ours)
1.002 +: 0.053 (0.25)
1.045 + 0.171 (0.18)
1.102 1: 0.225 (0.46)
GCN (low-pass)
0.997 0.088 (0.23)
0,925 1 0.181 (0.16)
0.829 +: 0.302 (0.40)
Erdós (fast)
0.969 + 0.103 (1.08)
0.924 0.210 (1.61)
0.895 + 0.246 (1.96)
Erdös (accurate)
0.994 + 0.067 (4.74)
0.943 (5.62)
0.975 = 0.086 (5,50)
RUN-CSS (fast)
0.925 + 0.082 (1.65)
0.895 0.133 (2.53)
0.985 = 0.134 (1.44)
RUN-CSP (accurate)
0.985 0.072 (4.72)
0.913 (4.69)
1.034 = (5.58)
Gurobi 9.0 (0.1s)
1,000 = 0.000 (I0.5)
1.000 0.000 (10.6)
1.000 0,000 (9.46)
Gurobi 9.0 (0.5s)
1.000 +: 0.000 (12.1)
1.000 = 0,000 (11.0)
1.000 0.000 (9.97)
Gurobi 9.0 (1.0s)
1.000 + 0.000 (12.7)
1,000 = 0.000 (11.1)
1.000 - 0.000 (10.1)
Gurobi 9.0 (5.0s)
1.000 + 0.000 (16.4)
1,000 0.000 (14.7)
1.000 0.000 (14.2)
Gurobi 9.0 (20.0s)
1.005 0.070 (30.0)
1.094 - 0.290 (29.4)
1.016 + 0.122 (29.0)
Gurobi 9.0 (50.0s)
1.009 + 0.082 (65.9)
1,276 + 0.431 (55.4)
1.335 + 0.459 (60.3)
Heuristic(5, 10)
0.326 1 0.039 (1.6)
0.331 1: 0.050 (2.1)
0.311 1 0.072 (2.2)
Heuristic(5,22)
0.619 1 0.008 (3.2)
0.617 0.097 (4.5)
0.575 0.130 (4.6)
Heuristic
0.895 1 0.008 (4.9)
0.880 0.121 (6.7)
0.813 1 0.185 (7.1)
Heuristic(20, 20)
0.623 0.075 (12.9)
0.630 = 0.095 (17.8)
0.593 = 0.136 (18.5)
Heuristic(1, 100)
0.975 + 0.050 (2.7)
0.972 - 0.259 (3.7)
0,948 + 0.399 (4.6)
Heuristic(5, 100)
0.999 + 0.003 (13.8)
1.149 = 0.351 (18.8)
1.296 + 0.483 (22.9)
parameters. In fact, the Erdös' GNN model contains 1,880,709 parameters for each dataset, while we only use 1,297 parameters for Twitter, 705 for IMDB and 1,001 for COLLAB, respectively. This corresponds to 0.07%, 0.04% and 0.05% of the parameter counts of Erdös' GNN, while achieving better performance in terms of both inference time and accuracy. Further, since the K- K-layer GCN-type model has time complexity Edd,, + Knd?, [Wu et al., 2020), is important to reduce d,. We use d2 = 8 (and no multi-head attention), resulting in low time complexity and thus faster inference.
5
Conclusion
In this paper, show the expressive power of GNNs can be critical for solving graph CO problems. Our results suggest that low-pass models that generally enforce smoothness over graph neighbor- hoods due to oversmoothing, make the nodes indistinguishable, which leads to unfavorable node representations for the MC problem. Inspired by the geometric scattering transform, we propose an efficient scattering-bast baseed GNN overcome the oversmoothing problem. We use two-term loss function (previously derived by a different method in Karalias and Loukas (2000), which encourages network to find a set of nodes that are both highly connected and contained within a clique, which in conjunction mimic the otherwise hard to optimize problem of finding maximum cliques. Our model produces efficient node representations that enable to approximate the maximum clique a fast speed using a coustrain-preserviing greedy decoder. Overall, our performance is competitive with other neural network-based methods on common benchmark datasets, while largely reducing the number of parameters and computation time. When run on larger and more complex graphs, our hybrid scattering model outperforms other neural network approaches.
Acknowledgements
We would like to thank Yiwei Bai for discussions. This work was partially funded by Fin-ML CREATE graduate studies scholarship for PhD [Frederik Wenkel]; IVADO (Institut de valorisation des données) grant PRF-2019-358311972
FRQNT (Fonds recherche du Québec Nature et technologies) grant 299376, Canada CIFAR AI Chair; and NIH (National Institutes of Health) grant NIGMS-ROIGM (GMM13592 [Guy Wolf]. The content provided here is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
10

---

References
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20-1), 2008.
Marco Gori, Gabricle Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729-734. IEEE, 2005.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In the 4th International Conference on Learning Representations (ICLR), 2016.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pages 1263-1272. PMLR, 2017.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances Neural Information Processing Systems, page 539, 2018a.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization graphs. Advances in Neural Information Processing Systems, 33: 6679, 2020.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprini 19.Xiv:9906001227,, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirly-Second AAAI conference on artificial intelligence, 2018b.
Radu Horaud and Thomas Skordas. Stereo correspondence through feature grouping and maximal cliques. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(11):1188-1180 1989.
Yun Zhang, Faisal N Abu-Khzam, Nicole Baldwin, Elissa Chesler, Michael A Langston, and Nagiza Samatova. Genome-scale computational approaches to memory-intensivv applications in systems biology. In SC'05: Proceedings of the 2005 ACM/IEEE Conference on Supercomputing, pages 12-12. IEEE, 2005.
Frederik Wenkel, Yimeng Min, Matthew Hir,, Michael Perlmutter, and Guy Wolf. Overcoming oversmoothness in graph convolutional networks via hybrid scattering networks. arXiv preprint arXiv:2201.08992. 2022.
Alex Grossmann. Wavelet transforms and edge detection. In Stochastic processes in physics and engineering, pages 149-157. Springer, 1988.
David Shuman, Benjamin Ricaud, and Pierre Vandergheynst. Vertex-frequency analysis on graphs. Applied and Computational Harmonic Analysis, 40(2):260-29) 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: convolutional networks. Advances in Neural Information Processing Systems, 33, 2020.
Overcoming oversmoothness in graph
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms on graphs. In International Conference on Learning Representations, 2019.
Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 4963)3)):0466-007, 2019.
Feng Gao, Guy Wolf, and Matthew Hirn. Geometric scattering for graph data analysis. In Proceedings of the 36th International Conference on Machine Learning, PMLR, volume 97, pages 2122-2131, 2019.

---

Ronald R Coifman and Mauro Maggioni. Diffusion wavelets. Applied and computational harmonic analysis, 21(1):53-94, 2006.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations, 2021.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:580607, 2021.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https://ww/ www
gurobi.com com
Andrea Grosso, Marco Locatelli, and Wayne Pullan. heuristics for the maximum clique problem. Journal of Heuristics, 14(6):587-612, 2008.
Simple ingredients leading to very efficient
Pinar Yanardag and SVN Vishwanathan. Deep graph kemnlss. In Proceedings the 2/th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
Xifeng Yan, Hong Cheng, Jiawei Han, and Philip S Yu. Mining significant graph patterns by leap search. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 433 444, 2008
Ke Xu, Frederic Boussemart, Fred Hemery, and Christophe Lecoutre. simple model to generate hard satisfiable instances. In Proceedings of the 19th international joint conference on Artificial intelligence, pages 337-342, 2005.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, (2)44:4-4 24, 2020.
12


Reviews:
[{"review_id": "rnQbSpk5M-6", "reviewer": "Reviewer_aPGv", "summary": "The paper proposes to tackle the maximal clique problem in graphs with a hybrid method that relies on a scattering step as well as a rule-based decoder step to extract the predicted maximal clique. Overall, the paper is novel, clearly written and self-contained.", "questions": "- The approximation score seems to only measure the \"size\" of the MC, but not if it's correct or not? (like an overlap to the ground truth?)\nplease clarify why you don't measure overlap (like Jaccard) to the ground truth.", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Relevant contribution to address oversmoothing of GNNs via scattering approach for MC retrieval\n- Clear paper structure, the reader is taken by the hand\n- The method outperforms the baselines in several datasets\n\nWeaknesses:\n\n- Section 1 misses some motivation: why should the general ML audience care about MC? Why is it interesting?\n- Notation is a bit sloppy sometimes: Concat operation in Eq 7 not introduced, attention scores a become alpha l.109-112. element-wise operation in Eq not defined, shape dims of H_cat not defined, Objective L*(C) is a bit poorly formalized (make explicit: max_{terms to maximize over}, p \\geq 0 in l.136 seems hand wavy, \n- Proof of Lemma 1 is a bit quick/short: where do u_0, v_0 come from? Maybe I just missed something, but this point needs more clarification as it's not obvious to me.\n\n- Result section could be structured more: Baselines, Evaluation metric, Results \n- The approximation score seems to only measure the \"size\" of the MC, but not if it's correct or not? (like an overlap to the ground truth?)\n\nFurther details:\n- l.124: we also want.. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K8B_5_k28ves", "reviewer": "Reviewer_fuxA", "summary": "The paper proposes a novel model that is trained without supervision to solve the maximum clique problem. Furthermore, a greedy decoding scheme is proposed to enable the discretization of the continuous output from the neural network. The model architecture relies on the scattering transform which has been proposed to avoid oversmoothing in GNNs. The proposed model achieves competitive results on common experimental benchmarks and on synthetically generated instances of varying difficulty.", "questions": "1) Did the authors use the RB model to generate the instances of table 3? Did the authors code it up from scratch? I could not find the implementation in the code provided. More details about the exact setup would be appreciated.\n2) Apart from over-smoothing, does the scattering architecture offer a particular benefit for the maximum clique problem? It is not clear to me whether the choice of this architecture relates to this particular problem or not.\n", "limitations": "The authors have not discussed the limitations or the societal impact (arguably not applicable here) of their work.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1) The approach is simple and well explained in the paper.\n2)  The authors evaluate on an experimental setup from the literature, making comparisons with related work easier.\n3) Results appear to be competitive across multiple datasets.\n\n## Weaknesses and criticism\n1) Parts of this paper's pipeline are not properly attributed to previous work. For example, the loss function includes two terms: \nthe expected weight of the edges in the selected set, and the expected weight of the edges on the complement graph. \nThis is essentially the loss function used in the paper by Karalias and Loukas (henceforth KL for brevity) that the authors cite throughout the paper, but not specifically for the loss. In fact, line 217 in the conclusion claims \"We further construct a novel two-term loss function...\". I think it is fair to say that this construction is not novel.\nThe loss function may appear to be different from the one in KL but is actually extremely similar, minus a few additional steps that are required in KL to secure the theoretical guarantee. To understand the similarity, it suffices to check the proof of corollary 1 in the appendix of that paper. The probability of constraint violation amounts to the expected weight on the complement graph (denoted by  the expectation of $\\bar{w}(S) $). \nHowever, that paper rewrites the term as a function of the graph itself and avoids the computation in the complement. This is the main reason behind the apparent differences between the two loss functions. Using both the original graph and its complement has the inevitable drawback of not exploiting the sparsity of the graph since at least one of the two will inevitably be dense. Ultimately, the proposed loss is a slightly simplified rewriting of the KL loss.\n\n2) The authors emphasize the over-smoothing problem, but this can be overcome with various architectures and/or skip connections. Indeed, both the Erdos paper and RUN-CSP do not just use plain GCN architectures and manage to do fairly well. I am not entirely convinced that the proposed model offers a substantial benefit.\nPerhaps some ablations that demonstrate the over-smoothing problem on existing implementations of combinatorial ML papers from the literature would have helped.\n\n3) Minor issue: the authors mention the \"maximal clique\" problem although I think they mean to say \"maximum\". Given that the authors mention the hardness of the problem and approximation ratios, I assume that maximum is the term that applies (maximal cliques can be found easily).\n\n4) Experimentally, it would be good to see how the other techniques (e.g., Erdos or RUN-CSP) perform on Xu instances (table 3).  A greedy heuristic would also be nice as well.\n\n5) Apart from the different model, this approach does not significantly differ from works like the KL paper or even RUN-CSP, with the added limitation that it only addresses the maximum clique problem.\n\n6) Scalability is not addressed in the paper. Does the proposed model scale well on larger graphs? The instances that this was tested on have at most a few hundred nodes. Given that the paper places heavy emphasis on the model, more thorough experimental demonstrations are required in that regard as well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8Uv5539t2GC", "reviewer": "Reviewer_7b6z", "summary": "The maximum clique problem is a classic NP-hard combinatorial optimization problem with numerous applications. Because of its difficult, heuristics that find good solutions fast are desirable, and there has been a few works that have explored machine learning for designing such algorithms. In this paper, the authors propose a novel approach based on a GNN that is trained by supervised learning to predict the probability of a node to belong to a maximal clique, followed by a greedy algorithm (a decoder) which constructs as large a clique as possible from the probabilities. In departure from previous work, they propose that the model use a geometric scattering transform, which reduces neighbor smoothing. They show improvements on empirical datasets against alternative neural network approaches, and Gurobi with a time limit.", "questions": "- I don't really understand why the decoder has a Tau parameter. Why not set Tau=infinity? Isn't the goal to have a large a clique as possible?\n- I don't understand why the time limits given to Gurobi are not respected. Ex. in table 1, how come Gurobi with a 0.1s time limit takes 0.21s?\n- Why are the competing neural network approaches are missing from Table 3?\n- A more theoretical question regards non-uniqueness of solutions: maximum clique problems, especially unweighted, can often have many optimal solutions. When this is the case, won't the unsupervised loss try to steer the GNN towards an average of the solutions, leading to something which is not a maximal clique?\n- I don't understand why approximation ratio is chosen as a ranking criterion in Table 1, but time is chosen as a ranking criterion in Table 3. I feel there is some cherry-picking here to make the method look best.\n", "limitations": "- I see that the method is often not competitive with Gurobi with a time limit, which makes me believe that the results would be even less competitive against human-designed heuristics for the problem. Right now, I don't think the authors really address this, which I think they should. At minimum, I think the results are too mixed to assert that the method is \"competitive with commercial solvers in time and accuracy\". ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The method looks faster than competing machine learning methods, at comparable performance (although this needs to be nuanced by some issues I have about the experimental results, which I detail in the weaknesses section.)\n- The geometric scattering transform idea makes sense, although I am not sure whether there is something specific here about the MC problem: I would feel like the explanation given in this work would apply to many other GNN-based heuristics for graph-based combinatorial problems (e.g. vertex cover, independent set, etc.) But this is a good thing I suppose.\n- The fact that the proposed training loss is unsupervised, yet differentiable, is an advantage, although I wonder what would happen if the GNN was trained in a supervised fashion to approximate pre-computed maximal cliques.\n\nWeaknesses\n\n- I have several issues with the experimental results. First, I find the benchmarks a little too easy: since the approximation ratio is your criterion, it is difficult to disentangle the different methods if the ratios are so high. This is particularly problematic for the IMDB dataset.\n- Second, I don't really find the bolding very fair. Why highlight the two best methods in Table 1? I find it difficult to not see it as a way to hide the fact that your method is not the best on the hardest dataset (Twitter).\n- I don't understand why no \"normal\" maximal clique heuristics are included - for example see Grosso et al. (2008). Instead you only have results against Gurobi with a time-limit, which is not really designed for your objective at hand (finding as good solutions as possible, fast). Although I can understand that it might be difficult to improve over state-of-the-art human-designed heuristics, not including them makes it difficult to assess problem difficulty.\n\n\nGrosso, A., Locatelli, M. and Pullan, W., 2008. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics, 14(6), pp.587-612.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept