Clique Number Estimation via Differentiable Functions of Adjacency Matrix Permutations

W 1.2. algorithms for approximate maximum clique detection or k-clique detection [2,3].

Scaling Up k-Clique Densest Subgraph Detection (SCTL) (paper [3] cited by the reviewer)

The SCTL paper addresses the k-clique densest subgraph problem. To use SCTL for clique number detection, we initially employed the same protocol as MxNet, SCOPE, and NeurSC ― incrementally increasing k from 2 to $\omega(G)$. However, we found that when $k$ is smaller than $\omega(G)$, the increase in the number of $k$-cliques leads to prohibitively long runtimes ― often hundreds of seconds per graph for a single $k$, which is far from the millisecond-level inference times achieved by MxNet and other baselines.

To optimize SCTL's runtime, we reversed the search direction: starting with the maximum possible clique size (equal to the graph size), we detect the absence of a clique (which is much faster) and decrease $k$ until a clique is detected. This adjustment significantly reduces computational overhead. However, SCTL is still 5x (PTC-MM-m, Brock) to 20x (AIDS-m, MUTAG-m) slower than MxNet.

We could not find the code of "Finding the maximum clique in massive graphs, VLDB 2017".

W2.1: The authors seem to argue that relying on "extreme or no supervision" is not beneficial (Line 061)... A better explanation would help the understanding of this paper.

We meant to state that existing methods fall in two broad regimes. Combinatorial methods often use no training at all, whereas methods from the ML community (e.g., Sun & Yang, 2024) depend on full supervision with a demonstration of an actual maximal clique. Our paper focuses on the neglected middle ground where supervision is provided as only the clique number (which can be estimated from various efficient relaxations) and not a clique demonstration (which is computationally expensive to arrange for training). In several graph search and retrieval scenarios, the relevance of a corpus graph depends on the extent to which query and corpus graphs overlap, which can be reduced to a maximum common induced subgraph (size) computation. In such cases, only clique number is available for supervision. We have updated the paper with further explanation.

W2.2 existing methods for estimating the clique number are not sufficiently explored.

We were unable to find neural models that estimate clique number with less emphasis on maximum clique. But we discussed papers from discrete algorithms on clique number estimation without maximum clique computation in Section 1.2. We indeed thank the reviewer for the suggested papers from database domain, which are quite intriguing. We added those and some other papers which we found to be related in Appendix C, where we discussed related work in details.

W3.1: the clique number can be bounded bound-based baseline would be a good choice.

We consider the following three Lower-Bounds and four Upper-Bounds from "Exact bounds on the order of the maximum clique of a graph," Budinich. 2003, Discrete Applied Mathematics (In Eq 7, Eq 4).

In particular, the bounds are:

1. (UB) Eq. 1:
   $\omega(G) \leq \frac{3+\sqrt{9 - 8(|V| -|E|)}}{2}$

2. Let $\rho(G)$ denote the spectral radius of the adjacency matrix $A$ of $G$. Then,
   (UB) Eq. 2:
   $\omega(G) \leq \rho(G) + 1$

3. Let $N _{-1} =|\{\lambda _i: \lambda _i \leq -1\}|$ where $(\lambda _i) _{i=1}^{|V|}$ denote the eigenvalues of $A$. Then,
   (UB) Eq. 3:
   $\omega(G) \leq N _{-1} + 1$

4. Let $\bar{A}$ denote the adjacency matrix of the complementary graph of $G$. Then,
   (UB) Eq. 4:
   $\omega(G) \leq|V| - \frac{\text{rank}(\bar{A})}{2}$

5. (LB) Eq. 5:
   $\omega(G) \geq \frac{1}{1 - \frac{2|E|}{|V|^2}}$

6. Let $\lambda _P$ denote the Perron eigenvalue of $A$, and $\mathbf{v} _P$ denote the corresponding eigenvector. Then,
   (LB) Eq. 6:
   $\omega(G) \geq \frac{\lambda _P}{(\mathbf{1}^\top \mathbf{v} _P)^2 - \lambda _P} + 1$

