論文の概要: Extremely Greedy Equivalence Search

• arxiv url: http://arxiv.org/abs/2502.19551v1
• Date: Wed, 26 Feb 2025 20:45:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-28 14:59:04.309869
• Title: Extremely Greedy Equivalence Search
• Title（参考訳）: 極度にグリーディな等価検索
• Authors: Achille Nazaret, David Blei,
• Abstract要約: 我々は、eXtremely Greedy Equivalent Search (XGES)を提案し、Greedy Equivalence Search (GES)の検索戦略を改善する。 XGESは、エッジの挿入よりも早期にエッジを削除することを好んでおり、ローカルオプティマにおける検索終了の可能性を減らす。 XGESは正しいグラフの復元においてGESを一貫して上回り、10倍高速である。
• 参考スコア（独自算出の注目度）: 2.486161976966064
• License:
• Abstract: The goal of causal discovery is to learn a directed acyclic graph from data. One of the most well-known methods for this problem is Greedy Equivalence Search (GES). GES searches for the graph by incrementally and greedily adding or removing edges to maximize a model selection criterion. It has strong theoretical guarantees on infinite data but can fail in practice on finite data. In this paper, we first identify some of the causes of GES's failure, finding that it can get blocked in local optima, especially in denser graphs. We then propose eXtremely Greedy Equivalent Search (XGES), which involves a new heuristic to improve the search strategy of GES while retaining its theoretical guarantees. In particular, XGES favors deleting edges early in the search over inserting edges, which reduces the possibility of the search ending in local optima. A further contribution of this work is an efficient algorithmic formulation of XGES (and GES). We benchmark XGES on simulated datasets with known ground truth. We find that XGES consistently outperforms GES in recovering the correct graphs, and it is 10 times faster. XGES implementations in Python and C++ are available at https://github.com/ANazaret/XGES.
• Abstract（参考訳）: 因果探索の目標はデータから有向非巡回グラフを学ぶことである。 この問題の最もよく知られている方法の1つは、Greedy Equivalence Search (GES)である。 GESは、モデル選択基準を最大化するためにエッジを追加または削除することにより、グラフを漸進的に検索する。 無限のデータには強い理論的保証があるが、実際には有限データでは失敗することがある。 本稿では、まずGESの故障の原因のいくつかを特定し、特により密度の高いグラフにおいて局所的な最適値でブロックできることを見出した。 次に、理論的な保証を維持しつつ、GESの探索戦略を改善するための新しいヒューリスティックを含むeXtremely Greedy Equivalent Search (XGES)を提案する。 特に、XGESは、エッジの挿入よりも早期にエッジを削除することを好んでおり、ローカルオプティマにおける検索終了の可能性を減らす。 この研究のさらなる貢献は、XGES(およびGES)の効率的なアルゴリズムの定式化である。 我々は、シミュレーションデータセット上のXGESを既知の基底真理でベンチマークする。 XGESは正しいグラフの復元においてGESよりも一貫して優れており、10倍高速であることがわかった。 PythonとC++のXGES実装はhttps://github.com/ANazaret/XGESで入手できる。

関連論文リスト

• Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning? [54.44813218411879]
  グラフがネットワークにどのように適合するかを定量化するために、新しいメトリック、すなわちエラー通過率(EPR)を導入する。 理論的な結論とポジティブ・インセンティブ雑音のアイデアに触発されて、我々は新しいGCLアルゴリズム、エラー・パッシングに基づくグラフコントラスト学習(EPAGCL)を提案する。 EPRから得られる重みに基づいてエッジの追加とドロップによりビューを生成する。
  論文  参考訳（メタデータ） (2024-12-11T06:31:06Z)
• Efficient Graph Encoder Embedding for Large Sparse Graphs in Python [3.5374094795720854]
  グラフ埋め込み(GEE)は最も高速なグラフ埋め込み技術として示されており、様々なネットワークデータアプリケーションに適している。 GEEの改良版であるスパースGEEを提案し、スパース行列におけるゼロエントリの計算と保存を最適化し、ランニング時間をさらに向上する。 実験により, スパース版は, 大規模なスパースグラフをPythonで実装したオリジナルのGEEと比較して, 大幅な高速化を実現しており, スパースGEEは標準ラップトップで数分で数百万のエッジを処理することができることがわかった。
  論文  参考訳（メタデータ） (2024-06-06T03:49:34Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection [44.501646702560635]
  GADBenchは静的グラフにおける教師付き異常ノード検出専用のベンチマークツールである。 我々の主な発見は、GADタスクに適した最新のGNNよりも、単純な近傍集約によるツリーアンサンブルの方が優れたことだ。
  論文  参考訳（メタデータ） (2023-06-21T13:16:10Z)
• 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)
• Limited Query Graph Connectivity Test [14.108454811023465]
  エッジが2つの可能な状態(On/Off)を持つグラフを考える。 我々は,経路(オンエッジのみの構成)とカット(オフエッジのみ構成)を識別し,s-t接続性をテストすることを目指している。 我々のモデルは主に、ネットワーク内に攻撃経路が存在するかどうかを確かめる必要があるサイバーセキュリティユースケースによって動機付けられている。
  論文  参考訳（メタデータ） (2023-02-25T09:27:02Z)
• Source Free Unsupervised Graph Domain Adaptation [60.901775859601685]
  Unsupervised Graph Domain Adaptation (UGDA) はノード分類のラベル付けコストを削減するための実用的価値を示している。 既存のUGDAメソッドの多くは、ソースドメインのラベル付きグラフに大きく依存している。 現実のシナリオでは、ソースグラフはプライバシーの問題のためにアクセスできない。 我々は、Source Free Unsupervised Graph Domain Adaptation (SFUGDA) という新しいシナリオを提案する。
  論文  参考訳（メタデータ） (2021-12-02T03:18:18Z)
• Graph Traversal with Tensor Functionals: A Meta-Algorithm for Scalable Learning [29.06880988563846]
  Graph Traversal via Functionals (GTTF)はグラフアルゴリズムを埋め込むための統合メタアルゴリズムフレームワークである。 提案手法は多種多様であり,学習方法は偏りのない方法で行われ,期待通り,特定の実装が直接実行されるかのように学習を近似する。
  論文  参考訳（メタデータ） (2021-02-08T16:52:52Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  本稿では,新たなノードやエッジを自動的に拡張して,高密度サブグラフ内のラベル類似性を向上する,新しい前処理手法であるElectoral College(ELCO)を提案する。 テストされたすべての設定において、我々の手法はベースモデルの平均スコアを4.7ポイントの広いマージンで引き上げるとともに、常に最先端のモデルよりも優れています。
  論文  参考訳（メタデータ） (2020-06-10T14:48:48Z)

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

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