論文の概要: Efficient block contrastive learning via parameter-free meta-node
approximation
- arxiv url: http://arxiv.org/abs/2209.14067v1
- Date: Wed, 28 Sep 2022 12:56:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 18:25:35.498561
- Title: Efficient block contrastive learning via parameter-free meta-node
approximation
- Title（参考訳）: パラメータフリーメタノード近似による効率的なブロックコントラスト学習
- Authors: Gayan K. Kulatilleke, Marius Portmann, Shekhar S. Chandra
- Abstract要約: サブサンプリングは最適ではなく、誤った負のサンプリングはサンプリングバイアスにつながる。
本稿では,メタノードをベースとした近似手法を提案する。
6つのベンチマークで、最先端グラフクラスタリングよりも有望な精度向上を示す。
- 参考スコア（独自算出の注目度）: 1.1470070927586016
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Contrastive learning has recently achieved remarkable success in many domains
including graphs. However contrastive loss, especially for graphs, requires a
large number of negative samples which is unscalable and computationally
prohibitive with a quadratic time complexity. Sub-sampling is not optimal and
incorrect negative sampling leads to sampling bias. In this work, we propose a
meta-node based approximation technique that can (a) proxy all negative
combinations (b) in quadratic cluster size time complexity, (c) at graph level,
not node level, and (d) exploit graph sparsity. By replacing node-pairs with
additive cluster-pairs, we compute the negatives in cluster-time at graph
level. The resulting Proxy approximated meta-node Contrastive (PamC) loss,
based on simple optimized GPU operations, captures the full set of negatives,
yet is efficient with a linear time complexity. By avoiding sampling, we
effectively eliminate sample bias. We meet the criterion for larger number of
samples, thus achieving block-contrastiveness, which is proven to outperform
pair-wise losses. We use learnt soft cluster assignments for the meta-node
constriction, and avoid possible heterophily and noise added during edge
creation. Theoretically, we show that real world graphs easily satisfy
conditions necessary for our approximation. Empirically, we show promising
accuracy gains over state-of-the-art graph clustering on 6 benchmarks.
Importantly, we gain substantially in efficiency; up to 3x in training time,
1.8x in inference time and over 5x in GPU memory reduction.
- Abstract（参考訳）: コントラスト学習はグラフを含む多くの領域で最近目覚ましい成功を収めている。
しかし、対照的な損失、特にグラフの場合、多くの負のサンプルが必要であり、これは2次時間複雑性で計算不可能で、計算的に禁じられている。
サブサンプリングは最適ではなく、誤った負のサンプリングはサンプリングバイアスにつながる。
本研究では,メタノードに基づく近似手法を提案する。
(a)すべての負の組み合わせを代理する
(b)二次クラスターサイズの時間複雑性。
(c) ノードレベルではなく,グラフレベルで,
(d)グラフスパーシティを利用する。
ノードパイアを付加クラスタパイアに置き換えることで,クラスタ時の負をグラフレベルで計算する。
結果として得られるProxy近似メタノードコントラスト(PamC)損失は、単純な最適化GPU演算に基づいて、負の完全なセットをキャプチャするが、線形時間複雑性では効率的である。
サンプリングを避けることで,サンプルバイアスを効果的に排除する。
我々は、より多くのサンプルの基準を満たすため、ペアワイズ損失よりも優れたブロックコントラスト性が得られる。
我々はメタノード制限のための学習ソフトクラスタ割り当てを使用し、エッジ生成時に付加されるヘテロフィリエやノイズを回避する。
理論的には、実世界のグラフは近似に必要な条件を容易に満たすことができる。
実験により、6つのベンチマーク上での最先端グラフクラスタリングよりも有望な精度向上を示す。
トレーニング時間に最大3倍、推論時間に1.8倍、GPUメモリの削減に5倍の効率を実現しています。
関連論文リスト
- Bootstrap Latents of Nodes and Neighbors for Graph Self-Supervised Learning [27.278097015083343]
対照的な学習は、モデルの崩壊を防ぎ、差別的な表現を学ぶために負のサンプルを必要とする。
我々は、アンカーノードに対する隣人の支持率を予測するために、クロスアテンションモジュールを導入する。
本手法は, 負の正試料と雑音の正試料とのクラス衝突を緩和し, クラス内コンパクト度を同時に向上する。
論文 参考訳（メタデータ） (2024-08-09T14:17:52Z) - Graph Ranking Contrastive Learning: A Extremely Simple yet Efficient Method [17.760628718072144]
InfoNCEは2つのビューを得るために拡張技術を使用し、1つのビューのノードがアンカーとして機能し、もう1つのビューの対応するノードが正のサンプルとして機能し、他のすべてのノードが負のサンプルとみなされる。
目標は、アンカーノードと正のサンプルの間の距離を最小化し、負のサンプルまでの距離を最大化することである。
トレーニング中にラベル情報が不足しているため、InfoNCEは必然的に同じクラスのサンプルを負のサンプルとして扱い、偽の負のサンプルの問題を引き起こす。
偽陰性サンプルの問題に対処する簡易かつ効率的なグラフコントラスト学習法であるGraphRankを提案する。
論文 参考訳（メタデータ） (2023-10-23T03:15:57Z) - Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。
まず、Emphnode-wiseアーキテクチャは各ノードの個別の埋め込みをプリコンパイルし、後に単純なデコーダで結合して予測を行う。
第二に、エンフェッジワイド法は、ペアワイド関係の表現を強化するために、エッジ固有のサブグラフ埋め込みの形成に依存している。
論文 参考訳（メタデータ） (2023-10-14T07:02:54Z) - Graph Self-Contrast Representation Learning [14.519482062111507]
本稿では,新しいグラフ自己コントラストフレームワークGraphSCを提案する。
1つの正のサンプルと1つの負のサンプルしか使用せず、目的として三重項損失を選択する。
我々は,他の19種類の最先端手法に対して,GraphSCの性能を評価するための広範囲な実験を行った。
論文 参考訳（メタデータ） (2023-09-05T15:13:48Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳（メタデータ） (2022-12-08T23:36:00Z) - From Spectral Graph Convolutions to Large Scale Graph Convolutional
Networks [0.0]
グラフ畳み込みネットワーク(GCN)は、様々なタスクにうまく適用された強力な概念であることが示されている。
古典グラフ理論の関連部分を含むGCNの定義への道を開いた理論を考察する。
論文 参考訳（メタデータ） (2022-07-12T16:57:08Z) - Prototypical Graph Contrastive Learning [141.30842113683775]
本稿では,有意なサンプリングバイアスを緩和するために,プロトタイプグラフコントラスト学習(PGCL)手法を提案する。
具体的には、PGCLは、グラフデータの基盤となる意味構造を、意味論的に類似したグラフを同じグループにクラスタリングすることでモデル化し、同時に、同じグラフの異なる拡張に対するクラスタリング一貫性を奨励する。
クエリのために、PGCLはさらに、プロトタイプ(クラスタセントロイド)とクエリプロトタイプの間の距離に基づいて、負のサンプルを再重み付けする。
論文 参考訳（メタデータ） (2021-06-17T16:45:31Z) - SCE: Scalable Network Embedding from Sparsest Cut [20.08464038805681]
大規模ネットワーク埋め込みは、教師なしの方法で各ノードの潜在表現を学習することである。
このような対照的な学習手法の成功の鍵は、正と負のサンプルを引き出す方法である。
本稿では, 負のサンプルのみを用いた教師なしネットワーク埋め込みのためのSCEを提案する。
論文 参考訳（メタデータ） (2020-06-30T03:18:15Z) - Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
グラフ畳み込みネットワーク(GCN)の訓練を高速化するために, ばらつきを低減したサンプリングアルゴリズムが提案されている。
これらのサンプリングアルゴリズムは、グラフ注意ネットワーク(GAT)のような固定重みよりも学習重量を含む、より一般的なグラフニューラルネットワーク(GNN)には適用できない。
論文 参考訳（メタデータ） (2020-06-10T12:48:37Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。