Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Acoustics Speech and Signal Processing

Unified Clustering and Outlier Detection on Specialized Hardware

Eldan Cohen, Hayato Ushijima‐Mwesigwa, Avradip Mandal, Arnab Roy

Published May 13, 2021• 2 citations
Publisher

Abstract

Clustering and outlier detection are often studied as separate problems. However, previous work has shown that a unified approach can lead to better performance. Unified clustering and outlier detection is a hard combinatorial problem that has received significant attention in recent years. The recent emergence of specialized optimization hardware capable of solving combinatorial problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) models has led to increased interest in harnessing these platforms in core data mining tasks. In this work, we present a novel QUBO formulation of the unified clustering and outlier detection problem and use the Fujitsu Digital Annealer, a specialized CMOS hardware, to solve it. Experiments on synthetic and real datasets demonstrate the effectiveness of our approach.

DOI
10.1109/icassp39728.2021.9413754

Related papers

Ising-Based Consensus Clustering on Specialized Hardware

Eldan Cohen, Avradip Mandal, Hayato Ushijima‐Mwesigwa +1 more

The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core mathematical abstraction used by a large number of these hardware platforms, and evaluating the performance of these models when solved on specialized hardware. An interesting area of application is data mining, where combinatorial optimization problems underlie many core tasks. In this work, we focus on consensus clustering (clustering aggregation), an important combinatorial problem that has received much attention over the last two decades. We present two Ising models for consensus clustering and evaluate them using the Fujitsu Digital Annealer, a quantum-inspired CMOS annealer. Our empirical evaluation shows that our approach outperforms existing techniques and is a promising direction for future research.

arXiv:2003.01887•Lecture notes in computer science•Jan 1, 2020•16 citations

Binary matrix factorization on special purpose hardware

Osman Asif Malik, Hayato Ushijima‐Mwesigwa, Arnab Roy +2 more

Many fundamental problems in data mining can be reduced to one or more NP-hard combinatorial optimization problems. Recent advances in novel technologies such as quantum and quantum-inspired hardware promise a substantial speedup for solving these problems compared to when using general purpose computers but often require the problem to be modeled in a special form, such as an Ising or quadratic unconstrained binary optimization (QUBO) model, in order to take advantage of these devices. In this work, we focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF. We show how clustering constraints can easily be incorporated into these formulations. The special purpose hardware we consider is limited in the number of variables it can handle which presents a challenge when factorizing large matrices. We propose a sampling based approach to overcome this challenge, allowing us to factorize large rectangular matrices. In addition to these methods, we also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations. We run experiments on the Fujitsu Digital Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS) annealer, on both synthetic and real data, including gene expression data. These experiments show that our approach is able to produce more accurate BMFs than competing methods.

arXiv:2010.08693•PLoS ONE•Dec 16, 2021•6 citations

Solving Combinatorial Optimization Problems on Fujitsu Digital Annealer

Yu-Ting Kao, Jia-Le Liao, Hsiu-Chuan Hsu

Combinatorial optimization problems are ubiquitous in various disciplines and applications. Many heuristic algorithms have been devoted to solve these types of problems. In order to increase the efficiency for finding the optimal solutions, an application-specific hardware, called digital annealer (DA) has been developed for solving combinatorial optimization problems using quadratic unconstrained binary optimization (QUBO) formulations. In this study, we formulated the number partitioning problem and the graph partitioning problem into QUBO forms and solved such problems with the DA developed by Fujitsu Ltd. The QUBO formulation of the number partitioning problem is fully connected. The DA found the overall runtime for the optimal solution to be less than 30 seconds for 6500 binary variables. For the graph partitioning problem, we adopted modularity as the metric for determining the quality of the partitions. For Zachary's Karate Club graph, the modularity obtained was 0.445, a 6% increase against D-wave Quantum Annealer and Simulated Annealing. Moreover, to explore the DA's potential applications to real-world problems, we used the search for communities or virtual microgrids in a power distribution network as an example. The problem was formulated into graph partitioning. It is shown that the DA effectively identified community structures in the IEEE 33-bus and IEEE 118-bus network.

arXiv:2311.05196•Nov 9, 2023•2 citations

Graph Clustering Via QUBO and Digital Annealing

Pierre Miasnikof, Seo Woo Hong, Yuri Lawryshyn

This article empirically examines the computational cost of solving a known hard problem, graph clustering, using novel purpose-built computer hardware. We express the graph clustering problem as an intra-cluster distance or dissimilarity minimization problem. We formulate our poblem as a quadratic unconstrained binary optimization problem and employ a novel computer architecture to obtain a numerical solution. Our starting point is a clustering formulation from the literature. This formulation is then converted to a quadratic unconstrained binary optimization formulation. Finally, we use a novel purpose-built computer architecture to obtain numerical solutions. For benchmarking purposes, we also compare computational performances to those obtained using a commercial solver, Gurobi, running on conventional hardware. Our initial results indicate the purpose-built hardware provides equivalent solutions to the commercial solver, but in a very small fraction of the time required.

arXiv:2003.03872•Mar 9, 2020•2 citations

Physics-Inspired Optimization in the QUBO Framework: Key Concepts and Approaches

Lien-Po Yu, Chin-Fu Nien

Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.

SPIN•Aug 30, 2023•1 citation

Cluster-based Index Tracking Via QUBO and Digital Annealing

Seo Woo Hong

