Clique Number Estimation via Differentiable Functions of Adjacency Matrix Permutations
Authors: Indradyumna Roy
Eeshaan Jain
Soumen Chakrabarti
Abir De
Venue: ICLR 2025 Poster (2025)
Keywords: Graph neural network
distant supervision
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a differentiable model for clique number estimation, learning from distant supervision by searching for dense submatrices in permuted adjacency matrices.

Abstract: Estimating the clique number in a graph is central to various applications, e.g., community detection, graph retrieval, etc. 
Existing estimators often rely on non-differentiable combinatorial components. Here, we propose a full differentiable estimator for clique number estimation, which can be trained from distant supervision of clique numbers, rather than demonstrating actual cliques.
Our key insight is a formulation of the maximum clique problem (MCP) as a maximization of the size of fully dense square submatrix, within a suitably row-column-permuted adjacency matrix.
We design a differentiable mechanism to search for permutations that lead to the discovery of such dense blocks.
However, the optimal permutation is not unique, which leads to the learning of spurious permutations. To tackle this problem, we view the MCP problem as a sequence of subgraph matching tasks, each detecting progressively larger cliques in a nested manner. This allows effective navigation through suitable node permutations.
These steps result in MxNet, an end-to-end differentiable model, which learns to predict clique number without explicit clique demonstrations, with the added benefit of interpretability.  Experiments on eight datasets show the superior accuracy of our approach.

Published as a conference paper at ICLR 2025
CLIQUE NUMBER ESTIMATION VIA DIFFERENTIABLE FUNCTIONS OF ADJACENCY MATRIX PERMUTATIONS
Indradyumna Roy") Eeshaan Jain"?, Soumen Chakrabarti', Abir De
'IT Bombay, "EPFL (indraroy15, soumen, abir] wwteesseeiib...... iitb.ac...... in, eeshaan, jain@epfl ch
ABSTRACT
Estimating the clique number in a graph is central to various applications. e.g.. community detection, graph retrieval, etc. Existing estimators often rely non- differentiable combinatorial components. Here, we propose a full differentiable estimator for clique number estimation, which can be trained from distant supervi- sion of clique numbers, rather than demonstrating actual cliques. Our key insight is formulation of the maximum clique problem (MCP) size of fully dense square submatrix, within a suitably row-column perinnn-ermutdd ad- jacency matrix. We design a differentiable mechanism to search for permutations that lead to the discovery of such dense blocks. However, the optimal permutation is not unique, which leads to the learning of spurious permutations. To tackle this problem, view the MCP problem each detecting progressively larger cliques in a nested manner. This allows effee- tive navigation through suitable node permutations. These steps result in MXNEт, an end-to-end differentiable model, which learns to predict clique number without explicit clique demonstrations, with the added benefit of interpretability. Experi- ments on eight datasets show the superior accuracy of our approach. The code is available on O GitHub.
maximization of the
sequence of subgraph matching tasks,
INTRODUCTION
The Maximum Clique problem (MCP) entails finding the largest subgraph where every pair of nodes is connected by an edge. MCP is extensively studied among NP-Complete combinatorial problems (Karp. 2010), with efforts on designing exact and heuristic solvers for general and spe- cialized graph classes (Reba et al., 2021; Carraghan & Pardalos, 1990; San Segundo et al., 2016; Depolli et al., 2013; Jiang et al., 2017: Tomita et al., 2017; Li & Quan, 2010; Konc & Janezic, 2007; McCreesh & Prosser, 2014). Beyond such theoretical appeal, MCP also has numerous real-world applications across molecular biology MMalodDoggil et al., 2010; Depolli et al., 2013), social net- work analysis (Balasundaram et al., 2011), protein matching (Malod-Dognin et al., 2010; Ehrlich & Rarey, 2011; Depolli et al., 2013), identifying chemical reaction sites (Raymond & Willett, 2002; Agrafiotis al., 2007; Fooshee et al., 2013), drug discovery (Cao et al., 2008), etc.
Clique number estimation vs. MCP Several of aforementioned applications require accurate estimation of the size of the maximum clique, known as clique number, with less emphasis in pre- dicting the maximum clique itself. This specifically include domains necessitating the comparison of graph structures, such as protein matching (Malod-Dognin et al., 2010; Ehrlich & Rarey, 201 1; Depolli et al., 2013), reaction site identification (Raymond & Willett, 2002; Agrafiotis et al., 2007: Fooshee et al., 2013), drug discovery (Cao et al., 2008), etc. In such cases, the maximum common induced subgraph often serves as a relevance metric, directly mapped to the clique number detection of the modular product graph (Solnon et al., 2015). Various network analysis models study clique relations (Pattillo al., 2013) for identifying cohesive subgroups in social networks (Balasundaram et al., 201 I). In such applications, a key question is the decision version of MCP, i.e., whether there a clique of size e exists in the graph, rather than finding the maximum clique. In such situations, where relevance is latently influenced by the clique size, neural architecture capable of directly predicting clique number while ensuring end-to-end differentiability becomes essential.
Prior work on MCP and their challenges in clique number estimation With the proliferation of real-world applications, a series of recent neural solvers aim to solve MCP harnessing data distri-
Indradyumna and Feshaan contributed equally. Feshaan Jain did this work while he was affiliated with IIT Bombay.

---

Published as a conference paper at ICLR 2025
butional characteristics across supervised (Sun & Yang, 2024), unsupervised (Karalias et al., 2022; Karalias & Loukas, 2020; Min et al., 2022) and reinforcement learning (Sanokowski et al., 2023; Zhang et al., 2024) paradigms. However, they suffer from two key limitations, which prevent them from realizing their full potential in clique number estimation task.
Lack of end-to-end differentiability: End-to-end differentiability is a critical requirement for ap- plications like graph matching, where the goal is quickly retrieve similar graphs from large corpus. Differentiable models enable us quick off-the-shelf use of indexing methods. However, most ex- isting neural designs operate in conjunction with non-differentiable decoders, which impede their integration to such applications.
Middle ground between extreme and no supervision: Existing clique number estimation meth- ods fall in two broad regimes. Combinatorial methods often use no training. whereas ML-based methods (Sun & Yang. 2024) depend on full demonstration of an actual clique. We focus 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 demonstration (which computationally expensive to collect). 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.
1.1 OUR CONTRIBUTIONS
We introduce MXNET, differentiable neural model specifically for clique number estimation rather than the maximum clique itself, by training under the distant supervision of the clique size without explicit clique guidance.
Clique detection via message passing on permuted adjaceney matrix Suppose the input graph G has a clique of size c, and to each node is added a self-loop. Then there exists a permutation, which, when applied on node indices, will let us write the node-node adjacency matrix in a manner that will reveal a x square block somewhere on the diagonal, completely filled with c² ones. If (G) is the clique number, the largest such square we can find will be (G) x w()). To turn this initial intuition into a neural estimator of ((G), we need two differentiable gadgets: network that proposes a node permutation, and a network that detects completely filled squares (maximal subsquare MSS detection).
The latter problem admits a simple polynomial-time dynamic programming-tye tttpe algorithm, which we generalize into a message-passing network over a grid-graph formed from the permuted adja- cency matrix. This effectively transfers the computational complexity of the clique problem to the row-column permutation proposer. We devise an end-to-end differentiable network for this former combinatorial task by adapting Gumbel-Sinkhorn network propose a permutation that lets us discover large filled squares. Here, we naturally work in a relaxed continuous domain, and directly output an estimate of (G)). We call this neural component of our model MxNET (MSS).
Curriculum- Burriculum-macching a series of cliques At least [V(G) w()) permutations (and possibly many more) can identify the MSS, leading to huge multiplicity of global optima. These will muddle gradient signals, potentially damaging learning quality. During inference, even if (G) is estimated reasonably well, we may not get an interpretable permutation. In response, we design MxNET (SubMatch), the second variant of MXNET. MxNET (SubMatch) proposes a cascade of ever-larger cliques Kr,, c = 2,3.... and prompts the permutation generator network to find an injective alignment of nodes Kr to nodes of G. We expect these attempts to succeed as long as S w(G), and noticeably fail when > w(G). This expected behavior is worked into a suitable loss function. As we shall see, the inductive bias asserted through this 'curriculum' not only improves interpretability, but can also improve estimates of w(G).
End-to-end training and constrained early stopping. We combine MXNET (MSS) and MXNET (SubMatch), described above, into MXNET (Composite), part of end-to-end trainable framework we call MXNET. To mitigate overfitting and the learning of spurious correlations, we introduce a bicriteria early stopping method which effectively balances both components, ensuring accurate predictions supported by interpretable clique-based justifications. Our experiments on eight datasets show that MxNET offers significant accuracy boost beyond several baselines.
1.2 BRIEF DISCUSSION ON RELATED WORK
Apart from the aforementioned prior work on MCP, our work is also related to recent advancements in neural models for combinatorial optimization approaches on graphs and traditional methods for
2

---

Published as a conference paper at ICLR 2025
estimating clique numbers in graphs. We briefly discuss them here. We further discuss related work in Appendix C.
Neural models for combinatorial optimization on graphs In recent years, there is series of works focusing on combinatorial optimization on graphs. This include designing neural networks which can solve graph matching (Yu et al., 2023; Liu et al., 2023; Wang al.. 2023; Nguyen al., 2023; Zhou et al.. 2023; Jiang et al., 2019; Yu et al., 2020; Fey et al., 2020). These works pre- dominantly have applications in image matching. Several works design generic neural networks, which can solve series of combinatorial optimization problems (Wang & Li, 2023; Zhao et al., 2023; Li et al., 2018; Goshvadi et al., 2023; Lu et al., 2023; Sun & Yang. 2024; Sanokowski et al., 2023; Zhang et al., 2024). Other works are tailored to solve specific problems including maximum clique (Karalias & Loukas, 2020; Min et al., 2022), maximum independent set (Brusca et al., 2023; Ahn et al., 2020), maximum common induced subgraph (Bai et al., 2021), etc.
Clique number estimation without maximum clique computation Presenting the learner with G and its clique number (G),, rather than maximal clique itself, presents a practical intermediate path between full supervision and training- training-free methods. Even though demonstrating G's cliques to the learner is itself computationally intractable, (G) can be bounded (Pardalos & Phillips, 1990; Gibbons et al., 1997) via the optimal values of various continuous optimizations, the most well- known being
x Ax, originally due to Motzkin Straus (1965). Sharper bounds have been developed (Budinich, 2003). Pelillo (1995) demonstrated how such quadratic programs can be solved by message passing networks.
2 NOTATION AND PROBLEM SETUP
Notation Given graph G. EV, we denote its adjacency matrix by A, which is possibly padded with zero rows and columns to ensure all matrices A have the same dimension N x N. We define N the set of all N X N hard permutation matrices, and PN as the set of all N x N soft permutation matrices, which are essentially doubly stochastic matrices. We will frequently use P E II (S Px) to denote hard (respectively, soft) permutation matrices. We write O. 1 where 1. is an all-one vector of dimension c. [a]+ = max(a, (,,0 0} represents the hinge or ReLU function. For a matrix R, we denote En, |[u, v]] by || Given a binary matrix B, we refer to the size of (number of rows columns) of the maximum sized all-ones square submatrix as MSS(B) B). We call such "all-ones square submatrix" as "fully dense subsquare", to generalize to continuous B.
Maximum clique problem (MCP), clique number A clique K. is a complete graph with num- ber of nodes. The maximum clique K (G)) in a graph G is the clique within G, containing the highest number of nodes. The size of this maximum clique, i.e., w(G) as the clique number. The clique number (G) of a graph is unique, although the maximum clique itself may not be there can be multiple maximum cliques K with same number of nodes (G)). However, as discussed in several classic papers from the Operations Research literature (Bomze al., 1999; Wilf, 1967; 1986), the clique number (G)) can be bounded using the spectral proper- ties of the graph G. When the computation of the maximum clique size is particularly challenging, these bounds can provide an estimation of the clique number, serving as distant supervisory labels for neural max-clique methods.
IV(K (G)),, is referred to
Problem statement Given graph G, our objective is to design an end-to-ent differentiable neural model which takes the graph as input and outputs estimate of its clique number. Formally, given a set of / training instances D {G,, (G.) E [4]] we aim to train our model on D, so that can predict the clique number of new graph G. Our goal is to avoid any non-differentiable combi- natorial routines during both training and testing phases. Our focus is on estimating specifically the clique number, rather than the elique itself, motivated by several real applications (Malod-Dognin et al., 2010; Ehrlich & Rarey, 2011: I; Depolli et al., 2013; Raymond & Willett, 2002; Agrafiotis et al., 2007: Fooshee et al., 2013; Cao et al., 2008).
3 THE DESIGN OF MXNET
We describe our proposed framework, MXNET, in three stages.
MXNET (MSS) First, we describe how to combine a soft permutation generator with a network that searches for the largest square submatrix in given matrix, to directly predict clique number. MXNET (SubMatch) While MXNET (MSS) gives accurate estimates of (G). the very large number of loss optima prevents it from finding sharply interpretable clique demonstrations. We
3

---

Published as a conference paper at ICLR 2025
Combinatorial Formulation
MSS
SUBMATCH K
Oracle
S
MSP
G
PAPI
Differentiable formulation
MSS
SWS
A
ON
DPuplate
GNN
DProulont
T2
18
4:
SUBMATCH
22
GNN
(C)
ACs
GNN
fpile Vy
(G)
K4
GNN
Q
Ccomposise
KG.
GNN,
Figure I: Input graph G with adjacency matrix A contains 14 and KCs, so (G) 4. The topmost part shows how node permutation P supplied by an oracle rearranges A to locate the maximal clique as a dense square diagonal block. The lower part shows the two neural components that turn the combinatorial intuition into differentiable network. In the first neural component (middle), GNN, obtains contextual node embeddings X. which drives a Gumbel-Sinkhon
network To to (rationale explained in text) to form
propose a soft permutation S. S is applied to W = A X X the relaxed counterpart of PAP in the oracular setting. If S is chosen well, we expect SW ST to have large, fully-filled diagonal squares. The largest among these is/are detected by message- passing (DPmsga: DPaggr DPreadout,s) in a grid graph. The second neural component (shown at the bottom) consists of a series of cliques K2 C KG3 C.., each processed by GNNo, provide contextual node embeddings Q2, Q3..... which are checked for a form of injective subsumption by X. Subsumption fails as we move from Qu(() to Qu(G)+1 a transition we detect via the Pa(c; G)) network. The losses from the two neural components are combined into Composite.
introduce a related strategy MXNET (SubMatch), where we prepare a series of cliques of increas- ing size and try to detect these cliques subgraphs of the input graph. By construction, MxNET (SubMatch) is better at producing clique certificates.
MxNET (Composite) We combine MxNET (MSS) and MxNET (SubMatch) to build accurate, yet interpretable clique number estimator MXNET (Composite). Here, MxNET (SubMatch) helps MxNET (MSS) navigate through suitable node permutations, while MXNET (MSS) promotes accuracy by directly predicting the clique number.
3.1 DESIGN OF MXNET (MSS)
We first introduce a novel combinatorial formulation of the Maximum Clique Problem (MCP) and then eustomize this formulation develop MXNET (MSS), which approximates this combinatorial solution in a differentiable manner.
Combinatorial formulation of MCP Given a graph G (V, E), suppose the nodes are magically ordered in such a way that all those nodes that belong to one of the max-
imal cliques, are consecutively numbered. Under this node ordering, the submatrix in- dexed by (G)) in the corresponding adjacency matrix (with added self loops) will be the largest possible fully dense (all-ones) subsquare in A. Formally, if V and (IC (G)) = {j+ I.... + (G) for some j S N - w())). then we have (i) (()) (G)) = Oaier and (ii) for any pair (j.j + c) with e wGG)) and 1 < O.-
[N]
(G)) - we have Abj:jtc.j
Given the above ordering among the nodes, the MCP is equivalent to finding the largest fully dense subsquare within the adjacency matrix, which can be solved in polynomial time. Therefore, all that we have achieved thus far is to relegate the hardness of MCP to the module that must suggest the node ordering. To more forward, we cast the MCP as a maximization of the size (number of rows columns) of the largest fully dense subsquare in the adjacency matrix, over all possible node
4

---

