pith. machine review for the scientific record. sign in

arxiv: 2603.11050 · v2 · submitted 2026-02-16 · 💻 cs.SI · math.CO

Recognition: 2 theorem links

· Lean Theorem

Overcoming Tight Constraints in Soft Happy Colouring

Mohammad Hadi Shekarriz , Asef Nazari , Dhananjay Thiruvady
Authors on Pith no claims yet

Pith reviewed 2026-05-15 21:58 UTC · model grok-4.3

classification 💻 cs.SI math.CO
keywords soft happy colouringcross-entropy methodlocal searchstochastic block modelconvergence analysismetaheuristicsnetwork homophilyNP-hard optimization
0
0 comments X

The pith

Restricting the cross-entropy search to local optima resolves stagnation and produces a convergent algorithm for soft happy colouring.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that pure cross-entropy methods stagnate in high-dimensional spaces when solving the soft happy colouring problem on networks. By combining it with local search that restricts sampling to local optima, the approach learns from high-quality structures. This leads to mathematical proof of convergence via exponential decay in Kullback-Leibler divergence. Empirical tests on 28,000 stochastic block model graphs confirm better performance and scalability than existing methods, especially in tight constraints.

Core claim

By restricting the search exclusively to local optima, CE+LS learns from high-quality structural characteristics rather than raw random samples, mathematically proving and empirically demonstrating that this resolves CE's stagnation, yielding a strictly convergent algorithm with exponential decay in Kullback-Leibler divergence that outperforms heuristic and memetic algorithms on large graphs.

What carries the argument

The CE+LS algorithm, which synergises cross-entropy's adaptive learning with a fast structure-aware local search restricted to local optima.

If this is right

  • CE+LS consistently outperforms existing algorithms in solution quality and scalability.
  • The algorithm remains efficient in tight constraint regimes where others fail.
  • It exhibits exponential decay in divergence leading to reliable convergence.
  • Superior performance holds across thousands of synthetic network instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar restrictions to local optima could mitigate stagnation in other metaheuristics for combinatorial problems on networks.
  • Testing on real-world social networks might reveal additional practical benefits beyond synthetic models.
  • The convergence property suggests potential for theoretical extensions to other probability-based optimizers.

Load-bearing premise

That restricting the search exclusively to local optima allows the cross-entropy component to learn from high-quality structural characteristics without introducing bias or losing necessary exploration in the probability distribution update.

What would settle it

Running the algorithm on large graphs and observing no exponential decay in Kullback-Leibler divergence or no consistent outperformance over baseline methods would falsify the claims.

Figures

Figures reproduced from arXiv: 2603.11050 by Asef Nazari, Dhananjay Thiruvady, Mohammad Hadi Shekarriz.