7. Let $\lambda _j$ denote an eigenvalue of $A$, and $\mathbf{v} _j$ denote the corresponding eigenvector. Define
   $g _j(\alpha) = \frac{\alpha^2\lambda _j + (1-\alpha^2)\lambda _P}{\alpha (\mathbf{1}^\top \mathbf{v} _j) + \sqrt{1-\alpha^2}(\mathbf{1}^\top \mathbf{v} _P)}.$
   For each $j$, $g _j(\alpha)$ is defined on
   $\left[\max _{i: \mathbf{v} _{ji} > 0} \frac{-\mathbf{v} _{Pi}}{\sqrt{\mathbf{v} _{Pi}^2 + \mathbf{v} _{ji}^2}}, \min _{i: \mathbf{v} _{ji} < 0} \frac{\mathbf{v} _{Pi}}{\sqrt{\mathbf{v} _{Pi}^2 + \mathbf{v} _{ji}^2}}\right].$
   Then, for graphs which are not regular complete multipartite,
   (LB) Eq. 7:
   $\omega(G) \geq \frac{1}{1 - \max _{j,\alpha} g _j(\alpha)}$

We report the MSE values of the best of the lower and best of the upper bounds as follows.

We observe that our method performs better.

We thank the reviewer for their suggestions, which we discuss below and have incorporated in the paper.

W1.1: A related field is subgraph counting [1,4].

We appreciate the reviewer’s suggestion regarding subgraph counting methods as potential baselines for our problem of clique number estimation.

Neural Subgraph Counting with Wasserstein Estimator (NeurSC) [1]

We adapt NeurSC ([1] cited by reviewer) as a baseline for our clique number prediction method by employing increasing $k$-cliques as query graphs and determining the subgraph count for each. The clique number is then estimated as the largest value of $k$ for which a non-zero count is returned. We present the results (MSE) of NeurSC in the following table, which shows that our method MxNet performs better.

We have also incorporated NeurSC's results into Table 1 of the main paper for completeness. While our proposed MxNet method consistently outperforms NeurSC across all datasets, NeurSC demonstrates strong performance in certain scenarios. Specifically, it ranks as the third-best performer among decoder and non-decoder models for the Enzymes and RB datasets. Additionally, among non-decoder-based models, NeurSC ranks third for the PTC-MM-m, AIDS-m, and MUTAG-m datasets. These results underscore the utility of integrating neural modules to obtain clique presence certificates, which are effective for clique number estimation.

We thank the reviewer for suggesting this highly relevant and competitive baseline, which has enriched our analysis and strengthened our comparisons.

Fast Local Subgraph Counting (SCOPE) [4]

SCOPE is a tree-decomposition-based method for local subgraph counting. It estimates the occurrence of a given query graph in the local neighborhood of each node within the corpus graph and provides a count for every corpus graph node. The method utilizes tree decomposition and symmetry-breaking rules to minimize redundancy and incorporates a novel multi-join algorithm for efficient computation. To predict the clique number, we supply SCOPE with a set of query clique graphs and retrieve the corresponding local subgraph counts. For every query clique smaller than the clique number, at least one node in the corpus graph contains the clique pattern in its local neighborhood. We determine clique presence by taking the maximum of the individual neighborhood counts, and the largest query clique with a non-zero count is deemed the predicted clique number.

It is important to note that SCOPE addresses a significantly more challenging task: estimating the count of patterns in each local neighborhood. As such, it naturally requires substantially more computational time compared to MxNet and earlier global subgraph counting methods. For each query–corpus graph pair provided to SCOPE, we set a timeout from the range [0.1, 1, 10, 100] seconds. If the timeout elapses without returning a result, we assume that no cliques were detected, and the clique number is determined accordingly.

The table below presents the performance of SCOPE under various timeout settings for each corpus graph. For MxNet, the numbers in parentheses indicate the average time taken per corpus graph (in seconds). We compare SCOPE against MxNet in terms of mean squared error (MSE).

We observe MxNet significantly outperforms SCOPE across all datasets when SCOPE is limited to a per-graph time of 0.1 seconds, which is comparable to the highest inference time taken by MxNet. Also, SCOPE's MSE consistently improves as it is afforded more computational time per graph, achieving perfect predictions on datasets such as Enzymes, AIDS-m, and PTC-MM-m. However, these improvements come at the cost of a substantial increase in inference time—exceeding 50x compared to MxNet.

