Sparsest Subgraph Problem: New QUBO Relaxations Achieve Exact Solutions with Iterative Algorithms

The sparsest -subgraph problem, which seeks the largest subgraph of a network with minimal connections, presents a significant challenge in network analysis and optimisation, with applications ranging from machine learning to social network studies. Omkar Bihani, Roman Kužel, and Janez Povh, from the Rudolfovo Science and Technology Centre in Slovenia, along with Dunja Pucher from the University of Klagenfurt in Austria, now present a novel approach to tackling this problem by formulating it as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. Their work introduces three distinct QUBO relaxations and, crucially, develops iterative algorithms that refine these relaxations, dynamically adjusting parameters to improve accuracy and efficiency. This research establishes a clear understanding of when these relaxations yield exact solutions and demonstrates, through extensive testing, that the proposed algorithms offer a powerful new tool for solving complex network problems.

Sparsest k-Subgraphs and Optimisation Techniques

This research investigates methods for solving the sparsest k-subgraph (SKS) problem, a challenging combinatorial optimization task with applications in network analysis, data mining, and machine learning. The SKS problem seeks to identify a subgraph of a given graph containing a specific number of nodes while minimizing the number of edges within that subgraph. Researchers explore different mathematical formulations and techniques to improve the performance of solvers for this problem, considering both classical and quantum computing approaches. This involves representing the nodes of the subgraph as binary variables and expressing the problem’s objectives and constraints as quadratic equations. Classical optimization techniques, such as Lagrangian relaxation and penalty methods, are also investigated. Lagrangian relaxation decomposes the complex problem into smaller, more manageable subproblems, while penalty methods add terms to the objective function to enforce constraints.

Furthermore, the team explores convex reformulation, aiming to transform the QUBO problem into a tighter convex program, which can improve the performance of classical solvers by providing stronger bounds and reducing the search space. Augmented Lagrangian methods combine the benefits of both Lagrangian relaxation and penalty methods, offering a balance between constraint satisfaction and objective function optimization. The paper delves into specific techniques, including standard QUBO formulation, tight convex reformulations, penalty-based QUBO, augmented Lagrangian QUBO, convex hull reformulation, and the Reformulation-Lemmas-Inequalities (RLI) approach. Each technique aims to strengthen the problem formulation and improve the efficiency of solvers.

The RLI approach, in particular, is highlighted as a particularly effective way to strengthen the convex relaxation, leading to improved performance of classical solvers. Creating a tighter convex hull of the feasible region can also lead to better bounds and faster convergence, while carefully tuning penalty weights is crucial for balancing constraint satisfaction and objective function optimization. A significant aspect of the research is the exploration of QUBO formulations for solving the SKS problem on quantum annealers. The authors aim to design QUBO models that are well-suited for the limitations of current quantum hardware, such as the number of qubits and their connectivity.

Reducing the number of artificial variables needed to map the problem onto the quantum hardware and minimizing the impact of hardware connectivity on solution quality are key considerations. The team utilizes classical optimization solvers, including SCIP, PySCIPOpt, and Biqbin, to evaluate the performance of different formulations. The key findings demonstrate that the choice of QUBO formulation significantly impacts solver performance. Tighter formulations generally lead to better solutions and faster convergence. Convex relaxation techniques can improve the performance of classical solvers by providing stronger bounds and reducing the search space.

For quantum annealers, minimizing artificial variables and considering hardware connectivity are crucial. Augmented Lagrangian methods offer a good balance between constraint satisfaction and objective function optimization, and the RLI approach can significantly strengthen the convex relaxation. These relaxations, a quadratic penalty approach, an augmented Lagrangian method, and a Lagrangian relaxation, transform the SkS problem into a form suitable for solving with quantum annealers, such as those produced by D-Wave systems. Each method introduces parameters that require careful calibration to achieve optimal performance. The team aims to find formulations that balance accuracy and computational efficiency.

Scientists proposed iterative algorithms that dynamically update these penalty parameters during the solving process, approximating solutions to the internal QUBO problems using both simulated and processing units. The quadratic penalty relaxation directly incorporates a penalty term into the objective function, influencing all coefficients. Researchers discovered that a large penalty parameter can decrease the value of these coefficients after normalization, potentially reducing accuracy due to the finite precision of digital-to-analog converters. Conversely, a small penalty parameter risks allowing infeasible solutions to dominate, leading to incorrect results.

Building on this, the augmented Lagrangian method combines the penalty approach with Lagrangian multipliers, aiming to more effectively represent the problem’s constraints. This method employs an iterative procedure to determine near-optimal values for both penalty parameters, partially resolving challenges related to reduced precision in large-scale problems. The team investigated this approach, recognizing its potential for discrete optimization problems, as demonstrated by improved performance on the set cover problem. Finally, the researchers explored Lagrangian relaxation, omitting the quadratic penalty term entirely and focusing on relaxing the SkS constraints. The team investigated a quadratic penalty relaxation, a Lagrangian relaxation, and an augmented Lagrangian relaxation, each offering a unique approach to transforming the SkS problem into a QUBO formulation suitable for quantum and classical solvers. Experiments demonstrate that the effectiveness of each relaxation is heavily dependent on the precise selection of penalty parameters, requiring careful consideration to achieve optimal performance. Researchers designed three iterative algorithms, each incorporating one of the QUBO relaxations, to dynamically adjust penalty parameters during the solution process while approximately solving the internal QUBO problems using both simulated annealing and quantum processing units.

The quadratic penalty approach influences all coefficients of the original objective function, and the team discovered that a large penalty parameter decreases the value of these coefficients after normalization, potentially reducing the accuracy of quantum annealing due to finite precision limitations. Conversely, a small penalty parameter risks domination by infeasible solutions, leading to incorrect results. The augmented Lagrangian method, combining a penalty method with Lagrangian multipliers, partially addresses the challenges of reduced precision in large-scale problems, and experiments show this approach outperforms the standard penalty method. In the third approach, scientists omitted the quadratic penalty term entirely, utilizing Lagrangian relaxation of the SkS problem, and the results indicate that careful parameter tuning is crucial for achieving accurate and efficient solutions across all three methods. These advancements offer new avenues for tackling complex optimization challenges with both classical and quantum computing techniques.