論文の概要: Enhancing Balanced Graph Edge Partition with Effective Local Search

• arxiv url: http://arxiv.org/abs/2012.09451v1
• Date: Thu, 17 Dec 2020 08:58:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-02 19:01:54.701011
• Title: Enhancing Balanced Graph Edge Partition with Effective Local Search
• Title（参考訳）: 効率的な局所探索によるバランスの取れたグラフエッジ分割の強化
• Authors: Zhenyu Guo, Mingyu Xiao, Yi Zhou, Dongxiang Zhang, Kian-Lee Tan
• Abstract要約: グラフパーティションは、ワークロードバランスを達成し、並列グラフ処理システムにおけるジョブ完了時間を短縮するための重要なコンポーネントです。 本稿では,本問題の局所探索アルゴリズムについて検討し,既存の手法による分割結果をさらに改善する。
• 参考スコア（独自算出の注目度）: 41.4257628524592
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. Among the various partition strategies, edge partition has demonstrated more promising performance in power-law graphs than vertex partition and thereby has been more widely adopted as the default partition strategy by existing graph systems. The graph edge partition problem, which is to split the edge set into multiple balanced parts to minimize the total number of copied vertices, has been widely studied from the view of optimization and algorithms. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods. More specifically, we propose two novel concepts, namely adjustable edges and blocks. Based on these, we develop a greedy heuristic as well as an improved search algorithm utilizing the property of the max-flow model. To evaluate the performance of our algorithms, we first provide adequate theoretical analysis in terms of the approximation quality. We significantly improve the previously known approximation ratio for this problem. Then we conduct extensive experiments on a large number of benchmark datasets and state-of-the-art edge partition strategies. The results show that our proposed local search framework can further improve the quality of graph partition by a wide margin.
• Abstract（参考訳）: グラフパーティションは、並列グラフ処理システムにおいて、ワークロードのバランスを達成し、ジョブ完了時間を短縮するための重要なコンポーネントである。 様々なパーティション戦略の中で、エッジパーティションは頂点パーティションよりもパワーローグラフの方が有望な性能を示しており、既存のグラフシステムではデフォルトパーティション戦略として広く採用されている。 エッジセットを複数のバランスのとれた部分に分割することで、コピーされた頂点の総数を最小化するグラフエッジ分割問題は、最適化とアルゴリズムの観点から広く研究されている。 本稿では,既存の手法による分割結果を改善するために,局所探索アルゴリズムについて検討する。 具体的には,2つの新しい概念,すなわち調整可能なエッジとブロックを提案する。 これらの結果をもとに,max-flowモデルの特性を生かした検索アルゴリズムを改良し,欲張りなヒューリスティックを開発した。 アルゴリズムの性能を評価するため,まず近似品質の観点から適切な理論的解析を行う。 この問題に対する既知の近似比を大幅に改善する。 そして、多数のベンチマークデータセットと最先端のエッジパーティション戦略に関する広範な実験を行う。 その結果,提案する局所探索フレームワークは,グラフ分割のクオリティをさらに向上させることができることがわかった。

関連論文リスト

• Optimal Partial Graph Matching [2.4378101048225735]
  最適部分移動にインスパイアされた部分グラフマッチングのための新しいフレームワークを提案する。 提案手法は, 偏りを取り入れつつ部分的代入を可能にする目的を定式化したものである。 ハンガリーのアルゴリズムを用いて、立方的時間複雑性を伴う効率的で正確な解を求める。
  論文  参考訳（メタデータ） (2024-10-22T05:56:57Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。 本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。 分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
  論文  参考訳（メタデータ） (2022-10-30T22:04:32Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning [0.13999481573773068]
  本稿では,強化学習とグラフ畳み込みニューラルネットワークに基づくグラフ分割手法を提案する。 提案手法はMETISやスコッチと同様の仕切り品質を実現する。 この方法は、あるクラスのグラフから別のグラフに一般化し、 suitesparse sparse matrix collectionの様々なグラフでうまく機能する。
  論文  参考訳（メタデータ） (2021-04-08T06:54:24Z)
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment [10.172041234280865]
  グラフ信号処理(GSP)は、様々な領域で発生する信号を分析する強力なフレームワークを提供する。 本稿では,観測されたグラフ構造を組み込んで,その基盤となるブロックコミュニティ構造を反映させる,新しい正則化部分最小二乗法を提案する。
  論文  参考訳（メタデータ） (2021-04-06T21:52:15Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  本稿では,この問題クラスにおける近位アルゴリズムの適応型事前条件付け手法を提案する。 不活性エッジのネスト・フォレスト分解により局所収束速度が保証されることを示す。 この結果から,局所収束解析は近似アルゴリズムにおける可変指標選択の指針となることが示唆された。
  論文  参考訳（メタデータ） (2020-02-27T16:33:09Z)

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

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