Additionally, on several datasets, SCOPE is unable to outperform MxNet even when given up to 100 seconds per graph, while MxNet achieves superior accuracy at a fraction of the computational cost. This behavior is expected, as SCOPE tackles a more challenging task of local subgraph counting, a level of granularity that is unnecessary for the specific task of clique number prediction. These results highlight MxNet's efficiency and suitability for practical applications requiring fast and accurate inference.

W3.2: [large datasets] Email and Amazon would be helpful to asses the performance of the MXNET.

There are two reasons why our primary focus was not on large graphs in the initial version. However, we have now stress-tested our method with additional experiments, as described later.

(1) Our goal is to design an end-to-end differentiable model ― which is guided by the needs of practical applications like estimation of size of maximum induced common subgraph for graph simialrity. These applications typically involves fewer than 200 nodes (but possibly very many graphs).

Still, some of our datasets are much larger than the datasets used by the baselines. Specifically, our method uses graphs with upto 33K edges (Mutag-m), which is larger than all other datasets used in any end-to-end differentiable neural network based method. Moreover, we use the RB dataset, which is known to be notoriously hard for clique detection. Since clique number computation stands out as one of the hardest NP-complete problems [A,B], designing neural methods for even such moderate sized graphs is already quite challenging. It is unsurprising that neural methods have all limited themselves to relatively small graphs.

(2) Like any other ML task, neural clique detectors need multiple graphs for training and one entire graph represents one instance of data. Data sets with a single large graph are more common than data sets containing multiple large graphs with known clique numbers, which prevents a neural method to test its performance on large graphs. Nevertheless, we have the following proposal to predict clique number for a large graph, from which all neural models can benefit.

We decompose a large graph $\mathcal{G}$ into overlapping subgraphs $G _1,..,G _N$ each with moderate sizes. Then, the clique number of $\mathcal{G}$ is estimated as $\max _i \omega(G _i)$. This decomposition is helpful because (1) ground truth clique number generation is much easier in smaller graphs and (2) a neural clique detector requires multiple (graph, clique number) pairs for training. The risk of missing a clique straddling multiple subgraphs can be reduced via various degree based or K-core decomposition based heuristics.

During the rebuttal, we worked with Amazon and email-Enron datasets. Amazon has 334,863 nodes and 925,872 edges. email-Enron has 36,692 nodes and 183,831 edges. The table below shows the true and predicted clique numbers.

We note that in each dataset, (1) MxNet was trained on a small set of subgraphs, sampled from the available single large graph, with corresponding ground truth clique numbers found using the Gurobi solver. During inference, MxNet effectively generalized to a much larger set of subgraphs extracted using degree-based heuristics, to ensure more comprehensive coverage of the large graph; (2) MxNet correctly identifies the subgraph containing the largest clique of the whole graph, i.e., $\arg \max _i \omega(G _i) = \arg \max _i \widehat{\omega}(G _i)$; (3) MxNet correctly predicts most of the member nodes of the maximum clique within the graph; (4) MxNet's predicted clique number for the large graph closely approximates the true clique number ― much better than the predictions made by baselines, even with smaller graphs.

[A] Håstad, J. (1999), Clique is hard to approximate within $n^{1-\epsilon}$, Acta Mathematica.

[B] Zuckerman, D. (2006), Linear degree extractors and the inapproximability of max clique and chromatic number, STOC.

whether the trained model can generalize to different datasets

We train our model on AIDS-m and use it for testing on PTC-MM-m, to get an MSE of 0.802. When our model was trained on PTC-MM-m and tested on itself, we got an MSE of 0.204. Our approach approximates an NP-hard problem. To do so, we primarily exploite the distributional patterns present in the training data, enabling the model to specialize in those specific characteristics. Consequently, in out-of-distribution (OOD) experiments—where the training and testing datasets differ—the model's performance may degrade as it encounters patterns and distributions it has not been optimized to handle.

Thank you for your comments and the improved version of the paper. It has well addressed my concerns, and thus I update the score.

Thank you very much for your encouraging comments.

[Contd from above]

