論文の概要: 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は様々なベースラインに対して品質と効率の間に大きなトレードオフを達成できることを示した。
関連論文リスト
- Interacting Particle Systems on Networks: joint inference of the network
and the interaction kernel [8.535430501710712]
エージェント間の相互作用のルールを決定するネットワークとシステムの重み行列を推論する。
我々は2つのアルゴリズムを使用する: 1つは演算子回帰と呼ばれる新しいアルゴリズムで、最小2乗のデータを交互に更新する。
どちらのアルゴリズムも、識別可能性と適正性を保証するスケーラブルな条件である。
論文 参考訳(メタデータ) (2024-02-13T12:29:38Z) - Graph Neural Ordinary Differential Equations-based method for
Collaborative Filtering [40.39806741673175]
グラフニューラル正規微分方程式を用いた協調フィルタリング法(GODE-CF)を提案する。
本手法は,GCN層1つまたは2つの層が取得した情報を利用して最終埋め込みを推定する。
提案したGODE-CFモデルは,従来のGCNモデルよりもいくつかの利点があることを示す。
論文 参考訳(メタデータ) (2023-11-21T03:42:15Z) - An Accelerated Doubly Stochastic Gradient Method with Faster Explicit
Model Identification [97.28167655721766]
本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。
まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
論文 参考訳(メタデータ) (2022-08-11T22:27:22Z) - Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems [61.48763653120301]
クリティカルノード問題(Critical Node Problem, 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) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。