論文の概要: Finding Maximum Independent Sets in Dynamic Graphs using Unsupervised Learning

• arxiv url: http://arxiv.org/abs/2505.13754v1
• Date: Mon, 19 May 2025 21:58:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-21 14:49:52.552901
• Title: Finding Maximum Independent Sets in Dynamic Graphs using Unsupervised Learning
• Title（参考訳）: 教師なし学習を用いた動的グラフにおける最大独立集合の探索
• Authors: Devendra Parkar, Anya Chaturvedi, Andréa W. Richa, Joshua J. Daymude,
• Abstract要約: 動的グラフに最大独立集合(MaxIS)を求めるための教師なし学習モデルを提案する。 本手法は,グラフニューラルネットワーク(GNN)からの構造化学習と,学習した分散更新機構を組み合わせる。 本モデルは,学習に用いたグラフよりも100倍大きいグラフを一般化し,グリーディ手法と商用混合整数計画法の両方に匹敵する性能を達成している。
• 参考スコア（独自算出の注目度）: 2.5749046466046903
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the first unsupervised learning model for finding Maximum Independent Sets (MaxIS) in dynamic graphs where edges change over time. Our method combines structural learning from graph neural networks (GNNs) with a learned distributed update mechanism that, given an edge addition or deletion event, modifies nodes' internal memories and infers their MaxIS membership in a single, parallel step. We parameterize our model by the update mechanism's radius and investigate the resulting performance-runtime tradeoffs for various dynamic graph topologies. We evaluate our model against state-of-the-art MaxIS methods for static graphs, including a mixed integer programming solver, deterministic rule-based algorithms, and a heuristic learning framework based on dynamic programming and GNNs. Across synthetic and real-world dynamic graphs of 100-10,000 nodes, our model achieves competitive approximation ratios with excellent scalability; on large graphs, it significantly outperforms the state-of-the-art heuristic learning framework in solution quality, runtime, and memory usage. Our model generalizes well on graphs 100x larger than the ones used for training, achieving performance at par with both a greedy technique and a commercial mixed integer programming solver while running 1.5-23x faster than greedy.
• Abstract（参考訳）: 本稿では,エッジが時間とともに変化する動的グラフにおいて,最大独立集合(MaxIS)を求めるための教師なし学習モデルを提案する。 本手法は,グラフニューラルネットワーク(GNN)からの構造化学習と,エッジの追加や削除イベントを与えられたノードの内部記憶を修正し,MaxISメンバシップをひとつの並列ステップで推論する分散更新機構を組み合わせる。 更新メカニズムの半径でモデルをパラメータ化し、様々な動的グラフトポロジのパフォーマンス-実行時のトレードオフについて検討する。 我々は,静的グラフに対する最新のMaxIS法に対して,混合整数計画解法,決定論的ルールベースアルゴリズム,動的プログラミングとGNNに基づくヒューリスティック学習フレームワークなどのモデルを評価する。 100～10,000ノードの合成および実世界の動的グラフ全体にわたって、我々のモデルは優れたスケーラビリティで競合近似比を達成し、大規模なグラフでは、ソリューションの品質、実行時、メモリ使用量において最先端のヒューリスティック学習フレームワークよりも大幅に優れています。 本モデルでは,グリーディよりも1.5～23倍高速に動作しながら,グリーディ法と商用混合整数計画法の両方と同等の性能を達成し,学習用グラフの100倍の精度で一般化する。

関連論文リスト

• LLM-Based Multi-Agent Systems are Scalable Graph Generative Models [73.28294528654885]
  GraphAgent-Generator (GAG) は動的でテキスト対応のソーシャルグラフ生成のための新しいシミュレーションベースのフレームワークである。 GAGは、ゼロショットソーシャルグラフ生成のための時間ノードとエッジ生成プロセスをシミュレートする。 得られたグラフは7つの主要なマクロ的ネットワーク特性に付着し、微視的グラフ構造測定において11%の改善が達成される。
  論文  参考訳（メタデータ） (2024-10-13T12:57:08Z)
• Efficient and Effective Implicit Dynamic Graph Neural Network [42.49148111696576]
  Indicit Dynamic Graph Neural Network (IDGNN) は動的グラフのための新しい暗黙的ニューラルネットワークである。 IDGNNの鍵となる特徴は、それが実証的に良好である、すなわち、固定点表現を持つことが理論的に保証されていることである。
  論文  参考訳（メタデータ） (2024-06-25T19:07:21Z)
• GraphFM: A Comprehensive Benchmark for Graph Foundation Model [33.157367455390144]
  ファンデーション・モデル(FM)は、人工知能システムの開発のための一般的なクラスである。 FMの基礎として自己教師型学習の研究が盛んに行われたが、いくつかの顕著な問題が続いている。 下流タスクにおける一般化能力の程度は未だ不明である。 これらのモデルが大規模なデータセットにどの程度効果的にスケールできるかは不明だ。
  論文  参考訳（メタデータ） (2024-06-12T15:10:44Z)
• Instant Graph Neural Networks for Dynamic Graphs [18.916632816065935]
  Instant Graph Neural Network (InstantGNN) を提案する。 提案手法は,時間を要する反復計算を回避し,表現の即時更新と即時予測を可能にする。 本モデルでは,既存手法よりも高精度かつ高次精度で最先端の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-03T03:27:42Z)
• Dynamic Graph Learning-Neural Network for Multivariate Time Series Modeling [2.3022070933226217]
  静的および動的グラフ学習ニューラルネットワーク(GL)という新しいフレームワークを提案する。 モデルはそれぞれ、データから静的グラフ行列と動的グラフ行列を取得し、長期パターンと短期パターンをモデル化する。 ほぼすべてのデータセットで最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2021-12-06T08:19:15Z)
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction [123.20238648121445]
  我々は、新しい自己教師型学習フレームワーク、グラフ情報支援ノード機能exTraction (GIANT)を提案する。 GIANT は eXtreme Multi-label Classification (XMC) 形式を利用しており、これはグラフ情報に基づいた言語モデルの微調整に不可欠である。 我々は,Open Graph Benchmarkデータセット上での標準GNNパイプラインよりもGIANTの方が優れた性能を示す。
  論文  参考訳（メタデータ） (2021-10-29T19:55:12Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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