• In MxNet (MSS), the goal is to find node permutation $S$ that brings all 1s in $S A S^\top$ into a dense submatrix. Achieving this requires moving the zeros to the right places. When $S$ is relaxed to continuous values, non-zeros spread throughout $S A S^\top$, making it difficult to detect the MSS. Various thresholds or nonlinearities nay reduce the problem, but also attenuate gradient signals when $x_u^\top x_v$ is very high or very low. Thus, $x_u^\top x_v$ scores serve as auxiliary signals for clique detection, but simply adding them to $A$ contributes much noise in the estimate of $\omega$. In contrast, the form $S (A \odot XX^{\top}) S^\top$ is better at absorbing the signal from $\{x_u\}$ without succumbing to its noise.

• As a further mechanistic discussion, suppose, instead of $A\odot XX^{\top}$, we use only the binary adjacency matrix $A$. Then, for each parameter $\theta\in \mathbb{R}$, the gradient term will involve computation of $S A \frac{dS^{\top}}{d\theta} + \frac{dS}{d\theta} A S^{\top}$. Since $S$ is computed using iterative normalization of rows and columns, starting with an exponential term, $\frac{dS}{d\theta}$ will contain terms such as $S_{ij} S_{i'j'}$ [2]. Thus, $S A \frac{dS^{\top}}{d\theta}$ contain terms of the form $S_{ij} S_{i'j'} S_{i''j''}$, with each $S_{.,.} \in [0,1]$. This leads to attenuation of gradient signals. If we keep $A\odot XX^{\top}$, then the gradient will have $S_{ij}S_{i'j'}$ $[\frac{d XX^T}{d\theta}]_{a,b}$, which will allow more significant gradient signals. Moreover, due to continuous adjacency entries, $S _{ij} S _{i'j'} S _{i''j''}$ will now be replaced with $S _{ij} S _{i'j'} S _{i''j''} X _{a,b} X _{a',b'}$, where $X$s can control the gradient signals better, leading to actual learning of clique number computation for a distribution over graphs.

[1] In neural NLP, it is common to pretrain a language model for masked word prediction, and simultaneously train for a suite of common language tasks (e.g., FLAN-T5), or fine-tune them later. We follow the same strategy.

[2] This can be obtained from the derivative of softmax probabilities $\frac{d}{do_k} e^{o_j} / \sum_i e^{o_i} = -(e^{o_j} / \sum_i e^{o_i}) (e^{o_k}/ \sum_i e^{o_i})$

(2) Relaxing Algorithm 1 using message passing GNN: $MSS(B)$ can accurately compute clique only when $B$ has (close to) binary values. However, our computation of $SWS^T$ involves relaxation of binary values to real values in $(0,1)$ from $S$ and +ve/-ve from $W$, which makes the entries of $B[i,j]$ to be +ve/-ve real numbers. Further, multiplication by B[i,j] in line 7 in Algorithm 1 compounds this issue. To reduce these deleterious effects of fractional numbers on clique detection, several thresholding/clipping functions, such as Sigmoid, Tanh, ReLU, and ReLU6, may be applied, achieving varying degrees of success (we tried these). However, the best results were obtained by our final GNN-inspired solution, which could implement some form of local adaptive soft thresholding, as the message wavefront progressed. Note that this GNN is extremely lightweight, consisting of only 20 parameters.

Below, we compare the results of the best non-GNN thresholding variant (ReLU1 = min(max(0,x), 1)) against the results of MSS with the GNN-based Algorithm 1 implementation.

We observe that using a GNN based implementation for Algorithm 1 gives a performance improvement (lower error) across all datasets.

(3) Relaxing clique coverage loss in MxNet: $\min _P[K _c-PAP^{\top}] _+$ is a quadratic assignment problem (QAP), which is a hard problem to solve. Moreover, the binary values of $A$ and $K _c$ attenuate the gradient signals as described in the last para of item (1) above. We overcome the above challenges by replacing $\min_P[K _c-PAP^{\top}] _+$ with $[Q _c-SX] _+$. Instead of solving QAP, it solves a linear assignment problem, which is more tractable; and allows substantial gradient signals.

[curriculum learning] is full sequence of c is helpful?

This is indeed a great suggestion. We performed experiments where in Eq (9), we limited the first inner summation to only $c= \omega(G)$ and the second summation to only $c=\omega(G)-1$. The following results show that summation from 2 to $\omega(G)$ shows better result.

