論文の概要: K-Core Decomposition on Super Large Graphs with Limited Resources
- arxiv url: http://arxiv.org/abs/2112.14840v1
- Date: Sun, 26 Dec 2021 04:34:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-09 13:29:37.365259
- Title: K-Core Decomposition on Super Large Graphs with Limited Resources
- Title（参考訳）: 限られた資源を持つ超大グラフ上のKコア分解
- Authors: Shicheng Gao, Jie Xu, Xiaosen Li, Fangcheng Fu, Wentao Zhang, Wen
Ouyang, Yangyu Tao, Bin Cui
- Abstract要約: 近年、グラフの規模は急速に拡大しており、特に工業環境では顕著である。
大規模グラフにKコア分解を適用することは、学者や業界からますます注目を集めている。
そこで本研究では,分散Kコア分解アルゴリズム上での分割・対数戦略を提案する。
- 参考スコア（独自算出の注目度）: 17.71064869466004
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: K-core decomposition is a commonly used metric to analyze graph structure or
study the relative importance of nodes in complex graphs. Recent years have
seen rapid growth in the scale of the graph, especially in industrial settings.
For example, our industrial partner runs popular social applications with
billions of users and is able to gather a rich set of user data. As a result,
applying K-core decomposition on large graphs has attracted more and more
attention from academics and the industry. A simple but effective method to
deal with large graphs is to train them in the distributed settings, and some
distributed K-core decomposition algorithms are also proposed. Despite their
effectiveness, we experimentally and theoretically observe that these
algorithms consume too many resources and become unstable on super-large-scale
graphs, especially when the given resources are limited. In this paper, we deal
with those super-large-scale graphs and propose a divide-and-conquer strategy
on top of the distributed K-core decomposition algorithm. We evaluate our
approach on three large graphs. The experimental results show that the
consumption of resources can be significantly reduced, and the calculation on
large-scale graphs becomes more stable than the existing methods. For example,
the distributed K-core decomposition algorithm can scale to a large graph with
136 billion edges without losing correctness with our divide-and-conquer
technique.
- Abstract（参考訳）: Kコア分解は、グラフ構造を分析したり、複雑なグラフにおけるノードの相対的重要性を研究するために一般的に用いられる計量である。
近年、グラフの規模は急速に拡大しており、特に工業環境では顕著である。
例えば、当社の産業パートナーは数十億のユーザを持つポピュラーなソーシャルアプリケーションを実行し、豊富なユーザデータを集めることができます。
その結果、Kコア分解を大きなグラフに適用することは、学者や業界からますます注目を集めている。
大規模なグラフを扱うための単純で効果的な方法は、分散環境でそれらを訓練することであり、分散Kコア分解アルゴリズムも提案されている。
有効性にもかかわらず、これらのアルゴリズムはあまりに多くの資源を消費しすぎ、特に与えられた資源が制限された場合、超大規模グラフ上で不安定になることを実験的に理論的に観察する。
本稿では,これらの超大規模グラフに対処し,分散Kコア分解アルゴリズム上での分割・分散戦略を提案する。
3つの大きなグラフに対する我々のアプローチを評価する。
実験結果から, 資源消費は著しく減少し, 大規模グラフの計算は既存手法よりも安定であることが示唆された。
例えば、分散Kコア分解アルゴリズムは136億のエッジを持つ大きなグラフにスケールすることができる。
関連論文リスト
- Expander Hierarchies for Normalized Cuts on Graphs [3.3385430106181184]
本稿では,拡張器の分解とその階層を計算するためのアルゴリズムについて紹介する。
様々な大きなグラフに対する実験により、この拡張器に基づくアルゴリズムは正規化カットに対する最先端の解法よりも優れていることが示された。
論文 参考訳（メタデータ） (2024-06-20T08:50:57Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。
提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。
我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
論文 参考訳（メタデータ） (2023-02-01T14:02:06Z) - Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。
我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
論文 参考訳（メタデータ） (2022-06-28T02:10:05Z) - GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
グラフコントラスト学習(GCL)は、手作業によるアノテーションの監督なしに、グラフ表現学習(GRL)において有望な性能を示した。
本稿では,この課題に対処するため,グラフココというグラフ補完型コントラスト学習手法を提案する。
論文 参考訳（メタデータ） (2022-03-24T02:58:36Z) - Scaling R-GCN Training with Graph Summarization [71.06855946732296]
リレーショナルグラフ畳み込みネットワーク(R-GCN)のトレーニングは、グラフのサイズに合わない。
本研究では,グラフの要約手法を用いてグラフを圧縮する実験を行った。
AIFB, MUTAG, AMデータセットについて妥当な結果を得た。
論文 参考訳（メタデータ） (2022-03-05T00:28:43Z) - Graph Coarsening with Neural Networks [8.407217618651536]
本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。
粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
論文 参考訳（メタデータ） (2021-02-02T06:50:07Z) - LCS Graph Kernel Based on Wasserstein Distance in Longest Common
Subsequence Metric Space [22.215852332444904]
パスとウォークのより包括的類似性を計算するグラフカーネルを提案する。
また、グラフのより深い特徴を抽出するために、最適輸送理論と組み合わせる。
提案手法は多くの最先端グラフカーネル手法に勝る。
論文 参考訳（メタデータ） (2020-12-07T11:59:14Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Understanding Coarsening for Embedding Large-Scale Graphs [3.6739949215165164]
機械学習(ML)アルゴリズムによるグラフの適切な解析は、研究や産業の多くの分野において、より深い洞察をもたらす可能性がある。
グラフデータの不規則構造は、グラフ上でMLタスクを実行するための障害を構成する。
本研究では, 粗大化品質が埋込み性能に及ぼす影響を, 速度と精度の両方で解析する。
論文 参考訳（メタデータ） (2020-09-10T15:06:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。