Fast Convex Relaxations using Graph Discretizations

• URL: http://arxiv.org/abs/2004.11075v2
• Date: Fri, 11 Sep 2020 11:42:38 GMT
• Title: Fast Convex Relaxations using Graph Discretizations
• Authors: Jonas Geiping, Fjedor Gaede, Hartmut Bauermeister and Michael Moeller
• Abstract summary: Matching and vision problems are fundamentals of computer computation applications. Applying techniques comes with a significant computational effort reducing their feasibility in practical applications. This setup allows us to faithfully work on problems constructed by SLIC or Cut-Pursuit.
• Score: 13.977100716044102
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matching and partitioning problems are fundamentals of computer vision applications with examples in multilabel segmentation, stereo estimation and optical-flow computation. These tasks can be posed as non-convex energy minimization problems and solved near-globally optimal by recent convex lifting approaches. Yet, applying these techniques comes with a significant computational effort, reducing their feasibility in practical applications. We discuss spatial discretization of continuous partitioning problems into a graph structure, generalizing discretization onto a Cartesian grid. This setup allows us to faithfully work on super-pixel graphs constructed by SLIC or Cut-Pursuit, massively decreasing the computational effort for lifted partitioning problems compared to a Cartesian grid, while optimal energy values remain similar: The global matching is still solved near-globally optimal. We discuss this methodology in detail and show examples in multi-label segmentation by minimal partitions and stereo estimation, where we demonstrate that the proposed graph discretization can reduce runtime as well as memory consumption of convex relaxations of matching problems by up to a factor of 10.

Related papers

• A Quantum Optimization Method for Geometric Constrained Image Segmentation [1.190902280324485]
  Quantum image processing is a growing field attracting attention from both the quantum computing and image processing communities. We propose a novel method in combining a graph-theoretic approach for optimal surface segmentation and hybrid quantum-classical optimization of the problem-directed graph. This work explores the use of quantum processors in image segmentation problems, which has important applications in medical image analysis.
  arXiv  Detail & Related papers  (2023-10-31T03:41:21Z)
• Representing Edge Flows on Graphs via Sparse Cell Complexes [6.74438532801556]
  We introduce the flow representation learning problem, i.e., the problem of augmenting the observed graph by a set of cells. We show that this problem is NP-hard and introduce an efficient approximation algorithm for its solution.
  arXiv  Detail & Related papers  (2023-09-04T14:30:20Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components [30.33731479053404]
  Minimizing a sum of simple submodular functions of limited support has numerous applications in machine learning. We develop fast techniques for instances where components in the sum are cardinality-based, meaning they depend only on the size of the input set. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem.
  arXiv  Detail & Related papers  (2021-10-28T02:36:55Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  We propose a graph kernel to compute more comprehensive similarity between paths and walks. We also combine it with optimal transport theory to extract more in-depth features of graphs. Our proposed method outperforms many state-of-the-art graph kernel methods.
  arXiv  Detail & Related papers  (2020-12-07T11:59:14Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• 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)
• Robust Submodular Minimization with Applications to Cooperative Modeling [0.0]
  This paper studies the problem of robust submodular Minimization subject to constraints. Constrained Submodular Minimization arises in several applications such as co-operative cuts in image segmentation, co-operative matchings in image correspondence, etc.
  arXiv  Detail & Related papers  (2020-01-25T20:40:37Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.