This is because, summation from 2 to $\omega (G)$ is providing more explicit guidance to the learner that, $K_2,..K_c$ are subgraphs of $G$. Otherwise, it is unable to reason that if $K_c$ is a subgraph of $G$ then also $K_2,..,$ are also subgraphs of $G$.

We thank the reviewer for their suggestions, which we address as follows. We have also added them in the revised version of the paper.

the computational burden of the MxNet model may be a concern when dealing with larger graphs

The limitation we stated applies not just to our method but for all neural methods. There are two reasons why our primary focus was not on large graphs in the initial version. However, we have now stress-tested our method with additional experiments, as described later.

(1) Our goal is to design an end-to-end differentiable model ― which is guided by the needs of practical applications like estimation of size of maximum induced common subgraph for graph simialrity. These applications typically involves fewer than 200 nodes (but possibly very many graphs).

Still, some of our datasets are much larger than the datasets used by the baselines. Specifically, our method uses graphs with upto 33K edges (Mutag-m), which is larger than all other datasets used in any end-to-end differentiable neural network based method. Moreover, we use the RB dataset, which is known to be notoriously hard for clique detection. Since clique number computation stands out as one of the hardest NP-complete problems [A,B], designing neural methods for even such moderate sized graphs is already quite challenging. It is unsurprising that neural methods have all limited themselves to relatively small graphs.

(2) Like any other ML task, neural clique detectors need multiple graphs for training and one entire graph represents one instance of data. Data sets with a single large graph are more common than data sets containing multiple large graphs with known clique numbers, which prevents a neural method to test its performance on large graphs. Nevertheless, we have the following proposal to predict clique number for a large graph, from which all neural models can benefit.

We decompose a large graph $\mathcal{G}$ into overlapping subgraphs $G_1,..,G_N$ each with moderate sizes. Then, the clique number of $\mathcal{G}$ is estimated as $\max_i \omega(G_i)$. This decomposition is helpful because (1) ground truth clique number generation is much easier in smaller graphs and (2) a neural clique detector requires multiple (graph, clique number) pairs for training. The risk of missing a clique straddling multiple subgraphs can be reduced via various degree based or K-core decomposition based heuristics.

During the rebuttal, we worked with Amazon and email-Enron datasets. Amazon has 334,863 nodes and 925,872 edges. email-Enron has 36,692 nodes and 183,831 edges. The table below shows the true and predicted clique numbers.

We note that in each dataset, (1) MxNet was trained on a small set of subgraphs, sampled from the available single large graph, with corresponding ground truth clique numbers found using the Gurobi solver. During inference, MxNet effectively generalized to a much larger set of subgraphs extracted using degree-based heuristics, to ensure more comprehensive coverage of the large graph; (2) MxNet correctly identifies the subgraph containing the largest clique of the whole graph, i.e., $\arg \max_i \omega(G_i) = \arg \max_i \widehat{\omega}(G_i)$; (3) MxNet correctly predicts most of the member nodes of the maximum clique within the graph; (4) MxNet's predicted clique number for the large graph closely approximates the true clique number ― much better than the predictions made by baselines, even with smaller graphs.

[A] Håstad, J. (1999), Clique is hard to approximate within $n^{1-\epsilon}$, Acta Mathematica, 182.

[B] Zuckerman, D. (2006), Linear degree extractors and the inapproximability of max clique and chromatic number, STOC.

differentiable approximation of the combinatorial MCP: Benefits of first and third approximation and submatch?

(1) Benefits of relaxing binary adjacency matrix to continuous values: In the following, we show the results of ablation study.

We observe that our smooth surrogate works better.

Next, we discuss the rationale for our design, and plausible explanations for its success.

• CLIQUE is a classical hard-to-approximate problem in the worst case, so the promise of neural methods is to take advantage of distributions from which graphs are generated in an application. A natural [1] way toward this goal is to train node representations $x_u$ that simultaneously predict the graph $A$ (via a generic GNN that aligns $x_u^\top x_v$ with $A[u,v]$), and make clique number prediction feasible (through a suitable task-customized network) ― in a graph containing a $k$-clique that includes nodes $u$ and $v$, they share the same $k-1$ node neighborhood, leading to a high $x_u^\top x_v$ value.

