Improved Exact and Heuristic Algorithms for Maximum Weight Clique

• URL: http://arxiv.org/abs/2302.00458v1
• Date: Wed, 1 Feb 2023 14:02:06 GMT
• Title: Improved Exact and Heuristic Algorithms for Maximum Weight Clique
• Authors: Roman Erhardt, Kathrin Hanauer, Nils Kriege, Christian Schulz, Darren Strash
• Abstract summary: We propose improved exact and labeling algorithms for solving the maximum weight clique problem. Our algorithms interleave successful techniques with novel data reduction rules that use local graph structure. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs.
• Score: 1.2074552857379273
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interleave successful techniques from related work with novel data reduction rules that use local graph structure to identify and remove vertices and edges while retaining the optimal solution. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs. Our data reductions always produce smaller reduced graphs than existing data reductions alone. As a result, our exact algorithm, MWCRedu, finds solutions orders of magnitude faster on naturally weighted, medium-sized map labeling graphs and random hyperbolic graphs. Our heuristic algorithm, MWCPeel, outperforms its competitors on these instances, but is slightly less effective on extremely dense or large instances.

Related papers

• Addressing Noise and Efficiency Issues in Graph-Based Machine Learning Models From the Perspective of Adversarial Attack [2.1937382384136637]
  We propose treating noisy edges as adversarial attack and use a spectral adversarial robustness evaluation method to diminish the impact of noisy edges on the performance of graph algorithms. Our method identifies those points that are less vulnerable to noisy edges and leverages only these robust points to perform graph-based algorithms.
  arXiv  Detail & Related papers  (2024-01-28T10:03:37Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• FORBID: Fast Overlap Removal By stochastic gradIent Descent for Graph Drawing [1.1470070927586014]
  Overlaps between nodes can hinder graph visualization readability. Overlap Removal (OR) algorithms have been proposed as layout post-processing. We propose a novel gradient models OR as a joint stress and scaling optimization problem.
  arXiv  Detail & Related papers  (2022-08-19T13:51:44Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  We propose a one-step gradient matching scheme, which performs gradient matching for only one single step without training the network weights. Our theoretical analysis shows this strategy can generate synthetic graphs that lead to lower classification loss on real graphs. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance.
  arXiv  Detail & Related papers  (2022-06-15T18:20:01Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  We propose a reinforcement learning algorithm that learns how to navigate the space of possible subgraphs using an Euclidean subgraph embedding as its map. LeNSE identifies small subgraphs yielding solutions comparable to those found by running the embeddings on the entire graph, but at a fraction of the total run time.
  arXiv  Detail & Related papers  (2022-05-20T11:54:03Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Graph Matching via Optimal Transport [11.93151370164898]
  Solving the graph matching problem is increasingly important due to it's applications in operations research, computer vision, neuroscience, and more. Current state-of-the-art algorithms are inefficient in matching very large graphs, though they produce good accuracy. We present GOAT, a modification to the state-of-the-art graph matching approximation algorithm "FAQ" (Vogelstein, 2015), replacing its linear sum assignment step with the "Lightspeed Optimal Transport" method of Cuturi (2013).
  arXiv  Detail & Related papers  (2021-11-09T19:18:18Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  We propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way.
  arXiv  Detail & Related papers  (2021-02-02T06:50:07Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.