論文の概要: Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs

• arxiv url: http://arxiv.org/abs/2209.14825v1
• Date: Thu, 29 Sep 2022 14:41:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 18:14:19.766846
• Title: Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs
• Title（参考訳）: コミュニティ検出の効率化のための品質の取引--グラフ間のインダクティブ手法
• Authors: Meng Qin, Chaorui Zhang, Bo Bai, Gong Zhang, Dit-Yan Yeung
• Abstract要約: 本稿では,NP難題を解決するために,システムやシナリオのグラフにまたがる帰納的コミュニティ検出手法を提案する。 ICDは、まず、システムの主要な特性を捉えるために、履歴グラフ上の逆双対GNNのオフライントレーニングを行う。 トレーニングされたモデルは、追加の最適化なしに、オンラインCD用の新しい見えないグラフに直接一般化される。
• 参考スコア（独自算出の注目度）: 25.629858572098755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD). Due to the NP-hardness, to balance the CD quality and efficiency remains a challenge. Most existing CD methods are transductive, which are independently optimized only for the CD on a single graph. Some of these methods use advanced machine learning techniques to obtain high-quality CD results but usually have high complexity. Other approaches use fast heuristic approximation to ensure low runtime but may suffer from quality degradation. In contrast to these transductive methods, we propose an alternative inductive community detection (ICD) method across graphs of a system or scenario to alleviate the NP-hard challenge. ICD first conducts the offline training of an adversarial dual GNN on historical graphs to capture key properties of the system. The trained model is then directly generalized to new unseen graphs for online CD without additional optimization, where a better trade-off between quality and efficiency can be achieved. ICD can also capture the permutation invariant community labels in the offline training and tackle the online CD on new graphs with non-fixed number of nodes and communities. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant trade-off between quality and efficiency over various baselines.
• Abstract（参考訳）: 多くのネットワークアプリケーションは、np-hard combinatorial optimization problem of community detection (cd)として定式化することができる。 NP硬度のため、CDの品質と効率のバランスをとることは依然として課題である。 既存のほとんどのCDメソッドはトランスダクティブであり、単一のグラフ上のCDにのみ独立に最適化されている。 これらの手法のいくつかは高度な機械学習技術を用いて高品質なCD結果を得るが、通常は複雑である。 他のアプローチでは、高速なヒューリスティック近似を使用してランタイムを低くするが、品質劣化に悩まされる可能性がある。 これらのトランスダクティブ手法とは対照的に,np-hardチャレンジを緩和するために,システムやシナリオのグラフにまたがる帰納的コミュニティ検出(icd)手法を提案する。 ICDは、まず、システムの主要な特性を捉えるために、履歴グラフ上の逆双対GNNのオフライントレーニングを行う。 トレーニングされたモデルは、さらに最適化することなく、オンラインcd用の新しい未認識グラフに直接一般化され、品質と効率のトレードオフが達成される。 ICDはまた、オフライントレーニングにおける置換不変コミュニティラベルをキャプチャし、修正されていないノード数とコミュニティを持つ新しいグラフ上のオンラインCDに取り組むこともできる。 一連のベンチマークの実験では、ICDは様々なベースラインに対して品質と効率の間に大きなトレードオフを達成できることを示した。

関連論文リスト

• IC/DC: Surpassing Heuristic Solvers in Combinatorial Optimization with Diffusion Models [6.260482448679642]
  IC/DCは,教師なしの学習型最適化フレームワークである。 IC/DCは2つの異なる項目を含む問題の解決に特化しており、有効な解を生成するのに問題固有の探索プロセスは必要ない。 私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。
  論文  参考訳（メタデータ） (2024-10-15T06:53:30Z)
• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。 これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。 我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
  論文  参考訳（メタデータ） (2024-07-22T23:24:03Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。 この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。 D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
  論文  参考訳（メタデータ） (2024-07-09T11:44:58Z)
• Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence [2.1348070823841363]
  本稿では,証明可能な堅牢性,証明可能な最適性,保証された収束性を備えた3進OCDフレームワークを開発する。 提案アルゴリズムは、完全に非同期な分散方式で実現でき、単一のサーバにデータを送信する必要がなくなる。 Triadic-OCDの非漸近収束特性は理論的に解析され、$epsilon$-Optimal点を達成するための複雑さが導出される。
  論文  参考訳（メタデータ） (2024-05-03T10:10:11Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。 まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
  論文  参考訳（メタデータ） (2022-08-11T22:27:22Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Few-Shot Electronic Health Record Coding through Graph Contrastive Learning [64.8138823920883]
  我々は,グラフベースのEHRコーディングフレームワークであるCoGraphを用いて,頻繁かつ希少なICD符号の性能向上を図る。 CoGraphは、異なるICDコードからHEWEグラフ間の類似点と相似点を学習し、それら間で情報を転送する。 2つのグラフコントラスト学習スキームであるGSCLとGECLは、HEWEグラフ構造を利用して、転送可能な特徴を符号化する。
  論文  参考訳（メタデータ） (2021-06-29T14:53:17Z)
• Cogradient Descent for Dependable Learning [64.02052988844301]
  双線形最適化問題に対処するために,CoGDアルゴリズムに基づく信頼度の高い学習法を提案する。 CoGDは、ある変数がスパーシティ制約を持つ場合の双線形問題を解くために導入された。 また、特徴と重みの関連を分解するためにも使用できるため、畳み込みニューラルネットワーク(CNN)をより良く訓練するための我々の手法をさらに一般化することができる。
  論文  参考訳（メタデータ） (2021-06-20T04:28:20Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Bi-level Off-policy Reinforcement Learning for Volt/VAR Control Involving Continuous and Discrete Devices [2.079959811127612]
  Volt/Varコントロールでは、スロータイムスケールの離散デバイス(STDD)と高速タイムスケールの連続デバイス(FTCD)の両方が関与する。 従来の最適化手法はシステムの正確なモデルに強く依存しているが、モデル化に対する耐え難い努力のために実用的でない場合もある。 本論文では, この問題をモデルフリーで解くために, RL(バイレベル・オフポリシ強化学習)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-13T02:22:43Z)

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

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