Dataless Quadratic Neural Networks for the Maximum Independent Set Problem

• URL: http://arxiv.org/abs/2406.19532v3
• Date: Wed, 16 Oct 2024 19:31:19 GMT
• Title: Dataless Quadratic Neural Networks for the Maximum Independent Set Problem
• Authors: Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, Alvaro Velasquez,
• Abstract summary: We show that pCQO-MIS scales with only the number of nodes in the graph not the number of edges. Our method avoids out-of-distribution, sampling, and data-centric approaches.
• Score: 23.643727259409744
• License:
• Abstract: Combinatorial Optimization (CO) addresses many important problems, including the challenging Maximum Independent Set (MIS) problem. Alongside exact and heuristic solvers, differentiable approaches have emerged, often using continuous relaxations of ReLU-based or quadratic objectives. Noting that an MIS in a graph is a Maximum Clique (MC) in its complement, we propose a new quadratic formulation for MIS by incorporating an MC term, improving convergence and exploration. We show that every maximal independent set corresponds to a local minimizer, derive conditions for the MIS size, and characterize stationary points. To solve our non-convex objective, we propose solving parallel multiple initializations using momentum-based gradient descent, complemented by an efficient MIS checking criterion derived from our theory. Therefore, we dub our method as parallelized Clique-Informed Quadratic Optimization for MIS (pCQO-MIS). Our experimental results demonstrate the effectiveness of the proposed method compared to exact, heuristic, sampling, and data-centric approaches. Notably, our method avoids the out-of-distribution tuning and reliance on (un)labeled data required by data-centric methods, while achieving superior MIS sizes and competitive runtime relative to their inference time. Additionally, a key advantage of pCQO-MIS is that, unlike exact and heuristic solvers, the runtime scales only with the number of nodes in the graph, not the number of edges.

Related papers

• On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
  We study the discriminative probabilistic modeling problem on a continuous domain for (multimodal) self-supervised representation learning. We conduct generalization error analysis to reveal the limitation of current InfoNCE-based contrastive loss for self-supervised representation learning.
  arXiv  Detail & Related papers  (2024-10-11T18:02:46Z)
• From Maximum Cut to Maximum Independent Set [7.250073177017239]
  It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. It turns out that this strategy greatly improves the approximation for the independence number of random ErdHos-R'enyi graphs. It also exhibits perfect performance on a benchmark arising from coding theory.
  arXiv  Detail & Related papers  (2024-08-13T09:33:41Z)
• Efficient k-means with Individual Fairness via Exponential Tilting [13.72284501663574]
  In location-based resource allocation scenarios, individually fair clustering is often employed to achieve the principle of treating all points equally. This paper proposes a novel algorithm, tilted k-means (TKM), aiming to achieve individual fairness in clustering.
  arXiv  Detail & Related papers  (2024-06-24T11:50:31Z)
• An Efficient Difference-of-Convex Solver for Privacy Funnel [3.069335774032178]
  We propose an efficient solver for the privacy funnel (PF) method. The proposed DC separation results in a closed-form update equation. We evaluate the proposed solver with MNIST and Fashion datasets.
  arXiv  Detail & Related papers  (2024-03-02T01:05:25Z)
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers [0.0]
  We provide a non-unit disk framework to solve optimization problems on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits. Our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state.
  arXiv  Detail & Related papers  (2023-08-15T14:24:45Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  This paper presents an algorithm to solve the Soft k-Means problem globally. A new model, named Minimal Volume Soft kMeans (MVSkM), is proposed to address solutions non-uniqueness issue.
  arXiv  Detail & Related papers  (2022-12-07T12:06:55Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  We study the problem of single-channel source separation (SCSS) We focus on cyclostationary signals, which are particularly suitable in a variety of application domains. We propose a deep learning approach using a U-Net architecture, which is competitive with the minimum MSE estimator.
  arXiv  Detail & Related papers  (2022-08-22T14:04:56Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  We study episodic two-player zero-sum Markov games (MGs) in the offline setting. The goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori.
  arXiv  Detail & Related papers  (2022-02-15T15:39:30Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  We propose a novel DRL scheme, coined learning what to defer (LwD), where the agent adaptively shrinks or stretch the number of stages by learning to distribute the element-wise decisions of the solution at each stage. We apply the proposed framework to the maximum independent set (MIS) problem, and demonstrate its significant improvement over the current state-of-the-art DRL scheme.
  arXiv  Detail & Related papers  (2020-06-17T02:19:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.