What Soft Clustering Objectives Compute, When They Are Tight, and What Softness Buys: The Case of Soft Structural Entropy

Differentiable relaxations of discrete clustering objectives are standard in graph learning: DMoN, MinCutPool, Neuromap and structural-entropy (SE) methods (LSEnet, DeSE) relax modularity, normalized cut, the map equation and SE by substituting soft volumes and internal weights into the discrete formula. The resulting bilinear plug-in is read as the discrete objective. We ask what it computes, when it is tight and what the softness buys, with two-level SE as the running case. For a row-stochastic assignment $S$ we compare the plug-in $H_{\mathrm{bil}}$, the multilinear extension $H_{\mathrm{mul}}(S)=\mathbb{E}[H_2(Z)]$ under independent rounding, and a memoryless stochastic-encoder code length $H_{\mathrm{code}}$. All three agree at hard assignments, and $H_{\mathrm{code}}(S)=H_{\mathrm{bil}}(S)+\frac{1}{2m}{\sum }_j{d}_j\mathcal{H}(S_j)$ exactly: the deployed objective is a bits-back net rate. The multilinear extension is an exact relaxation (its minimum is a vertex and equals the discrete minimum), whereas the plug-in is provably loose: at the uniform assignment it equals $H_1-{\log }_2(K)/K$ on every graph, so a strictly soft $S$ beats every partition whenever the discrete optimum lies above that floor, and local overlap makes it loose even when it does not (5-node bowtie: ${\log }_{2}3$ against $\frac{7}{6}+\frac{1}{3}{\log }_{2}3$ bits). Beyond SE, the multilinear extension is exact for every partition objective; Neuromap's plug-in obeys the same bits-back identity but has no floor; pairwise objectives differ from their expectation by a degree-weighted Gini refund, which makes Markov stability at even times exactly tight and bounds modularity's looseness by $(1-\frac{1}{K}){\sum }_i{d}_i^2/(2m{)}^2$. In an exhaustive census plug-ins deployed for SE, DMoN, MinCutPool and Dasgupta's cost beat every partition on 12, 14, 10 and 9 of 20 instances; the map equation's never did by more than $10^{-3}$ bits. On the sparse graphs we tested the looseness does not bind: on Cora, CiteSeer and planted SBMs the plug-in optima are near-hard, the multilinear objective trained with its unbiased gradient finds no better partitions, and the soft-over-hard advantage of our encoder control largely vanishes against a Gumbel-softmax hard arm. Preregistered gates are reported verbatim, including the failures (a planted-overlap null control fails at 5 and at 20 seeds).