論文の概要: Degree-Based Random Walk Approach for Graph Embedding

• arxiv url: http://arxiv.org/abs/2110.13627v1
• Date: Thu, 21 Oct 2021 19:16:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-01 05:46:38.773119
• Title: Degree-Based Random Walk Approach for Graph Embedding
• Title（参考訳）: グラフ埋め込みのためのDegree-based Random Walk Approach
• Authors: Sarmad N. Mohammed, Semra G\"und\"u\c{c}
• Abstract要約: 計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。 提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph embedding, representing local and global neighborhood information by numerical vectors, is a crucial part of the mathematical modeling of a wide range of real-world systems. Among the embedding algorithms, random walk-based algorithms have proven to be very successful. These algorithms collect information by creating numerous random walks with a redefined number of steps. Creating random walks is the most demanding part of the embedding process. The computation demand increases with the size of the network. Moreover, for real-world networks, considering all nodes on the same footing, the abundance of low-degree nodes creates an imbalanced data problem. In this work, a computationally less intensive and node connectivity aware uniform sampling method is proposed. In the proposed method, the number of random walks is created proportionally with the degree of the node. The advantages of the proposed algorithm become more enhanced when the algorithm is applied to large graphs. A comparative study by using two networks namely CORA and CiteSeer is presented. Comparing with the fixed number of walks case, the proposed method requires 50% less computational effort to reach the same accuracy for node classification and link prediction calculations.
• Abstract（参考訳）: 局所的および大域的近傍情報を数値ベクトルで表現するグラフ埋め込みは、幅広い実世界のシステムの数学的モデリングにおいて重要な部分である。 埋め込みアルゴリズムのうち、ランダムウォークベースのアルゴリズムは非常に成功したことが証明されている。 これらのアルゴリズムは、再定義されたステップ数で多数のランダムウォークを生成して情報を集める。 ランダムウォークを作成することが、埋め込みプロセスの最も要求される部分です。 計算要求はネットワークのサイズに応じて増加する。 さらに、実世界のネットワークでは、同じ足場上の全てのノードを考えると、低次ノードの多さは不均衡なデータ問題を引き起こす。 本研究では,計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。 提案手法では,ランダムウォークの数をノードの次数に比例して生成する。 提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。 CORAとCiteSeerという2つのネットワークを用いて比較研究を行った。 一定数のウォークケースと比較すると,提案手法は,ノード分類やリンク予測計算において同じ精度に達するのに50%の計算労力を要しない。

関連論文リスト

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Hub-aware Random Walk Graph Embedding Methods for Classification [44.99833362998488]
  ノード分類問題に特化して設計されたランダムウォークに基づく2つの新しいグラフ埋め込みアルゴリズムを提案する。 提案手法は,実世界のネットワークの埋め込みを訓練した3つの分類アルゴリズムの分類性能を解析して実験的に評価する。
  論文  参考訳（メタデータ） (2022-09-15T20:41:18Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• Efficient and Local Parallel Random Walks [21.29022677162416]
  ランダムウォークは、多くの機械学習アルゴリズムで使用される基本的なプリミティブである。 ランダムウォークを効率的に局所的に構築することで,この制限を克服するアルゴリズムを提案する。 本手法はメモリとラウンド効率の両方で,特に並列局所クラスタリングアルゴリズムを効率よく実現している。
  論文  参考訳（メタデータ） (2021-12-01T17:06:11Z)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。 固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
  論文  参考訳（メタデータ） (2021-11-04T14:57:43Z)
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks [1.345669927504424]
  局所ランダムウォークは準局所的手法のカテゴリで最もよく知られたアルゴリズムの1つであると考えられている。 ほとんどのデータセットでは、この手法は著しく類似したノードを正確に評価することができない。 より強い影響を持つノードへのランダムウォーキングを奨励し,局所的ランダムウォーキングを改善するための効率的な手法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T03:35:38Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Private Weighted Random Walk Stochastic Gradient Descent [21.23973736418492]
  グラフ内のノードに分散したデータを分散する分散学習環境を考える。 本稿では,データの一様サンプリングと重要サンプリングという2種類のランダムウォークに基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-03T16:52:13Z)

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

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