We thank the reviewer for their feedback. We address them here and have also added them in the revised version of the paper.

adding a figure illustrating the task

Acting on your suggestions, we have overhauled Figure 1, clearly showing how maximal dense subsquare detection works, and then illustrate the nested tests for a series of sub-clique containment tests, and finally the overall differentiable composite loss. The caption has been modified to be clearer and more descriptive.

purpose of smooth surrogate for the adjacency matrix? ... ablation study

In the following, we show the MSE from ablation study, which shows smooth surrogate works better (smaller MSE).

Next, we discuss the rationale for our design, and plausible explanations for its success.

• CLIQUE is a classical hard-to-approximate problem in the worst case, so the promise of neural methods is to take advantage of distributions from which graphs are generated in an application. A natural [1] way toward this goal is to train node representations $x_u$ that simultaneously predict the graph $A$ (via a generic GNN that aligns $x_u^\top x_v$ with $A[u,v]$), and make clique number prediction feasible (through a suitable task-customized network) ― in a graph containing a $k$-clique that includes nodes $u$ and $v$, they share the same $k-1$ node neighborhood, leading to a high $x_u^\top x_v$ value.
• In MxNet (MSS), the goal is to find node permutation $S$ that brings all 1s in $S A S^\top$ into a dense submatrix. Achieving this requires moving the zeros to the right places. When $S$ is relaxed to continuous values, non-zeros spread throughout $S A S^\top$, making it difficult to detect the MSS. Various thresholds or nonlinearities nay reduce the problem, but also attenuate gradient signals when $x_u^\top x_v$ is very high or very low. Thus, $x_u^\top x_v$ scores serve as auxiliary signals for clique detection, but simply adding them to $A$ contributes much noise in the estimate of $\omega$. In contrast, the form $S (A \odot XX^{\top}) S^\top$ is better at absorbing the signal from $\{x_u\}$ without succumbing to its noise.
• As a further mechanistic discussion, suppose, instead of $A\odot XX^{\top}$, we use only the binary adjacency matrix $A$. Then, for each parameter $\theta\in \mathbb{R}$, the gradient term will involve computation of $S A \frac{dS^{\top}}{d\theta} + \frac{dS}{d\theta} A S^{\top}$. Since $S$ is computed using iterative normalization of rows and columns, starting with an exponential term, $\frac{dS}{d\theta}$ will contain terms such as $S_{ij} S_{i'j'}$ [2]. Thus, $S A \frac{dS^{\top}}{d\theta}$ contain terms of the form $S_{ij} S_{i'j'} S_{i''j''}$, with each $S_{.,.} \in [0,1]$. This leads to attenuation of gradient signals. If we keep $A\odot XX^{\top}$, then the gradient will have $S_{ij}S_{i'j'}$ $[\frac{d XX^T}{d\theta}]_{a,b}$, which will allow more significant gradient signals. Moreover, due to continuous adjacency entries, $S _{ij} S _{i'j'} S _{i''j''}$ will now be replaced with $S _{ij} S _{i'j'} S _{i''j''} X _{a,b} X _{a',b'}$, where $X$s can control the gradient signals better, leading to actual learning of clique number computation for a distribution over graphs.

[1] In neural NLP, it is common to pretrain a language model for masked word prediction, and simultaneously train for a suite of common language tasks (e.g., FLAN-T5), or fine-tune them later. We follow the same strategy.

[2] This can be obtained from the derivative of softmax probabilities $\frac{d}{do_k} e^{o_j} / \sum_i e^{o_i} = -(e^{o_j} / \sum_i e^{o_i}) (e^{o_k}/ \sum_i e^{o_i})$

bicriteria early stopping strategy have not been verified.

We found bicriteria early stopping to be an effective guardrail against potential overfitting of MXNET (MSS). Below are the numbers for Brock and Enzyme. MSS based early stopping led to overfitting of MSS, which is why the performance of submatch was worse. But Bicriteria early stopping improved performance of submatch significantly, with a small increase in MSE of MSS. For Enzyme, Bicriteria early stopping improved the performance of submatch without any deterioration of MSS.