論文の概要: Flashlight: Scalable Link Prediction with Effective Decoders
- arxiv url: http://arxiv.org/abs/2209.10100v1
- Date: Sat, 17 Sep 2022 03:16:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 15:52:58.742454
- Title: Flashlight: Scalable Link Prediction with Effective Decoders
- Title(参考訳): flashlight: 効率的なデコーダによるスケーラブルなリンク予測
- Authors: Yiwei Wang, Bryan Hooi, Yozen Liu, Tong Zhao, Zhichun Guo, Neil Shah
- Abstract要約: リンク予測(LP)は,グラフ学習における重要な課題として認識されており,その実践的応用も行われている。
本研究では,アダマールMLPの上位点数検索を高速化するtextitFlashlightアルゴリズムを提案する。
我々の研究は、HadamardMLPデコーダを用いた大規模LPアプリケーションへの道を開いた。
- 参考スコア(独自算出の注目度): 36.108651389686706
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Link prediction (LP) has been recognized as an important task in graph
learning with its board practical applications. A typical application of LP is
to retrieve the top scoring neighbors for a given source node, such as the
friend recommendation. These services desire the high inference scalability to
find the top scoring neighbors from many candidate nodes at low latencies.
There are two popular decoders that the recent LP models mainly use to compute
the edge scores from node embeddings: the \textbf{HadamardMLP} and \textbf{Dot
Product} decoders. After theoretical and empirical analysis, we find that the
HadamardMLP decoders are generally more effective for LP. However, HadamardMLP
lacks the scalability for retrieving top scoring neighbors on large graphs,
since to the best of our knowledge, there does not exist an algorithm to
retrieve the top scoring neighbors for HadamardMLP decoders in sublinear
complexity. To make HadamardMLP scalable, we propose the \textit{Flashlight}
algorithm to accelerate the top scoring neighbor retrievals for HadamardMLP: a
sublinear algorithm that progressively applies approximate maximum inner
product search (MIPS) techniques with adaptively adjusted query embeddings.
Empirical results show that Flashlight improves the inference speed of LP by
more than 100 times on the large OGBL-CITATION2 dataset without sacrificing
effectiveness. Our work paves the way for large-scale LP applications with the
effective HadamardMLP decoders by greatly accelerating their inference.
- Abstract(参考訳): リンク予測(LP)は,グラフ学習における重要な課題として認識されており,その実践的応用も行われている。
LPの典型的な応用は、友人の推薦など、あるソースノードのトップスコアリング隣人を取得することである。
これらのサービスは、低レイテンシで多くの候補ノードから上位のスコアリング隣人を見つけるために、高い推論スケーラビリティを望んでいる。
最近のlpモデルはノード埋め込みからエッジスコアを計算するために主に使われている2つの一般的なデコーダがある: \textbf{hadamardmlp} と \textbf{dot product} デコーダである。
理論的および経験的分析の結果,アダマールMLPデコーダは一般的にLPに対して有効であることが判明した。
しかし、HadamardMLPは、大きなグラフ上で上位のスコアリング隣人を検索するスケーラビリティに欠けており、私たちの知る限り、下位の複雑さで上位のスコアリング隣人を検索するアルゴリズムは存在しない。
HadamardMLPをスケーラブルにするために、HadamardMLPの上位評価近傍検索を高速化する \textit{Flashlight} アルゴリズムを提案する。
実験結果から, Flashlight は大きな OGBL-CITATION2 データセットにおいて,有効性を犠牲にすることなく,LP の推論速度を 100 倍以上改善することが示された。
提案手法は,AdamardMLPデコーダを用いた大規模LPアプリケーションを実現するための手法である。
関連論文リスト
- Improving Dual-Encoder Training through Dynamic Indexes for Negative
Mining [61.09807522366773]
本稿では,ソフトマックスを証明可能な境界で近似し,木を動的に維持するアルゴリズムを提案する。
我々は,2000万以上のターゲットを持つデータセットについて検討し,オラクル・ブルート力負の鉱業に関して,誤差を半分に削減した。
論文 参考訳(メタデータ) (2023-03-27T15:18:32Z) - MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP
Initialization [51.76758674012744]
大きなグラフ上でグラフニューラルネットワーク(GNN)をトレーニングするのは複雑で、非常に時間がかかる。
我々は、PeerInitと呼ばれるGNNトレーニングアクセラレーションに対して、恥ずかしく単純だが非常に効果的な方法を提案する。
論文 参考訳(メタデータ) (2022-09-30T21:33:51Z) - FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor
Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。
FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。
実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文 参考訳(メタデータ) (2022-06-22T22:30:46Z) - Filter-enhanced MLP is All You Need for Sequential Recommendation [89.0974365344997]
オンラインプラットフォームでは、ログされたユーザの行動データはノイズを含まないことは避けられない。
周波数領域の雑音を減衰させる信号処理から,フィルタアルゴリズムのアイデアを借用する。
逐次レコメンデーションタスクのための学習可能なフィルタを備えたオールMLPモデルである textbfFMLP-Rec を提案する。
論文 参考訳(メタデータ) (2022-02-28T05:49:35Z) - Quantum message-passing algorithm for optimal and efficient decoding [8.122270502556372]
我々はBPQMアルゴリズムの理解、形式、適用性を拡張する。
BPQMアルゴリズムの完全かつ曖昧さのない最初の公式記述を提供する。
BPQM がサイクルを持つ因子グラフ上で最も優れた古典デコーダを著しく上回ることを示す有望な数値結果を示す。
論文 参考訳(メタデータ) (2021-09-16T18:01:12Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳(メタデータ) (2021-03-17T23:13:25Z) - Projection-based QLP Algorithm for Efficiently Computing Low-Rank
Approximation of Matrices [6.952039070065292]
投影型部分QLP(PbP-QLP)は、p-QLPを精度良く効率的に近似する新しいアルゴリズムである。
pbp-qlpは、競合するランダムアルゴリズムよりも、現代のコンピュータアーキテクチャを利用することができる。
論文 参考訳(メタデータ) (2021-03-12T12:53:04Z) - A PDD Decoder for Binary Linear Codes With Neural Check Polytope
Projection [43.97522161614078]
基本ポリトープに基づく最大可算(ML)復号問題に対処するPDDアルゴリズムを提案する。
また、PDD復号アルゴリズムの最も時間を要する部分に機械学習技術を統合することを提案する。
本稿では、デコード遅延を低減するために特別に設計されたニューラルCPP(N CPP)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-11T07:57:15Z) - Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。
最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
論文 参考訳(メタデータ) (2020-05-07T00:39:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。