Joint Graph Decomposition & Node Labeling: Problem, Algorithms, Applications
We state a combinatorial optimization problem whose feasible solutions define both a decomposition and a node labeling of a given graph. This problem offers a common mathematical abstraction of seemingly unrelated computer vision tasks, including instance-separating semantic segmentation, articulated human body pose estimation and multiple object tracking. Conceptually, it generalizes the unconstrained integer quadratic program and the minimum cost lifted multicut problem, both of which are NP-hard. In order to find feasible solutions efficiently, we define two local search algorithms that converge monotonously to a local optimum, offering a feasible solution at any time. To demonstrate the effectiveness of these algorithms in tackling computer vision tasks, we apply them to instances of the problem that we construct from published data, using published algorithms. We report state-of-the-art application-specific accuracy in the three above-mentioned applications.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationMultiple Object TrackingObject TrackingPose EstimationSemantic SegmentationSimilar Papers 제목 키워드 기반
Joint Graph Decomposition and Node Labeling: Problem, Algorithms, Applications
We state a combinatorial optimization problem whose feasible solutions define both a decomposition and a node labeling of a given graph. This problem offers a common mathematical abstraction of seemingly unrelated comput…
Combinatorial OptimizationMultiple Object TrackingObject TrackingPose Estimation+1Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
In this paper, we provide a theory of using graph neural networks (GNNs) for multi-node representation learning (where we are interested in learning a representation for a set of more than one node, such as link). We kno…
General ClassificationGraph ClassificationLink PredictionLink Property Prediction+2Improving Graph Neural Networks on Multi-node Tasks with Labeling Tricks
In this paper, we provide a theory of using graph neural networks (GNNs) for \textit{multi-node representation learning}, where we are interested in learning a representation for a set of more than one node such as a lin…
Hyperedge PredictionLink PredictionPredictionRepresentation LearningJoint Embedding of Meta-Path and Meta-Graph for Heterogeneous Information Networks
Meta-graph is currently the most powerful tool for similarity search on heterogeneous information networks,where a meta-graph is a composition of meta-paths that captures the complex structural information. However, curr…
Network EmbeddingTensor DecompositionLost in Serialization: Invariance and Generalization of LLM Graph Reasoners
While promising, graph reasoners based on Large Language Models (LLMs) lack built-in invariance to symmetries in graph representations. Operating on sequential graph serializations, LLMs can produce different outputs und…