Clique-density feasibility regularizer

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.