論文の概要: Fast Online Node Labeling for Very Large Graphs

• arxiv url: http://arxiv.org/abs/2305.16257v2
• Date: Sun, 28 May 2023 14:16:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-30 11:09:39.454849
• Title: Fast Online Node Labeling for Very Large Graphs
• Title（参考訳）: 非常に大きなグラフのための高速オンラインノードラベリング
• Authors: Baojian Zhou, Yifan Sun, Reza Babanezhad
• Abstract要約: 現在のメソッドは、$mathcalO(n3)$または$mathcalO(n2)$スペースの複雑さでグラフカーネルランタイムマトリックスを反転させるか、ランダムなスパンニングツリーを大量にサンプリングする。 本稿では,一連の研究によって導入されたテクスチトリン緩和技術に基づく改善を提案する。
• 参考スコア（独自算出の注目度）: 11.700626862639131
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the online node classification problem under a transductive learning setting. Current methods either invert a graph kernel matrix with $\mathcal{O}(n^3)$ runtime and $\mathcal{O}(n^2)$ space complexity or sample a large volume of random spanning trees, thus are difficult to scale to large graphs. In this work, we propose an improvement based on the \textit{online relaxation} technique introduced by a series of works (Rakhlin et al.,2012; Rakhlin and Sridharan, 2015; 2017). We first prove an effective regret $\mathcal{O}(\sqrt{n^{1+\gamma}})$ when suitable parameterized graph kernels are chosen, then propose an approximate algorithm FastONL enjoying $\mathcal{O}(k\sqrt{n^{1+\gamma}})$ regret based on this relaxation. The key of FastONL is a \textit{generalized local push} method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the per-prediction cost is $\mathcal{O}(\text{vol}({\mathcal{S}})\log 1/\epsilon)$ locally dependent on the graph with linear memory cost. Experiments show that our scalable method enjoys a better tradeoff between local and global consistency.
• Abstract（参考訳）: 本稿では,トランスダクティブ学習環境下でのオンラインノード分類問題について検討する。 現在の手法は、$\mathcal{O}(n^3)$ランタイムと$\mathcal{O}(n^2)$空間の複雑さでグラフカーネル行列を反転させるか、ランダムに広がる木を大量にサンプリングする。 本研究では,一連の著作(rakhlin et al., 2012, rakhlin and sridharan, 2015; 2017)によって導入された, \textit{online relax} 技法に基づく改善を提案する。 まず、適切なパラメータ化されたグラフカーネルが選択されたときに、有効後悔$\mathcal{O}(\sqrt{n^{1+\gamma}})$を証明し、この緩和に基づいて、$\mathcal{O}(k\sqrt{n^{1+\gamma}})を満足する近似アルゴリズムFastONLを提案する。 FastONLの鍵は、逆行列列を効果的に近似し、一連の人気のあるカーネルに適用する \textit{ Generalized local push} メソッドである。 さらに、予測コストは$\mathcal{O}(\text{vol}({\mathcal{S}})\log 1/\epsilon)$ である。 実験の結果,我々のスケーラブルな手法は,局所的一貫性とグローバル的一貫性のトレードオフを良好に享受できることがわかった。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• A framework for optimal quantum spatial search using alternating phase-walks [0.0]
  我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。 様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
  論文  参考訳（メタデータ） (2021-09-29T11:16:52Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
  そこで,MathcalS$ の目的 $min_textbfM は計量行列 $textbfM$ の凸微分可能な関数である。 Gershgorinディスクは、最初のeigenvector $textbfv$ of $textbfM$を使って完全に整列可能であることを証明します。 実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
  論文  参考訳（メタデータ） (2020-01-28T17:44:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。