論文の概要: 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倍の効率を実現しています。
関連論文リスト
- Sparse Training of Discrete Diffusion Models for Graph Generation [50.691834214298]
グラフの生成モデルは、各ノードペアの相互作用を予測する必要があるため、スケーラビリティ上の問題に遭遇することが多い。
本稿では,SparseDiffについて紹介する。SparseDiffは,グラフ生成のためのデノナイズ拡散モデルである。
実験結果から, SparseDiffは, 小グラフと大グラフの両方において, 生成性能の同時一致を示す。
論文 参考訳(メタデータ) (2023-11-03T16:50:26Z) - Do We Really Need Contrastive Learning for Graph Representation? [18.42853283915796]
グラフコントラスト学習(GCL)は、他のサンプル(負のサンプル)の埋め込みを分離しながら、互いに近接して強化されたアンカーサンプルを埋め込むことを目的としている。
既存のGCL法は、埋め込みの品質を確保するために、大きく多様な負のサンプルを必要とする。
類似度スコアを測定するためにランクに基づく学習を導入し、偽陰性証明をうまく緩和する。
論文 参考訳(メタデータ) (2023-10-23T03:15:57Z) - 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) - Enhancing Graph Contrastive Learning with Node Similarity [4.60032347615771]
グラフコントラスト学習(GCL)は、自己教師型学習の代表的なフレームワークである。
GCLは、意味的に類似したノード(正のサンプル)と異種ノード(負のサンプル)とアンカーノードとの対比によってノード表現を学習する。
本稿では,全ての正のサンプルと偽陰性サンプルを含まない拡張目的を提案する。
論文 参考訳(メタデータ) (2022-08-13T22:49:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。