論文の概要: A Unified Framework for Integer Programming Formulation of Graph Matching Problems
- arxiv url: http://arxiv.org/abs/2406.07666v1
- Date: Tue, 11 Jun 2024 19:20:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-13 21:25:46.284596
- Title: A Unified Framework for Integer Programming Formulation of Graph Matching Problems
- Title（参考訳）: グラフマッチング問題の整数計画定式化のための統一フレームワーク
- Authors: Bahram Alidaee, Haibo Wang, Hugh Sloan,
- Abstract要約: 本研究の目的は,グラフマッチング問題のIP定式化のための統一的なフレームワークを提供することである。
このフレームワークには、文献における様々なグラフ最適化の問題が含まれている。
- 参考スコア（独自算出の注目度）: 2.994117664413568
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph theory has been a powerful tool in solving difficult and complex problems arising in all disciplines. In particular, graph matching is a classical problem in pattern analysis with enormous applications. Many graph problems have been formulated as a mathematical program and then solved using exact, heuristic, and/or approximated-guaranteed procedures. On the other hand, graph theory has been a powerful tool in visualizing and understanding complex mathematical programming problems, especially integer programs. Formulating a graph problem as a natural integer program (IP) is often a challenging task. However, an IP formulation of the problem has many advantages. Several researchers have noted the need for natural IP formulation of graph theoretic problems. The present study aims to provide a unified framework for IP formulation of graph-matching problems. Although there are many surveys on graph matching problems, none is concerned with IP formulation. This paper is the first to provide a comprehensive IP formulation for such problems. The framework includes a variety of graph optimization problems in the literature. While these problems have been studied by different research communities, however, the framework presented here helps to bring efforts from different disciplines to tackle such diverse and complex problems. We hope the present study can significantly help to simplify some of the difficult problems arising in practice, especially in pattern analysis.
- Abstract（参考訳）: グラフ理論は、あらゆる分野における困難で複雑な問題を解決する強力なツールである。
特に、グラフマッチングは、膨大な応用を伴うパターン解析における古典的な問題である。
多くのグラフ問題は数学的プログラムとして定式化され、正確な、ヒューリスティックな、あるいは近似された保証された手順を用いて解かれる。
一方、グラフ理論は複雑な数学的プログラミング問題、特に整数プログラムを可視化し理解するための強力なツールである。
グラフ問題を自然整数プログラム(IP)として定式化することは、しばしば難しい課題である。
しかし、IPの定式化には多くの利点がある。
数人の研究者が、グラフ理論問題の自然なIP定式化の必要性について言及している。
本研究の目的は,グラフマッチング問題のIP定式化のための統一的なフレームワークを提供することである。
グラフマッチング問題に関する多くの調査があるが、IPの定式化には関心がない。
本稿では,このような問題に対する包括的IP定式化を初めて提供する。
このフレームワークには、文献における様々なグラフ最適化の問題が含まれている。
しかしながら、これらの問題は異なる研究コミュニティによって研究されてきたが、ここで提示される枠組みは、このような多様で複雑な問題に取り組むために、異なる分野からの取り組みを促進するのに役立っている。
本研究は,特にパターン解析において,実際に発生する難題のいくつかを単純化する上で,極めて有効であることを期待する。
関連論文リスト
- When Graph Data Meets Multimodal: A New Paradigm for Graph Understanding
and Reasoning [54.84870836443311]
本稿では,画像エンコーディングとマルチモーダル技術を統合することで,グラフデータの理解と推論を行う新しいパラダイムを提案する。
このアプローチは, GPT-4Vの高度な機能を利用して, 命令応答形式によるグラフデータの理解を可能にする。
研究は、このパラダイムを様々なグラフタイプで評価し、特に中国のOCRパフォーマンスと複雑な推論タスクにおいて、モデルの強みと弱みを強調した。
論文 参考訳（メタデータ） (2023-12-16T08:14:11Z) - Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。
自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
論文 参考訳（メタデータ） (2023-05-17T08:29:21Z) - Graph Pooling for Graph Neural Networks: Progress, Challenges, and
Opportunities [128.55790219377315]
グラフニューラルネットワークは多くのグラフレベルのタスクの主要なアーキテクチャとして登場した。
グラフプーリングは、グラフ全体の全体的グラフレベル表現を得るためには不可欠である。
論文 参考訳（メタデータ） (2022-04-15T04:02:06Z) - A Survey on Machine Learning Solutions for Graph Pattern Extraction [17.911041497412132]
本稿では,機械学習手法を用いて取り組んだ5つの有名なサブグラフ問題について概説する。
これらは、部分グラフ同型(カウントとマッチングの両方)、最大共通部分グラフ、コミュニティ検出、コミュニティ検索問題である。
我々は,各問題に対する非学習型アルゴリズムについて検討し,簡単な議論を行う。
論文 参考訳（メタデータ） (2022-04-03T11:54:22Z) - Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement
Learning [1.3534683694551497]
近年,NP-hardグラフ問題に対する解を見つけるためのディープラーニング技術が注目されている。
本稿では,グラフに基づく動的最適化問題の解法を学ぶために,GTA-RL (Graph Temporal Attention with Reinforcement Learning) という新しいアーキテクチャを提案する。
論文 参考訳（メタデータ） (2022-01-13T11:36:05Z) - Deep graph matching meets mixed-integer linear programming: Relax at
your own risk ? [8.05409526074409]
グラフマッチング問題のMILP定式化を統合する手法を提案する。
同様のアプローチは、グラフマッチング解決器の最適保証と品質レベルの導入によって導かれる。
実験により,いくつかの理論的知見が得られ,深部グラフマッチング手法の方向性を導出する。
論文 参考訳（メタデータ） (2021-08-01T08:29:55Z) - GeoQA: A Geometric Question Answering Benchmark Towards Multimodal
Numerical Reasoning [172.36214872466707]
我々は、テキスト記述、視覚図、定理知識の包括的理解を必要とする幾何学的問題を解くことに注力する。
そこで本研究では,5,010の幾何学的問題を含む幾何学的質問応答データセットGeoQAを提案する。
論文 参考訳（メタデータ） (2021-05-30T12:34:17Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time [12.43303621344215]
専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。
本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。
最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
論文 参考訳（メタデータ） (2020-06-06T01:35:45Z) - Learning Combinatorial Optimization on Graphs: A Survey with
Applications to Networking [2.817395666721831]
グラフ上の最適化問題を解くための既存のアプローチは、アルゴリズムで各問題を設計する必要がある。
我々は,通信分野に特化して,学習に関わる構造を整理し,比較する。
論文 参考訳（メタデータ） (2020-05-22T09:45:36Z) - Machine Number Sense: A Dataset of Visual Arithmetic Problems for
Abstract and Relational Reasoning [95.18337034090648]
文法モデルを用いて自動生成される視覚的算術問題からなるデータセット、MNS(Machine Number Sense)を提案する。
これらの視覚的算術問題は幾何学的フィギュアの形をしている。
我々は、この視覚的推論タスクのベースラインとして、4つの主要なニューラルネットワークモデルを用いて、MNSデータセットをベンチマークする。
論文 参考訳（メタデータ） (2020-04-25T17:14:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。