論文の概要: Topology-Guided Sampling for Fast and Accurate Community Detection
- arxiv url: http://arxiv.org/abs/2108.06651v1
- Date: Sun, 15 Aug 2021 03:20:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-17 14:46:15.719118
- Title: Topology-Guided Sampling for Fast and Accurate Community Detection
- Title（参考訳）: 迅速かつ高精度なコミュニティ検出のためのトポロジー誘導サンプリング
- Authors: Frank Wanye, Vitaliy Gleyzer, Edward Kao, Wu-chun Feng
- Abstract要約: 本稿では,ブロック分割の高速化を目的としたトポロジー誘導サンプリング手法を提案する。
また、高速化を犠牲にして、我々のアプローチの有効性を向上させるための学位ベースのしきい値設定手法も導入する。
以上の結果から,本手法はサンプリングなしでブロック分割を最大15倍高速化する可能性が示唆された。
- 参考スコア（独自算出の注目度）: 1.0609815608017064
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Community detection is a well-studied problem with applications in domains
ranging from computer networking to bioinformatics. While there are many
algorithms that perform community detection, the more accurate and
statistically robust algorithms tend to be slow and hard to parallelize. One
way to speed up such algorithms is through data reduction. However, this
approach has not been thoroughly studied, and the quality of results obtained
with this approach varies with the graph it is applied to. In this manuscript,
we present an approach based on topology-guided sampling for accelerating
stochastic block partitioning - a community detection algorithm that works well
on graphs with complex and heterogeneous community structure. We also introduce
a degree-based thresholding scheme that improves the efficacy of our approach
at the expense of speedup. Finally, we perform a series of experiments on
synthetically generated graphs to determine how various graph parameters affect
the quality of results and speedup obtained with our approach, and we validate
our approach on real-world data. Our results show that our approach can lead to
a speedup of up to 15X over stochastic block partitioning without sampling
while maintaining result quality and can even lead to improvements of over 150%
in result quality in terms of F1 score on certain kinds of graphs.
- Abstract（参考訳）: コミュニティ検出は、コンピュータネットワークからバイオインフォマティクスまで幅広い分野のアプリケーションでよく研究されている問題である。
コミュニティ検出を行うアルゴリズムは数多く存在するが、より正確で統計的に堅牢なアルゴリズムは遅く、並列化が難しい傾向がある。
このようなアルゴリズムを高速化する方法の1つは、データ削減である。
しかし、このアプローチは十分に研究されておらず、このアプローチで得られた結果の質は、適用するグラフによって異なる。
本稿では,複雑で異種なコミュニティ構造を持つグラフ上でうまく機能するコミュニティ検出アルゴリズムである,確率的ブロック分割を高速化するためのトポロジー誘導サンプリングに基づくアプローチを提案する。
また、高速化を犠牲にして、我々のアプローチの有効性を向上させるための学位ベースのしきい値設定手法も導入する。
最後に, 合成グラフに対する一連の実験を行い, 様々なグラフパラメータが結果の質にどのように影響するかを検証し, 実世界のデータに対するアプローチを検証した。
以上の結果から,我々のアプローチは,確率的ブロック分割よりも最大15倍の高速化につながり,また,特定のグラフ上のf1スコアの点において,結果品質が150%以上向上する可能性が示唆された。
関連論文リスト
- Evolvable Agents, a Fine Grained Approach for Distributed Evolutionary
Computing: Walking towards the Peer-to-Peer Computing Frontiers [0.0]
本稿では,分散進化計算における自己適応的移動率を用いた微粒化手法を提案する。
我々は,プロセッサ数の増加に伴って,ソリューションの品質とアルゴリズムの速度がどう変化するかを比較することで,アプローチの生存可能性を分析する。
この実験により,本手法はアイランドモデルよりも優れたスケーラビリティを示し,実験中の3つのテスト関数の平均値に対して等価なロバスト性を示す。
論文 参考訳（メタデータ） (2024-01-30T18:11:31Z) - Addressing Noise and Efficiency Issues in Graph-Based Machine Learning
Models From the Perspective of Adversarial Attack [2.1937382384136637]
本稿では,ノイズエッジを逆襲攻撃として扱うことを提案し,スペクトル対向ロバスト性評価法を用いて,ノイズエッジがグラフアルゴリズムの性能に与える影響を低減させる。
提案手法は,ノイズの多いエッジに対して脆弱でない点を識別し,これらの頑健な点のみを活用してグラフベースのアルゴリズムを実行する。
論文 参考訳（メタデータ） (2024-01-28T10:03:37Z) - Contraction-Guided Adaptive Partitioning for Reachability Analysis of
Neural Network Controlled Systems [5.359060261460183]
非線形フィードバックループにおける区間値到達可能集合の推定値を改善するための収縮誘導適応分割アルゴリズムを提案する。
ニューラルネットワーク検証ステップとリーチビリティパーティショニングレイヤの分離を活用することで、アルゴリズムは計算コストの少ない精度の向上を提供することができる。
本稿では,現状の手法と比較して,ランタイムのごく一部において,到達可能な集合推定の精度が大幅に向上したことを報告する。
論文 参考訳（メタデータ） (2023-04-07T14:43:21Z) - Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。
UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
論文 参考訳（メタデータ） (2022-06-21T01:46:38Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。
グラフが現在の勾配を混合する能力を定量化する計量法を提案する。
そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
論文 参考訳（メタデータ） (2022-04-13T15:54:35Z) - Accelerated Graph Learning from Smooth Signals [10.426964757656743]
高速な双対ベース近位勾配アルゴリズムは, 強い凸, 滑らか性に則ったネットワーク逆問題に対処するために開発された。
既存の解法とは異なり、新しい反復法はグローバル収束率を保証するとともに、追加のステップサイズチューニングを必要としない。
論文 参考訳（メタデータ） (2021-10-19T01:02:57Z) - Straggler-Resilient Federated Learning: Leveraging the Interplay Between
Statistical Accuracy and System Heterogeneity [57.275753974812666]
フェデレーション学習は、データをローカルに保持しながら、クライアントのネットワークに分散したデータサンプルから学習する。
本稿では,学習手順を高速化するために,クライアントデータの統計的特徴を取り入れてクライアントを適応的に選択する,ストラグラー・レジリエントなフェデレーション学習手法を提案する。
論文 参考訳（メタデータ） (2020-12-28T19:21:14Z) - Progressive Spatio-Temporal Graph Convolutional Network for
Skeleton-Based Human Action Recognition [97.14064057840089]
本稿では,グラフ畳み込みネットワークのためのコンパクトで問題固有のネットワークを,段階的に自動的に見つける手法を提案する。
骨格に基づく人体行動認識のための2つのデータセットの実験結果から,提案手法は競争力あるいはより優れた分類性能を有することが示された。
論文 参考訳（メタデータ） (2020-11-11T09:57:49Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。