論文の概要: Graphlets correct for the topological information missed by random walks

• arxiv url: http://arxiv.org/abs/2405.14194v1
• Date: Thu, 23 May 2024 05:42:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-24 18:45:29.297612
• Title: Graphlets correct for the topological information missed by random walks
• Title（参考訳）: ランダムウォークで欠落した位相情報に対するグラフレットの補正
• Authors: Sam F. L. Windels, Noel Malod-Dognin, Natasa Przulj,
• Abstract要約: 我々は、2つのノードの隣接度を、与えられた一対のグラフレット軌道上で共起するものとして定量化する軌道隣接性を導入する。 我々は、kノードまでのランダムウォーキングが、kノードグラフレットまでの全ての軌道隣接部分集合のみをキャプチャすることを証明する。 ランダムウォークで見えないものを含む軌道上の隣接性は、ランダムウォークに基づく隣接性よりも優れています。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Random walks are widely used for mining networks due to the computational efficiency of computing them. For instance, graph representation learning learns a d-dimensional embedding space, so that the nodes that tend to co-occur on random walks (a proxy of being in the same network neighborhood) are close in the embedding space. Specific local network topology (i.e., structure) influences the co-occurrence of nodes on random walks, so random walks of limited length capture only partial topological information, hence diminishing the performance of downstream methods. We explicitly capture all topological neighborhood information and improve performance by introducing orbit adjacencies that quantify the adjacencies of two nodes as co-occurring on a given pair of graphlet orbits, which are symmetric positions on graphlets (small, connected, non-isomorphic, induced subgraphs of a large network). Importantly, we mathematically prove that random walks on up to k nodes capture only a subset of all the possible orbit adjacencies for up to k-node graphlets. Furthermore, we enable orbit adjacency-based analysis of networks by developing an efficient GRaphlet-orbit ADjacency COunter (GRADCO), which exhaustively computes all 28 orbit adjacency matrices for up to four-node graphlets. Note that four-node graphlets suffice, because real networks are usually small-world. In large networks on around 20,000 nodes, GRADCOcomputesthe28matricesinminutes. Onsixrealnetworksfromvarious domains, we compare the performance of node-label predictors obtained by using the network embeddings based on our orbit adjacencies to those based on random walks. We find that orbit adjacencies, which include those unseen by random walks, outperform random walk-based adjacencies, demonstrating the importance of the inclusion of the topological neighborhood information that is unseen by random walks.
• Abstract（参考訳）: ランダムウォークは、それらを計算する計算効率のため、マイニングネットワークに広く使われている。 例えば、グラフ表現学習はd-次元埋め込み空間を学習するため、ランダムウォーク(同じネットワーク近傍にあるプロキシ)で共起するノードが埋め込み空間に近くなる。 特定の局所ネットワークトポロジ(構造)はランダムウォークにおけるノードの共起に影響を与えるため、制限された長さのランダムウォークは部分的トポロジ情報のみをキャプチャし、ダウンストリーム法の性能を低下させる。 我々は、グラフレット上の対称位置(大きなネットワークの小さい、連結で、同型ではない、誘導された部分グラフ)である与えられた一対のグラフレット軌道上で共起する2つのノードの隣接度を定量化する軌道アジャクシーを導入することにより、すべての位相的近傍情報を明示的に捕捉し、性能を向上させる。 重要なことは、kノードまでのランダムウォーキングが、最大kノードグラフレットの可能な全ての軌道隣接部のサブセットのみをキャプチャすることを証明することである。 さらに,高速なGRaphlet-orbit ADjacency Counter (GRADCO) を開発し,最大4ノードのグラフレットに対して全28の軌道隣接行列を網羅的に計算することで,ネットワークの軌道隣接に基づく解析を可能にする。 実ネットワークは通常小さな世界であるため、4ノードグラフレットは十分である。 約20,000ノードの大規模ネットワークでは、GRADCOcomputesthe28matricesinminutesである。 Onsixrealnetworks fromvarious domain, we compare the performance of node-label predictor obtained by using the network embeddeds based on our orbit adjacencies to those based on random walk。 ランダムウォークで見えないものを含む軌道隣接性は、ランダムウォークで見えないトポロジ的近傍情報を含めることの重要性を示す。

関連論文リスト

• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Node Embedding for Homophilous Graphs with ARGEW: Augmentation of Random walks by Graph Edge Weights [2.2935273605606494]
  ARGEWはランダムウォークのための新しい拡張手法であり、コーパスをより大きなエッジ重みを持つノードがより近い埋め込みで終わるように拡張する。 いくつかの実世界のネットワークにおいて、ARGEWはそれを使用しないのに対し、より大きなエッジ重みを持つノード対がより密着した埋め込みを持つという望ましいパターンはより明確であることを示す。
  論文  参考訳（メタデータ） (2023-08-11T06:19:23Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。 そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
  論文  参考訳（メタデータ） (2021-11-19T08:54:21Z)
• Inferential SIR-GN: Scalable Graph Representation Learning [0.4699313647907615]
  グラフ表現学習法は、ネットワーク内のノードの数値ベクトル表現を生成する。 本研究では,ランダムグラフ上で事前学習されたモデルであるInferential SIR-GNを提案し,ノード表現を高速に計算する。 このモデルではノードの構造的役割情報を捉えることができ、ノードやグラフの分類タスクにおいて、目に見えないネットワーク上で優れた性能を示すことができる。
  論文  参考訳（メタデータ） (2021-11-08T20:56:37Z)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。 固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
  論文  参考訳（メタデータ） (2021-11-04T14:57:43Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。 提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
  論文  参考訳（メタデータ） (2021-10-21T19:16:16Z)
• Node Similarity Preserving Graph Convolutional Networks [51.520749924844054]
  グラフニューラルネットワーク(GNN)は、ノード近傍の情報を集約し変換することで、グラフ構造とノードの特徴を探索する。 グラフ構造を利用してノード類似性を効果的かつ効率的に保存できるSimP-GCNを提案する。 本研究は,SimP-GCNが3つの分類グラフと4つの非補助グラフを含む7つのベンチマークデータセットに対して有効であることを示す。
  論文  参考訳（メタデータ） (2020-11-19T04:18:01Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。 埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
  論文  参考訳（メタデータ） (2020-09-30T04:59:10Z)
• node2coords: Graph Representation Learning with Wasserstein Barycenters [59.07120857271367]
  グラフの表現学習アルゴリズムである node2coords を導入する。 低次元空間を同時に学習し、その空間内のノードを座標する。 実験の結果,node2coordで学習した表現は解釈可能であることがわかった。
  論文  参考訳（メタデータ） (2020-07-31T13:14:25Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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