論文の概要: Frustrated Random Walks: A Fast Method to Compute Node Distances on Hypergraphs

• arxiv url: http://arxiv.org/abs/2401.13054v1
• Date: Tue, 23 Jan 2024 19:26:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-25 16:17:37.928736
• Title: Frustrated Random Walks: A Fast Method to Compute Node Distances on Hypergraphs
• Title（参考訳）: フラストレーションランダムウォーク:ハイパーグラフ上のノード距離を計算する高速手法
• Authors: Enzhi Li, Bilal Fadlallah
• Abstract要約: ハイパーグラフ(英: hypergraph)は、実体間の属性共有を考えると自然に現れるグラフの一般化である。 本稿では,ハイパーグラフ上でのラベル伝搬を実現するために,ランダムウォークに基づく新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A hypergraph is a generalization of a graph that arises naturally when attribute-sharing among entities is considered. Although a hypergraph can be converted into a graph by expanding its hyperedges into fully connected subgraphs, going the reverse way is computationally complex and NP-complete. We therefore hypothesize that a hypergraph contains more information than a graph. In addition, it is more convenient to manipulate a hypergraph directly, rather than expand it into a graph. An open problem in hypergraphs is how to accurately and efficiently calculate their node distances. Estimating node distances enables us to find a node's nearest neighbors, and perform label propagation on hypergraphs using a K-nearest neighbors (KNN) approach. In this paper, we propose a novel approach based on random walks to achieve label propagation on hypergraphs. We estimate node distances as the expected hitting times of random walks. We note that simple random walks (SRW) cannot accurately describe highly complex real-world hypergraphs, which motivates us to introduce frustrated random walks (FRW) to better describe them. We further benchmark our method against DeepWalk, and show that while the latter can achieve comparable results, FRW has a distinct computational advantage in cases where the number of targets is fairly small. For such cases, we show that FRW runs in significantly shorter time than DeepWalk. Finally, we analyze the time complexity of our method, and show that for large and sparse hypergraphs, the complexity is approximately linear, rendering it superior to the DeepWalk alternative.
• Abstract（参考訳）: ハイパーグラフ(英: hypergraph)は、実体間の属性共有を考えると自然に現れるグラフの一般化である。 ハイパーグラフは、ハイパーエッジを完全な連結部分グラフに拡張することでグラフに変換することができるが、逆方向は計算的に複雑でNP完全である。 したがって、ハイパーグラフはグラフよりも多くの情報を含んでいると仮定する。 さらに、グラフに拡張するのではなく、ハイパーグラフを直接操作するのがより便利である。 ハイパーグラフのオープン問題は、ノード間の距離を正確かつ効率的に計算する方法である。 K-nearest neighbors (KNN) アプローチを用いて,ノード近傍のノードを推定し,ハイパーグラフ上でラベル伝搬を行う。 本稿では,ハイパーグラフ上のラベル伝搬を実現するためのランダムウォークに基づく新しい手法を提案する。 ランダムウォークの待ち時間としてノード距離を推定する。 単純ランダムウォーク(srw)は高度に複雑な実世界のハイパーグラフを正確に記述できないことに注意し,フラストレーションのあるランダムウォーク(frw)を導入する動機付けとなる。 さらに、DeepWalkに対して我々の手法をベンチマークし、後者が同等の結果が得られる一方で、FRWはターゲット数がかなり小さい場合において、計算上の優位性があることを示す。 このような場合、FRWはDeepWalkよりもはるかに短い時間で実行されることを示す。 最後に,本手法の時間的複雑さを解析し,大小のハイパーグラフの場合,その複雑さは概ね線形であり,DeepWalk法よりも優れていることを示す。

関連論文リスト

• PipeNet: Question Answering with Semantic Pruning over Knowledge Graphs [56.5262495514563]
  本稿では,雑音の多い計算ノードに対して,グラウンドング・プルーニング・レゾニング・パイプラインを提案する。 また,グラフアテンションネットワーク(GAT)をベースとしたサブグラフデータに基づくモジュールを提案する。
  論文  参考訳（メタデータ） (2024-01-31T01:37:33Z)
• Hypergraph Structure Inference From Data Under Smoothness Prior [46.568839316694515]
  本稿では,ラベル付きデータを監視対象とせずに,潜在的なハイパーエッジの確率を推定する手法を提案する。 本稿では,この手法を用いてハイパーグラフ構造とノード特徴の関係を確率論的モデリングにより導出する。 本手法は,既存のハイパーグラフ構造推定法よりも効率的にデータから有意義なハイパーグラフ構造を学習できることを示す。
  論文  参考訳（メタデータ） (2023-08-27T18:28:58Z)
• Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
  リンク予測はグラフ構造化データ計算の基本的な問題である。 本稿では,スパース囲み部分グラフを用いて予測を行うScaLedというスケーラブルな解を提案する。 より小さなサンプルサブグラフを活用することで、ScaLedは高い精度を維持しながらオーバーヘッドをはるかに少なく大きなグラフにスケールすることができる。
  論文  参考訳（メタデータ） (2022-06-23T22:48:44Z)
• Core-periphery Models for Hypergraphs [0.0]
  コア周辺構造に対するランダムなハイパーグラフモデルを提案する。 我々は,実際に線形wrtを持つ大規模ハイパーグラフにスケール可能な,新しい統計的推論アルゴリズムを開発した。 我々の推論アルゴリズムはハイパーグラフ内のノードの評判(ランク)に対応する埋め込みを学習することができる。
  論文  参考訳（メタデータ） (2022-06-01T22:11:44Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  本稿では,EDVWおよびEIVWハイパーグラフを処理可能な一般学習フレームワークであるGeneral Hypergraph Spectral Convolution(GHSC)を提案する。 本稿では,提案するフレームワークが最先端の性能を達成できることを示す。 ソーシャルネットワーク分析,視覚的客観的分類,タンパク質学習など,様々な分野の実験により,提案手法が最先端の性能を達成できることが実証された。
  論文  参考訳（メタデータ） (2022-03-31T10:46:47Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Minimizing Localized Ratio Cut Objectives in Hypergraphs [32.80813008862995]
  局所化率削減目標の最小化に基づく局所的ハイパーグラフクラスタリングのためのフレームワークを提案する。 我々のアルゴリズムは強局所的であり、その実行は入力セットのサイズにのみ依存し、優れたローカルクラスタを見つけるためにハイパーグラフ全体を探索する必要はない。
  論文  参考訳（メタデータ） (2020-02-21T17:42:22Z)
• Investigating Extensions to Random Walk Based Graph Embedding [0.3867052484157571]
  ランダムウォークに基づくグラフ埋め込みの新たな拡張を提案する。これは、ウォークから最も頻度の低いノードのパーセンテージを異なるレベルで除去する。 この除去により、我々は遠く離れたノードがノードの近傍に存在することをシミュレートし、従ってそれらの接続を明示的に表現する。 その結果、ランダムウォークベースの手法の拡張(うちを含む)は、予測性能をほんの少しだけ改善することがわかった。
  論文  参考訳（メタデータ） (2020-02-17T21:14:02Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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