論文の概要: Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search

• arxiv url: http://arxiv.org/abs/2311.03583v1
• Date: Mon, 6 Nov 2023 22:29:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-11-08 17:41:46.493465
• Title: Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
• Title（参考訳）: AlphaZero と Tabu Search による超大型グラフの探索
• Authors: Abbas Mehrabian, Ankit Anand, Hyunjik Kim, Nicolas Sonnerat, Matej Balog, Gheorghe Comanici, Tudor Berariu, Andrew Lee, Anian Ruoss, Anna Bulanova, Daniel Toyama, Sam Blackwell, Bernardino Romera Paredes, Petar Veli\v{c}kovi\'c, Laurent Orseau, Joonkyung Lee, Anurag Murty Naredla, Doina Precup and Adam Zsolt Wagner
• Abstract要約: この研究は、1975年のエルドホスの予想から着想を得た中心極端グラフ理論の問題を研究する。 それは、与えられた大きさ(ノード数)のグラフを見つけることを目的としており、3サイクルや4サイクルを必要とせずに、エッジの数を最大化する。
• 参考スコア（独自算出の注目度）: 35.11415228076876
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work studies a central extremal graph theory problem inspired by a 1975 conjecture of Erd\H{o}s, which aims to find graphs with a given size (number of nodes) that maximize the number of edges without having 3- or 4-cycles. We formulate this problem as a sequential decision-making problem and compare AlphaZero, a neural network-guided tree search, with tabu search, a heuristic local search method. Using either method, by introducing a curriculum -- jump-starting the search for larger graphs using good graphs found at smaller sizes -- we improve the state-of-the-art lower bounds for several sizes. We also propose a flexible graph-generation environment and a permutation-invariant network architecture for learning to search in the space of graphs.
• Abstract（参考訳）: この研究は、1975年のerd\h{o}sの予想に触発された中心極値グラフ理論の問題を研究するもので、与えられた大きさ(ノード数)のグラフを見つけることを目的としており、3サイクルまたは4サイクルを持つことなく辺の数を最大化している。 この問題を逐次意思決定問題として定式化し,ニューラルネットワーク誘導木探索であるalphazeroと,ヒューリスティック局所探索法であるtabu searchを比較した。 どちらの方法も、カリキュラムを導入することによって、より小さなサイズのよいグラフを使って、より大きなグラフの検索をjump-startする -- いくつかのサイズで最先端の下限を改善する。 また,グラフ空間における探索学習のためのフレキシブルなグラフ生成環境と置換不変ネットワークアーキテクチャを提案する。

関連論文リスト

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。 これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。 4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-05-31T10:38:04Z)
• GraphPAS: Parallel Architecture Search for Graph Neural Networks [12.860313120881996]
  グラフニューラルネットワークのための並列グラフアーキテクチャ探索(GraphPAS)フレームワークを提案する。 GraphPASでは、共有ベースの進化学習を設計することで、検索空間を並列に探索する。 実験結果から,GraphPASは最先端モデルの効率と精度を同時に向上することが示された。
  論文  参考訳（メタデータ） (2021-12-07T02:55:24Z)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。 アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
  論文  参考訳（メタデータ） (2021-09-13T13:17:41Z)
• A step towards neural genome assembly [0.0]
  我々はMPNNモデルを最大集約器で訓練し、グラフ単純化のためのいくつかのアルゴリズムを実行する。 アルゴリズムがうまく学習され、トレーニングで使用されるグラフの最大20倍の大きさのグラフにスケールできることを示す。
  論文  参考訳（メタデータ） (2020-11-10T10:12:19Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。