論文の概要: Exact Graph Learning via Integer Programming

• arxiv url: http://arxiv.org/abs/2601.20589v1
• Date: Wed, 28 Jan 2026 13:24:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.943201
• Title: Exact Graph Learning via Integer Programming
• Title（参考訳）: 整数プログラミングによる厳密なグラフ学習
• Authors: Lucas Kook, Søren Wengel Mogensen,
• Abstract要約: 非パラメトリックな条件独立性テストと整数計画に基づく非パラメトリックグラフ学習フレームワークを提案する。 提案手法は,様々なサイズのインスタンスやグラフに対して,既存の正確なグラフ学習手法よりも高速であることを示す。
• 参考スコア（独自算出の注目度）: 3.0556942817031456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning the dependence structure among variables in complex systems is a central problem across medical, natural, and social sciences. These structures can be naturally represented by graphs, and the task of inferring such graphs from data is known as graph learning or as causal discovery if the graphs are given a causal interpretation. Existing approaches typically rely on restrictive assumptions about the data-generating process, employ greedy oracle algorithms, or solve approximate formulations of the graph learning problem. As a result, they are either sensitive to violations of central assumptions or fail to guarantee globally optimal solutions. We address these limitations by introducing a nonparametric graph learning framework based on nonparametric conditional independence testing and integer programming. We reformulate the graph learning problem as an integer-programming problem and prove that solving the integer-programming problem provides a globally optimal solution to the original graph learning problem. Our method leverages efficient encodings of graphical separation criteria, enabling the exact recovery of larger graphs than was previously feasible. We provide an implementation in the openly available R package 'glip' which supports learning (acyclic) directed (mixed) graphs and chain graphs. From the resulting output one can compute representations of the corresponding Markov equivalence classes or weak equivalence classes. Empirically, we demonstrate that our approach is faster than other existing exact graph learning procedures for a large fraction of instances and graphs of various sizes. GLIP also achieves state-of-the-art performance on simulated data and benchmark datasets across all aforementioned classes of graphs.
• Abstract（参考訳）: 複雑なシステムにおける変数間の依存構造を学習することは、医学、自然科学、社会科学における中心的な問題である。 これらの構造は自然にグラフで表すことができ、データからそのようなグラフを推測するタスクは、グラフが因果解釈を受けた場合、グラフ学習または因果発見として知られている。 既存のアプローチは、典型的にはデータ生成プロセスに関する制限的な仮定に頼り、強欲なオラクルアルゴリズムを使用したり、グラフ学習問題の近似的な定式化を解いたりしている。 結果として、それらは中心的な仮定の違反に敏感であるか、世界的な最適解を保証できないかのいずれかである。 非パラメトリックな条件独立性テストと整数計画に基づく非パラメトリックグラフ学習フレームワークを導入することで、これらの制限に対処する。 グラフ学習問題を整数プログラミング問題として再構成し、整数プログラミング問題の解法が元のグラフ学習問題に対する世界的最適解であることを示す。 本手法は,グラフィカルな分離基準を効率的に符号化することで,以前実現可能であったよりも大きなグラフの正確な復元を可能にする。 オープンに利用可能なRパッケージ"glip"の実装を提供し、学習(非循環)指向(混合)グラフと連鎖グラフをサポートする。 結果の出力から、対応するマルコフ同値類や弱同値類の表現を計算することができる。 実験により,本手法は,多数のインスタンスやグラフに対して,既存の正確なグラフ学習法よりも高速であることを示す。 GLIPはまた、上記のグラフの全クラスにわたるシミュレーションデータとベンチマークデータセットの最先端のパフォーマンスも達成している。

関連論文リスト

• HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
  異種グラフ上のノードのマルチレベル埋め込みフレームワーク(HeteroMILE)を提案する。 HeteroMILEは、グラフを埋め込む前に、グラフのバックボーン構造を保ちながら、大きなグラフを小さなサイズに繰り返し調整する。 その後、ヘテロジニアスグラフ畳み込みニューラルネットワークを用いて、元のグラフへの粗い埋め込みを洗練する。
  論文  参考訳（メタデータ） (2024-03-31T22:22:10Z)
• The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure [18.00833762891405]
  Graph Lottery Ticket (GLT)仮説: グラフごとに非常に疎いバックボーンが存在する。 本研究は,グラフ学習アルゴリズムの性能に直接影響を及ぼす関心の指標を8つ研究する。 任意のグラフでこれらのGLTを見つけるための単純で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T00:24:44Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。 この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。 我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-05-31T11:04:53Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。 その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
  論文  参考訳（メタデータ） (2022-12-08T23:36:00Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Explanation Graph Generation via Pre-trained Language Models: An Empirical Study with Contrastive Learning [84.35102534158621]
  エンドツーエンドで説明グラフを生成する事前学習言語モデルについて検討する。 本稿では,ノードとエッジの編集操作によるグラフ摂動の簡易かつ効果的な方法を提案する。 提案手法は,説明グラフの構造的精度と意味的精度を両立させる。
  論文  参考訳（メタデータ） (2022-04-11T00:58:27Z)
• Graph Pooling via Coarsened Graph Infomax [9.045707667111873]
  本稿では,各プーリング層の入力と粗いグラフ間の相互情報を最大化するために,粗いグラフプールインフォマキシング(cgi)を提案する。 相互情報ニューラルを実現するために,コントラスト学習を適用し,正負のサンプルを学習するための自己照査に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-04T03:50:21Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Graph topology inference benchmarks for machine learning [16.857405938139525]
  本稿では,グラフ推論手法の相対的メリットと限界を明らかにするために,いくつかのベンチマークを導入する。 我々はまた、文学において最も顕著な技法のいくつかを対比している。
  論文  参考訳（メタデータ） (2020-07-16T09:40:32Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Learning Product Graphs Underlying Smooth Graph Signals [15.023662220197242]
  本稿では,製品グラフの形式で与えられるデータから構造化グラフを学習する方法を考案する。 この目的のために、まずグラフ学習問題は線形プログラムとして表され、これは(平均的に)最先端のグラフ学習アルゴリズムより優れている。
  論文  参考訳（メタデータ） (2020-02-26T03:25:15Z)

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

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