論文の概要: Re-visiting Skip-Gram Negative Sampling: Dimension Regularization for More Efficient Dissimilarity Preservation in Graph Embeddings
- arxiv url: http://arxiv.org/abs/2405.00172v1
- Date: Tue, 30 Apr 2024 19:43:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-05-02 17:16:17.697075
- Title: Re-visiting Skip-Gram Negative Sampling: Dimension Regularization for More Efficient Dissimilarity Preservation in Graph Embeddings
- Title(参考訳): スキップグラム負サンプリングの再検討:グラフ埋め込みにおけるより効率的な相似性保存のための次元正規化
- Authors: David Liu, Arjun Seshadri, Tina Eliassi-Rad, Johan Ugander,
- Abstract要約: ノードワイドの反発は、集合的に、ノード埋め込み次元の近似的な再中心化であることを示す。
本稿では,教師付きあるいは教師なしのアルゴリズムを高速化するアルゴリズム拡張フレームワークを提案する。
- 参考スコア(独自算出の注目度): 8.858596502294471
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A wide range of graph embedding objectives decompose into two components: one that attracts the embeddings of nodes that are perceived as similar, and another that repels embeddings of nodes that are perceived as dissimilar. Because real-world graphs are sparse and the number of dissimilar pairs grows quadratically with the number of nodes, Skip-Gram Negative Sampling (SGNS) has emerged as a popular and efficient repulsion approach. SGNS repels each node from a sample of dissimilar nodes, as opposed to all dissimilar nodes. In this work, we show that node-wise repulsion is, in aggregate, an approximate re-centering of the node embedding dimensions. Such dimension operations are much more scalable than node operations. The dimension approach, in addition to being more efficient, yields a simpler geometric interpretation of the repulsion. Our result extends findings from the self-supervised learning literature to the skip-gram model, establishing a connection between skip-gram node contrast and dimension regularization. We show that in the limit of large graphs, under mild regularity conditions, the original node repulsion objective converges to optimization with dimension regularization. We use this observation to propose an algorithm augmentation framework that speeds up any existing algorithm, supervised or unsupervised, using SGNS. The framework prioritizes node attraction and replaces SGNS with dimension regularization. We instantiate this generic framework for LINE and node2vec and show that the augmented algorithms preserve downstream performance while dramatically increasing efficiency.
- Abstract(参考訳): グラフの埋め込み目的は、類似していると見なされるノードの埋め込みを惹きつけるものと、異なると見なされるノードの埋め込みを反映するものの2つのコンポーネントに分解される。
実世界のグラフはスパースであり、相似ペアの数はノード数と2次的に増加するので、Skip-Gram Negative Sampling (SGNS) は人気があり効率的な反発法として現れている。
SGNSは、全ての異種ノードとは対照的に、異種ノードのサンプルから各ノードを中継する。
本研究では, ノードワイド反発が, 集約的に, ノード埋め込み次元の近似的再中心化であることを示す。
このような次元演算はノード演算よりもはるかにスケーラブルである。
次元的アプローチは、より効率的であることに加えて、反発のより単純な幾何学的解釈をもたらす。
本研究は,自己教師型学習文献からスキップグラムモデルまでの結果を拡張し,スキップグラムノードコントラストと次元正規化の関連性を確立した。
より穏やかな正則性条件下では、大きなグラフの極限において、元のノード反発目標が次元正則化による最適化に収束することを示す。
本稿では,SGNSを用いて既存のアルゴリズムを高速化するアルゴリズム拡張フレームワークを提案する。
このフレームワークはノードアトラクションを優先し、SGNSを次元正規化で置き換える。
LINE と node2vec の汎用フレームワークをインスタンス化し、拡張アルゴリズムが下流のパフォーマンスを劇的に向上させながら維持することを示す。
関連論文リスト
- Sparse Decomposition of Graph Neural Networks [20.768412002413843]
本稿では,集約中に含まれるノード数を削減する手法を提案する。
線形変換された特徴の重み付け和を用いてノード表現の近似を学習し、スパース分解によりこれを実現できる。
提案手法は推論高速化のために設計された他のベースラインよりも優れていることを示す。
論文 参考訳(メタデータ) (2024-10-25T17:52:16Z) - Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
教師なしグラフアライメントは、グラフ構造とノード特徴のみを利用して、属性グラフのペア間の1対1ノード対応を見つける。
モデル表現性の理論的解析によって動機付けられたそれらの利点を組み合わせるための原理的アプローチを提案する。
我々は,問題を最大重み付けに還元することで,一対一のマッチング制約を最初に保証する。
論文 参考訳(メタデータ) (2024-06-19T04:57:35Z) - Subspace Node Pruning [2.3125457626961263]
ノードプルーニング(node pruning)とは、ニューロン、フィルタ、アテンションヘッド、さらには層全体といった計算単位を除去し、ネットワーク性能を維持しながら推論時間を著しく短縮する技術である。
本研究では、余剰な活動が存在しない直交部分空間へのユニットアクティベーションのプロジェクションを提案し、損失ユニットの影響を同時に回復しながらノードをプーンする。
提案手法は,ImageNet が訓練した VGG-16 で,ResNet-50 ネットワークを刈り取る場合のより複雑な手法と競合する。
論文 参考訳(メタデータ) (2024-05-26T14:27:26Z) - Generative Semi-supervised Graph Anomaly Detection [42.02691404704764]
この研究は、グラフ内のノードの一部が正規であることが知られている、実用的な半教師付きグラフ異常検出(GAD)シナリオについて考察する。
我々は,通常のノードをよりよく活用するために,半教師付きシナリオのための新しいGAD手法(GGAD)を提案する。
GGADは、異常ノード(非対称な局所親和性と自中心的親密性)に関する2つの重要な先行情報を活用するように設計されている。
論文 参考訳(メタデータ) (2024-02-19T06:55:50Z) - Disentangled Condensation for Large-scale Graphs [29.384060761810172]
グラフニューラルネットワーク(GNN)の高価なトレーニングコストを節約するための興味深いテクニックとして、グラフ凝縮が登場した。
本稿では, 凝縮過程を2段階のGNNフリーパラダイムに分解し, ノードを独立に凝縮し, エッジを生成することを提案する。
この単純で効果的なアプローチは、中規模グラフの精度に匹敵する精度で最先端の手法よりも少なくとも10倍早く達成できる。
論文 参考訳(メタデータ) (2024-01-18T09:59:00Z) - Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。
このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
論文 参考訳(メタデータ) (2023-12-16T14:09:23Z) - Latent Graph Inference with Limited Supervision [58.54674649232757]
潜在グラフ推論(LGI)は、データ特徴から基礎となるグラフ構造とノード表現を共同で学習することを目的としている。
既存のLGI手法は、意味的な監督なしに巨大なエッジウェイトが学習され、トレーニング損失に寄与しない、監督飢餓の問題に悩まされることが一般的である。
本稿では,この問題の原因はグラフスカラー化操作であり,重要なノードとラベル付きノード間の接続を著しく破壊する。
論文 参考訳(メタデータ) (2023-10-06T15:22:40Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳(メタデータ) (2023-10-05T02:58:29Z) - Node Embedding for Homophilous Graphs with ARGEW: Augmentation of Random
walks by Graph Edge Weights [2.2935273605606494]
ARGEWはランダムウォークのための新しい拡張手法であり、コーパスをより大きなエッジ重みを持つノードがより近い埋め込みで終わるように拡張する。
いくつかの実世界のネットワークにおいて、ARGEWはそれを使用しないのに対し、より大きなエッジ重みを持つノード対がより密着した埋め込みを持つという望ましいパターンはより明確であることを示す。
論文 参考訳(メタデータ) (2023-08-11T06:19:23Z) - BOURNE: Bootstrapped Self-supervised Learning Framework for Unified
Graph Anomaly Detection [50.26074811655596]
自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。
ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。
BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
論文 参考訳(メタデータ) (2023-07-28T00:44:57Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
我々はMixed Graph Contrastive Network(MGCN)と呼ばれる新しいグラフコントラスト学習手法を提案する。
本研究では,非摂動増強戦略と相関還元機構により,潜伏埋め込みの識別能力を向上する。
これら2つの設定を組み合わせることで、識別表現学習のために、豊富なノードと稀に価値あるラベル付きノードの両方から、豊富な監視情報を抽出する。
論文 参考訳(メタデータ) (2022-06-06T14:26:34Z) - Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。
教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。
G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
論文 参考訳(メタデータ) (2022-02-13T07:46:24Z) - Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。
そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
論文 参考訳(メタデータ) (2021-11-19T08:54:21Z) - Integrating Network Embedding and Community Outlier Detection via
Multiclass Graph Description [15.679313861083239]
そこで本稿では,ノード埋め込みとアウトレーヤとコミュニティ検出を統合した非教師なしグラフ埋め込み手法(DMGD)を提案する。
DMGDにより検出された外れ値の数に関する理論的境界を示す。
我々の定式化は、外れ値、コミュニティ割り当て、ノード埋め込み関数の間の興味深いミニマックスゲームに起因する。
論文 参考訳(メタデータ) (2020-07-20T16:21:07Z) - Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。
少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。
我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
論文 参考訳(メタデータ) (2020-06-18T00:55:10Z) - Towards Deeper Graph Neural Networks with Differentiable Group
Normalization [61.20639338417576]
グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。
オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。
2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
論文 参考訳(メタデータ) (2020-06-12T07:18:02Z) - Graph Highway Networks [77.38665506495553]
グラフ畳み込みネットワーク(GCN)は、グラフ表現の有効性と効率性から、グラフ表現の学習に広く利用されている。
彼らは、多くの層が積み重ねられたとき、学習された表現が類似したベクトルに収束するという悪名高い過度に滑らかな問題に悩まされる。
本稿では,GCN学習プロセスにおける均一性と不均一性との間のトレードオフのバランスをとるため,ゲーティングユニットを利用したグラフハイウェイネットワークを提案する。
論文 参考訳(メタデータ) (2020-04-09T16:26:43Z) - Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling [31.812988573924674]
グラフニューラルネットワーク(GNN)では、プール演算子は入力グラフの局所的な要約を計算し、そのグローバルな特性をキャプチャする。
グラフトポロジ全体を保存しながら粗いグラフを生成するGNNのためのプール演算子であるNode Decimation Pooling (NDP)を提案する。
NDPは、最先端のグラフプーリング演算子よりも効率的であり、同時に、様々なグラフ分類タスクにおける競合性能にも達する。
論文 参考訳(メタデータ) (2019-10-24T21:42:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。