WeaveNet: A Differentiable Solver for Non-linear Assignment Problems
Assignment, a task to match a limited number of elements, is a fundamental problem in informatics. Traditionally, non-linear assignment is discussed as a combinatorial optimization problem with its calculation complexity. On the other hand, it is often a sub-problem of image processing tasks, such as 3D point cloud matching. This paper proposes WeaveNet, a differentiable solver for diverse non-linear assignment problems. Traditional graph convolutional networks (GCNs) suffer from an over-smoothing problem when characterizing nodes with their relationship. WeaveNet overcomes this problem by forwarding edge-wise features at each layer rather than aggregated node features. To deal with the exponentially large input space of combinatorial optimization problems, we designed WeaveNet to be highly parameter efficient while characterizing edges through stacked set-encoder with cross-concatenation operations. Experimental results show that WeaveNet approximates two strongly NP-hard variants of stable matching in a comparative performance with the gold standard hand-crafted algorithms under the limited size of problem instances. We have also confirmed that it can boost 3D point cloud matching performance significantly.
Code (0)
등록된 구현이 없습니다.
Tasks
3D Point Cloud MatchingCombinatorial OptimizationSimilar Papers 제목 키워드 기반
WeaveNet for Approximating Assignment Problems
Assignment, a task to match a limited number of elements, is a fundamental problem in informatics. Many assignment problems have no exact solvers due to their NP-hardness or incomplete input, and their approximation alg…
GLAN: A Graph-based Linear Assignment Network
Differentiable solvers for the linear assignment problem (LAP) have attracted much research attention in recent years, which are usually embedded into learning frameworks as components. However, previous algorithms, with…
Multi-Object TrackingObject TrackingTurboSAT: Gradient-Guided Boolean Satisfiability Accelerated on GPU-CPU Hybrid System
While accelerated computing has transformed many domains of computing, its impact on logical reasoning, specifically Boolean satisfiability (SAT), remains limited. State-of-the-art SAT solvers rely heavily on inherently …
Logical ReasoningMatSat: a matrix-based differentiable SAT solver
We propose a new approach to SAT solving which solves SAT problems in vector spaces as a cost minimization problem of a non-negative differentiable cost function J^sat. In our approach, a solution, i.e., satisfying assig…
WeaveNet for Approximating Two-sided Matching Problems
Matching, a task to optimally assign limited resources under constraints, is a fundamental technology for society. The task potentially has various objectives, conditions, and constraints; however, the efficient neural n…
Efficient Neural NetworkGraph Neural Network