論文の概要: 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 の汎用フレームワークをインスタンス化し、拡張アルゴリズムが下流のパフォーマンスを劇的に向上させながら維持することを示す。
関連論文リスト
- Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
教師なしグラフアライメントは、グラフ構造とノード特徴のみを利用して、属性グラフのペア間の1対1ノード対応を見つける。
モデル表現性の理論的解析によって動機付けられたそれらの利点を組み合わせるための原理的アプローチを提案する。
我々は,問題を最大重み付けに還元することで,一対一のマッチング制約を最初に保証する。
論文 参考訳（メタデータ） (2024-06-19T04:57:35Z) - Generative Semi-supervised Graph Anomaly Detection [42.02691404704764]
この研究は、グラフ内のノードの一部が正規であることが知られている、実用的な半教師付きグラフ異常検出(GAD)シナリオについて考察する。
我々は,通常のノードをよりよく活用するために,半教師付きシナリオのための新しいGAD手法(GGAD)を提案する。
GGADは、異常ノード(非対称な局所親和性と自中心的親密性)に関する2つの重要な先行情報を活用するように設計されている。
論文 参考訳（メタデータ） (2024-02-19T06:55:50Z) - Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。
このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
論文 参考訳（メタデータ） (2023-12-16T14:09:23Z) - 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) - 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 [5.431036185361236]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。