Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units

Technical Summary: Modularity Maximization and Community Detection via Recursive Hierarchical Annealing on D-Wave

Problem Statement
Community detection in complex networks is a fundamental problem in network science, typically formulated as maximizing the modularity index ($Q$). This optimization task is NP-hard. While classical heuristic algorithms (e.g., Louvain, Leiden) exist, they do not guarantee global optima. Quantum Annealing (QA) offers a potential pathway to solve such NP-hard problems by finding the global minimum of an energy landscape. However, a significant barrier to applying pure QA to community detection is the encoding of the problem. Standard approaches often rely on "one-hot" encoding to represent $M$ communities using $N \times M$ binary variables. This necessitates hard constraints (ensuring each node belongs to exactly one community), which are typically enforced via Lagrange multipliers. Tuning the penalty weights for these multipliers is empirically difficult and often requires problem-specific guessing, potentially obscuring the quantum process and limiting scalability. Furthermore, existing hybrid quantum-classical solutions often lack transparency regarding the division of labor between classical and quantum processors.

Methodology
The authors propose a novel algorithm, Hierarchical Annealing, designed to maximize modularity using pure quantum annealing on D-Wave Advantage QPUs without one-hot encoding or Lagrange multipliers.

• Recursive Binary Decomposition: Instead of assigning nodes to $M$ communities simultaneously, the algorithm recursively subdivides the network. It starts with the entire network as a single community and iteratively splits each community into two sub-communities. This transforms the problem into a sequence of unconstrained binary optimization problems.
• QUBO Formulation:
  • For undirected networks, the modularity gain of splitting a community $k$ into $k_1$ and $k_2$ is mapped to a Quadratic Unconstrained Binary Optimization (QUBO) problem. The cost function is derived from the generalized modularity matrix $B^k$, where the objective is to minimize the negative change in modularity ($p_k = -[Q(C_{k+1}) - Q(C_k)]$).
  • For directed networks, the authors address the asymmetry of the modularity matrix by optimizing the symmetrized linear combination $\frac{1}{2}(p_k + p_k^\top)$. This ensures the first step of the hierarchy optimizes the correct global function and maintains the QUBO formalism without linear terms.
• Resolution Parameter ($\gamma$): The resolution parameter, which controls the scale of detected communities, is integrated directly into the generalized modularity matrix calculation. The algorithm remains formally independent of $\gamma$ regarding the optimization structure, allowing it to be treated as a free parameter.
• Execution Flow: The process is executed recursively (Algorithm 1). For each step, a generalized modularity matrix is computed, a QUBO is constructed, and a clique embedding is loaded from a cache. The D-Wave sampler performs binary QA to find the optimal split. The recursion halts when a split yields no improvement (modularity change is zero) or results in an empty set.
• Implementation: The authors developed a Python library, Qommunity, which interfaces with the D-Wave ecosystem. They utilized the Advantage system (Pegasus topology, degree 16) with default chain strength strategies and majority voting for broken chains.

Key Contributions

1. Pure Quantum Annealing without Constraints: The work demonstrates a systematic procedure to find global optima for modularity maximization using only pure annealers, bypassing the need for one-hot encoding and the associated difficulty of tuning Lagrange multipliers.
2. Generalized Formalism: The authors extend the modularity maximization formalism to handle undirected, directed, and weighted networks within a unified recursive framework.
3. Interpretability: Unlike "black-box" hybrid solvers, the recursive nature of the algorithm produces a dendrogram of intermediate subdivisions. This offers an interpretable view of the community hierarchy, revealing how the network structure unfolds at different levels of resolution.
4. Scalability and Efficiency: The study provides empirical evidence that this approach yields solutions at least as optimal as state-of-the-art classical algorithms (Louvain, Leiden) while maintaining tractable computing times.

Results

• Benchmarking: The algorithm was tested on various network topologies, including Erdős-Rényi, Barabási-Albert, power-law clustered networks, and directed scale-free networks.
  • In simple 3-clique chains and the Zachary Karate Club network, the Hierarchical Annealing (H. Annealing) achieved modularity scores identical to or slightly exceeding those of Louvain and Leiden.
  • In stochastic block models (SBM), the method successfully recovered planted communities across varying mixing parameters, performing competitively against probabilistic inference methods.
  • For scale-free networks, the algorithm showed robust performance, often outperforming classical counterparts in terms of modularity scores, particularly when inherent hierarchies were present.
• Resolution Sensitivity: The algorithm remained stable across different values of the resolution parameter $\gamma$. While performance degraded slightly for extreme $\gamma$ values in directed networks, it remained competitive near $\gamma=1$.
• Computational Complexity:
  • The classical pre-processing (modularity matrix computation) scales as $O(n^2)$.
  • The recursive tree complexity is estimated at $O(n \log n)$ based on the Akra-Bazzi theorem, assuming balanced splits.
  • Empirically, QPU access times scaled logarithmically with network size ($t \propto \ln N$), suggesting efficient scaling for the quantum component.
  • The total runtime is dominated by communication and queueing overheads rather than the QPU execution time itself.
• Real-World Application: The method was applied to a real brain structural connectivity network (166 nodes). The resulting community structure and dendrogram were highly consistent with those found by Louvain and Leiden, with minor differences only in highly interconnected frontoparietal borders.

Significance and Claims
The paper positions this work as a "first step towards an applicable practice-oriented usage of pure quantum annealing." The authors claim to bridge the gap between network science and quantum computing by demonstrating that pure QA can solve community detection problems without relying on hybrid "black-box" solutions or complex constraint tuning.

The significance lies in:

• Transparency: Providing an interpretable, recursive solution (dendrograms) rather than a single flat partition, which is valuable for uncovering hidden hierarchies in complex systems like brain networks.
• Feasibility: Showing that current quantum hardware (D-Wave Advantage) can handle community detection tasks of practical size (up to ~166 nodes tested, limited by Pegasus topology) with competitive performance.
• Methodological Shift: Offering a viable alternative to one-hot encoding that avoids the empirical tuning of penalty weights, potentially making quantum optimization more accessible for network analysis.

The authors remain modest, acknowledging that the recursive process does not guarantee global optimality (a limitation shared by all heuristics for this NP-hard problem) and that scalability to very large networks currently requires hybrid solvers or local QPU access to mitigate communication overheads. They do not claim universal superiority over classical methods but highlight the potential for quantum annealing to provide meaningful, interpretable, and equally optimal solutions in specific topological contexts.