Speeding up Glauber Dynamics for Random Generation of Independent Sets

Rémi Varloot, Ana Busic, Anne Bouillard

TL;DR

Generating maximum independent sets in graphs is a notoriously hard problem often tackled using Markov Chain Monte Carlo (MCMC) methods. This paper introduces an "oracle skipping" technique for the Coupling From The Past (CFTP) algorithm that drastically speeds up exact sampling by ignoring "passive" events that don't change the system's state. The result is a mathematically rigorous, unbiased sampler that scales much better, particularly when prioritizing the generation of larger independent sets.

What Problem Does This Paper Address?

Finding the Maximum Independent Set (MIS)—a set of vertices in a graph where no two share an edge—is an NP-hard problem with applications in wireless network scheduling (CSMA), statistical physics, and information theory. Because finding the absolute maximum is computationally intractable, researchers often use Glauber dynamics (a type of MCMC) to sample independent sets from a Gibbs distribution. By cranking up a parameter called "fugacity" ($\lambda$), the distribution heavily favors larger independent sets.

To get an exact sample from this stationary distribution, researchers use a technique called Coupling From The Past (CFTP) combined with bounding chains. However, there is a massive bottleneck: when $\lambda$ is high, the algorithm rejects almost all proposed state changes. The simulation spends the vast majority of its time processing "passive" events that have absolutely no effect on the bounding chain, making the mixing time prohibitively slow. The authors set out to find a way to skip these useless steps without introducing statistical bias.

Methods

The authors build upon the standard CFTP algorithm with bounding chains, but introduce a novel concept called CFTP with Oracle Skipping.

The intuitive idea is simple: just don't simulate the passive events. However, doing this in CFTP is highly non-trivial. Because CFTP works by starting simulations further and further back in time, an event that was "passive" when starting at time $-k$ might suddenly become "active" when starting at time $-(k+1)$. You cannot simply delete passive events from memory, or the algorithm will yield biased, incorrect samples.

To solve this, the authors introduce a rigorous mathematical framework using:

  • Contraction: Safely removing passive letters (events) from the sequence.
  • Expansion: Re-inserting passive letters according to a specific geometric distribution based on the active state.
  • Delimiters ($\sharp$): Special markers used to track the history of the sequence.

Instead of simulating every step, Algorithm 3 dynamically maintains a queue of only the active events. When the algorithm needs to look further back in time, it uses the expansion rules to probabilistically reconstruct what the sequence "could have been," ensuring the final sample remains perfectly drawn from the target Gibbs distribution.

Datasets

As this is a theoretical and algorithmic paper, it does not use standard machine learning datasets. Instead, the authors evaluate their algorithm on synthetic graph models:

  • Star Graphs: Evaluated with 100 and 1000 vertices.
  • Barabási-Albert Model: Random graphs generated via preferential attachment, evaluated with 100 vertices.

Key Insights and Ideas

  • Skipping backward in time is possible: The biggest conceptual leap is proving that you can dynamically drop and probabilistically re-insert events in a backward-time simulation without ruining the exact sampling guarantees of CFTP.
  • Immunity to high fugacity ($\lambda$): In standard Gibbs sampling, pushing the system to find larger independent sets (high $\lambda$) causes exponential slowdowns due to rejected moves. Oracle skipping naturally bypasses these rejections, making the runtime largely independent of $\lambda$.
  • Local updates make oracle skipping efficient: The authors note that for independent sets, whether an event is active or passive only depends on a vertex and its immediate neighbors. This locality makes it computationally cheap to update the "activeness" of events on the fly.

Key Results

  • Theoretical Speedup: The authors mathematically prove that on a star graph with $n$ vertices, standard Gibbs sampling has an expected coupling time of $O(\lambda^n)$. Their oracle skipping method reduces this to $O(n)$, completely removing the exponential dependence on $\lambda$.
  • Empirical Dominance: On star graphs (100 and 1000 nodes), oracle skipping required orders of magnitude fewer steps than standard Gibbs sampling. It also consistently outperformed the Dyer-Greenhill scheme (a competing method that uses swap operations to speed up convergence).
  • Fewer steps for harder problems: Counterintuitively, the empirical results showed that as $\lambda$ grew larger, the number of events generated by the oracle skipping algorithm actually decreased. Because large independent sets are favored, the probability of a new event being active drops, allowing the algorithm to skip massive chunks of time.
  • Robustness: The performance gains held true on the Barabási-Albert random graphs, proving the method works on more complex topologies than just star graphs.

Limitations and Future Work

  • Data Structure Overhead: While the algorithm drastically reduces the number of steps (events processed), maintaining the queues and dynamically calculating conditional probabilities for expansion/contraction adds computational overhead per step.
  • Focus on Unweighted Graphs: The explicit analysis in the paper focuses on graphs where all vertices have equal weights, though the authors note the math can be extended to the weighted case.
  • Future Work: The authors explicitly state that applying this accelerated sampling technique to the simulation of queueing networks (which directly models wireless CSMA protocols) is an area of ongoing research.

Summary updated

Abstract

The maximum independent set (MIS) problem is a well-studied combinatorial optimization problem that naturally arises in many applications, such as wireless communication, information theory and statistical mechanics. MIS problem is NP-hard, thus many results in the literature focus on fast generation of maximal independent sets of high cardinality. One possibility is to combine Gibbs sampling with coupling from the past arguments to detect convergence to the stationary regime. This results in a sampling procedure with time complexity that depends on the mixing time of the Glauber dynamics Markov chain. We propose an adaptive method for random event generation in the Glauber dynamics that considers only the events that are effective in the coupling from the past scheme, accelerating the convergence time of the Gibbs sampling algorithm. The full paper is available on arXiv.
BibTeX
@inproceedings{varloot2015speeding,
  author = {Rémi Varloot and Ana Busic and Anne Bouillard},
  title = {{Speeding up Glauber Dynamics for Random Generation of Independent Sets}},
  booktitle = {SIGMETRICS},
  year = {2015},
  url = {https://openreview.net/forum?id=Zmcz6fIiav},
}

Loading related content...

Figure