The cardinality constrained index-tracking problem seeks to find a combination of financial assets to replicate the return of a broad market index while using only a small subset of the asset universe. However, finding this combination of assets is NP-hard. In this thesis, we show the computational efficacy of solving a quadratic unconstrained binary optimization (QUBO) problem using purpose-built hardware Digital Annealer. We express an intra-cluster distance minimization problem as a QUBO problem and examine the computational performance between Digital Annealer and a commercial solver Gurobi running on conventional hardware. Moreover, we develop a new framework to solve the cardinality constrained index-tracking problem using the quadratic k-medoids clustering method on a market graph. To circumvent the nature of NP-hardness, we use the penalty method to formulate the problem as a QUBO problem, allowing us to utilize purpose-built hardware to solve the problem.

•Mar 1, 2021•0 citations
Clustering and outlier detection are often studied as separate problems. However, previous work has shown that a unified approach can lead to better performance. Unified clustering and outlier detection is a hard combinatorial problem that has received significant attention in recent years. The recent emergence of specialized optimization hardware capable of solving combinatorial problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) models has led to increased interest in harnessing these platforms in core data mining tasks. In this work, we present a novel QUBO formulation of the unified clustering and outlier detection problem and use the Fujitsu Digital Annealer, a specialized CMOS hardware, to solve it. Experiments on synthetic and real datasets demonstrate the effectiveness of our approach.
The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core mathematical abstraction used by a large number of these hardware platforms, and evaluating the performance of these models when solved on specialized hardware. An interesting area of application is data mining, where combinatorial optimization problems underlie many core tasks. In this work, we focus on consensus clustering (clustering aggregation), an important combinatorial problem that has received much attention over the last two decades. We present two Ising models for consensus clustering and evaluate them using the Fujitsu Digital Annealer, a quantum-inspired CMOS annealer. Our empirical evaluation shows that our approach outperforms existing techniques and is a promising direction for future research.
Many fundamental problems in data mining can be reduced to one or more NP-hard combinatorial optimization problems. Recent advances in novel technologies such as quantum and quantum-inspired hardware promise a substantial speedup for solving these problems compared to when using general purpose computers but often require the problem to be modeled in a special form, such as an Ising or quadratic unconstrained binary optimization (QUBO) model, in order to take advantage of these devices. In this work, we focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF. We show how clustering constraints can easily be incorporated into these formulations. The special purpose hardware we consider is limited in the number of variables it can handle which presents a challenge when factorizing large matrices. We propose a sampling based approach to overcome this challenge, allowing us to factorize large rectangular matrices. In addition to these methods, we also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations. We run experiments on the Fujitsu Digital Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS) annealer, on both synthetic and real data, including gene expression data. These experiments show that our approach is able to produce more accurate BMFs than competing methods.
Combinatorial optimization problems are ubiquitous in various disciplines and applications. Many heuristic algorithms have been devoted to solve these types of problems. In order to increase the efficiency for finding the optimal solutions, an application-specific hardware, called digital annealer (DA) has been developed for solving combinatorial optimization problems using quadratic unconstrained binary optimization (QUBO) formulations. In this study, we formulated the number partitioning problem and the graph partitioning problem into QUBO forms and solved such problems with the DA developed by Fujitsu Ltd. The QUBO formulation of the number partitioning problem is fully connected. The DA found the overall runtime for the optimal solution to be less than 30 seconds for 6500 binary variables. For the graph partitioning problem, we adopted modularity as the metric for determining the quality of the partitions. For Zachary's Karate Club graph, the modularity obtained was 0.445, a 6% increase against D-wave Quantum Annealer and Simulated Annealing. Moreover, to explore the DA's potential applications to real-world problems, we used the search for communities or virtual microgrids in a power distribution network as an example. The problem was formulated into graph partitioning. It is shown that the DA effectively identified community structures in the IEEE 33-bus and IEEE 118-bus network.
This article empirically examines the computational cost of solving a known hard problem, graph clustering, using novel purpose-built computer hardware. We express the graph clustering problem as an intra-cluster distance or dissimilarity minimization problem. We formulate our poblem as a quadratic unconstrained binary optimization problem and employ a novel computer architecture to obtain a numerical solution. Our starting point is a clustering formulation from the literature. This formulation is then converted to a quadratic unconstrained binary optimization formulation. Finally, we use a novel purpose-built computer architecture to obtain numerical solutions. For benchmarking purposes, we also compare computational performances to those obtained using a commercial solver, Gurobi, running on conventional hardware. Our initial results indicate the purpose-built hardware provides equivalent solutions to the commercial solver, but in a very small fraction of the time required.
Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.
The cardinality constrained index-tracking problem seeks to find a combination of financial assets to replicate the return of a broad market index while using only a small subset of the asset universe. However, finding this combination of assets is NP-hard. In this thesis, we show the computational efficacy of solving a quadratic unconstrained binary optimization (QUBO) problem using purpose-built hardware Digital Annealer. We express an intra-cluster distance minimization problem as a QUBO problem and examine the computational performance between Digital Annealer and a commercial solver Gurobi running on conventional hardware. Moreover, we develop a new framework to solve the cardinality constrained index-tracking problem using the quadratic k-medoids clustering method on a market graph. To circumvent the nature of NP-hardness, we use the penalty method to formulate the problem as a QUBO problem, allowing us to utilize purpose-built hardware to solve the problem.