# Clique-density feasibility regularizer

- ID: 293
- Canonical URL: https://synthcore.org/idea/293/clique-density-feasibility-regularizer
- API JSON: https://synthcore.org/api/idea/293.json
- API Markdown: https://synthcore.org/api/idea/293.md
- Verification status: unverified
- Source: [arXiv:2606.31967](https://arxiv.org/abs/2606.31967)
- Category: regularization
- Solves: accuracy, generalization, stability
- ML areas: graph-nn, vae, loss, regularization
- Math tags: graph-theory, combinatorics, optimization
- Ratings: usefulness 5/10; difficulty 4/10; novelty 7/10

## Idea description

Add a differentiable penalty to a graph generator or graph predictor when its soft higher-order clique density violates the sharp lower bound implied by its lower-order clique density. The regularizer encourages generated graphs to have mathematically consistent motif statistics without hard-discretizing the predicted adjacency matrix.

## Mathematical statement

The paper proves the asymptotically sharp relation $k_t(G)/n^t \geq F_t(F_s^{-1}(k_s(G)/n^s))$ for integers $2\leq s<t$, where $k_r(G)$ is the number of $r$-cliques, $F_r:[0,1/2]\to[0,1/r!]$ is the Lovász–Simonovits minimum asymptotic $r$-clique-density function at a prescribed edge density, and $F_s^{-1}(y)=\inf\{x:F_s(x)\geq y\}$ is its generalized inverse. The weighted extension represents a graph by node weights $\vec{x}$ satisfying $x_i\geq0$ and $\sum_i x_i=1$, together with symmetric soft edge weights $a_{ij}\in[0,1]$ and $a_{ii}=0$. Its $r$-clique density is $\mathcal{G}(K_r)=\sum_{S\in\binom{[n]}{r}}(\prod_{e\in\binom{S}{2}}a_e)(\prod_{i\in S}x_i)$. For a neural model producing soft adjacency probabilities $A$ and uniform node weights $x_i=1/n$, define $p_r(A)=n^{-r}\sum_{|S|=r}\prod_{i<j\in S}A_{ij}$ and impose the adapted hinge penalty $L_{\mathrm{clique}}=\max\{0,F_t(F_s^{-1}(p_s(A)))-p_t(A)-\epsilon\}^2$, with slack $\epsilon\geq0$ to accommodate finite-size and model-calibration error. The theorem's useful property is that it gives a sharp lower envelope, so the penalty targets impossible motif combinations rather than an arbitrary correlation prior.

## Key formulas

- $$\frac{k_t(G)}{n^t}\geq F_t\!\left(F_s^{-1}\!\left(\frac{k_s(G)}{n^s}\right)\right),\qquad 2\leq s<t.$$
- $$\mathcal{G}(K_r)=\sum_{S\in\binom{[n]}{r}}\left(\prod_{e\in\binom{S}{2}}a_e\right)\left(\prod_{i\in S}x_i\right),\qquad x_i\geq0,\ \sum_i x_i=1,\ 0\leq a_{ij}\leq1,\ a_{ii}=0.$$
- $$p_r(A)=\frac{1}{n^r}\sum_{S\in\binom{[n]}{r}}\prod_{\{i,j\}\in\binom{S}{2}}A_{ij},\qquad L_{\mathrm{clique}}=\left[\max\left(0,F_t\!\left(F_s^{-1}(p_s(A))\right)-p_t(A)-\epsilon\right)\right]^2.$$

## Implementation notes

Integrate the regularizer into the loss of a graph VAE, autoregressive graph generator, or GNN that outputs a symmetric soft adjacency matrix $A\in[0,1]^{n\times n}$. Apply it to the decoder's pre-threshold edge probabilities during training, not to sampled binary graphs; set $A\leftarrow(A+A^\top)/2$ and $A_{ii}=0$. First choose $s=2,t=3$: compute $p_2(A)=n^{-2}\sum_{i<j}A_{ij}$ using the same normalization used to tabulate $F_2$, then compute $p_3(A)=n^{-3}\sum_{i<j<k}A_{ij}A_{ik}A_{jk}$. Evaluate $b=F_3(F_2^{-1}(p_2))$ and add $\lambda[\max(0,b-p_3-\epsilon)]^2$ to the reconstruction or likelihood loss. Pseudocode is: `A=sigmoid(decoder(z)); A=(A+A.T)/2; fill_diagonal(A,0); p2=sum_upper(A)/n**2; p3=sum_triangles(Aij*Aik*Ajk)/n**3; u=F2_inverse(p2); b=F3(u); loss=base_loss+lambda*relu(b-p3-eps)**2; loss.backward()`. Store $F_2$ and $F_3$ as monotone lookup tables with linear interpolation. Construct the tables before training by evaluating the known clique-density curve; if unavailable, approximate each $F_r(u)$ on a dense grid using balanced complete multipartite weighted graphs, computing $u=(1-\sum_i x_i^2)/2$ and $p_r=\sum_{|S|=r}\prod_{i\in S}x_i$, then taking the lower envelope and applying isotonic regression to enforce monotonicity. The mathematical quantities are the density polynomial and lower-envelope bound; $\epsilon$ and $\lambda$ are empirical hyperparameters. Begin with a small GraphVAE on 20–50-node stochastic block-model graphs or QM9 molecules, comparing the standard decoder loss against the regularized model at matched parameter count. Measure held-out graph likelihood, triangle-density calibration, motif-count Wasserstein error, and invalid or disconnected output rate. Success is a reduction in higher-order motif error and fewer structurally inconsistent samples at equal likelihood, without a substantial increase in decoder training time.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.