Published as a conference paper at ICLR 2025
permutations the optimization variable. If we define MSS(B) as the size of the largest fully dense diagonal subsquare in a matrix B, then MCP amounts to
maximizepenly MSS(PAP))
(I)
The routine MSS(-) is summarized in Algorithm 1. A matrix called FF (mnemonic for flood- -fll,,, or frontier-flooding which is updated using a simple dynamic programming (DP) routine. After updating the (i, position, FF represents the size of the largest fully dense subsquare in B (which is PAPT in our problem), with the bottom-right element as B(i, Algorithm first initializes the first row and column of FF with those from B.
Once we update FF(r, cl with r FF[2 1.j 1] contain the values of the size of largest fully dense subsquare in B, Algorithm 1 MSS(B) # B is binary
i.c < j. then FF 1.7]. FF[i,j - 1] and
with bottom right position as (i 1.)), (i.j 1) 1) and (i 1,j 1) respectively. If [i],]]
1, the size of the corresponding subsquare ending at (i,5) is computed by increasing one over the mini- mum of the above three entries of FF as: FF = 1+min (FF(i 1. Ff - 11, FF 1,j 1]}. We can visualize this computation as a wavefront pro- gressing down the main diagonal. Finally, we com- pute the required size of fully dense subsquare as [ FF...
1: FF t Empty(N, + [
2:
1] + Bl: 1]
for i,j FFli 1.
5:
f2 - f
6:
fa FF(i 1.j
7:
FF[i.]] + B
(1+ min 4)
8: Return max FF 2E(1.23)
puassage-passing perspective of MSS(B) Next, we conceptualize MSS as an instance of iter- ative message passing, akin to graph neural networks. applied to a directed acyclic graph where the nodes are initialized with binary states. This perspective enables us to develop a neural network ca- pable of simulating Algorithm 1. Given the input matrix B PAP we construct the graph 9N as N x N directed acyclic grid graph. The nodes of GN are V(GN) )= = [N] x [N], with each node () having an in-neighbor set In-Nbr((i.)). == {(i - J). (i.j 1), (i 1.j 1)} except the boundaries. The node embeddings of GN are initialized as ho = B ji IR. At propagation layer E [N], each node (i, first receives messages from its in-neighbors (s, 4), then aggregates these messages, and finally updates its embedding
Mi = (ee.t)e DPmsg (hess(he(s, t), he(
(2)
bef (1, = DPupdate (ho(i,)), DPaggr (Mi(())))
Note that, unlike traditional GNNs, which use he(i,j) as input at each layer, we feed the initial feature hi as input at each propagation step, specifically tailoring our approach to simulate
Algorithm 1. After the completion of N of such propagations, we compute the output of the DP as DPoutput
[B DPreadout (Ux,))ev(G,,
(3)
Note that when B E 10,1N the specific choices of the functions: DPmsg(æ; v) = max(z) ensures
x, DPaggr (2,)) 11 min; He, DPupdate( x. y) = zy. DPreadout({r)) that DPoutput(B B) = MSS(B), as computed in Algorithm 1.
Differentiable approximation of the combinatorial MCP in Eq. (1) Here, we propose a neural network wg, with model parameters 0, Φ, and &a (to be described later), to approximate the combinatorial MCP formulation (I), Our approach involves continuous relaxations of the original objective (1) on three fronts.
(1) We relax the hard permutation matrix P into a soft permutation matrix S. modeled as doubly stochastic matrix. (2) It becomes difficult to attain zero values in the right entries of SAST due to the continuous relaxation of S. Moreover, the binary matrix A attenuates gradient signals. To address these problems we substitute the binary 0/1 values in the adjacency matrix A with continuous values, computed using node embeddings for each node VCG). (3) Since items (1) and (2) result in continuous relaxations of PAPT the initial states h)) now contain continuous values instead of binary 0/1 values. Consequently, we model the embeddings of the grid graph using continuous values.
Computation of node embeddings: We use a graph neural network GNN, with parameters 0, to perform message passing across L propagation layers to compute node embeddings X E Nxd where X = [+ (u) Rd [d] The embeddings (u) capture the information about the sub- graph containing nodes within L-hop distance from These embeddings are then used to perform continuous relaxations W of the adjacency matrix A as follows:
W = A O XXT,
where, X [u)( E IR JUE[N]] == GNNo(G)
(4)
5

---

Published as a conference paper at ICLR 2025
Relaxation of hard to soft permutatiinn:: The hard permutation matrix P in Eq. (1) is the essential blocker to an efficient and differentiable expression. To address this, we approximate P with a doubly stochastic soft permutation matrix S. We obtain S by first feeding the node embeddings X into a neural network To. and then applying Sinkhorn iterations (Mena et al., 2018; Cuturi, 2013) to the resulting matrix (x) Given a maximum number of iterations Tmaxx we compute S
S = T Tiaa
where, To exp(TT (X)) (X): Tr+1 ColumnSSale(RowwSeii (T+)), (5)
where À is temperature parameter, RowScale and ColumnScale perform row and column normal- izations of the matrix argument. As Tmax + oc, S approaches a doubly stochastic matrix and as O and Tinxx - 00, S converges to hard permutation matrix. Using Eqs. (4) and (5), compute the relaxation of PAP as: B = SWST
Relaxation of Algorithm 1: Unlike the binary input in Algorithm 1, B now takes continuous values. Therefore, we use continuous (i. e R in Eqs. (2)- (3) and model DPmsg, DPupdate and DPrcadout using neural networks (Details in Appendix D) with parameters v. Under these re- laxations, we compute the node embeddings he(i, on GN. starting with ho j) = (SWS )
as follows:
(i,)( DPupdato (ISWS [i..].
( (s.1)Em) DPmsg (he(t,)). ())))t)) (6)
Finally, we predict the clique number (G)) via max pooling, following Step in Algorithm 1: w = (aX DPreadout, (hx (1.
Training Given training instances {G, (G.) [T], we learn 0, o. 1 by minimizing the mean squared eтror LMsS Eier (Wa, .. (G.) (
Limitation of MXNET (MSS) As mentioned in Section 1.1, MXNET (MSS) can estimate (G) accurately, but, owing massive symmetries in the distant supervision, succumbs to confusing gradient signals from a large number of equivalent soft permutations that achieve the optimal ob- jective, and does not always succeed producing interpretable "clique certificates" S. The space of globally optimal Ss increases further because neither the combinatorial MCP (1) nor its neural approximation (7) constrains the position of the subsquare within the permuted matrix B. We now proceed to rectify this limitation.
3.2 DESIGN OF MXNET (SUBMATCH)
Finding cliques via subgraph matching the Gumbel-Sinkhon network Ta is powerful enough to find an effective soft permutation S, it may well be powerful enough to arrange the maximal subsquare in a fixed position, say, [Gw( (G)], How do we endow T's with this inductive bias?
We start with the standard observation that clique K.,
is subgraph of G' (written as Kc, S G) if and only if S w(G). If we had a perfect black box subgraph test,
Clique Coverage Loss
En, -E-AA]]].
Eno QQ= SX).
75-
"Ke G", "Ka C G",
"Kuicy C G" would pass, but "X C G and subsequent tests would fail.
50-
Formally, K1 C K2 Ku(a) S G. but ICo g G for any (G)).
25
We shift our perspective on S as "a permutation that col- leets clique nodes into a contiguous subsquare" to "a per- "ar- mutation that maps Ic. injectively into G", where each Ke is presented in a specific format. K2, the adjacency matrix of Ke., is zero-padded to an N x N adjacency ma- trix, but the edges are always presented in the [1:c, l:c]
4
8
10
12
14
C
Figure 2: Testing if K. C G for increasing c until >> w(G)=8.
lexe
O Oex(N--)
upper left corner. Formally, K. ((N-o)xx
Then there exists a hard node
((N-))((N-))
permutation P such that
K1 S K₂ S ... < KW(G) S PAPT; K. PAPT Ve > w(G) (elementwise inequality). (8) The inequality K, PAPT can be written equivalently as (K.-PAPT = 0. The asymmetric distance K- -PAP 1+l,, measures the coverage of Kc, by the graph G and can be used as distance measure for subgraph matching (Lou et al., 2020; Ranjan et al., 2022; Roy et al., 2022). Then, using the nested inequality in Eq. (8), we will have K, PAP (G)) and for > w(G), will have K. PAP 1T > O. The green line in Figure shows
0 for all S

---

Published as a conference paper at ICLR 2025
+ increases. As expected, with the ideal P, it jumps from positive values for e w(G) 8.
K PAPP
Neural relaxation We employ GNNo, introduced in Eq. (4), to represent graphs G and K. as N x contextual node embedding matrices X and Qc- We replace the hard clique coverage loss Eig [K. PAP [6,j]] with soft clique coverage loss (e.o(c; G) Eij( Qe Qe where S is the soft permutation matrix (5). Consistent with K., the first rows of Q contain the non-trivial embedding vectors corresponding to clique nodes V(K.),, whereas the lower N c rows are zero pads. The blue line in Figure 2 shows pe.o(c; (c; G) against c, after 0, @ are reasonably trained. We can again see a detectable jump after = ((').
SX + [i,
Training curriculum Instead of using MxNET (MSS) to directly estimate w()), we will train pa,a(c; G) using 'curriculum' that encourages the neural counterpart of Eqn. (8) hold. Specifi- cally, we seek to minimize ming.6 LSubMotch( (po,o(c; G)) where LsubMatch is written as
w(C)
((G)- [po.a + L;G) po.o(c: G) - -1+
pc G)
SubMatch
Σ
Σ
(G)
(w( -
2|
VE[I]
+ ( (w(G); - po. (w) +;;)+ +0)+)
+ (I) The first term encourages discover that K. C G for E [2, (G)]
(9)
(II) As long < w(G), we do not want pa,o(c; G) > po, G)). The second term constitutes this "nesting curriculum".
(III) The third term encourages the jump: pa.a (w)() +1:G) > (G))
Here 8 and y are margin hyperparameters, with y < typically giving the best performance. In Eq. (9), we may limit the inner summation of the first term to only tion of the last term to (G) - 1. However, summation from 2 to w(G) provides more explicit guidance to the learner that, K2,.... K₂ are subgraphs of G. Our experiments Appendix F show that it is unable to reason that if Ke is subgraph of G then also K2.... are also subgraphs of G.
w(G) and the inner summa-
Inference During inference, we evaluate pa.a(c; G) as we increment reporting our estimate (G) as the smallest e" such that po.ø(c" + 1: po,a(c"; +
Pros and cons Loss expression (9) achieves two goals. It guides the search for S using pro- gression from smaller to largest cliques, and it guides the positioning of the MSS to the upper left corner for variety of clique sizes. Together, these improve the interpretability of "clique certifi- cates" (somewhat dense subsquares in the continuous regime). Experiments suggest that MxNET (MSS) can sometimes beat MxNET (SubMatch) in terms of the raw accuracy of estimating (G))
3.3 DESIGN OF MXNET (COMPOSITE)
Given their complementary strengths, we are naturally motivated to combine MXNET (MSS) and MXNET (SubMatch) into our final proposal, MxNET (Composite).
Training We simultaneously train the neural networks we, d and po, G) by minimizing with a composite loss function, with the mixing hyperparameter X, written as
Ccomposite ALMsS + SubMaathh
(10)
Bicriteria early stopping Early experiments suggested that the two parts of the composite loss can be oppositional. Therefore, we developed bicriteria early stopping logic. It consists of two phases. Initially, we monitor the reduction in CSubMarch, indicating the model's effectiveness in identifying an optimal permutation that satisfies the query clique detection challenges. Once LuubMatch saturates, we transition to monitoring LMSS. To prevent the second phase from reversing the gains of the first, we allow/accept reduction in LMsS only if the damage to LuubMach is below a threshold. This enhanced early stopping policy ensures balanced optimization of (10).
Inference During inference, we have the option to base our predictions on either wa.e. or (c, G). While (c: G) provides certificate for the maximum detected clique, Wa. di- rectly predicts the clique number based on neural maximum subsquare detection (7). Given our objective of accurate clique number prediction, we choose the prediction of wo.
4 EXPERIMENTS
We report on extensive experiments using eight datasets, comparing the performance of MXNET with other methods. We also instrument different components of MxNET understand their impact.
7

---

Published as a conference paper at ICLR 2025
4.1 SETUP
Datasets We conduct experiments on eight datasets, comprising five real-world and three syn- thetic datasets. Real-world datasets include (1) IMDB-BINARY (IMDB), (2) Enzymes and modular products of graph pairs from (3) PTC-MM-n. (4) AIDS, (5) Mutagenicity (MUTAG-m) datasets. We also generate three synthetic datasets from (6) DSJC, (7) Brockington (Brock), and (8) RB. One key application of clique number estimation to compute the similarity score between two graphs based on the size of their maximum common induced subgraph, expressed as the modular product' between the graph pairs. Motivated by applications in graph similarity, we use modular graph prod- ucts for three datasets, viz. AIDS, MUTAG, PTC-MM. We call them AIDS-m, MUTAG-m and PTC-MM-M respectively. Additional details are in in Appendix E.
Baseline neural and neural-combiinttoiaal MCP solvers Prior methods that operate under the three practically motivated métiers of our problem setting end-to-end differentiability, focus on clique number prediction rather than a maximal clique itself, and the ability to train under dis- tant supervision
surprisingly hard to find. Plausible baselines from the neural network and machine learning community include six unsupervised methods, viz., (1) EGN (Karalias & Loukas, 2020), (2) SCT (Min al., 2022). (3) SFE (Karalias et al., 2022), (4) NSFE (Karalias et al., 2022), (5) ST (Bengio et al., 2013), (6) Reinforce (Williams, 1992); two variants of Difusco (Sun & Yang, 2024), which are trained under extreme supervision of explicit clique demonstration, viz., (7) Di- fusco (Cont) and (8) Difusco (Cat), which use continuous (Gaussian) and categorical sampling at the de-noising stage; one neural subgraph counting based approach trained under distant supervi- sion- (9) NeurSC (Wang et al., 2022); and two models trained under Reinforcement Learning, viz,, (10) GFnet (Zhang al., 2024) and (11) VAG-CO (Sanokowski al., 2023). None of these methods is trained under distant supervision, nor are they able to estimate the clique numbers without making implicit or explicit hard decisions about which nodes constitute the clique.
Heavy-lifting decoders A differentiable network, as well as many heuristic MCP solvers or relax- ations of integer programs, will usually associate score with each node E (G) that u indicating its membership in the maximal clique it has identified. We call this a heatmap on the nodes. To demonstrate a concrete clique, these methods then feed these heatmap into the decoder, which is generally procedural, not declarative, and therefore not differentiable. EGN, SCT, Difusco, GFnet, and VAG-COuse such non-differentiable decoders. Appendix E.3 discusses decoders at length.
Evaluation In the face of such heterogeneity and "culture differences", it is difficult to compare competing systems with a single yardstick. We first present comparisons segregated between meth- ods with and without decoders. MxNET easily beats all non-decoder methods, and even most decoder- based methods on many data sets. Later, we allow decoders, but we must carefully control the computational costs of sampling inside decoders. Some more details are in Appendix E.3.
We split each dataset D {G,, (G.) E [T] into 60% training. 20% eval, and 20% test folds. We report Mean Squared Error (MSE) between the predicted clique number and the ground truth clique number. Appendix E.4 explains why traditional metries like approximation ratio are not suitable.
4.2 RESULTS
Comparison with baselines Here, compare the performance of MXNET (Composite) against all the ten neural baselines in terms of MSE We use two variants of MXNET, viz. MXNET (ES: which uses early stopping using MSS loss L and MXNET (ES: Bi) which uses bi- criteria early stopping (Section 3.3). Table I summarizes the results. The key observations are as follows. (1) Although six out of ten baselines use combinatorial decoders during inference, and two of them use extreme supervision, MXNET achieves the best performance on five datasets and the second best performance on two datasets. In these datasets, EGN is the second-bew, performer in the first five and the best in the last three. (2) The baselines that do not use a decoder (the last four methods in Table 1) are massively outperformed by MxNET. In fact, they are outperformed by ev- ery baseline that uses a decoder. Remarkably, MXNET is the only model that does not use a decoder and yet not only competes with but often surpasses the decoder- based baselines. (3) Overall, GFnet is the third-best performer in four out of eight datasets. (4) Difusco (Cat) consistently outperforms Difusco (Cont) across all datasets, aligning with the observations reported in their original paper.
Ablation study on variants of MXNET. We compare the performance of the three variants of method, viz., MXNET (MSS), MXNET (SubMatch) and MxNET (Composite), whose training
Phttps://ent http///wwwikkke www.wwiiiiiiiiaiaammmmm wi wik htwp://ooooorrrocttooooooooooooe
8

---

Published as a conference paper at ICLR 2025
Table 1: Performance in terms of mean squared eπror (MSE) between predicted and true clique numbers for two variants of MXNET (MXNET (ES: :MSS), MXNET (ES: EGN (Karalias & Loukas, 2020), SCT (Min et al., 2022), Difusco (Cont, Cat) (Sun & Yang. 2024), GFnet (Zhang et al., 2024), VAG-CO (Sanokowski et al., 2023), SFE (Karalias et al., 2022). NSFE (Karalias et al., 2022), ST (Bengio et al., 2013), Reinforce (Williams, 1992) and NeurSC (Wang et al., 2022) on 20% test set. MXNET :MSS uses early stopping using Lsss, whereas MXNET :B) uses bicriteria early stopping described in Section 3.3. In all cases, we use MXNET (Composite), which is trained using the composite loss (10). First six (last seven) methods (do not) use decoder. Green, blue, and yellow show the best, second-best, and third-best methods, respectively.
IMDB
AIDS-m
PIC-MM-M
DSJC
Brock
Enzymic
RB
MUTAG-m
EGN (Karalias & Loukas. 2020)
0.102
0.610
0.284
0,030
1,310
0.109
15.615
1,010
Decoder
SCT (Min et al., 2022)
4.102
3.865
1.802
92.675
35.885
0.891
50,230
11.105
Difusco (Cont) (Sun & Yong. 2024)
5.333
4.665
2.621
59.820
39.040
1.034
63,490
10,590
Difusco (Cat) (San & Yang. 2024)
1,361
4,170
2.244
1,560
10.595
0,950
55.630
10.965
GFact (Zhang et al.. 2024),
2.815
0.740
0.554
4.820
8.975
0.857
34,200
2,565
VAG-CO (Sanokowski
2023)
5.037
33.905
19,962
7.665
15.450
4.244
320.240
132,700
SFE 3FEE(Karalaae (Karalias et al., 2022)
4,833
44.340
26,568
12.465
53.595
1.630
72.020
110.905
Now Decoder
NSFE (Karalias et al., 2022)
3.185
36.005
19,800
5.255
47,920
1.118
78.890
96.445
ST (Bengio et al., 2013)
8.972
44.885
26.703
5.410
55.740
5.454
131.230
111.020
Reinforce (Williams, 1992)
16,472
$9.170
37.455
13,280
403.095
1.731
229 229.435
132.700
NeurSC (Wang et al., 2022)
5.330
1,240
1.510
15.350
88.790
0.630
10.080
3,520
MXNET (ES MSSS
0.094
0.341
0.179
0,383
10.022
0.203
6.875
4.130
MXNET :B))
0.094
0.341
0.179
0.383
10.022
0.196
6.875
0.613
Table 2: Comparison of MXNET (MSS), MxNET (SubMatch), and MXNET (Composite) in terms of Mean Squared Error (MSE) eight datasets. Numbers in green, blue indicate the best performers and second best performers respectively.
IMDB
AIDS-m
PMC-MM-m
DSIC
Brock
Fnzyyes
MUTAG-1
MXNET (MSS)
24.434
0.295
2.364
66.890
150.430
0.205
10.190
4.130
MXNET (SubMutch)
0,056
0.420
0.512
2.820
150,890
0.210
7.170
4,040
MXNET (Composite)
0.094
0.341
0.179
0.383
10.022
0.196
6.875
0.613
losses are LMss, LSuhMatch (9) and Loomposite (10), respectively. Table 2 shows the results. The key observations
follows. (1) MXNET (Composite) emerges as the exclusively best performer in six out of eight datasets, with a comparable performance to MXNET (MSS) in Enzymes, and being outperformed by MXNET (MSS) in DSJC. Particularly noteworthy is the substantial improvement in MxNET'S performance in datasets like IMDB, MUTAG-m, and RB, highlighting the efficacy of combining LMss and LaahMatch for accurate clique prediction tasks; (2) In five out of eight datasets, MxNET (MSS) significantly outperforms MXNET (SubMatch), thereby demonstrating its better capability predicting the clique number directly. (3) MxNET (SubMatch) is never the top per- former on its own, highlighting that while it provides important signals for MXNET'S 's performance, its indirect signal about clique sizes is insufficient for accurately predicting clique number.
Table 3: Performance of MxNET (Composite) for different early stopping criteria, which are based on LMSS. CsubMatch and LComposite respectively. For each of these early stopping criteria, we use MXNET (MSS) and MxNET (SubMatch) (denoted as MSS and SubMatch) components to measure the performance in terms of MSE on the test set. Numbers in green indicate the best performers.
IMDB SubMarch
AIDS-m
PIC-MM-
DSIC
MSS
MSS
SubMatch
MSS
SubMaich
MSS
SubMatch
MXNET MSS)
0.094
0.241
0.341
0.705
0.179
0.265
0.383
9.360
MxNET (ES: SubMatch)
0.331
0.065
0.307
0.450
0.232
0.495
0,581
7.335
MXNET (BS:BL)
0.094
0.241
0,341
0.705
0.179
0.265
0,383
9.360
Brock
Enzymes
RB
MC TAG-m
MSS
SubMatch
MSS
SubMatch
MSS
SubMatch
MSS
SubMatch
MXNET (ES:MSS)
10.022
726.995
0.203
0.353
6.875
35.620
4.130
7,805
MXNET (ES: SubMatch)
19.165
170.280
0.196
0.210
10.167
6.830
4.151
4,040
MXNET (ES:B1)
10.022
726.995
0.196
0.210
6.875
35.620
0.613
4.680
Effect of bicriteria early stopping We investigate the impact of training MXNET (Compos-
ite) under the bicriteria early stopping mechanism (MxNET (ES: Bi)), by comparing it against two early stopping criteria, based solely on LMsS (MxNET (ES MSS)) and LSuhMatch (MXNET (ES: SubMatch)). We use the inference methods corresponding to both MXNET (MSS) and MxNET (SubMatch) on the test set. Table 3 reports the MSE numbers, which reveal the follow- ing observations. (1) MXNET (ES: shows extremely strong performance across all datasets, consistently achieving the best MSE results, when the inference is performed using MXNET (MSS). However, as often seen, most notably in MUTAG-m, RB and Brock, this sometimes comes at

---

Published as a conference paper at ICLR 2025
significant cost of MSE resulted from inference using MXNET (SubMatch), which indicates poten- tial overfitting. (2) MXNET (ES SubMatch) achieves best MSE results across five out of eight datasets, when inference is performed using MXNET (SubMatch). However the performance mea- sured in terms of MSE resulted from MxNET (MSS) based inference is not as strong, except for Enzymes where it matches the best performance; (3) MXNET :ES:Bi) provides more balanced approach, and we found bicriteria early stopping to be an effective guardrail against potential over- fitting of MXNET (MSS). As seen in Table 3, MXNET (ES: prevents extreme overfitting in datasets like MUTAG-m, RB and Brock, while matching the MSE achieved by MXNET (MSS) in datasets such as IMDB, AIDS-m, PTC-MM-m. and Enzymes. Therefore, while MxNET (ES :ii does not directly enhance performance, it ensures that inference via MXΝET (SubMatch) does not degrade significantly. This makes bicriteria early stopping a reliable mediator.
Contribution of combinatorial decoder Here, we compare the performance of each decoder based neu- ral model against its corresponding non-neural variant (named as Heuristic), which consists of only its own con- stituent decoder. The initial node heatmap input to the decoder computed using structure guided node score, selected from node degree, PageRank and clustering co- efficient, based on minimum validation error. addition, we also empower all methods by increasing the number of clique proposals by 4x from Table Table presents the results on two datasets in terms of both MSE and time. We observe that: (1) In some cases, the non-neural Heuristic variants
Table 4: Decoder vs No-decoder. green, blue, and yellow indicate the best, second- best, and third best performers
IMDB
PTC-MM
(5)
MSE
Time
EGN
0.102
0.117
0.284
0.149
BGN (4k)
0.102
0.236
0.183
0.410
Heuristic
2.824
0.146
0.861
0.159
Houristio(ks)
0.137
0.497
0.493
SCT
4.102
1.802
0.099
SCT (4x)
0.250
0.048
0.701
0.063
Heuristic
3.287
0.002
0.922
0.016
Houristic (dx)
0.250
0.007
0.480
0,030
Dilusoo
1,361
2214
Difusco (Cat) (lx)
0.231
0.722
0.979
0.799
Houristic
2.741
0.011
0931
0.045
Houristic (4k)
2,741
0.010
0.31
0.058
comparable to or even outperform the neural variants. This is particularly noticeable in SCT baseline for all variants, Difusco (Cat) in PTC-MM-m, and GFnet in IMDB. This highlights the significant role of the decoder in the clique detection tasks. (2) While MXNET still outperforms all baselines in
GFaet
0.032
0.554
(4x)
0.167
0.166
Heurisic
2.333
0.018
2.623
0.027
Houristic (ds)
0.213
0.053
1.160
0.143
MXNET
0.094
0.029
0.179
0.018
IMDB despite their improvements, it ranks third in PTC-MM-m. behind EGN (4x) and GFnet (4x). However, this improvement in the baselines comes with an almost 2x increase in run-time, making our method more efficient in terms of inference time latency.
Effect of distribution shift We construct an OOD -futtof-distribution) dataset based on the orig- inal PTC-MM-n dataset as follows: Given the dataset D (Gi, w (G.)) select all graphs with [V] 2 80 and w; 2 7 for the test set, while randomly partitioning the remaining graphs into training and validation splits. Consequently, during training, neither MXNET nor the baselines are exposed to large graphs with large clique sizes. We then evaluate the performance of all methods in predicting clique numbers on the test set. As the test dataset distriiiittiittinnn we observe per- formance drops for all methods (Table 5). Nevertheless, MXNET consistently outperforms others.
Table 5: Performance in terms of mean squared eтror (MSE) between the predicted and true clique numbers for two variants of PTC-MM-m dataset: (1) Default: which has been used in all experi- ments, and (2) OOD: which consists of specialized test set with all graphs containing [V] 2 80
and (G) 2 7. Numbers in green, blue indicate the best and second best performers respectively.
EGN SCAT GENET SFE NSFE ST REINFORCE MXNET
PTC-MM-m (Default)
0,284
1.802
0.554
26.568
19,800 26.703
37.455
0.179
PTC-MM-m (OOD)
3.26
1.256
0.832
42.328
33.129 42.644
56.682
0.822
CONCLUSIONS
The proposed MCP method, MXNET, introduces an end-to-end differentiable neural approach for predicting clique numbers of graphs. It can seamlessly integrate into existing deep learning frame- works (for retrieval applications, e.g.), where clique numbers serve as critical latent signals. By combining MXNET (MSS) and MxNET (SubMatch), we achieve a robust balance between high prediction accuracy and interpretability. Future work could focus on enhancing interpretability, han- dling dynamic graphs, and integrating domain knowledge through dense node/edge features within relevance learning frameworks. This research also paves the way for exploring differentiable pre- dictions of other combinatorial optimization challenges on graphs, extending applications in graph analysis and beyond.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
IR acknowledges Google PhD Fellowship. SC acknowledges IBM Grant and SERB grant. AD acknowledges SERB CRG grant.
REFERENCES
Dimitris K Agrafiotis, Maxim Shemanarev, Peter J Connolly, Michael Farnum, and Victor Lobanov. Sar maps: a new sar visualization technique for medicinal chemists. Journal of Medic- inal Chemistry, 50(24):5926 5937, 2007.
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verifi- cation and the hardness of approximation problems. J. ACM, 45(3)5001-55,, may 1998. ISSN 0004-5411. doi: 10. 141114477898827883666 URL httphtttp/.ccc /ttp:::://o...o http::///ooooo///////// /tt..////...11//2222...... 278306.
Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning to search. In The 38th International Conference on Machine Learning, ICMI, 2021, pp. 588-598, 2021.
Balabhaskar Balasundaram. Sergiy Butenko, and Illya V Hicks. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, 19(1):133-142, 2011.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.
Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blun- dell, Jovana Mitrovic, and Petar Veličković. Neural algorithmic reasoning with causal regularisa- tion. In International Conference on Machine Learning, pp. 2272-2288. PMLR, 2023.
M. Bohde, M. Liu, A. Saxton, and S. Ji. On the markov property of neural algorithmic reasoning: Analyses and methods. arXiv preprint MxXi::2403.04929 2024.
Immanuel M Bomze, Marco Budinich, Panos Pardalos, and Marcello Pelillo. The maximum clique problem. Handbook of Combinatorial Optimization: Supplement Volume A, pp. 1-74, 1999.
Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of undirected graph. Commun. ACM, 16(9):575-577, sep 1973. ISSN 0001-0782. doi: 10.1145/362342.362367 URL https:
//dpii.ogg//iio/o///ooooo 10. 11 45/ /04443365555 3623222222222 363367.
Lorenzo Brusca, Lars CPM Quaedvlieg, Stratis Skoulakis, Grigorios G. Chrysos, and Volkan Cevher. Maximum independent set: Self-training through dynamic programming. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Marco Budinich. Exact bounds on the order of the maximum clique of a graph. Discrete
Applied Mathematics, 127(3)535--443 2003. ISSN 0166-218X. doi: https://do..or//10. conet.ioo/cccieeeee.
1011//0066-2118x00000066668 URL attps://www. http://wwwwiiineeireee..... wtt.://eirreett..ccccccceeeeeeee axricieepp1/000111111000000
Yiqun Cao, Tao Jiang, and Thomas Girke. A maximum common substructure-based algorithm for
searching and predicting drug-like compounds. Bioinformatics, 24(13):1366-i744 2008
Randy Carraghan and Panos M Pardalos. An exact algorithm for the maximum clique problem. Operations Research Letters, 96):375-38 1990.
Lijun Chang. Efficient maximum clique computation over large sparse graphs. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 529-538, 2019.
11

---

Published as a conference paper at ICLR 2025
Alok Choudhary, Bharath Pattabiraman, Md. Mostofa Ali Patwary, Assefaw H. Gebremedhin, and Wei-keng Liao. Fast algorithms for the maximum clique problem on massive graphs with ap- plications to overlapping community detection. Internet Mathematics, 11(4), 9 2015. doi:
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300 2013.
Matjaz Depolli, Janez Konc, Kati Rozman, Roman Trobec, and Dusanka Janezic, Exact parallel maximum clique algorithm for general and protein graphs. Journal of chemical information and modeling, (20))2227722288 2013.
Ehrlich and Matthias Rarey. Maximum common subgraph isomorphism algorithms and their applications in molecular seience: a review. Wiley Interdisciplinary Reviews: Computa- tional Molecular Science, 1(1):68-79) 2011.
U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is almost np- complete. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2-12, 1991. doi: 10. 10.1109/SFCS, 1991.185341.
Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations (ICLR), 2020.
David Fooshee, Alessio Andronico, and Pierre Baldi. Reactionmap: An efficient atom-mapping algorithm for chemical reactions. Journal of chemical information and modeling, 53(11):2811 2819, 2013.
Dobrik Georgiev Georgiev, Danilo Numeroso, Davide Bacciu, and Pietro Liò. Neural algorithmic reasoning for combinatorial optimisation. In Learning on Graphs Conference, pp. 28-1 1. PMLR, 2024.
Luana E. Gibbons, Donald W. Hearn, Panos M. Pardalos, and Motakuri V. Ramana. Continuous characterizations of the maximum clique problem. Mathematics of Operations Research, 22(3): 754-768, 1997. ISSN 0364765X, 15265471. URL http: /ttp://wwwwww////// wttstttorrsssttteeeeeeeeoeeeeeee 3690403.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Sussman Grath- wohl, Dale Schuurmans, and Hanjun Dai. Dises: benchmark for discrete sampling. In Advances in Neural Information Processing Systems (NeurlPS), 2023.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https://wwwt
gurobi. com.
Johan Hastad.
Clique is hard to approximate within n/sup 1-/spl epsiv. In Proceedings of 37th Conference on Foundations of Computer Science, pp. 627-636. IEEE, 1996.
Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. Scaling up k-clique densest subgraph detection. Proceedings of the ACM on Management of Data, 1(1):1-26, 2023a.
Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. Scaling up k-clique densest subgraph detection. Proc. ACM Manag. Data, 1(1), May 2023b. doi: 10. 00.1145/3588923, URL.
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, et al. A generalist neural algorithmic learner. In Learning Graphs Conference, pp. 2-1. PMLR, 2022.
Bo Jiang, Pengfei Sun, Jin Tang, and Bin Luo. Glmnet: Graph leaniing-matchig matching networks for feature matching. arXiv preprint, 2019.
Hua Jiang, Chu-Min Li. and Felip Manya. An exact algorithm for the maximum weight clique prob- lem in large graphs. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
12

---

Published as a conference paper at ICLR 2025
D.S. Johnson and M.A. Trick. Cliques, Coloring, and Satisfiability: Second DIMACS Imple- mentation Challenge, October 11-13, 1993. Center for Discrete Mathematics and Theoretical Computer Science New Brunswick, NJ: DIMACS series in discrete mathematics and theoret- ical computer science. American Mathematical Society, 1996. ISBN 9780821870723. URL
https:
pettps:/bboks. /books/./ss/////////// srrookks.oogle.. co. in wiweokksiid-yyyoooooooo
Jonas JürB, Dulhan Hansaja Jayalath, and Petar Veličković. Recursive algorithmic reasoning. In Learning on Graphs Conference, pp. 5-1. PMLR, 2024.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
Nikolaos Karalias, Joshua Robinson, Andreas Loukas, and Stefanie Jegelka, Neural set function extensions: Learning with discrete functions in high dimensions. Advances in Neural Information Processing Systems, 35:15338-11 5352, 2022.
Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
Janez Kone and Dušanka Janezic. An improved branch and bound algorithm for the maximum clique problem. proteins, 4(5):590-596, 2007.
Chu-Min Li and Zhe Quan. An efficient branch-and-boume algorithm based on maxsat for the maximum clique problem. Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pp. 128-133, 2010.
Qiyan Li and Jeffrey Xu Yu. Fast local subgraph counting. Proceedings of the VLDB Endowment, 17(8):1977-1980, 2024a.
Qiyan Li and Jeffrey Xu Yu. Fast local subgraph counting. Proc. VLDB Endow., 1768):1967-1980, April 2024b, ISSN 2150-8097, doi: 10.4477133694373.66944.. URL https: /td.di.oorg/
N0.14778/3655
3659451.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: /5/ 1.05493, 2015.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In International conference on machine learning, pp. 3845-3845. PMLR, 2019. URL https://arxxiiii http://awww...orrrb///////////// 12787.
Zhuwen Li. Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Xuan Liu, Lin Zhang, Jiaqi Sun, Yujuu Yang, and Haiqing Yang. D2match: Leveraging deep learning and degeneracy for subgraph matching. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural sub- graph matching. arXiv preprint arXiv:2007.03099 00399, 2020.
Can Lu, Jeffrey Xu Yu, Hao Wei, and Yikai Zhang. Finding the maximum clique in massive graphs. Proceedings of the VLDB Endowment, 10(11) 1:118-11599 2017.
Han Lu, Zenan Li, Runzhong Wang, Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang. and Junchi Yan. Roco: A general framework for evaluating robustness of combinatorial optimization solvers on graphs. In International Conference on Learning Representations (ICLR), 2023.
Noël Malod-Dognin Rumen Andonov, and Nicola Yanev. Maximum cliques in protein structure comparison. In Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings 9, pp. 106-117. Springer, 2010.
13

---

Published as a conference paper at ICLR 2025
Ciaran McCreesh and Patrick Prosser. Reducing the branching in branch and bound algorithm for the maximum clique problem. In International Conference on Principles and Practice of Constraint Programming, pp. 549-563. Springer, 2014.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with gumbel-sinkhorn networks. arXiv preprini 180v:1800..08655, 2018. URL https:
//aaxiv.org/////eeiv. /ttpr/////////////////////////// 1802. 08660.6666..888 pdf.
Yimeng Min, Frederik Wenkel, Michael Perlmutter, and Guy Wolf. Can hybrid geometric scattering networks help solve the maximum clique problem? Advances in Neural Information Processing Systems, 35:22713 12:22713-22724 2022.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In JCML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. graphlearning. ic.
Theodore S. Motzkin and Ernst G. Straus. Maxima for graphs and new proof of theorem of turán. Canadian Journal of Mathematics, 17:533 - 540, 1965. URL https://api.
semanticscholar. wwwscholar.og//Coooo wwt.
Duy MH Nguyen. Hoang Nguyen. Nghiem T Diep. Tan N Pham, Tri Cao, Binh T Nguyen, Paul Swoboda, Nhat Ho, Shadi Albarqouni, Pengtao Xie, et al. Lvm-med: Learning large-scale self- supervised vision models for medical imaging via second-order graph matching. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
P. M. Pardalos and A. T. Phillips. A global optimization approach for solving the maximum clique problem. International Journal of Computer Mathemattics, 33(3-4):09-2166, 1990. doi: 10.10 002071690088038511. URL https: /tt////oii/ org/ 10.
Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. On clique relaxation models in network anal- ysis. European Journal of Operational Research, 226( 1:9--8, 2013.
M. Pelillo. Relaxation labeling networks that solve the maximum clique problem. In 1995 Fourth International Conference on Artificial Neural Networks, pp. 166-170, 1995, doi: 10.1049/cp: 19950548.
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. Greed: A neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Pro- cessing Systems 2022, NeurlPS 2022, November 29- Decemer 1, 2022, 2022.
John W Raymond and Peter Willett. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of computer-aided molecular design, 16(7):521-533, 2002.
Kristjan Reba, Matej Guid, Kati Rozman, Dušanka Janežič, and Janez Konc. Exact maximum clique algorithm for different graph types using machine learning. Mathematics, 10(1):97, 2021.
Gleb Rodionov and Liudmila Prokhorenkova. Neural algorithmic reasoning without intermediate supervision. Advances in Neural Information Processing Systems, 36, 2024.
Indradyumna Roy, Venkata Sai Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. AAAI, 2022.
Pablo San Segundo, Alvaro Lopez, and Panos M Pardalos. A new exact maximum clique algorithm for large and massive sparse graphs. Computers Operations Research, 66:81-94, 2016
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Variational annealing graphs for combinatorial optimization, 2023.
Christine Solnon, Guillaume Damiand, Colin De La Higuera, and Jean- -aan-Chrittophe Janodet. On the complexity of submap isomorphism and maximum common submap problems. Pattern Recogni- fion, 48(2):302-316 2015.
14

---

Published as a conference paper at ICLR 2025
Victor Spirin and Leonid A Mirny. Protein complexes and functional modules in molecular net- works. Proceedings of the national Academy of sciences, 100(21):12123--2222:: 12128, 2003.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 36, 2024.
Etsuji Tomita, Sora Matsuzaki, Atsuki Nagao, Hiro Ito, and Mitsuo Wakatsuki. much faster algorithm for finding maximum clique with computational experiments. Journal of Information Processing, 25:667-677, 2017.
Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In Proceedings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 104-112, New York, NY, USA, 2013. Association for Computing Machin- ery. ISBN 978145032 doi: 14114552447775524887666 URL https: /twi. /10. 1145/248788 7575 2487645.
Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7), 2021.
Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning bench- mark. In International Conference Machine Learning, pp. 22084-22102. PMLR, 2022.
Hanchen Wang, Rong Hu, Ying Zhang, Lu Qin, Wei Wang. and Wenjie Zhang. Neural subgraph counting with wasserstein estimator. In Proceedings of the 2022 International Conference Management of Data, pp. 160-175, 2022.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta learning. In International Conference on Learning Representations (ICLR), 2023.
Runzhong Wang. Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, and Junchi Yan. Linsat- net: The positive linear satisfiability neural networks. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Herbert S Wilf. The eigenvalues of graph and its chromatic number. Journal of the London mathematical Sociery, 1(1):330-332, 1967.
Herbert S Wilf. Spectral bounds for the clique and independence numbers of graphs. Journal of Combinatorial Theory, Series B, 40(1):113-111 1986.
Ronald J. Williams. Simple statistical follient-following algorithms for connectionist reinforce-
ment learning. Mach. Learn., 8(3-4):229-2555 256. may 1992. ISSN 0885-6125. doi: 10.1007/ BF00992696. URL https: doi. wttpd/oogg...../...........
Kaijia Xu and Petar Veličković. Recurrent aggregators in neural algorithmic reasoning. arXiv preprint arXiv:2409.071: 2024.
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Random constraint satis- faction: Easy generation of hard (satisfiable) instances. Artif. Intell,, 171:514-534, 2007. URL
https: /pss://app /api. sseannt cschol ar. org/ Corpoorrussss ITr 27811887888
Liren Yu, Jiaming Xu, and Xiaojun Lin. Seedgnn: Graph neural network for supervised seeded graph matching. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-independent embedding and hungarian attention. In International Conference on Learn ing Representations (ICLR), 2020.
Shuangfei Zhai, Tatiana Likhomanenko, Etai Littwin, Dan Busbridge, Jason Ramapuram, Yizhe Zhang, Jiatao Gu, and Joshua M Susskind. Stabilizing transformer training by preventing attention entropy collapse. International Conference on Machine Learning, pp. 40770-40805 PMLR, 2023.
15

---

Published as a conference paper at ICLR 2025
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in Neural Information Processing Systems, 36, 2024.
Zhongyuan Zhao, Ananthram Swami, and Santiago Segarra. Graph-based deterministic policy gra- dient for repetitive combinatorial optimization problems. In International Conference on Learn- ing Representations (ICLR), 2023.
Yixiao Zhou, Ruiqi Jia, Hongxiang Lin, Hefeng Quan, Yumeng Zhao, and Xiaoqing Lyu. Improving graph matching with positional reconstruction encoder-decoder network. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth anmual ACM symposium Theory of computing, pP- 681-690, 2006.
16

---

Published as a conference paper at ICLR 2025
Clique Number Estimation via Differentiable Functions of Adjacency Matrix Permutations (Appendix)
CONTENTS
A Limitations
18
Broader Impact
18
Further discussion of related work
19
D Implementation details
21
D.I Details of our network architecture
21
D.2 Details about training
21
D.3 Complexity Analysis of MXNET
21
D.4 Details about baselines
22
D.5 Hardware and license
22
Details about experimental setup
22
E.1
Datasets Description
22
E.2
Datasets Statistics
22
E,3
Further notes on heavy-lifting decoders
22
E.4
Further notes evaluation metrics
23
E.5
Discussion on Baselines
23
Additional experiments
25
F.
Results on comparisons with state-of-the-art baselines with standard error
25
F2
Investigating the effect of bicriteria early stopping
26
F3
Ablation study on variants of MxNET
26
F.4
Adaption of baselines to learning under distant supervision
27
F.5
Zooming in on the results of competitors closest to MXNET
28
F66
Ablations on baselines and decoders
28
F.6.1
Ablation EGN
29
F.6.2
Ablation SCT
30
................................
F.6.3
Ablation Difusco
31
F.6.4
Ablation GFnet
.
32
F.7
Ablation study
.
................................
33
F.8
Performance large graphs
34
F9
Robustness with respect to
35
F.10
Full curriculum terms vs. curriculum learning with fewer terms
35
F.1
Comparison with combinatorial methods
35
17

---

Published as a conference paper at ICLR 2025
A LIMITATIONS
While MxNET presents an end-to-end differentiable mechanism for robust prediction of clique num- bers in graphs, several potential limitations should be considered.
1. The method's reliance on node permutations and subgraph matching may lead to memory or computational constraints when dealing with large or dense graphs. Although scaling concerns common among combinatorial and neural approaches, our method still war- rants additional attention in this regard.
2. In various graph applications where cliques are important latent signals, graphs often come with domain knowledge encoded as dense node or edge features. While our integration with common GNN-based encoders provides solution to incorporate such domain information, disentangled modeling of these influences in relevance judgments may be needed.
3. While MXNET demonstrates remarkable capability in navigating the exponentially large space of permutations, as seen in the experiments, there is still room for improvement, especially compared to combinatorial methods or decoder-based pipelines. This requires further investigation into improving model decisions, perhaps through better search tech- niques leading to more interpretable certificates of clique presence.
4. This proposal highlights significant opportunities for developing fully differentiable and backpropagable neural pipelines for solving combinatorial problems on graphs. While existing neural architectures have successfully reduced amortized solution costs compared to combinatorial approaches, these methods could not scamlessly integrated into existing neural network pipelines. While our proposal addresses clique number estimation tasks, extension to other combinatorial challenges requires further research.
B BROADER IMPACT
Our proposed work MXNET has significant broader impact across various domains of research and applications.
1. In biological networks, cliques represent highly connected functional units such as protein complexes and regulatory modules (Spirin & Mirny, 2003). Our neural clique number prediction module can assist in studying these biological systems and their functions.
2. In social networks, cliques represent tightly interconnected communities. Our model can provide insights related to community detection, influence propagation, maximization, and studying other network dynamics.
3. In recommendation systems, cliques often represent closely connected sets of items and users. Additionally, structural notions of pairwise similarity, such as the maximum com- mon induced subgraph (MCIS), use clique number prediction subroutine. Accurate prediction clique numbers can enhance recommendation pipelines by identifying rele- vant items and modeling user interest overlap.
4. Furthermore, the combination of MxNET (MSS) and MxNET (SubMatch) ensures not only high prediction accuracy but also interpretability. This is erucial in applications where understanding the reasoning behind predictions is essential for decision-making.
5. Since our proposed method MXNET primarily focuses on improving the accuracy and in- terpretability of predicting clique numbers in graphs using neural networks, there are no significant ethical concerns. The method does not involve human subjects or personal data, and it is not directly applicable to negative societal impacts.
18

---

Published as a conference paper at ICLR 2025
C FURTHER DISCUSSION OF RELATED WORK
Combinatorial methods for maximum clique detection The maximum clique problem (MCP) No-collee (Karp, 2010). It is notoriously hard to even approximate (Feige et al., 1991; Arora et al., 1998). Strong motivation from applications have nevertheless driven the development of combinatorial and math programming methods to find large cliques in real-life scenarios. The Bron-Kerbosch algorithm (Bron & Kerbosch, 1973) is among the well-known enumerative algo- rithms for MCP, Other systems (Choudhary et al., 2015) are tailored for social network analysis in massive graphs. Lu et al. (2017); Chang (2019) provide heuristics for exact maximum clique de- tection. He et al. (2023a) is for approximate k-clique detection with theoretical guarantee. One can adapt this technique to predict the clique number.
Neural models for maximum elique detection Neural maximum clique detection methods fall into three main categories: supervised learning, unsupervised learning, and reinforcement learning,
Supervised approaches: Recent advancements, such Difusco (Sun & Yang, 2024), propose a diffusion- based generative model trained using node-level supervision of ground truth cliques, enabling non-autoregreesivv one-shot prediction of cliques. However, given the NP-Completeness of the problem, obtaining large quantities of labeled data with fine-gres one-grained optimal node-labels is impractical, which is essential for providing explicit guidance to training algorithms regarding clique structures.
Unsupervised approaches: Consequently, the research community has shifted towards unsuper- vised (Karalias al.. 2022: Karalias & Loukas, 2020: Min et al., 2022) or reinforcement learn- ing (Sanokowski et al., 2023; Zhang et al., 2024) approaches. Unsupervised methods learn pa- rameterized distribution over candidate solutions (Karalias & Loukas, 2020; Min et al., 2022), gen- erating node-level heatmaps that indicate the likelihood of node participation in cliques. Yet, due to the problem's multimodal nature, such approaches resort to a greedy decoder with built-in clique maximization heuristics for autoregressive clique generation, limiting scalability and rendering end- to-end differentiable pipelines unfcasible. Our experiments reveal that the performance of such approaches heavily relies on the non-differentiable greedy decoder, as its removal leads to consid- crable performance degradation. Interestingly, these methods underscore the potency of decoding heuristics, where synergies between random graph selcture-basedd signals and the decoder yield comparable or superior performance to neural mechanisms.
Reinforcement learning approaches: In a concurrent line of research, reinforcement learning models (Sanokowski et al., 2023; Zhang et al., 2024) frame maximum clique detection se- quential decoding process, training a Markov Decision Process (MDP) with final reward based on detected maximum clique size. While such methods offer high accuracy and reduced amortized solution generation times, the costly decoding process and sparse reward structure render them in- compatible with certain applications. Additionally, our experiments indicate that substituting the learned policy with graph statistic-based heuristics often yields comparable performance.
Neural Algorithmic Reasoning (NAR) In recent years, body of work study the design of neural network to mimic procedural algorithms (e.g., sorting, searching, fundamental graph al- gorithms, etc), predominantly by leveraging the message passing module of graph neural net- work (GNN) (Veličković & Blundell, 2021; Bevilacqua et al., 2023; Rodionov & Prokhorenkova, 2024; Georgiev et al., 2024; Xu & Veličkovié, 2024; Ibarz al., 2022; Veličković al., 2022; Jürß et al., 2024; Bohde et al., 2024). Veličković & Blundell (2021) introduced this problem, where they provided intermediate states of the underlying procedural algorithm into the underly- ing GNN. Bevilacqua et al. (2023) apply causal regularization on top of the NAR framework. Ro- dionov & Prokhorenkova (2024) tackles NAR with intermediate states of the underlying algo- rithm. Veličković et al. (2022) performs benchmarking on a wide variety of popular algorithms from CLRS textbook. Very recently, Bohde et al. (2024) designs NAR model which preserves Markov property of algorithmic execution.
Related graph search problems The database community has witnessed much recent interest in the closely related problem of counting the number of occurrences of a query graph in a corpus graph. NeurSC (Wang et al., 2022) starts by finding, for each node u in query graph, plausible corpus graph nodes v to which it may map. While doing this, NeurSC takes advantage of labels of u, u and their neighborhoods. The query and each candidate graph in turn are then encoded via GNNs in both early unter-graph and late intra-graphh interaction modes, and then these graph representations compared using optimal transport method to arrive a (soft) boolean prediction of whether the
19

---

Published as a conference paper at ICLR 2025
query graph is subgraph of the candidate. SCOPE (Li & Yu, 2024a) provides combinatorial algorithm for subgraph counting based on tree decomposition of the pattern (similar to a query) graph, then using specific counting techniques (tISO-match) for trees and their combinations. These counting methods can be used for clique number prediction. We can invoke one of these methods count the number of occurrences of K.; in the corpus graph for c 1, ....... after which ((G) is predicted as the largest for which a positive count is reported. Given a subgraph S of graph G, the density of S is the ratio of the number of edges the number of nodes in S. The densest subgraph problem is that of finding subgraph of maximum density. Yet another problem is to find the k- clique densest subgraph (He et al., 2023a; Tsourakakis et al., 2013). Here, given an input graph, the goal is to detect subgraph that maximizes the ratio between the number of k-cliques contained in and the number of vertices it. The densest subgraph problem a special case with k 2.
20

---

Published as a conference paper at ICLR 2025
D IMPLEMENTATION DETAILS
D.1 DETAILS OF OUR NETWORK ARCHITECTURE
Our approach consists of three key components: the graph neural network GNN,, transformation network Tg. and neural relaxations DPmsg DPupdate, and DPreadouty. g. The graph neural network GÑN, consists of L = layer graph neural network, that projects the initial node features to d 10 dimension embedding space. For all datasets, initial node features. Following the methodology proposed in (Li et al., 2015; 2019), we com- pute the updated node embeddings follows using a Gated Recurrent Unit (GRU) as follows: (=(u)) GRU, ( Engnbr(u) LINEAR((Z;-1(1). (x-11) x<-1(1) where LINEAR is a single lin- car layer with both input dimension and output dimensions set to 10, and GRU, is the GRU network where the computed node embedding is utilized in the hidden state. After L = 5 such iterations, derive X = I (u)] [N] as the final node embeddings. The transformation network Tę consists of 2-layer feedforward network which consists of linear layer followed by ReLU activation and a linear layer. This maps the embeddings X from d = 10 dimensions to N dimensions, where N represents the number of nodes in the padded graph. Following the Sinkhorn iterations with Tmax = 20, where the Sinkhorn temperature is chosen from E f0.01, 0.05], the input matrix to the neural MSS algorithm E NxN, and SW S [ E Rdd where d' = 1. For the neural relaxation of the MSS algorithm, DPmsg and DPupdate are 2-layer feedforward networks with ReLU ac- tivation mapping from 2d' to d' Meanwhile, DPreadouty is a 2-layer feedforward network with ReLU activation mapping from d' to 1, which outputs the predicted clique number. For the design of Ccompesite we set = 1, and search for y, À in {0.25, 0.75), and {0.1, 1} respectively. Hence, the total search space for hyperparameters consists of 8 combinations ((r) x {n} x {X}), and we select the best model out of the 8 hyperparameter configurations.
set x (0) = [1] as the
D.2 DETAILS ABOUT OUR TRAINING
For the early stopping criteria based on the validation MSE, we use a patience parameter as 200 epochs. All models are trained using the Adam optimizer, with learning rate of 10-3, and weight decay x 10-4
D.3 COMPLEXITY ANALYSIS OF MXNET
Considering [V[ N, we compute the computational complexity of MXNET (MSS) and MXNET (SubMatch) as follows:
MXNET (MSS): Since X E
EERNK Nxx, the complexity of computing W = O xX is O(N'd). Further, the computation of S has complexity O(N)). Since S approximates permutation matrix, and the temperature À is small, we have constant order of elements in each row and column leading to an O(N2) complexity for computing SWST. Finalyy, overall complexity of (() MXNET (SubMatch): Since X E RN xd and S is sparse, computation of SX has com- compute Σ,, jQ SX]+ in O(N) time. However, due to extensive tensorization in our implementations, the effective time complexity is much less. In Table 6, we compare the time (in ms) for a forward pass for different values of N=IVl.
Algorithm I runs for 2 iteration, giving
plexity ONd) and
Table 6: Time (in ms) for a forward pass for MxNET (SubMatch) on graphs with increasing [ from 100 to 900.
100
200
300
400
500
600
700
800
900
Time (ms)
21.78
20.94
21.58
21.47
21.94
22.12
21.83
22.29
23.11
Further, note that since we store the adjacency matrices and the FF matrix from Algorithm I explic- itly, our space complexity O
21

---

Published as a conference paper at ICLR 2025
D.4 DETAILS ABOUT BASELINES
For all methods, dimension to d = 10. We use the default implementations publicly available on GitHub for all methods- (1) EGN (2) SCT (3) Difusco (4) GFnet (5) VAG-CO and (6) SFE, NSFE, ST, Reinforce
the number of GNN propagation layers L and the embedding
D.5 HARDWARE AND LICENSE
We implement our models using Python 3.10 and Py PyTorch 2.3.0. The training of our models and the baselines was performed on servers containing AMD EPYC 7642 48-Core Processors at 2.30GHz CPUs, and Nvidia RTX A6000 GPUs. Running times of all methods are compared on clean machine with the above specifications.
E DETAILS ABOUT EXPERIMENTAL SETUP
E.I DATASETS DESCRIPTION
We perform comprehensive experiments on eight datasets, including five real-world and three syn- thetic datasets. For the real-world datasets, following (Sanokowski al., 2023),
(1) IMDB- BINARY (IMDB), (2) ENZYMES (Enzymes) and modular product graphs from three real-world datasets sourced from the TUDatasets repository (Moriis al., 2020): (3) PTC-MM, (4) AIDS and (5) Mutagenicity. We use PTC-MM-m. AIDS-m and MUTAG-m to denote these datasets consisting of modular products. The clique number these graphs represents the size of the max- imum common induced subgraph. Given graph G1. G2, the modular product graph H G1 o G2 has V(H) V(G,) x ((22). and nodes (u,,Ug) U2). (V), 02) V(H) have an edge if (i) U1 (u2, U2) E E(G2), (ii) W2 = 12/(u1, v1) E E,G,), (iti) (u1, v1) E(G1)A(w2 v2) E E(G2), or (iv) (u1, 01) & E(G1) A (u2, 02) & AE(G2). It is known that w(H) is the size of the maximum common induced subgraph of G1 and G2. addition to these five real datasets, we also gener- ate three synthetic datasets- (6) DSIC (Johnson & Trick, 1996), consisting of k-partite random graphs with at least one k-clique; (7) Brockington (Johnson Trick, 1996), consisting graphs with cliques hidden within low-degree nodes; and (8) RB (RB) (Xu et al., 2007), representing ran- dom hard constraint satisfaction problem instances that yield hard-to-find cliques. We generate one dataset consisting of 50 nodes sized graphs from DSJC (DSJC) and Brockington (Brock) families. We use the Gurobi solver (Gurobi Optimization, LLC, 2023) (with no time-limit) to generate the gold ground truth elique numbers for distant supervision.
E.2 DATASETS STATISTICS
Table 7: Description of the datasets used for training and evaluation on clique number estimation. Table reports number of graphs, average and maximum number of nodes (VV,, average and maxi- mum number of edges [E,, average edge density (E)/ ((K)) and the average and maximum ground truth clique numbers (w).
Num Graphs
Avg. VV
Max. [V]
Avg. [
Max. [
Avg. ((())
Avg. w
Max. w
(Morris al., 2020)
337
23.382
0.413
Brock (Johnson & Trick. 1996)
1000
50.000
50
857.029
1225
0.700
24.875
50
DSIC (Johnson Trick,
1000
50.000
730.820
936
0.597
20.640
AIDS-m (Morris et al., 2020)
1000
96.039
110
2470.012
3528
0.523
7.678
PMC (Morris al., 2020)
2372
79,847
100
1518.133
2700
0.453
5.962
9
Enzymes (Moris et al., 2020)
595
32.482
125
62, 168
149
0.160
3.797
5
MUTAG-m (Morris
2020)
1000
258.435
300
22352.62 642
31654
0.660
11,203
RB (Xu et al., 2007)
1000
252.276
300
4069.608
8805
0.126
17,428
26
E.3 FURTHER NOTES ON HEAVY-LIFTING DECODERS
Our experiments suggest that some decoders in prior methods are very powerful, capable of returning near-maximal cliques starting from even uninformative heatmaps from naive heuristics. For some datasets, just sorting the nodes decreasing order of degree or PageRank, and then including nodes
hattap::/gthaaa.ccm////taeeeeeee 'ttpps:/ htt.fprr//aaaaaacccommmaaaalllls
22

---

Published as a conference paper at ICLR 2025
that form clique with already-included nodes, performs quite well. In some cases, removing the decoder and estimating the clique number directly from the heatmap resulted in drastic degradation of accuracy. This is testament to how much value the decoder adds to the overall method, com- pared to the module that computes the heatmap. Some decoders involve backtracking search over node selection decisions informed by the heatmap. Some of the decoders simply consist of repeated sampling from the heatmap distribution and checking if the sample forms a clique - with such de- coders, performance increases monotonically with increased investment of decoding time. In some implementations, sampling more costs predictably more time. In others, clever tensorization masks such costs effectively. This makes time-aceuracy comparisons of non-standardized implementations based on wall-clock time quite misleading.
E.4 FURTHER NOTES ON EVALCATION METRICS
We have proposed (R)MSE as a robust measure of estimation quality. In the combinatorial opti- mization literature, it is common to measure the approximation ratio between the reported clique size and the ground truth clique size, which is at most 1 (for methods that find actual cliques), aver- aged over instances. Approximation ratio is not appropriate for methods that can both overestimate and underestimate the ground truth clique size, because estimation errors across multiple instances may cancel out, giving an excessively optimistic impression of a method.
E.5 DISCUSSION ON BASELINES
In the context of maximum clique detection, methods can be broadly classified into supervised learning, unsupervised learning and reinforcement learning based approaches.
Supervised under extreme supervision: DIFUSCO (Sun & Yang. 2024) uses extreme supervision by incorporating the exact maximum clique as input features and employing Cross Entropy Loss for training. This method is paired with a non-differentiiale greedy clique number decoder.
Several methods estimate the clique number without supervision. Our experiments include: (1) SFE and NSFE (Karalias et al., 2022), which are end-to-end differentiable methods that extend set functions to continuous domains; (2) REINFORCE algorithm (Williams, 1992) and (3) Straught-Through (ST) Estimator (Bengio et al., 2013), which enable backpropagation through discrete functions; (4) EGN (Karalias & Loukas, 2020), which trains GNN with probabilistic decoder; and (4) Scattering GCN (SCT) (Min et al., 2022), which trains scattering GNN with a probabilistic penalty loss and uses non- differentiable walk- decoder. (5) NeurSC: Neural Subgraph Count- ing with Wasserstein Estimator (NeurSC) NeurSC addresses the subgraph counting problem using neural networks with GNN-based estimators that leverage both intra-graph and inter-graph neural architectures, complemented by Wasserstein discriminator. We adapted NeurSC baseline for our clique number prediction framework 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 l: for which non-zero count is returned.
Unsupervised:
penalty loss function and retrieves the clique number using a wrobabllitic-sampling
In its default implementation, NeurSC employs neural network with final ReLU layer to ensure non-negative count predictions. After experimenting with various loss functions, we found that the best performance is achieved by removing the final ReLU layer and training the model to output positive scores for query cliques with ( k S w(G) ) the ground truth clique number and negative scores for ( k w(G)) the ground truth. This adaptation simplifies inference by identifying the point in the sequence of query cliques where the predicted score transitions from positive to negative, while also enabling effective training.
Reinforcement Learning: We include: (1) VAG-CO (Sanokowski et al., 2023), which frames the clique number problem as a variational learning problem in an RL setting and uses non- differentiable decoder to sample the clique number. (2) GFlowNet (GFNET) (Zhang et al., 2024), which designs an MDP with states forming latent flow network and estimates the clique number through a dindeifferenti heuristic- based decoder.
Details about Decoder-reliatt baselines We observe that methods with a non-differentiable com- ponent in the neural pipeline rely on decoders to generate the clique number from the output of the model. We describe each of the baselines below:
1. Heuristic: This generates heatmap values for a graph which may be based upon graph statistics such as node degree, clustering coefficient or pagerank. It first sorts these values in non-increasing
23

---

Published as a conference paper at ICLR 2025
order and iterates over the nodes, adding them to the solution set if (i) the total number of edges in the clique increases, and (ii) the clique constraint is not violated. We use the greedy decoder with the Difusco (Cont) and Difusco (Cat) baselines, described next.
2. Difusco: Difusco generates multimodal distribution heatmaps for the underlying task, with two variants: Difusco (Cont) for diffusion with continuous Gaussian noise, and Difusco (Cat) for diffu- sion with categorical Bernoulli noise. Originally evaluated on the traveling salesman problem and the maximum independent set (MIS), for which greedy decoder is used, we implement a similar greedy decoder for the clique number problem and evaluate DIFUSCO on this task.
3. EGN: EGN outputs the probability of each node belonging the maximum clique. The proba- bilistic decoder used by EGN sorts these probability values in non-increasing order and iteratively adds each node to the solution set if it decreases constrained probabilistic loss function, which is zero when a clique is detected. The maximum over multiple solutions is reported the clique number.
4. SCT: Similar to EGN, SCAT outputs probability value for each node indicating its likelihood of being in the maximum clique. The SCAT decoder sorts these values non-decreasing order and iterates over the nodes. At each step, it starts walk the remaining nodes, adding node the solution set if the clique property is satisfied. The maximum cardinality of all found solutions is returned.
5. VAG-CO: VAG-CO approaches to solve the clique number problem by framing it in the space of Ising Models, and trains in an RL manner, and finally samples solutions from a learned autoregressive parameterized distribution
GFnet: Since GFnet is a RL. method, maintains states and actions. At each iteration step, samples an action, which decides which node to include in the clique. If the node inclusion violates the clique condition in the solution, it is removed from the solution set. Moreover, after addition of node, it does degree-based pruning to remove any node which might not be feasible.
24

---

Published as a conference paper at ICLR 2025
F ADDITIONAL EXPERIMENTS
F.1 RESULTS ON COMPARISONS WITH STATE-OF-THE BASELINES WITH STANDARD ERROR
In the main paper, Table compares MxNET and MxNET (MSS), against all the state-of-the art basclines. We were unable to report standard error due to space constraints. In Table 8, we report the results along with the standard error all eight datasets. The standard error is computed over the squared enror over all of the graphs in each dataset.
Table 8: Comparison of MXNET against ofate-of-the-art baselines in terms of Mean Squared Er- ror (MSE) with standard error (lower better). The baselines include EGN (Karalias & Loukas, 2020), SCT (Min et al., 2022), Difusco (Cat) (Sun & Yang, 2024), Difusco (Cont) (Sun & Yang. 2024), GFnet (Zhang et al., 2024), VAG-CO (Sanokowski et al., 2023), SFE (Karalias et al., 2022), NSFE (Karalias et al., 2022), ST (Bengio al., 2013), and Reinforce (Williams, 1992). Baselines
are divided into two categories: (i) those with a decoder, and (ii) those without. Numbers in green, blue, and yellow indicate the best, second-best, and third-best performers, respectively.
IMDB
AIDS-m
PTC-MM-m
DSIC
EGN (Karalias & Loukas, 2020)
0.102 + 0.054
0.610
0.060
0,284 + 0.026
0.030 + 0.021
Decoder
SCT (Min et al.. 2022)
4.102 0.810
3.865 1 0.278
1,802 1 0,109
92.675 1 8.394
Difusco (Cont) (Sun & Yang, 2024)
5.333 +: 2.174
4.665
0.277
2.621 1 0.199
59.820 +: 6.776
Difusco (Cat) (Sun & Yang, 2024)
1.361 = 0.510
2.244 + 0.129
1.560 + 0.473
GFnet (Zhang et al., 2024)
2.815 0.779
0.740 0.085
0.554
4,820 1 1.388
VAG-CO (Sanokowski et al., 2023)
5.037 1.896
0.800 33,905
19.962 + 0.540
7.665 + 0.529
SFE (Karalias el al., 2022)
4.833 1.356
44.340
0.833
26.568 0.649
12,465 1 1.803
Non- Den-Deccder
NSFE (Karalias et al., 2022)
3.185 1.394
36.005
0.911
1
5,255 + 1.048
(Bengio et al., 2013)
8.972 2.595
44.885
1 0,882
26.703
0.640
5,410 1 0,991
Reinforce (Williams, 1992)
16.472 4.341
59.170
1,014
37.455
0.797
13.280 3.884
NcurSC (Wang al., 2022)
5.330 0.22
1,240 0.079
1.510
15.350 + 0.268
MxNET (ES MSS)
0.094 0.022
0.341
0.044
0.179 0.013
0.383 1 0.074
MXNET BB)
0.094 + 0.022
0.341 + 0.044
0.179 + 0.013
0.383 + 0.074
Brock
Enzymes
MUTAG-m:
EGN (Karalias & Loukas, 2020)
1,310 0.453
0.109 0.044
15.615
1.738
1,010 1 0.101
Decoder
SCT (Min et al., 2022)
35.885 + 5.868
0.891 0.124
50.230
3.489
11.105 + 0.855
Difusco (Cons) (Sun & Yang. 2024)
39.040 + 12.402
1.034 + 0.133
63.490
4.258
10,590 + 0.610
Difusco (Cat) (Sun Yang, 2024)
10.595 + 2.584
0.950 + 0.103
4.118 55.630
10,965 + 0.598
GTnet (Zhang el ul., 2024)
1.574
0.857 0.093
34,200
2.989
2.565 1 0.208
VAG-CO (Sanokowski al., 2023)
15.450 +: 2.186
4.244 0.2244
320.240
7.867
132.700 1 3.046
SFE (Karalias et al., 2022)
53.595 1 6.124
1.200
72.020
3.002
110.905 1 2.764
Non- Decode
NSFE (Karalias ct al., 2022)
47.920 + 5.543
1.118 +118 0.170
78.890
4.220
96.445 + 2.636
ST (Bengio et al., 2013)
55.740 + 6.363
5.454 + 0.284
0.2284
131.230
6.584
111.020 + 2.769
Reinfurce (Williams, 1992)
403.095 37.037
1,731
229.435
132,700 3.054
NeurSC (Wang el al., 2022)
88.790 1 0.667
0.630
10.080 0.214
3,520 1 0.132
MXNET (ES: : MSS)
10.022 1 1.185
0.203 1 0.024
6.875 0.604
4.130 +: 0.399
MXNET (ES: : B1)
10.022 + 1.185
0.196 - 0.026
6.875 0.604
0.613 1 0.067
25

---

Published as a conference paper at ICLR 2025
F.2 INVESTIGATING THE EFFECT OF BICRITERIA EARLY STOPPING
In Table 3, we compared the effect of training with the three different early stopping strategies, leading to MxNET (ES: MSS), MXNET (ES: SubMatch) and MxNET BES: Due to space constraints, we could not report the standard error numbers in the main paper. Here, in Table 9 present results in terms of MSE and standard error for all eight datasets.
Table Performance MXNET (Composite) for different early stopping criteria, which are based on LMSS. LSubMatch and Composite respectively. For each of these early stopping criteria, we use MXNET (MSS) and MxNET (SubMatch) (denoted as MSS and SubMatch respectively) components to measure the performance in terms of MSE on the test set. Numbers in green indicate the best performers.
IMDE SubMarch
Allas-
PTC
DASIC
MSS
MSS
SubMarch
MSS
SalMucc
M55
SabManch
MANETVES 3455) MXNeT ES SubKaaatchh) ESS:
0194 0.002
0:41 0.09
0:341 0.04
0.179 + 0.13
0.265
0.027
0.383
0.04
9 RM0 2.488
0.381 0.122
DAKS + 0O00
0.507
+ 0033
D.50 0.52
0,232
= 0015
0
D089
0.561
+ 0.004
7.335
+ 0.022
0.341
0.09
0.34)
# 0.844
0,705 + 0.186
0.179
= 0.13
0,265 # 0.027
0.383
# 0.074
9.366
2.488
Boock
hargmes
RBI
MUTAG--
MSS
SubMach
MSS
SahMarc
M85
MSS
MSS
SabMaach
MENNET E8 H88)
10J02 2 L.85
726955 E 4336%
02005 1 0,024
0.333 E 0102
6,375
9.004
15,300 2 9,273
4,130 1
7,905 1 0,98
MxNet (88: chb
165
1,399
170.200 &: 14.236
0.19 d 0,255
0.200 0.008
10.102
= 0.579
6,830 0.752
4,151 4 0,392
4,000 s 0.333
10,02 8 1.185
726 796-9555 43.56
196 # 0.066
0.210 i 0.085
6.875
0.94
35630 6 9,223
0.613 18 0067
4.600 0.602
F.3 ABLATION STUDY ON VARIANTS OF MXNET
In the main paper, Table 2 presents an ablation study where we compare the impact of the three pos- sible variations of our models, MxNET (MSS), MXNET (SubMatch), and MxNET (Composite) terms of MSE. Due to space constraints, we did not report the standard error numbers the main. We now do so in Table 10.
Table 10: Comparison of MXNET (MSS), MxNET (SubMatch), and MXNET variants in terms of Mean Squared Error (MSE) on eight datasets. Numbers in green, blue indicate the best performers and second best performers respectively.
IMDB
AIDS-m
PTC-MM-m
DSJC
MXNET (MSS)
24.434
7.392
0.295 1 0.035
2.364 0.174
66.890 1 5.394
MXNET (SubMatch)
0.056
0.039
0.420 + 0.049
0.512 0.039
2,820 = 0.772
MxNET
0.022 0.094
0.341 1 0.044
0.179 1 0.013
0.383 1 0.074
Brock
Enzymes
RB
MUTAG-M
MXNET (MSS)
150.430 10.911
0.205 + 0.023
10.190 0.879
4.130 0.399
MXNET (SubMarch)
150.890 # 11.504
0.210 = 0.038
7.170 = 0.975
4.040 = 0.333
MXNET
10.022 1: 1.185
0.196 : 0.026
6.875 1 0.604
0.613 1 0.067
26

---

Published as a conference paper at ICLR 2025
F.4 ADAPTION OF BASELINES TO LEARNING UNDER DISTANT SUPERVISION
Here, we expand our exploration of supervised methods by adapting decoder-based baselines to our direct clique prediction objective. Although there are no clear guidelines for customizing decoder techniques specifically for our purposes, we outline our adaptation attempts for each baseline below.
Extension Non-decoder Unsupervised baselines We have four baselines based on the Set Function Extension (SFE) paradigm proposed by Karalias et al. (2022). These methods, while unsu- pervised and devoid of iterative decoding mechanisms, leverage SFEs to design loss functions cen- tered on discrete objectives arising from the maximum clique detection task, which involves binary prediction of clique-affiliated nodes. To align this with our clique detection objective, we introduce supervised mean square error (MSE) loss component to their original loss function, treating the predicted clique number as the summation of their predicted set indicator values. This combined loss function aims minimize both the original SFE-based objective and the discrepancy between the predicted and ground truth clique-affiiated nodes. Consequently, we derive four supervised variants of the corresponding baselines: SFE-SUP, NSFE-SUP, Reinforce-SUP, and ST-SUP.
EGN While the original implementation of EGN is unsupervised. we enhance it by providing a supervision signal derived from the ground truth clique number. First, we obtain the node-level heatmap output by EGN for a graph G, which indicates the probability p; of each node partic- ipating in the maximum clique. Then, we add an additional MSE loss term to their objective: (E,p: -G()) During inference, we use the node-level heatmaps to threshold to binary (clique- participation) indicators and then sum them to obtain the predicted clique number as >: [p: 2 0.5]. resulting in the supervised baseline EGN-SUP.
SCT It uses a distinct scattering GCN-based encoder that also outputs a node-level heatmap. This heatmap is subsequently fed into their walk-based decoder. Following similar approach as with EGN, we were able to incorporate supervision by adding an MSE loss term based on the predicted node participation probabilities in the maximum clique. This adaptation results in the supervised baseline SCT-SUP.
Difusco
They employ extreme supervision based on binary indicators of ground truth node-level clique participation. Their model generates multi-modal distribution heatmaps over nodes using either categorical (Difusco (Cat)) or Gaussian (Difusco (Cont)) noise, trained under cross-entropy loss. Subsequently, they use a greedy decoder. For our purposes, we allow them to continue using their extreme supervision pipeline but replace their decoder with thresholding mechanism to obtain the clique number as E, [p: 2 0.5), where pt are the entries of the diffusion denoising output mechanism, normalized to values between O and 1. This approach gives rise to the two baselines Difusco (CP and Difusco (Cont)-SUP.
Comparison of MXNET against all the baselines in terms of MSE. Here, the baselines are modified to be trained under distance supervision. We name each baseline as "baseline-SUP Numbers in green, blue, and yellow indicate the best, second- best, and third-best performers, re- spectively.
Table 11:
IMDB
AIDS-m
PIC-MM-M
DSJC
Brock
Enzymes
RB
MUTAG-m
EGN-SUP SCT-SUP
13,3556
18.9350
10.0589
1. 1,7950
140.4650
43.9916
59.5200
493.0050
265.2037
5638.2300
2536.1388
440.0850
338 338.0600
101,5714
25617.3203
27464.914
Difusco (Cont)-SUP
110.3426
1372.7999
1091.7263
432.9300
313.1450
304,0672
22398.1895
22398.
4736.3198
Difusco (Ca))-UP
16,2870
59,1700
20.8716
10,9500
60.5550
9,9496
142.5900
132.7000
SFE-SUP
4.2222
48.7800
26.5116
12.3950
55.0400
2.0924
76,9500
110.8500
NSFE-SUP
4,3981
34,5100
21.0653
9,6850
47.2650
1.5966
88.5000
89.0150
ST-SUP
5.6111
44,4900
26.6337
5.1850
56.5700
5.5126
147
110.8950
Reinforce-SUP
12.1667
59.1700
37.5221
11,7800
366. 466.5650
1.6639
202.2800
132.7000
MxNET
0.094
0.341
0.179
0.383
10.022
0.196
6.875
0.613
Table 11 compares all these baselines in terms of MSE across eight datasets. We observe that:
(1) MxNET still outperforms all the supervised baselines by a significant margin. This is not sur- prising given that the baselines were not originally designed for the clique prediction task. Instead, they are optimized to provide heatmap-based node ordering, which reduces the amortized solution generation time for their greedy decoder. However, we had no better alternative than attempting the approach described.
(2) EGN-SUP maintains its position "first among equals" by being the second best performer in four out of eight datasets, while NSFE-SUP is second best in three out of eight, and SFE-SUP is second best in the remaining one.
27

---

Published as a conference paper at ICLR 2025
(3) In general, Difusco (Cat)-SUP and Difusco (Cont)-SUP unable match the performance of the other baselines, highlighting their significant dependence on the non-differentiable greedy decoding component.
(4) Reinforce-SUT is the third best performer in the Enzymes dataset and shows reasonable perfor- mance in the remaining datasets, although being behind EGN-SUP and NSFE-SUP.
F.5 ZOOMING IN ON THE RESULTS OF COMPETITORS CLOSEST TO MXNET
Among all baselines, SFE, NSFE, ST Reinforce and NeurSC do not use a decoder and they are end-to-end differentiable. Hence, they closest to our setup. Here focus them in isolation.
Table 12:
Effect of distant supervision on unsupervised non-decoder baselines. Numbers in green indicate best performer overall, while numbers in blue indicate the second-best performer overall, and the better performer among the two variants per baseline.
IMDB
AIDS-m
PMC-MM-m
DSIC
Brock
Enzymes
RB
TAG--M
SFE
4,833
44.340
26,568
12.465
53.595
1630
72.020
110,905
SFE (Supervised)
4.222
44.780
26.512
12.395
55,040
2.092
76,950
110.850
NSFE
3.185
36,005
19,800
5.255
47.920
1.118
78,890
96.445
NSFE (Supervised)
4.398
34.510
21.065
9.6850
47.265
1.597
88,500
89.015
ST
8,972
44.885
26,703
5,410
55,740
5,454
131,230
111.020
ST (Supervised)
5.611
44.490
26.634
5.185
56.570
5.513
147.445
110.895
Reinforce
16.472
59.170
37.455
13.280
403.095
1.731
229.435
132.700
Reinforce (Supervised)
12.167
59.170
37.522
11.780
366.565
1.664
202.280
132.700
MXNET
0,094
0.341
0.179
0.383
10:022
0.196
6.875
0.613
We first look into the effect of supervision on end-to-end differentiable unsupervised baselines.Here NeurSC, being supervised method, is excluded from consideration. In Table 12, we compare the effect of additional supervision loss the performance of these baselines: SFE vs SFE-SUP, NSFE VS NSFE-SUP, Reinforce vs Reinforce-SUP. and ST vs ST-SUP. We observe that:
(1) For SFE, Reinforce, and ST. the supervision leads to a moderate improvement in final clique prediction accuracy in approximately 60% of the cases.
(2) In NSFE, however, the supervision actually causes performance drop in most cases. This suggests that the set function extension pipeline as currently leveraged is not very conducive to effective backpropagation-guicn
training through supervised loss terms.
In the main paper, Table compares MXNET and MxNET (MSS) against all the state-of-the-art baselines, along with the four unsupervised end-to-end differentiable baselines. Due to space con- straints, we were unable to report standard error or timing analysis. In Table 13, we provide the results along with the standard error, with the time in brackets alongside, across all eight datasets. The standard error is computed over the squared error of all graphs in each dataset. Brackets indicate the amortized rumning time per graph in seconds. We observe that:
(1) MXNET maintains significant lead against all four baselines even when standard error is sidered. Additionally, MxNET exhibits significantly lower standard emoor compared to all of the baselines.
(2) terms of amortized run time, all four methods are comparable to, and often 2-3x faster than MXNET. This is due to their avoidance of any greedy decoding heuristic, resulting in extremely low inference time latency. However, despite MxNET being slightly behind them in terms of run-time, it still significantly outperforms them.
F.6 ABLATIONS ON BASELINES AND DECODERS
We thoroughly investigate each of the decoder-reliant baselines to identify the contributions of their neural and decoder- based components to the clique detection and prediction task. The baselines, namely EGN, SCT, Difusco, and GFnet, each employ their own decoder mechanisms, warranting individual examination. Our ablation studies follow this theme:
Increasing the number of parallel samples allowed contrast to Table 1 where each decoder- based baseline could propose only one clique and Table where each decoder-based bascline could propose only one or four cliques, here we empower them to propose up to cliques. We then take the maximum of these eight proposals the predicted clique.
28

---

Published as a conference paper at ICLR 2025
Table 13: Comparison of MXNET against state-of-the-art baselines, which do not use decoder and are end-to-end differentiable, in terms of Mean Squared Error (MSE) with standard error (lower is better). Numbers highlighted in green, blue, and yellow indicate the best, second- best, and third- best performers, respectively. Brackets denote the amortized running time per graph in seconds. Best runtime (lowest inference latency) bolded for each dataset.
IMDB
AIDS-m
PTC-MM-m
DSIC
SFE
4.833 + 1.556 (0.013)
44.340 = 0.853 (0.013)
26,568
0.649 (0.009)
12,465 = 1.803 (0.010)
NSFE
3.185 + 1.394 (0.025)
36.005 = 0.911 (0.046)
19,800 + 0.583 (0.037)
5,255 = 1.048 (0.034)
ST Reinforce
8.972 + 2.545 (0.013)
44.885 = 0.882 (0.014)
26,703 + 0.640 (0.009)
5,410 - 0.991 (0.009)
16.472 + 4.341 (0.012)
59.170 + 1.014 (0.007)
37.455 + 0.797 (0.005)
13.280 + 3.884 (0.007)
MXNET
0.094 1 0.022 (0.029)
0.341 1 0.044 (0.021)
0.179 1 0.013 (0.018)
0,383
0.074 0.074
Brock
Enzymes
RB
MUTAG-m
SFE
53.595 + 6.124 (0.009)
1.630 + 0.210 (0.013)
72,020 = 3.002 (0,024)
110.905 = 2.764 (0.024)
NSFE
47.920 + 5,543 (0.026)
1.118 + 0.170 (0.026)
78.890 = 4.220 (0.066)
96,445 = 2.636 (0.066)
ST
55,740 + 6,363 (0.009)
5,454 + 0.284 (0.013)
131.230 = 6.584 (0.020)
111.020 = 2.769 (0.020)
Reinforce
403.095 37.037 (0.008)
1.731 + 0.142 (0.011)
229.435 = 10,409 (0.008)
132,700 + 3.054 (0.010)
MXNET
10.022 L.185 (0.014)
0.196 + 0.026 (0.023)
6.875 0.604 (0.119)
0.613 = 0.067 (0.134)
Non-neural heuristic version To isolate the impact of the decoder-based components, we design non-neural versions of these baselines. Here, we generate three alternative non-neural heatmaps based on elementary graph statistics: node degree, clustering coefficient, and pagerank. We provide each of these three resultant heatmaps in turn to each of the baseline decoder variants and evaluate their performance. We prefix the names of these non-neural baselines with Heuristic-e.
In the main paper, Table compares MxNET and MXNET (MSS), against all the sfate-of-the art baselines. We were unable to report standard error due to space constraints. In Table 8, we report the results along with the standard error on all eight datasets. The standard error is computed over the squared error over all of the graphs in each dataset.
F. ABLATION ON EGN
Table 14: Performance variation of EGN, across its non neural variants (Heuristic .) and different
number of clique proposal samples used to select the clique. Results in terms of Mean Squared Error (MSE) with standard error (lower is better), along with amortized inference time per graph (in seconds). Numbers highlighted in green, blue, and yellow indicate the best, second-best, and third- best performers, respectively. Brackets denote the amortized running time per graph in seconds. Best runtime (lowest inference latency) bolded for each dataset.
IMDB
AIDS
PMC m
DSIC
EGN
0.102 0.54 (0.117)
0.610 = 0.000 (0. 190)
0.284 + 0.026 (1.149)
0.030 + 0.02 (0.152)
EGN (4x)
0,102 0.054 (0.236)
0.340
0.038 (0.533)
0,183 1 0.019 (0.410)
0.005 1 0.005 (0.525)
EGN (8x)
0.102 - 0.054 (0.351)
0,280 - 0.036 (1.007)
0.141 0 (0.781)
0.000 + 0.000 (0.718)
Heuristic- Degreeee-D
2.824 1,389 (0.146)
3,920 0.2223 (0.221)
2.11 (0.229)
0.820 0.278 (0.149)
Meeuritiic-Degree-FF (4x)
1.806 1.159 (0.227)
3,100 - 0.201 (0.668)
1.827 0.10 (0.518)
0.400 + 0. 179 (0.424)
Heuristic Degree EGN (8x)
0.769 0.750 (0.382)
2,500 0.169 (1.338)
1.554 0.088 (0.931)
0.215 1 0.134 (0.944)
Crnistti-CussterCoef--FOO0
3.750
0.787 (0.079)
1,500 - 0.139 (0. 198)
0.861 + 0.074 (0.159)
5. 5.490 + 1.680 (0. 138)
Heuristic ClusterCoeff EGN (4x)
0.222
0.069 (0.137)
0.965 0.101 (0.662)
0.497 0.048 (0.493)
0.395 1 0.322 (0.355)
SrtisttiCCuusserCoo---GGC (8x)
0.065 0.040 (0.271)
0.675 - 0.079 (0.939)
0.366 1: 0.038 (0.698)
0.035 1 0.022 (0.668)
Heuristic PageRank- EGN
4.806 1.094 (0.1 (16
3.515 0.212 (0.295)
2.596 0.140 (0.184)
0. 960 1 0.304 (0.167)
Heuristic-PP Meuristii-PagoRRnnk- Pag (4x)
2.139
0.898 (0.257)
2.755 - 0.190 (0.672)
2,080 0.120 (0.491)
0.490 1 0.204 (0.418)
Heuristic-PageRan PageRank-GGGNN (8K)
0.778
0,750 (0.376)
2,100
0.155 (1,224)
1.676 0.096 (0.942)
0. 0,265 = 0,141 (0.735)
MXNET
0.094
0.022 (0.029)
0,341
0.144 (0.021)
0.179 + 0.013 (6.018)
O. 0.383 0.074 (0.014)
Brock
Enzymes
RB
MUTAG-m
EGN
1310 0.453 (0.151)
0.109
1 0.041 (0.087)
15.615
1.738 (0.201)
1.10 0.101 (0.473)
EGN (IK)
0.315 0.079 (0.462)
0.042 0.018 (0.150)
12.635 + 1.620 (0.529)
0.665 : 0.085 (1.480)
EGN (8x)
0.175 0.050 (0.977)
0.034 0.017 (0.173)
9.645 + 1,380 (1.003)
0.555 = 0.080 (2.712)
Heuristie-Deer Degree-BNN
7.580
1.820 (0.157)
0.412 0.055 (0.080)
47.700 1 3.372 (0.309)
9.320 0.412 (0.686)
Daarrstti--Drree-BNNN (4x)
6.405
1.637 (0.435)
0,227 + 0.039 (0.129)
40.070 + 2.904 (0.837)
7,990 = 0,374 (2.117)
Denritii-Degee-EGNNN (8k)
4.375
1.152 (0.792)
0,101 + 0.028 (0.189)
33.135 + 2.632 (8.66)
7.245 0,363 (4.053)
Heuristic- ClusterCCoeff.FCC EGN
14.900
6.377 (0.151)
0.143
(0.069)
61,270 2.933 (0.198)
0,289 10))
Heuristic Heeumstee-ClustteCoofff ClusterCofff-ECC (4x)
2.315 1 0.497 (0.380)
0.067 0.023 (0.135)
57.705 1 2.986 (0.281)
3.295 1: 0,246 (2.265)
Coatio-CCSSsteofo-CECCCC (8x)
1.360 0.394 (0.715)
0.034 0.017 (0.196)
(0.425)
2.875 0.220 (3.647)
Paariste-PagRRaak-EGN
7.030 = 1.741 (0.163)
0.588 + 0.074 (0.102)
48. 48.200
+ 3.438 (0. (0.256)
7.320 = 0.367 (0.957)
Heuristic- PageRank-FRR (4x)
6.215 1.646 (0.422)
0,202 + 0.037 (0.127)
39.665 2.853 (0.673)
6.670 0.348 (2.307)
Heuristic HleuristiePaagRRank EGN (8x)
3.725 0.880(1.03) (1.031)
0.118 1 0.030 (0.245)
33,525 1 2.659 (1.213)
6. 6.095 1 0,331 (4.261)
MXNET
10.022 # 1,185 (0.014)
0.196 + 0.026 (0.023)
6.875 + 0.604 (0.119)
0.613 = 0.067 (0.134)
In Table 14, we present the results of our ablation study in terms of Mean Squared Error (MSE) with standard error, along with per-graph amortized run-time in brackets. We evaluate three vari- ants of the original baseline EGN with multiple samples: namely EGN, EGN (4x), and EGN (8x). Additionally, we examine three non-neural heuristic baselines based on node degree, clustering co-
29

---

Published as a conference paper at ICLR 2025
efficient, and PageRank, each of which is allowed one, four, eight samples. In the last row, report the results for MXNET. We observe that:
(1) EGN shows significant improvement as the number of samples increases, with a 2-3x reduction in MSE in most cases. Notably, in Brock, there is 8x improvement with the increase in samples.
(2) The performance improvement in EGN comes at the cost of increased inference time. For in- stance, in MUTAG-m. EGN (8x) results in almost 20X higher latency compared to MXNET, while providing only around a 50% improvement in MSE.
(3) The heuristic-driven baselines generally perform worse than their neural counterparts, highlight- ing the relative effectiveness of neural learning procedures.
(4) Although the neural baselines show slightly worse average MSE than the neural variants with decoders, they significantly outperform the decoder-fiee free baselines. This underscores the significant enhancement in prediction accuracy achieved by using decoders, despite their non-differentiable nature.
F.6.2 ABLATION ON SCT
Table 15: Performance variation of SCT, across its non neural variants (Heuristic .) and different number of clique proposal samples used select the clique. Results in terms of Mean Squared Error (MSE) with standard error (lower is better), along with amortized inference time per graph (in seconds). Numbers highlighted in green, blue, and yellow indicate the best, second-best, and third- best performers, respectively. Brackets denote the amortized running time per graph in seconds.
Best runtime (lowest inference latency) bolded for each dataset.
IMDB
AIDS m
PTC
DSIC
SCT
0.810 (1.05T)
3,865
0.278 (0.117)
1.002
0.109
(0.019)
92.675 + 8.394 (11019))
SCT (4x)
0.259 1 0.077 (0.048)
1.685
0.146 (0.081)
0.701
0.058 (0.063)
37.415 1 4.525 (0.052)
(8x)
0.046 (0.059)
1,070
(0.095)
0.406
0.037 (0. 102)
18,280 + 2.676 (0.076)
Seuristie-Degreo-S
3,287 + 1.410 (0.000)
3,885 0.220 (0.008)
2,000 = 0.125 (0.003)
1,025 + 0.312 (0.003)
Deuristic-Degree-SS (4x)
1.944
(0.005)
(0.023)
0.088 (0.022)
0,515 0.
(0.013)
Heuristic Degree SCT (8x)
0.630 1 0.177 (0.010)
1,935 1 0.144 (0.055)
1.291 0,075 (0.046)
0,365 1 0.150 (0.027)
MeuuistieCClssterCCee
10.556 5,070
1,545
(0.030)
0 (0.016)
5,490 1 1.680
Heuristie-Clustee Caaati--ChusstrCCoftSSCCCC (4x)
0.250 + 0. 100 (0.007)
0.885 = 0.093 (0.045)
0.480
0.049 (0.030)
0.425 + 0.322 (0.019)
Heuristic- CCusterrCoetT:SCC (8k)
0.013 (0.012)
(0.076)
0.364
0.037 (0.046)
0,185 1 0.088 (0:025)
SaaristiePagcRank--- (4x)
4.806 + 1.:::11000 1.094 (0.004)
3,390 = 0. 208 (0.012)
2.602
0.141 (0.010)
0,960 + 0 0.304 (0.006)
1.028 0.261 (0.008)
2.310 0.168 (0.026)
1.785 0.098 (0.028)
0.470 + 0. 181 (0.015)
Heuristic PageRunk-SCC SCT (8x)
0.843 1. 0.197 (0.013)
1,845 0.145 (0.058)
1.413 0.075 (0.046)
0.315 1 0.144 (0.027)
MXNET
0.094 (0.029)
0,341 = 0.044 (0.021)
0.179 = 0.013 (0.018)
0,383 + 0.074 (0.014)
Brock
Eazymes
RB
MLL
SCT
35,885 = 5,868 (0.037)
0.891 0.124 (0:035)
50,230 +.2230333.443 (0.064)
11. 105 0 (0.088)
SCT (4x)
12.070 + 2.144 (0.052)
0.277 + 0.051 (0.055)
44.040 + 2.875 (0. 156)
6.830 + 0.558 (0.241)
SCT (8x)
8.055 1.452 (0.074)
0.202 0.047 (0.071)
39.615 2.716 (0.278)
5.040
0.450 (0.395)
Neuristi-Deggee DeT
6:00= = 1.648 (0.004)
0.513 + 0.068 (0.002)
10, + 3.309 (0.017)
9.125 + 0.392 (0.040)
lleuristi--Degree.S SCT (4x)
5.280 1 1.438 (0.013)
0.176 1 0.035 (0.007)
37,820 2,899 (0.089)
7.640 0.357 (0.147)
HleuristceDegrree SCT (8x)
3.145 :: 0.802 (0.020)
0.143 1 0.032 (0.014)
31.565 2.767 (0.139)
7.020 :: 0,334 (0.292)
Ceariitic-Cluster CCT
20.340 = 8.738 (0.009)
0.134 = 0.031 (0.003)
62,950 + 2,998 (0.055)
4.930 0.310 (0.544)
Heuristic-Chuun ClusterCooff-SCCC (4x)
2:200 = 0.496 (0.017)
0.067 + 0.023 (0.008)
56, 3.18 (0.1
3,250 + 0.244 (0 (0.648)
Heuristic ClusterCoeffSSCC (8x)
1.755 + 0.431 (0.031)
0,017 : 0.012 (0.018)
52,550
3. 141 (0.201)
2.750 +: 0,207 (0.793)
Heuristic PugeRRnkk SCT
7.030 1.741 (0.006)
0.588 0.074
48,200
(0.032)
7,250 0.370 (0.133)
Heuristic-Pagee PugoRank-SCT (1x)
4.545 = 1.129 (0.016)
0,151 = 0.033 (0.010)
37.485
2.755 (0.095)
6.535 = 0,351 (0.239)
Reuristic-PggRankke (8x)
3,190 0.770 (0.028)
0,101 0.028 (0:017)
313315 2.588 (66)
5.775
0,317 (0.390)
MXNET
1,185 (0.014)
0.196 0.026 (0.023)
0.604 (0.119)
0.613 0.067 (0.134)
In Table 15, we present the results of our ablation study in terms of Mean Squared Error (MSE) with standard error, along with per-graph amortized run-time in brackets. We evaluate three variants of the original baseline SCT with multiple samples: namely SCT, SCT (4x), and SCT (8x). Addition- ally, we examine three non-neural heuristic baselines based on node degree, clustering coefficient, and PageRank, each of which is allowed one, four, or eight samples. In the last row, we report the results for MxNET. We observe that:
(1) SCT demonstrates significant performance improvement with an increase in the number of sam- ples. In most cases, performance improves approximately 2x when going from one to four samples, and the improvement is even more pronounced with eight samples. Notably, in IMDB, the improve- ment from one to eight samples is almost 10x.
(2) In general, the inference time latency for SCT is very low, being almost comparable to MXNET for one sample.
30

---

Published as a conference paper at ICLR 2025
(3) Generally, the performance of SCT is significantly worse than that of MXNET, except in cases where eight samples are used. Even then, notably in larger graphs like RB and MUTAG-m, the performance of SCT with eight samples is still around 5-10x lower than MXNET.
(4) Remarkably, non-neural heuristics in the SCT decoder, particularly when allowed eight samples along with the clustering coefficient heuristic, perform exceptionally well. This highlights the sub- stantial power of the SCT decoder, which is almost comparable to its neural variant across most datasets.
F.6.3 ABLATION ON DIFUSCO
In Table 16, we present the results of our ablation study in terms of Mean Squared Error (MSE) with standard error, along with per-graph amortized run-time brackets. We evaluate three variants of the original baselines Difusco (Cat) and Difusco (Cont) with multiple samples: namely Difusco (Cat), Difusco (Cont), Difusco (Cat) (4x), Difusco (Cont) (4x), Difusco (Cat) (8x) and Difusco (Cat) (8x). Additionally, we examine three non-neural heuristic baselines based node degree, clustering coefficient, and PageRank. It's s important to note that a key aspeet of Difusco is that the randomness in the sampling procedure arises from the diffusion noise generation process. The greedy decoder used by Difusco is deterministic and does not allow for multiple samples. Therefore, unlike other baselines, every non-neural heuristic has only one set of observations based on single sample. In the last row, we report the results for MXNET.
Table 16: Performance variation of Difusco (Cat) and Difusco (Cont), across its non neural variants (Heuristic- e) and different number of clique proposal samples used to select the clique. Results in terms of Mean Squared Error (MSE) with standard error (lower is better), along with amortized inference time per graph (in seconds). Numbers highlighted in green, blue, and yellow indicate the best, second-best, and third-best performers, respectively. Brackets denote the amortized running time per graph in seconds. Best runtime (lowest inference latency) bolded for each dataset.
IMDB
AID88 m
PTC.MM-m
DSIC
Difusco (Cat)
[361 1 0,510 (0.789)
4,170 0.288 (0.705)
2.244 0,129 (0.690)
1.560 1 0.473 (0.686)
Difusco (Cat)
0.231
(0.722)
1.865 0.145 (0.837)
0.979 :: 0.066 (0.799)
0.094 (0.771)
Difuseo (Car) (8x)
0,185 a: 0.149 (0.766)
1.345 0.117 (1.006)
0.644 1: 0.047 (0.923)
0.045 0.023 (D.862)
Difusco (Cor)
5,333 +: (0.744) (0.745)
4.665 0.2777 (0.57)
2.621 + 0.139 (0.634)
59,820
6.776 (0.646)
Difusco (Com) (4X)
0.120 = 0.055 (0.798)
1,830 0.131 (0.782)
1,133 0.072 (0:772)
8,220 + 1.573 (0.713)
Difusco (Corr (8x)
0.000 + (.0001) (0.711)
1,345 +-0.007 (0.942)
0.205 + 0.049 (0.883)
2,605 + 0.546 822)
Heuristic Degree- Difuseo (Cat)
2.741 1,385 (0.011)
0.24 (0.056)
2,703 0.133 (0:047)
0.258 (00022)
Heuristie-Clue ClusterCoell- Difus-o (Cat)
12.370 = 6.667 (0.012)
1.495 1: 0.13 (0.077)
0.931 + 0.079 (0.045)
5.490 : 1,680 (0.029)
HeuristicPaagee Paassss--PaaRaa-ifffiiia (Cal)
4,806 1.094 (0.017)
3.455 0.211 (0.061)
2.617 + 0.141 (0:037)
96060
0.304 (0:024)
MXNET
0.094 0.022 (0.029)
0.044
(0.021)
0.179 +: 0,013 (0.018)
0,074 (0,014)
Brock
Enzynes
RBB
MU MUTAG-
Difusco (Ca))
10.395 = 2.384 (0.756)
0.950 : 0.103 (0.789)
55.630 4.118
10:363
0.598 (0.827)
Difusco (Cat) (4x)
4,820 + 1 4.400 (0.746)
0.311 0.059 (0.718)
28.595
2.690 (1 .000)
6.095
0.321 (2.193)
Difusco (Ca) (8X)
0.726 (0.846)
0.033 (0.782)
(3.970)
Difusco (Com)
39.040 = 12.402 (0.759)
1.044 0.13 (0.637)
63,490
4.258 (0.792)
10,590 :: 0.610 (0.780)
Difusco (Con)) (1X)
10.185 + 3.823 (0.719)
0,286 0.051 (0.814)
36.150
3.063 (1.030)
3.965 0,501 (2.097)
Difusco (Com) (8K)
7,355 + 4.001 (0.954)
0.118 + 0.030 (0.763)
14,555 = 1.787 (1 603)
(003))
3,245 0.275 (4.271)
Heurisic- Degree- Dilisen (Cai)
6,855 + 1.723 (0.021)
0.005 + 01089 (0.016)
48,555 + 1.418 (0.019)
9.490 + 0.440 (6.110)
Heuristic-Cluse Caaissii-Cusstcrof----iiiii
(Cal)
20.520 : 8.762 (0.036)
0.032 (0.017)
42,960
3.001 (0.152)
4,805
(0.615)
Heuristic-PageRank PageRank-Diffssc Difusco (Cat)
7,030 4: 1.741 (0.025)
0.588 1: 0.074 (0.026)
48,200
2 3.438 (0.148)
7,200 0.363 (0.203)
MXNET
10.022 1 1.185 (0.014)
0.196 1 0.026 (0.023)
6,875
0.604 (0.119)
0.613 0.067 (0.134)
We observe that:
(1) Difusco (Cat) generally performs better than Difusco (Cont) across the board. This demonstrates that Difusco (Cat)'s Bernoulli noise generation process is most suitable for the task of predicting discrete labels indicating node participation in maximum clique, confirming claims made by the original authors (Sun & Yang, 2024). (2) Like other decoder-based baselines, both Difusco (Cat) and Difusco (Cont) exhibit significant performance improvements when more samples are allowed. In IMDB, Difusco (Cat) achieves an MSE of zero without a substantial increase in inference time latency.
(3) The increase in inference time latency from one to four to eight samples is not as significant for Difusco (Cat) and Difusco (Cont) compared other decoder-based baselines. This is attributed to the greedy deterministic nature of the decoder, which does not introduce large overhead relative to the entire pipeline.
(4) However, the average inference time latency of both Difusco (Cat) and Difusco (Cont) is signif- icantly worse than both other baselines and MXNET. This is due to the costly noise generation and denoising steps undertaken by Difusco.
31

---

Published as a conference paper at ICLR 2025
(5) Overall, MXNET outperforms both Difusco (Cat) and Difusco (Cont) in most datasets while maintaining significantly lower inference latency. Notably, in MUTAG-m, one of the larger datasets, MxNET's ' MSE performance is almost 4x better than Difusco's best, while being almost 20X faster at the same time.
(6) The non-neural heuristic baselines of Difusco can perform significantly better (c.g., in DSJC) or significantly worse (e.g., in IMDB) than Difusco's best. In general, the neural variants tend to outperform the non-neural ones, providing confidence in the effectiveness of the neural approach.
F.6.4 ABLATION ON GENET
In Table 17, we present the results of our ablation study in terms of Mean Squared Error (MSE) with standard error, along with per-graph amortized run-time in brackets. We evaluate three variants of the original baseline GFnet with multiple samples: namely GFnet, GFnet (4x), and GFnet (8x). Additionally, we examine three non-neural heuristic baselines based on node degree, clustering coefficient, and PageRank, each tested with one, four, or eight samples. GFnet is a reinforcement learning-basse based method where actions are sampled from a learned policy, with samples drawn from multinomial distributions over logits. For non-neural baselines, we replace the logits with graph statistic-based heatmaps. In the last row, we report the results for MXNET
Table 17: Performance variation of GFnet, across its non neural variants (Heuristic - .) and different number of clique proposal samples used to select the clique. Results in terms of Mean Squared Error (MSE) with standard error (lower is better), along with amortized inference time per graph (in seconds). Numbers highlighted in green, blue, and yellow indicate the best, second-best, and third- best performers, respectively. Brackets denote the amortized running time per graph in seconds. Best runtime (lowest inference latency) bolded for each dataset.
IMDB
AID8-m m
PTC.MM-1
DSJC
Genet GFnet (4x)
0.75 (0.032)
0.740 0.085 (0.017)
0.54 = 0.045 (0.011)
4.820 1,388 (0.034)
0.167 1: 0.066 (0.081)
0,210 0.034 (0.054)
0.166 = 0.017 (0.035)
0,175 2:75:100 0.080 (0.109)
GFnet (8K)
0.016
0.125 = 0.023 (0. 100)
0.067 = 0.012 (0.068)
0,080 0.050 (0.206)
Denriati--egree-Giint
2.333+ 1.351 (0.018)
3,66 + (0.230)
2.623 + 0.130 (0.027)
1.170 0.351 (0.032)
Heuristic Degree- Gl'net (4x)
0.213 0.153 (0.053)
2,070 1 0,141 (0. (0.144)
1,539 1: 0.086 (0.095)
0.175 0.072 (0.133)
Ceuristte-Degree-CCC Danet (8x)
0.806 0.750 (0.098)
1,600 1:10=0..1100 (0.281)
1.105 0.069 (0.189)
0,175 + 0.080 (0.243)
Heuristic- ChisterCoeff-CC GFaet
8.759 1 4.564 (0.014)
4.690 0.274 (0.059)
2.817 0.163 (0.034)
134,200 # 10.512 (0.034)
Heuristic ClusterCoel-- Glaett (4x)
0.361 0.133
0.140 (0.234)
(0.143)
29,815 3,700
Heuristic- Chusterr Coeff-GPas GFnet (8x)
0.083 0.042 (0.087)
1,280 0.101 (0.456)
0.731 0.050 (0.283)
11,290 + 1.921 (0.241)
Heuristic PugeRank, GUnnt
16.213 6.751 (0.018)
4,710 0.285 (0.040)
2.646 0.136 (0.028)
144.875 11.211 (0.028)
HcuristiePaaeeRe Page-aak-- GFnet (dx)
0.343 0.133 (0.064)
1970
0.141 (0.159)
1,248 = 0.080 (0.107)
38.695 1 4.577 (0.103)
Heuristec PageRank. GigeRank-Gunett (8x)
0.083 1: 0.042 (0.107)
1,300 0.105 (0.312)
0.718
0.053 (0,202)
11.165 1.908 (0.19)
MXNET
0.094 0.02 (0.029)
0.341 0.644
(0:021)
0.179 :: 0.013 (0.018)
0,383 + 0.074 (0.014)
Brock
Engymes
RB
MUTAG-M
GFnet
8.95 1.574 (0.040)
0.857
0.093 (0.016)
34,200 = 2.989 (0.029)
0.208 (0.070)
GPnet (4x)
3.625 + 1.157 (0. 148)
0.193 0.036 (0.032)
21.675 + 2.178 (0. (0.1
1O05 + 0.100 (0 290)
GFnet (8%)
1.125 = 0.328 (0.289)
0.050
0.020 (0.059)
17.745 : 2,060 (0.203)
0.610 = 0.072 (0.578)
9.545 1: 2.11 (0.036)
0.706 0.083 (0,009)
49.065 1: 3.533 (0.068)
8.690 1: 0.382 (0.256)
Heuristic- Heuristic-Degree- GFnet (4x)
Degree-GFnet
3.110 + 0.822 (0.141)
0.227 0.039 (0.027)
39.565 + 2.963 (0.273)
6.580 0.325 (1.012
Heuristic- Degree Gl'net (8x)
2.985
(0.282)
0.028 (0.048)
37.150 2,802 (0.503)
0.285 (2.020)
Heuristie-Clusee ClustcrCodl--GPPee GFact
85.215 +: 13.559 (0.045)
0.697 2 0.088 (0.009)
83.235 : 4.779 (0.104)
11,995 : 0.577 (0.763)
Heuristic ClusterCoeff- Gl'net (4x)
16.080 1. 3.083 (0.150)
0.244 0.049 (0.028)
43.050 3.504 (0.392)
7,180 0.379 (3.014)
Heuristie-lluse ClusterrColll-GGFe GFae (8x)
4.720 = 0.876 (0.305)
0.160 0.045 (0.055)
31.055 : 2.860 (0.811)
5.355 1 0.282 (6.022)
Heuriste-PagcRani PageRank--Fiet
94.455 + 12.817 (0.036)
0,840 = 0.098 (0.012)
80.715 + 4,718 (0.073)
12,290 0,604 (0.339)
Heuristic- PugeRank- GFnet
(0.134)
0.079 (0.036)
47.680 3.746 (0.285)
6.865 0.385 (1.311)
HeuristicPPagcRe Matile--PPggaak--GGaaaa (8x)
6.110 = 368 (0.272)
0.143 + 0.052 (0.073)
29.160 + 2,806 (0.549)
4,770 + 0.262 (2.671)
MxNET
10,022 # L,885 (0.014)
0.196 2 0.026 (0.023)
6,875 = 0.604
0.613 : 0.067 (0.134)
Key observations include:
(1) Like earlier decoder-based methods, GFnet shows significant performance boosts with more samples. In most datasets, performance at least doubles, with the most notable improvement in DSJC, showing almost 10x increase.
(2) The performance improvement coincides with increased inference latency. With one sample, GFnet is either comparable to or faster than MxNET. However, with eight samples, GFnet becomes significantly slower than MxNET in most cases.
(3) The non-neural variants of GFnet show similar MSE performance vs. inference time latency trade-offs. Among these, the node-degree heuristic performs best, sometimes ranking second over- all.
(4) GFnet with eight samples often outperforms MxNET significantly. However, the inference time for GFnet is much higher. This highlights the trade-off between prediction accuracy and latency,
32

---

Published as a conference paper at ICLR 2025
with decoder-basee models iteratively deciding node inclusion in clique for clique number predic- tion, compared to a direct prediction neural network like MXNET.
F.7 ABLATION STUDY
(1) Benefits of relaxing binary adjacency matrix to continuous values: In the following, we show the results of ablation study.
Table 18: Effects of relaxing binary adjacency matrix to continuous values
IMDB
PTC-MM-m
DSIC
MXNET
0.094
0.179
0.383
Binary A in MXNET
86.231
2.364
0.470
We observe that smooth surrogate works better. We believe that there are two reasons behind this:
(i) CLIQUE is a classical to-pppooximate problem in the worst case, so the promise of neural methods is take advantage of distributions from which graphs generated in application. A natural way toward this goal is to train node representations I, that simultaneously predict the graph A (via generic GNN that aligns v. F. 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 and v. they share the same k node neighborhood. leading to a high x._ F. value.
(ii In MXNET (MSS), the goal is to find node permutation S that brings all Is in SAST 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 SAST, making it difficult to detect the MSS. Various thresholds nonlinearities may reduce the problem, but also attenuate gradient signals when x By is very high or very low. Thus, x Dg scores serve as auxiliary signals for clique detection, but simply adding them to A contributes much noise in the estimate of w. In contrast, the form S(A @ XX S is better at absorbing the signal from Tu without succumbing to its noise.
(iii) As a further mechanistic discussion, suppose, instead of A + XXT, we use A. Then, for each parameter 0 I. the gradient term contains SA AST ds AST. Here S contains soft-max-
alike-terms and therefore, ds will have terms such as S Slu, u u'|S U v/J. Thus, SA TST
de consists of
de terms of the form S(u, u²) (11 v/) S[]S( w²), with each S S(e.0) E [0, 1]. This leads to attenuation of gradient signals. If we keep A ④ XXT, then the gradient will have S(u, [/u,,'SSpp ((,
[xx d0 u,aa
which will allow more significant gradient signals. Moreover, due to continuous adjacency en- tries, Slu, u L/t W w'] will now be replaced with Slu, S'), v']S[w w') X [u", xi [o", [.]. where Xs can control the gradient signals better, leading to actual learning of clique number com- putation for a distribution over graphs.
(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 SW 5 involves general values in (0, 1) from S and +ve/-ve from W. which makes the entries of B(ū,.j] to be +ve/-ve real numbers. Further, multiplication by Bii [] in line 7 in Algorithm I compounds this issue. To reduce these deleterious effects of fractional numbers on clique detection, several thresholding/ 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 thresholing, 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, 2). 1)) against the results of MSS with the GNN-based Algorithm 1 implementation variant across three representative datasets of varying sizes: Enzymes, PTC-MM-m, and DSJC on average.
Table 19: Ablation of message passing GNN for Algorithm 1
IMDB
PTC-MM-m
DSIC
MxNET
0.094
0.179
0.383
No GNN in Algorithm 1
1.970
0.254
0.997
We observe that using a GNN based implementation for Algorithm 1 affords a performance im- provement across all datasets.
33

---

Published as a conference paper at ICLR 2025
(3) Relaxing clique coverage loss in MXNET: minp|K. PAPP is quadratic assignment problem (QAP), which is a hard problem to solve. Moreover, the binary values of A and K. attenuate the gradient signals described in the last para of item (1) above. We overcome the above challenges by replacing min p K. P PAPT]+ ]+ with [Q, - SSX Instead of solving QAP, it solves linear assignment problem, which is more tractable; and allows substantial gradient signals.
Table 20: Effect of relaxing coverage loss in MxNET (SubMatch)
IMDB
PTC-MM-m
DSJC
MXNET
0.094
0.179
0.383
Hard Clique Loss
0.540
0.371
0.566
We present our results as follows, which shows smooth surrogate performs better.
F.8 PERFORMANCE ON LARGE GRAPHS
There are two reasons why our primary focus was not on large graphs in the initial version. However, have stress-tested our method with additional experiments, as described later.
(1) Our goal is to design 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 (Hastad, 1996; Zuckerman, 2006), 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 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 G into overlapping subgraphs Gi..., GN each with moderate sizes. Then, the clique number of G is estimated as max; (G+). This decomposition is helpful because (I) 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 clique straddling multiple subgraphs can be reduced via various degree based or K-core decomposition based heuristics.
Here, we worked with Amazon and email-Enron datasets. Amazon has 334,863 nodes and 925,872 edges. Amail-Enron has 36,692 nodes and 183,831 edges. The table below shows the true and predicted clique numbers.
Table 21: Results on large dataset
Dataset
True clique number Predicted clique number
Amazon
7
6
Email-enron
20
19
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 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; w(2) = arg max; (G.); (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.
34

---

Published as a conference paper at ICLR 2025
If the number of nodes VV is large, the entries of doubly stochastic matrix S become more diffused. For the same temperature, the highest value each row/column of S becomes smaller as we in- crease |V]. Hence, to be interpretable. Further, we can use reparameterization of weight matrices (Zhai et al., 2023) in Sinkhorn network using spectral norm based scaling to facililate training in large graph training.
decrease the temperature to ensure that S has sufficiently low entropy
F.9 ROBUSTNESS WITH RESPECT TO À
Our experiments show that the proposed method is robust lambda, as shown below.
Table 22: Variation of MSE with À for PTC-MM-m
0.221 0.283 0.172 0.179 0.163 0.402 1.456
F.10 FULL CURRICULUM TERMS vs. CURRICULUM LEARNING WITH FEWER TERMS
We performed experiments where in Eq. (9), limited the first inner summation to only w and the second summation to only c = (G) - 1. The following results show that summation from 2 to (G) shows better result.
Table 23: Full curriculum terms vs. curriculum learning with fewer terms
IMDB
PTC-MM-m
DSJC
MxNET MXNET (ew--Curiculumm)
0.094
0.179
0.383
0.109
0.417
0.490
This is because, summation from 2 to (G)) is providing more explicit guidance to the learner that, Ke are subgraphs of G. Otherwise, it is unable to reason that if K is subgraph of G then also K2,.,, are also subgraphs of G.
F.11 COMPARISON WITH COMBINATORIAL METHIOSS
Here, we discuss several combinatorial methods used as baselines and compare their performance against MXNET.
Fast Local Subgraph Counting (SCOPE) SCOPE, proposed by (Li & Yu, 2024b) is tree- decomposition- method for local subgraph counting. It estimates the occurrence a given query graph in the local neighborhood of each node within the corpus graph and provides 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 non-zero count is deemed the predicted clique number.
It is important note that SCOPE addresses significantly more challenging task: estimating the count of patterns each local neighborhood. As such, it naturally requires substantially more computational time compared MXNET and earlier global subgraph counting methods. For each query-corpus graph pair provided to SCOPE, we set timeout from the range [0.1, 1, 10, 100] seconds. If the timeout elapses without returning a result, we assume that cliques were detected, and the clique number is determined accordingly.
Table 24: Comparison of SCOPE and MxNET across datasets (in terms of MSE) and timeout set- tings (in seconds). Numbers highlighted in green, and blue, indicate the best and second-best per- formers, respectively.
Timeout
IM13
AIb8-m
PIC-MM-0
DSIC
Brock
Enzymes
MUTAGG-1
42.620
6.140
1486
274.335
545
0.613
185,525
66.565
25.000
0,005
0.000
226.165
469.120
0.000
81.975
50.255
TO
23.148
0.005
0.000
217.180
430.150
0.000
81.160
32.175
100
20.093
0,000
0.000
192.615
398.050
0.000
68.040
12.515
MXNET
0.094
(0.029 sec)
(0.021 soc)
0.341
(0.018 sec)
0.179
(0.014 sec)
0.383
(0.014 sec)
10.022
(0,023 sec)
(0.119 sec)
(0.134 sec)
0.613
We observe that MXNET significantly outperforms SCOPE across all datasets when SCOPE is lim- ited to per-graph time of 0.1 seconds, which is comparable to the highest inference time taken
35

---

Published as a conference paper at ICLR 2025
by MXNET. Furthermore, SCOPE's MSE consistently improves as it is afforded more computa- tional 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 substantial increase in inference imeeeexceding 50x compared to MxNET.
Additionally, on several datasets, including IMDB-m, DSJC, Brock, RB, and MUTAG-m, SCOPE unable to outperform MXNET even when given up 100 seconds per graph, while MxNET achieves superior accuracy at a fraction of the computational cost. This behavior is expected, as SCOPE tackles more challenging task of local subgraph counting, a level of granularity that 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.
Scaling Up k-Clique Densest Subgraph Detection (SCTL) (He et al., 2023b) proposes SCTL to address the k-clique densest subgraph problem. To use SCTL for clique number detection, initially employed the same protocol as MXNET, SCOPE, and NeurSC k from 2 to (G)) However, found that when k is smaller than w (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 far from the millisecond-lews inference times achieved by MXNET and other baselines.
incrementally increasing
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 & until clique 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.
Comparison with upper and lower bounds w (G) We present results different bound based methods as follows. We consider the best of the lower bounds and upper bounds as presented by the paper in terms of MSE, and present them here:
Table 25: Comparison with upper and lower bounds on (G)
Enzymes
PTC-MM-m
RB
MXNET
0.196
0.179
6.875
Best Upper-Bound (UB) (Budinich, 2003, Eq. 1,2,3,4)
1.756
637.70
532.530
Best Lower-Bound (LB) (Budinich, 2003, Eq. 5,6,7)
3.429
15.101
253,800
In partieular, the bounds are:
1. (UB) Eq. w(G) 3+ -
2. Let p(G) denote the spectral radius of the adjacency matrix A of G. Then,
(UB) Eq. 2: w(G) S p(G) +1
VI denote the eigenvalues of A. Then 3. Let N-1 = HA A < -1 where {A
(UB) Eq. w(G) NN1+1
4. Let A denote the adjacency matrix of the complementary graph of G. Then,
(UB) Eq. ((G V sak((A)
2
5. (LB) Eq. S: w(G)
1V12
6. Let Ap denote the Perron eigenvalue of A, and up denote the corresponding eigenvector.
Then, (LB) Eq. 6: w(G)= (I (1'pp"=>> +1
Ap
7. Let Xy denote an eigenvalue of A, and By denote the corresponding eigenvector. Define a² (1=
9 (a) a(1 (11
For each j. g (a) is defined on
max 3
UPi
min B
UPC
Then, for
1/ + Dj
<D
Upp:
2 + 0²
graphs which are not regular complete multiparitt, (LB) Eq. 7: ((G)= 2
I-max,, (0
36


Reviews:
[{"review_id": "KawHnDoUE8", "reviewer": "Reviewer_7fYN", "summary": "In this submission, the authors propose a differentiable solution to the clique number estimation problem. In particular, they formulate the maximum clique problem (MCP) as a maximization of the size of a fully dense square submatrix within a suitably row-column-permuted adjacency matrix. \nThis problem can be further treated as a sequence of subgraph matching tasks, and the cliques can be progressively detected, leading to a fully differentiable neural network called MxNet. Experiments show that the proposed method outperforms baselines in most situations, which is more robust to the OOD issue.", "questions": "Please see above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is significant for many applications.\n2. The proposed method is reasonable, and the re-formulation of MCP is insightful.\n3. The experiments are solid and sufficient. Analytic experiments such as ablation studies are provided.", "weaknesses": "1. The writing and organization of the proposed method are not friendly to readers without sufficient background. In the introduction section, adding a figure illustrating the task may help readers quickly grasp the key concepts of the paper. Similarly, in Figure 1, binding notations like MSS(B) and rho_theta to the modules in the figure is necessary.  \n2. The motivation and rationale behind certain modeling strategies are not clearly explained. For instance, in Figure 1, what is the purpose of using a smooth surrogate for the adjacency matrix? Is there an ablation study that supports this approach? Additionally, the effects of the bicriteria early stopping strategy have not been verified.\n3. The scalability of the proposed method for large graphs has not been verified. In particular, the Sinkhorn network often experiences numerical instability when dealing with very large graphs. What approaches can be taken to mitigate this issue? Additionally, how should the temperature of the Gumbel-softmax be set within the network?\n4. The lambda balances the two terms in the loss function, is the proposed method robust to this hyperparameter?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "MvuVMz45Ul", "reviewer": "Reviewer_GJPR", "summary": "In this work, the authors present a method for learning the maximum clique size in graphs by parameterizing node permutations using neural networks and training them with a composition of two types of losses, maximal subsquare (MSS) and SubMatch. Combined with techniques including various neural relaxations, curriculum training and bi-criteria early stopping, the model is able to learn to predict maximum clique size better than or close to the best among a number of baseline methods on several benchmark datasets.", "questions": "1. In Section 3.1, the authors proposed a differentiable approximation of the combinatorial MCP by relaxing the discrete objective in three fronts, and I am curious if there is evidence or to believe that the first (relaxing the adjacency matrix to be continuously-valued embeddings) and the third (replacing Algorithm 1 by a message passing GNN) are necessary / beneficial in the case of featureless graphs. Without them, it seems that the model can still be trained via a differentiable loss function and the model might actual be more interpretable. A similar question on the relaxation of the clique average loss for the definition of MxNet (SubMatch) in Section 3.2.\n\n2. In equation (8) for the subgraph matching problem, the last inequality ($K_{\\omega(G)} \\leq P A P^{\\intercal}$) necessarily entails the earlier ones (e.g., $K_1 \\leq P A P^{\\intercal}$). Hence, instead of using the full curriculum with $c$ ranging from $2$ to $\\omega(G)$, it seems possible to consider a simplification of the SubMatch loss in (9) by reducing the first (respectively, second) inner summation over $c$ to only the last term with $c = \\omega(G)$ (respectively, $c = \\omega(G)-1$). Is there evidence that including the full sequence of $c$'s is helpful?\n\nFinally just a typo: On the bottom of Page 7, \"$u$ indicating\" --> \"indicates\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "While prior works have proposed various deep learning approaches for solving the maximum clique problem, the \"distant supervision regime\" where only the size of the maximum clique is provided during training is under-explored, and the authors' proposal to parameterize node permutation matrices with GNNs and Sinkhorm iterations is novel to my knowledge and an interesting one. The authors have also performed extensive numerical experiments to compare the proposed method with several baselines as well as analyzing the various design choices such as the loss choice and the early stopping criteria. The paper is clearly-written overall with technical details well-documented.", "weaknesses": "As acknowledged by the authors, the computational burden of the MxNet model may be a concern when dealing with larger graphs, and indeed the datasets used in the experiments consist of relatively small graphs.\n\nSee two questions below regarding some design choices in the MxNet model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "JYneqFX0tt", "reviewer": "Reviewer_U7Wn", "summary": "This paper introduces MXNET, an end-to-end differentiable model for estimating the clique number in the graph. It contains MXNET(MSS) detection that detects cliques via message passing on permuted adjacency matrix and MXNET(SubMatch) that curriculum matches a series of cliques. Extensive experiments highlight the effectiveness of the proposed methods.", "questions": "Q1: How do these subgraph counting algorithms perform in the clique number estimation?\n\nQ2: How do these bound-based algorithms perform in the clique number estimation?\n\nQ3: How does the proposed method perform in large graph.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: It integrates both the message-passing-based clique detection and the matching-based techniques for accurate clique number estimation.\n\nS2: The design of the proposed method has sufficient motivations.\n\nS3: Experiments over multiple datasets validate its effectiveness.", "weaknesses": "W1: A more thorough comparison and introduction of related works would enhance the quality of this paper.\nW1.1: A related field is subgraph counting [1]. We can directly use 2-cliques, 3-cliques, ..., k-cliques as query graphs and apply subgraph counting methods to determine the number of k-cliques in the data graph. If the number of k-cliques is 1, then the clique number may be k. Given the limited availability of direct baselines for the problem of clique number estimation, this method could serve as a promising baseline. Some promising methods are in [1] and [4]. The first one stands as a representative that uses the neural method to estimate the subgraph number while the second, while the second one stands as a representative that designs an algorithm for subgraph counting.\n\nW1.2: Another promising area is the development of algorithm-based methods for approximate maximum clique detection or k-clique detection, as well as exact maximum clique detection [2]. These methods appear capable of quickly identifying accurate cliques. Exploring the motivation for using learning-based approaches and comparing these methods would be beneficial. Some promising methods are in [2] and [3]. The method in [2] is for exact maximum clique detection while the method in [3] is for approximate k-clique detection with theoretical guarantee which can be adapted for Clique Number Estimation.\n\n========\n\nW2: Some claims can be improved\nW2.1: The authors seem to argue that relying on \"extreme or no supervision\" is not beneficial (Line 061).  However, intuitively, avoiding such supervision could enhance the generalization and applicability of the algorithms used. A better explanation would help the understanding of this paper.\n\nW2.2: The author seems to focus on introducing prior work related to the Maximum Clique problem (Lines 49-62) in the introduction. However, the existing methods for estimating the clique number and their limitations are not sufficiently explored.\n\n========\n\nW3: Some experiments can be enhanced.\n\nW3.1: As demonstrated in the related works introduced in Section 1.2, the clique number can be bounded. (There are also many other metrics that can be used to bound the clique number.) Given that the graph used in this paper is small and dense (see Table 7), employing these bounded metrics may yield good results and assist in pruning unpromising outcomes. As there are not many methods directly predicting the clique number, this bound-based baseline would be a good choice.\n\nW3.2: The datasets evaluated in the paper are dense and small, with the largest containing only 300 nodes. It would be interesting to assess the performance on more diverse and larger datasets, as we can easily identify the exact cliques in smaller graphs. For example, the method proposed in previous works like in [3] can handle billion-scale graphs. Some smallest datasets in this paper like Email and Amazon would be helpful to asses the performance of the MXNET.\n\n\n\nW3.3: The authors evaluate the effect of distribution shift; however, they remain within the same graph. It would be interesting to assess whether the trained model can generalize to different datasets, especially since there may be scenarios where labels are not available for training. An interesting scenario is that could the model trained in this paper can be generalized to predict the clique number for the datasets in [3].\n\n[1]: \"Neural Subgraph Counting with Wasserstein Estimator\" in SIGMOD 2022\n\n[2]: \"Finding the Maximum Clique in Massive Graphs\" in VLDB 2017\n\n[3]: \"Scaling Up 𝑘-Clique Densest Subgraph Detection\" in SIGMOD 2023\n\n[4]: \"Fast Local Subgraph Counting\" in VLDB 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)