論文の概要: Refutation of Spectral Graph Theory Conjectures with Search Algorithms)

• arxiv url: http://arxiv.org/abs/2409.18626v1
• Date: Fri, 27 Sep 2024 10:55:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-01 19:54:56.558039
• Title: Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
• Title（参考訳）: 探索アルゴリズムによるスペクトルグラフ理論の難解化
• Authors: Milo Roucairol, Tristan Cazenave,
• Abstract要約: 本稿では,探索アルゴリズムを用いて,スペクトルグラフ理論の予測に対する潜在的に大きな反例を数秒で見つけることを提案する。 すでにGraffitiの予想に反論している13のうち、我々のアルゴリズムは12秒で反論できる。
• 参考スコア（独自算出の注目度）: 3.860785927193332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement learning. Exhaustive generation is limited by the size of the generated graphs and deep reinforcement learning takes hours or days to refute a conjecture. We propose to use search algorithms to address these shortcomings to find potentially large counter-examples to spectral graph theory conjectures in seconds. We apply a wide range of search algorithms to a selection of conjectures from Graffiti. Out of 13 already refuted conjectures from Graffiti, our algorithms are able to refute 12 in seconds. We also refute conjecture 197 from Graffiti which was open until now.
• Abstract（参考訳）: 我々はスペクトルグラフ理論予想の自動解法に興味を持っている。 既存の研究の多くは、サイズが制限されたグラフの網羅的な生成や、深い強化学習によってこの問題に対処している。 被曝生成は生成されたグラフのサイズによって制限され、深層強化学習は予想を否定するのに数時間または数日かかる。 本稿では,これらの欠点に対処する探索アルゴリズムを用いて,スペクトルグラフ理論の予想に対する潜在的に大きな反例を数秒で見つけることを提案する。 本研究では,Graffiti の予想に対して,幅広い探索アルゴリズムを適用した。 すでにGraffitiの予想に反論している13のうち、我々のアルゴリズムは12秒で反論できる。 また、これまで開いていたGraffiti から予想 197 を否定する。

関連論文リスト

• Local Vertex Colouring Graph Neural Networks [8.11828056160271]
  Wesfeiler-Lehman (1-WL) フレームワークを超えて拡張されたグラフ表現を,従来の検索アルゴリズムで効率的に計算できることが示される。 また,2つの探索戦略,幅優先探索と深さ優先探索に基づく新しいタイプのGNNも開発している。
  論文  参考訳（メタデータ） (2024-03-10T03:59:24Z)
• Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search [31.68823192070739]
  この研究は、1975年のエルドホスの予想から着想を得た中心極端グラフ理論の問題を研究する。 それは、与えられた大きさ(ノード数)のグラフを見つけることを目的としており、3サイクルや4サイクルを必要とせずに、エッジの数を最大化する。
  論文  参考訳（メタデータ） (2023-11-06T22:29:55Z)
• Projecting infinite time series graphs to finite marginal graphs using number theory [15.711918159136387]
  本研究では,有限時間ウィンドウ上で,連続エッジを持つ無限時系列グラフを境界グラフィカルモデルに投影する手法を開発した。 本論文は,理論的な基礎と手法に依存しない,様々な因果推論手法の一般化に向けて重要な一歩を踏み出したものである。
  論文  参考訳（メタデータ） (2023-10-09T08:45:06Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。 幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。 次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
  論文  参考訳（メタデータ） (2023-05-05T14:04:52Z)
• 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)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• CLEAR: Generative Counterfactual Explanations on Graphs [60.30009215290265]
  グラフ上での対実的説明生成の問題について検討する。 グラフに関する反実的な説明を調査する研究はいくつかあるが、この問題の多くの課題はまだ十分に適応されていない。 本稿では,グラフレベルの予測モデルに対して,グラフ上の反実的説明を生成するための新しいフレームワークCLEARを提案する。
  論文  参考訳（メタデータ） (2022-10-16T04:35:32Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Could you give me a hint? Generating inference graphs for defeasible reasoning [28.138055274299866]
  哲学やAI文学でよく使われる手法は、推論グラフをサポートする手作業による議論である。 本稿では,他のNLPタスクからの移動学習を通じて,このような推論グラフを自動生成する。 このタスクにおける人間の正確性は、生成されたグラフのコンサルティングによって20%向上する。
  論文  参考訳（メタデータ） (2021-05-12T04:04:10Z)
• Grale: Designing Networks for Graph Learning [68.23038997141381]
  我々は,数十億のノードを持つグラフのグラフ設計問題に対処するために,スケーラブルなGraleを提案する。 グレールは、(潜在的に弱い)類似性の異なる測度を融合して、そのノード間の高いタスク固有のホモフィリーを示すグラフを作成する。 Googleでは、数千億のノードを持つデータセットや、数十兆の潜在的なエッジを含む、20以上の異なる産業環境にGraleをデプロイしています。
  論文  参考訳（メタデータ） (2020-07-23T13:25:36Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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