Figure 1
Figure 1. Figure 1: Flowchart of the CE+LS Algorithm. The diagram illustrates the synergy between the Global Exploration (Adaptive Sampling) of the Cross-Entropy method and the Local Ex￾ploitation provided by the Local Search improver. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The diagram illustrates a continuous 2D projection of the discrete [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Logarithmic plot of the absolute Kullback-Leibler (KL) divergence over the initial [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Average ratios of ρ-happy vertices in the output of the tested algorithms when no condition is imposed on ρ. sive testing phase to ensure the consistency of results and enable direct comparison with existing benchmarks. First, we compare the algorithms for their average performance [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Histogram of ratios of ρ-happy vertices (α(σ)) of colouring outputs (σ) of the tested algorithms. For each of the six diagrams, the dotted vertical line represents the mean value that is also reported in [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Average ratios of ρ-happy vertices in the output of the tested algorithms when ρ < µ, µ ≤ ρ ≤ ˜ξ, or ρ > ˜ξ. and CE (0.027) suffer near-total solution collapse. These findings underscore that for highly constrained problem instances, the integration of the sophisticated LS is a necessary condition for achieving high-quality solutions. The plot in Figure 7a illustrates the scalability of the six algorithms … view at source ↗
Figure 7
Figure 7. Figure 7: Comparison of the tested algorithms for their average ratios of [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Average accuracy of community detection in the output of the tested algorithms when [PITH_FULL_IMAGE:figures/full_fig_p024_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Average accuracy community detection (ACD) when the tested algorithms found complete ρ-happy colourings. When ρ > ˜ξ, no algorithm could find a complete ρ-happy colour￾ing. Consequently, no green bar is visible on the chart. across the three constraint regimes (Mild: ρ < µ, Intermediate: µ ≤ ρ ≤ ˜ξ, and Tight: ρ > ˜ξ). The data reveals a critical insight: in the tight regime, no algorithm can achieve solut… view at source ↗
read the original abstract

The Soft Happy Colouring (SHC) problem, a mathematical framework for identifying homophilic network structures, seeks to maximise the number of $\rho$-happy vertices, i.e. vertices with at least a proportion $\rho$ of neighbours that share the same colour. Because this NP-hard problem makes exact solutions intractable for large networks, probabilistic metaheuristics such as the Cross-Entropy (CE) method are suitable candidates to be employed. However, pure CE frequently suffers from probabilistic stagnation and non-convergence in high-dimensional spaces. To address this, we introduce {\sf CE+LS}, synergising CE's adaptive learning with a fast, structure-aware local search ({\sf LS}). By restricting the search exclusively to local optima, {\sf CE+LS} learns from high-quality structural characteristics rather than raw random samples. We mathematically prove and empirically demonstrate that this search space reduction resolves CE's stagnation, yielding a strictly convergent algorithm characterised by an exponential decay in Kullback-Leibler divergence. Evaluating {\sf CE+LS} across 28,000 Stochastic Block Model graphs demonstrates that it consistently outperforms existing heuristic and memetic algorithms, exhibiting superior scalability and solution quality. Crucially, {\sf CE+LS} remains highly efficient even in the tight regime, where comparative algorithms fail.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript introduces CE+LS, a hybrid of the Cross-Entropy (CE) method and a fast local search (LS) operator, for the NP-hard Soft Happy Colouring (SHC) problem of maximising the number of ρ-happy vertices in networks. It claims to mathematically prove that restricting CE sampling exclusively to local optima resolves probabilistic stagnation, yielding strict convergence with exponential decay in Kullback-Leibler divergence, and to empirically demonstrate consistent superiority over existing heuristics and memetic algorithms on 28,000 Stochastic Block Model graphs, with particular strength in tight regimes.

Significance. If the convergence proof is rigorous and the empirical protocol is reproducible with pre-specified parameters, the result would advance probabilistic metaheuristics for homophily-based network problems by providing a convergent, scalable alternative to pure CE. The scale of the 28,000-graph benchmark is a clear strength for assessing practical performance.

major comments (3)
  1. [Convergence Analysis] Convergence Analysis: The proof that restricting samples to local optima produces an elite set whose conditioned distribution still satisfies the standard CE contraction mapping (yielding exponential KL decay) is not supported by an explicit invariance or mixing argument. Standard CE convergence requires the elite-set support to remain sufficiently rich; the LS step can shrink that support in a graph-structure-dependent way, and no demonstration is given that the filtered distribution preserves the necessary contraction rate.
  2. [Experimental Results] Experimental Results: The superiority claim on 28,000 SBM graphs is load-bearing for the practical contribution, yet the abstract and description provide no error bars, no protocol for parameter selection, and no confirmation that parameters were fixed before seeing the tight-regime results. Post-hoc tuning would undermine the cross-algorithm comparison.
  3. [Method Description] Method Description: The assumption that LS filtering supplies unbiased, high-quality structural characteristics without loss of necessary exploration is central to both the proof and the empirical claims, but receives no quantitative justification (e.g., a bound on the bias introduced by conditioning on local-optima fixed points).
minor comments (2)
  1. [Abstract] The abstract should explicitly name the local-search operator and the precise definition of 'local optimum' used in the filtering step.
  2. Notation for the proportion ρ and the KL divergence should be introduced with a short reminder of their definitions when first used in the main text.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We are grateful to the referee for the thorough review and valuable suggestions. Below we address each major comment in detail, outlining the revisions we plan to incorporate.

read point-by-point responses

  1. Referee: Convergence Analysis: The proof that restricting samples to local optima produces an elite set whose conditioned distribution still satisfies the standard CE contraction mapping (yielding exponential KL decay) is not supported by an explicit invariance or mixing argument. Standard CE convergence requires the elite-set support to remain sufficiently rich; the LS step can shrink that support in a graph-structure-dependent way, and no demonstration is given that the filtered distribution preserves the necessary contraction rate.

    Authors: We thank the referee for this observation. Our proof establishes the contraction by noting that the local search maps to local optima while preserving the probabilistic structure from the CE update. To address the concern about support richness, we will add an explicit invariance argument in the revised manuscript demonstrating that the elite set support does not collapse under the LS operator for connected graphs, thereby maintaining the exponential KL decay rate. revision: partial

  2. Referee: Experimental Results: The superiority claim on 28,000 SBM graphs is load-bearing for the practical contribution, yet the abstract and description provide no error bars, no protocol for parameter selection, and no confirmation that parameters were fixed before seeing the tight-regime results. Post-hoc tuning would undermine the cross-algorithm comparison.

    Authors: We agree with the importance of clear experimental protocols. In the revision, we will add error bars to all reported results and include a new section on parameter tuning, specifying that parameters were determined using a validation set of graphs disjoint from the test set and fixed prior to the main experiments on the 28,000 SBM graphs. revision: yes

  3. Referee: Method Description: The assumption that LS filtering supplies unbiased, high-quality structural characteristics without loss of necessary exploration is central to both the proof and the empirical claims, but receives no quantitative justification (e.g., a bound on the bias introduced by conditioning on local-optima fixed points).

    Authors: We acknowledge the lack of a quantitative bias bound in the current manuscript. While a general bound may be intractable without additional assumptions, we will provide a more detailed discussion of the exploration-exploitation balance maintained by the hybrid approach and include empirical evidence of maintained diversity in the elite sets. This will clarify the justification for the assumption. revision: partial

Circularity Check

0 steps flagged

No significant circularity in the claimed derivation

full rationale

The paper presents a mathematical proof of strict convergence with exponential KL decay for the CE+LS algorithm as an independent derivation, separate from its empirical evaluations. The benchmarks are performed on 28,000 externally generated Stochastic Block Model graphs, with no evidence that any prediction or result reduces by construction to a fitted parameter or self-citation within the paper's own equations. The local-optima restriction is introduced as a methodological step whose convergence properties are claimed to be proven mathematically rather than assumed tautologically. No self-definitional constructs, fitted inputs renamed as predictions, or load-bearing self-citation chains appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based on abstract only; no explicit free parameters, axioms, or invented entities are detailed beyond standard metaheuristic assumptions. The local-search restriction is treated as a domain assumption whose validity is not independently verified here.

axioms (1)
  • domain assumption Local search efficiently reaches high-quality local optima that reflect useful network structure
    Invoked to justify restricting CE updates to local optima rather than raw samples.

pith-pipeline@v0.9.0 · 5530 in / 1294 out tokens · 26306 ms · 2026-05-15T21:58:39.809109+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Drawdown minimization in asset portfolio selection: Minlp models and efficient cross-entropy algorithm.International Transactions in Operational Research, 2024

    M Bayat, F Hooshmand, and SA MirHassani. Drawdown minimization in asset portfolio selection: Minlp models and efficient cross-entropy algorithm.International Transactions in Operational Research, 2024. 1

    work page 2024

  2. [2]

    Metaheuristics in combinatorial optimization: Overview and conceptual comparison.ACM Comput

    Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison.ACM Comput. Surv., 35(3):268–308, September 2003. 1

    work page 2003

  3. [3]

    Cambridge Studies in Advanced Mathematics

    Béla Bollobás.Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2001. 2

    work page 2001

  4. [4]

    Chapman and Hall/CRC, 6th edition, 2015

    Gary Chartrand, Linda Lesniak, and Ping Zhang.Graphs and digraphs. Chapman and Hall/CRC, 6th edition, 2015. 2

    work page 2015

  5. [5]

    Szymanski, and Xiaoyan Lu

    Hocine Cherifi, Gergely Palla, Boleslaw K. Szymanski, and Xiaoyan Lu. On community structure in complex networks: challenges and opportunities.Applied Network Science, 4(1):117, Dec 2019. 1

    work page 2019

  6. [6]

    Anne Condon and Richard M. Karp. Algorithms for graph partitioning on the planted par- tition model. In Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, and Alistair Sinclair, editors,Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques, pages 221–232, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. 1

    work page 1999

  7. [7]

    A tutorial on the cross-entropy method.Annals of operations research, 134(1):19–67, 2005

    Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. A tutorial on the cross-entropy method.Annals of operations research, 134(1):19–67, 2005. 1, 3.1

    work page 2005

  8. [8]

    A projection-adapted cross entropy (pace) method for transmission network planning.Energy Systems, 2:189–208, 2011

    Ali Eshragh, Jerzy Filar, and Asef Nazar. A projection-adapted cross entropy (pace) method for transmission network planning.Energy Systems, 2:189–208, 2011. 1

    work page 2011

  9. [9]

    Girvan and M

    M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002. 1

    work page 2002

  10. [10]

    Guimerà, L

    R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas. Self-similar community structure in a network of human interactions.Phys. Rev. E, 68:065103, Dec 2003. 1

    work page 2003

  11. [11]

    Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt

    Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic block- models: First steps.Social Networks, 5(2):109–137, 1983. 2

    work page 1983

  12. [12]

    Mark Jerrum and Gregory B. Sorkin. The metropolis algorithm for graph bisection.Dis- crete Applied Mathematics, 82(1):155–175, 1998. 2

    work page 1998

  13. [13]

    Finding happiness: An analysis of the maximum happy vertices problem.Computers & Operations Research, 103:265–276,

    Rhyd Lewis, Dhananjay Thiruvady, and Kerri Morgan. Finding happiness: An analysis of the maximum happy vertices problem.Computers & Operations Research, 103:265–276,

    work page

  14. [14]

    The maximum happy induced sub- graph problem: Bounds and algorithms.Computers & Operations Research, 126:105114,

    Rhyd Lewis, Dhananjay Thiruvady, and Kerri Morgan. The maximum happy induced sub- graph problem: Bounds and algorithms.Computers & Operations Research, 126:105114,

    work page

  15. [15]

    Miller McPherson, Lynn Smith-Lovin, and James M. Cook. Birds of a feather: Homophily in social networks.Annual Review of Sociology, 27(1):415–444, 2001. 1

    work page 2001

  16. [16]

    J. R. Norris.Markov Chains. Cambridge Series in Statistical and Probabilistic Mathemat- ics. Cambridge University Press, 1997. 3.3

    work page 1997

  17. [17]

    The cross-entropy method for combinatorial and continuous optimiza- tion.Methodology and computing in applied probability, 1:127–190, 1999

    Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimiza- tion.Methodology and computing in applied probability, 1:127–190, 1999. 1, 3.1

    work page 1999

  18. [18]

    Springer Science & Business Media, 2004

    Reuven Y Rubinstein and Dirk P Kroese.The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning. Springer Science & Business Media, 2004. 1

    work page 2004

  19. [19]

    Shekarriz, Dhananjay Thiruvady, and Asef Nazari

    Mohammad H. Shekarriz, Dhananjay Thiruvady, and Asef Nazari. Finding happiness by evolutionary algorithms.Preprint available at ArXiv: 2508.20934, 2025. 2, 4, 5

    work page arXiv 2025

  20. [20]

    Shekarriz, Dhananjay Thiruvady, Asef Nazari, and Wilfried Imrich

    Mohammad H. Shekarriz, Dhananjay Thiruvady, Asef Nazari, and Wilfried Imrich. Local search improvement for soft happy colouring.Preprint available at ArXiv: 2506.19284,

    work page arXiv

  21. [21]

    1, 1, 2, 2, 2, 4, 5, 5

    work page

  22. [22]

    Shekarriz, Dhananjay Thiruvady, Asef Nazari, and Rhyd Lewis

    Mohammad H. Shekarriz, Dhananjay Thiruvady, Asef Nazari, and Rhyd Lewis. Soft happy colourings and community structure of networks.Computers & Operations Re- search, 174:106893, 2025. 1, 2, 1, 2, 2, 4, 5

    work page 2025

  23. [23]

    Recombinativeapproachesforthemaximumhappy vertices problem.Swarm and Evolutionary Computation, 75:101188, 2022

    DhananjayThiruvadyandRhydLewis. Recombinativeapproachesforthemaximumhappy vertices problem.Swarm and Evolutionary Computation, 75:101188, 2022. 2

    work page 2022

  24. [24]

    Tackling the Maximum Happy Vertices Problem in Large Networks.4OR, 18(4):507–527, 2020

    Dhananjay Thiruvady, Rhyd Lewis, and Kerri Morgan. Tackling the Maximum Happy Vertices Problem in Large Networks.4OR, 18(4):507–527, 2020. 2

    work page 2020

  25. [25]

    Cross-entropy method for the maximal covering location problem.INFORMS Journal on Computing, 2025

    Hongtao Wang and Jian Zhou. Cross-entropy method for the maximal covering location problem.INFORMS Journal on Computing, 2025. 1

    work page 2025

  26. [26]

    Algorithmic aspects of homophyly of networks.Theoretical Computer Science, 593:117–131, 2015

    Peng Zhang and Angsheng Li. Algorithmic aspects of homophyly of networks.Theoretical Computer Science, 593:117–131, 2015. 1, 2, 2

    work page 2015

  27. [27]

    Improved approximation algorithms for the maximum happy vertices and edges problems.Algorith- mica, 80(5):1412–1438, May 2018

    Peng Zhang, Yao Xu, Tao Jiang, Angsheng Li, Guohui Lin, and Eiji Miyano. Improved approximation algorithms for the maximum happy vertices and edges problems.Algorith- mica, 80(5):1412–1438, May 2018. 2 27

    work page 2018