論文の概要: Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach

• arxiv url: http://arxiv.org/abs/2609.13836v1
• Date: Sat, 12 Sep 2026 09:44:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.563745
• Title: Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach
• Title（参考訳）: ソーシャルネットワークにおける影響最大化のためのグラフニューラルネットワーク:教師なし最小支配セットアプローチ
• Abstract要約: 最小支配集合問題 (MDS) は、ソーシャルネットワーク分析において重要な応用を持つ古典的なNPハード最適化問題である。 本稿では,MDS問題に対する新しい非教師付きGNNフレームワークを提案する。 本手法は,メタヒューリスティックベースラインの最大55倍,教師付き学習手法の最大14倍の高速化を実現する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Minimum Dominating Set (MDS) problem is a classic NP-hard combinatorial optimization problem with critical applications in social network analysis, including viral marketing, influence maximization, public health interventions, and information dissemination. Identifying a minimal set of influential individuals whose reach covers an entire social network is central to these applications, yet remains computationally challenging at scale. Graph neural networks (GNNs) have emerged as powerful tools for learning over graphs, and recent work explores their application to hard combinatorial problems. This paper presents a novel unsupervised GNN framework for the MDS problem that eliminates the need for ground-truth solutions during training. Trained on 12,000 synthetic graphs with diverse structural properties, our method achieves up to 55x faster inference than metaheuristic baselines and up to 14x faster inference than supervised learning approaches, while finding optimal or near-optimal dominating sets on real-world social network benchmarks. Our learned heuristic generalizes effectively to unseen graph distributions, demonstrating strong practical applicability for large-scale social network analysis.
• Abstract（参考訳）: Minimum Dominate Set (MDS) 問題は、バイラルマーケティング、影響力の最大化、公衆衛生介入、情報拡散など、ソーシャルネットワーク分析における重要な応用に対する古典的なNPハード組合せ最適化問題である。 ソーシャルネットワーク全体をカバーする最小限の影響力のある個人を特定することは、これらのアプリケーションの中心であるが、大規模に計算的に困難である。 グラフニューラルネットワーク(GNN)は、グラフ越しに学習するための強力なツールとして登場し、最近の研究で、その難解な組合せ問題への応用を探求している。 本稿では,MDS問題に対する新しい非教師付きGNNフレームワークを提案する。 多様な構造を持つ12,000の合成グラフを用いて学習し、メタヒューリスティックなベースラインよりも最大55倍、教師付き学習アプローチより最大14倍高速な推論を実現した。 学習したヒューリスティックはグラフ分布を効果的に一般化し、大規模ソーシャルネットワーク分析に強力な実用性を示す。

関連論文リスト

• Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs [81.39865232674413]
  グラフニューラルネットワーク(GNN)は、無線リソース割り当てのための強力なツールとして登場した。 この研究は、スパースランダム幾何グラフ(RGGs)から得られるグラフ上のGNNの転送可能性に関する理論的結果を確立する。
  論文  参考訳（メタデータ） (2026-06-02T15:42:14Z)
• A Distributed Training Architecture For Combinatorial Optimization [0.0]
  最適化のための分散グラフニューラルネットワーク(GNN)に基づくトレーニングフレームワークを提案する。 実大規模ソーシャルネットワークデータセットと合成された高複雑性グラフの両方で実験を行った。 我々のフレームワークは、ソリューションの品質と計算効率の両方において最先端のアプローチより優れています。
  論文  参考訳（メタデータ） (2025-11-12T12:22:10Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  スケーラブルで効果的なグラフ学習のためのマルチホップノード機能を適応的に融合する新しいフレームワークであるScaleGNNを提案する。 予測精度と計算効率の両面で,ScaleGNNは最先端のGNNよりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-22T14:05:11Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  グラフレベルグラフニューラルネットワーク(GNN)のための統一評価フレームワークを提案する。 このフレームワークは、さまざまなデータセットにわたるGNNを評価するための標準化された設定を提供する。 また,表現性の向上と一般化機能を備えた新しいGNNモデルを提案する。
  論文  参考訳（メタデータ） (2025-01-01T08:48:53Z)
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。 本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。 本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
  論文  参考訳（メタデータ） (2024-09-06T14:58:31Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  言語エージェントにおけるタスクプランニングは、大規模言語モデル(LLM)の開発とともに重要な研究トピックとして浮上している。 本稿では,課題計画のためのグラフ学習に基づく手法について検討する。 我々のグラフ学習への関心は、注意のバイアスと自己回帰的損失が、グラフ上の意思決定を効果的にナビゲートするLLMの能力を妨げているという理論的な発見に起因している。
  論文  参考訳（メタデータ） (2024-05-29T14:26:24Z)
• Network Interdiction Goes Neural [26.308933674471895]
  ネットワーク断面積問題は、2人のプレイヤーが関与する最適化問題である。 1つは、ネットワーク上の最適化問題を解決することを目的としており、もう1つは、最初のプレイヤーの目的を阻止するためにネットワークを変更することを目的としている。
  論文  参考訳（メタデータ） (2024-05-26T02:34:26Z)
• Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach [13.439099770154952]
  本稿では,従来のベストインフルエンスアルゴリズムよりも優れた性能を実現する効果的な強化学習モデルを提案する。 具体的には、グラフニューラルネットワークアルゴリズムをエンコーダとして、強化学習をデコーダとして組み合わせたエンドツーエンド学習フレームワークDREIMを設計する。
  論文  参考訳（メタデータ） (2023-09-09T14:19:00Z)
• ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning [4.266866385061998]
  本稿では、影響最大化(IM)問題に対処するため、新しいエンドツーエンドDRLフレームワークToupleGDDを提案する。 我々のモデルは、小さな予算でランダムに生成されたいくつかの小さなグラフで訓練され、様々な大きな予算の下で全く異なるネットワークでテストされる。
  論文  参考訳（メタデータ） (2022-10-14T03:56:53Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Graph Neural Networks for Wireless Communications: From Theory to Practice [10.61745503150249]
  グラフニューラルネットワーク(GNN)は、無線通信問題におけるグラフトポロジ(グラフトポロジ)というドメイン知識を効果的に活用することができる。 理論的保証のために、GNNは従来のニューラルネットワークに比べてトレーニングサンプルがはるかに少ない無線ネットワークにおいて、ほぼ最適性能を達成できることを示す。 設計ガイドラインでは,無線ネットワークにおける一般的な設計問題に適用可能な統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-03-21T08:39:44Z)
• FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks [39.86798194955807]
  ソーシャルネットワークで影響力のあるユーザーを見つけることは、多くの有用なアプリケーションにおいて根本的な問題である。 本稿では,IM の問題を予算制約付き d-hop 支配集合問題 (kdDSP) に還元する。 我々は、効率的な欲求戦略を教師なしで学習することでkdDSPを解決するために、統合機械学習(ML)フレームワークであるFastCoverを提案する。 FastCoverは、GNNの1つの前方伝播で計算されたノードのスコアから設定されたシード全体を決定する。
  論文  参考訳（メタデータ） (2021-10-31T10:49:21Z)

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

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