Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

- Relevant contribution to address oversmoothing of GNNs via scattering approach for MC retrieval
- Clear paper structure, the reader is taken by the hand
- The method outperforms the baselines in several datasets

Weaknesses:

- Section 1 misses some motivation: why should the general ML audience care about MC? Why is it interesting?
- 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, 
- 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.

- Result section could be structured more: Baselines, Evaluation metric, Results 
- 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?)

Further details:
- l.124: we also want.. 

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?)
please clarify why you don't measure overlap (like Jaccard) to the ground truth.
limitations: -
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths

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

Weaknesses

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


Grosso, 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.
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?
- 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?
- Why are the competing neural network approaches are missing from Table 3?
- 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?
- 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.

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".
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: ## Strengths
1) The approach is simple and well explained in the paper.
2)  The authors evaluate on an experimental setup from the literature, making comparisons with related work easier.
3) Results appear to be competitive across multiple datasets.

## Weaknesses and criticism
1) Parts of this paper's pipeline are not properly attributed to previous work. For example, the loss function includes two terms: 
the expected weight of the edges in the selected set, and the expected weight of the edges on the complement graph. 
This 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.
The 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) $). 
However, 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.

2) 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.
Perhaps some ablations that demonstrate the over-smoothing problem on existing implementations of combinatorial ML papers from the literature would have helped.

3) 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).

4) 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.

5) 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.

6) 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.
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.
2) 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.

limitations: The authors have not discussed the limitations or the societal impact (arguably not applicable here) of their work.
review_title: null

Meta-review: metareview: All reviewers agree that the proposed approach to use the geometric scattering transform is simple and effective both computationally and in terms of the ability of the method to identify larger cliques for the max-clique problem (except perhaps for one reviewer on the last point).

The work would have more impact if it could be demonstrated that using the geometric scattering transform yields improvement for other combinatorial optimization problems on graphs, or if it could outperform classical heuristics even if they are run for longer time. Currently the experiments presented in the appendix are more compelling than the experiments presented in the main paper.
Given elements they provided in the discussion with the reviewers, the authors should also emphasize more clearly in the paper how their proposed architecture differs from other scattering GCNs that have been proposed, and I would suggest to do an ablation study to show that the enhancements that they introduced in the architecture are actually useful.

A consensus between all reviewers could unfortunately not be found: 
- Two reviewers were satisfied with the way the authors had addressed their concerns and with the additional experiments proposed.
 - One reviewer considers that the idea of using the scattering transform in this application is not a sufficient contribution to grant publication.

Given that
- two reviewers find the contribution compelling and their concerns are well addressed
-  the use the geometric scattering transform is simple and yet effective both computationally and in terms of the ability of the method to identify larger cliques
- the sole motivation of the reviewer who votes for rejection is a claim that the scientific contribution is not sufficient against the opinion of the two reviewers and that of the AC,
 
the AC is in favor of acceptance.

### Acknowledging that the proposed loss function is the same as in Karalias and Loukas (2021) !

One element which is very important is that the discussion with one of the reviewers has clearly established that **the loss function introduced in this paper is exactly the same** (up to a constant and a multiplicative factor) **as the loss function $\ell_{\text{clique}}$ obtained in** Corollary 1 of **Karalias and Loukas (2021)**.

In the discussion with the reviewer, the authors wrote
 "We are happy to add discussion and clarification of the loss terms to our manuscript. This discussion and clarification can also help readers to understand the model better." (which I entirely agree with) but they did not act upon that, yet...
 
It would now be more than **absolutely necessary to add that discussion** ! This will add value to the paper as it will show that the proposed loss is less ad hoc than it might seem, given that it can be obtained via at least two routes. Moreover establishing connections between approaches in the literature is clearly a valuable contribution.

Currently, the conclusion says: "We further construct a two-term loss function which [...]" which still strongly suggests that the loss function is novel, and it therefore very problematic ethically. The sentence added in blue on line 186 is not sufficient to address the issue.

**The authors should** at the very least **add a sentence** at the beginning of section 3.4 **saying** something like: "We propose a simple derivation of a multi-objective loss function, and retrieve **a loss function which was also obtained by Karalias and Loukas (2021)** as a natural upper bound to the probabilistic penalty loss that they propose".
And at the end of section 3.4, the authors should add a sentence saying: **"The proposed loss matches the loss $\ell_{\text{clique}}$ obtained in Corollary 1, Section 4.1 of Karalias and Loukas (2021)."**
confidence: Certain
Decision: Accept