論文の概要: A continuum limit for the PageRank algorithm
- arxiv url: http://arxiv.org/abs/2001.08973v3
- Date: Sun, 10 Jan 2021 15:05:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-07 05:37:47.438144
- Title: A continuum limit for the PageRank algorithm
- Title（参考訳）: PageRankアルゴリズムの連続極限
- Authors: Amber Yuan, Jeff Calder, Braxton Osting
- Abstract要約: 半教師あり、教師なしの機械学習手法は、しばしばデータモデリングにグラフに依存する。
本稿では,有向グラフ上での学習アルゴリズムの連続限界を厳密に研究するための新しいフレームワークを提案する。
正規化グラフの一種であるラプラシアンを含む有向グラフ上の数値スキームとして解釈する方法を示す。
- 参考スコア（独自算出の注目度）: 1.2891210250935146
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Semi-supervised and unsupervised machine learning methods often rely on
graphs to model data, prompting research on how theoretical properties of
operators on graphs are leveraged in learning problems. While most of the
existing literature focuses on undirected graphs, directed graphs are very
important in practice, giving models for physical, biological, or
transportation networks, among many other applications. In this paper, we
propose a new framework for rigorously studying continuum limits of learning
algorithms on directed graphs. We use the new framework to study the PageRank
algorithm, and show how it can be interpreted as a numerical scheme on a
directed graph involving a type of normalized graph Laplacian. We show that the
corresponding continuum limit problem, which is taken as the number of webpages
grows to infinity, is a second-order, possibly degenerate, elliptic equation
that contains reaction, diffusion, and advection terms. We prove that the
numerical scheme is consistent and stable and compute explicit rates of
convergence of the discrete solution to the solution of the continuum limit
PDE. We give applications to proving stability and asymptotic regularity of the
PageRank vector. Finally, we illustrate our results with numerical experiments
and explore an application to data depth.
- Abstract（参考訳）: 半教師付きおよび教師なしの機械学習手法は、しばしばデータをモデル化するためにグラフに依存し、グラフ上の演算子の理論的性質が学習問題にどのように活用されるかの研究を促す。
既存の文献のほとんどは非指向グラフに焦点を絞っているが、有向グラフは実際は非常に重要であり、物理的、生物学的、輸送ネットワークのモデルを提供する。
本稿では,有向グラフ上で学習アルゴリズムの連続限界を厳密に研究するための新しい枠組みを提案する。
新しい枠組みを用いてpagerankアルゴリズムを研究し,正規化グラフラプラシアンの一種を含む有向グラフ上の数値スキームとして解釈する方法を示した。
本研究では,webページ数が無限に成長するにつれて生じる,対応する連続体極限問題は,反応,拡散,付加項を含む2次,おそらくは縮退する楕円型方程式であることを示す。
数値的スキームは、連続極限 PDE の解に対する離散解の収束の一貫性と安定性、および計算的明示率であることを示す。
ページランクベクトルの安定性と漸近正則性を証明するために応用する。
最後に,数値実験を行い,データ深さへの応用について考察する。
関連論文リスト
- Continuous Product Graph Neural Networks [5.703629317205571]
複数のグラフ上に定義されたマルチドメインデータは、計算機科学の実践的応用において大きな可能性を秘めている。
TPDEGの自然な解として現れるCITRUS(Continuous Product Graph Neural Networks)を紹介する。
我々は、CITRUSをよく知られた交通・時間天気予報データセットで評価し、既存の手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2024-05-29T08:36:09Z) - Overcoming Order in Autoregressive Graph Generation [12.351817671944515]
グラフ生成は、化学やソーシャルネットワークなど、さまざまな領域における基本的な問題である。
近年の研究では、リカレントニューラルネットワーク(RNN)を用いた分子グラフ生成が、従来の生成手法と比較して有利であることが示されている。
論文 参考訳（メタデータ） (2024-02-04T09:58:22Z) - Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。
固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。
GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
論文 参考訳（メタデータ） (2022-05-19T14:08:15Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。
本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
論文 参考訳（メタデータ） (2022-02-05T08:21:04Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2021-12-15T01:45:32Z) - Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。
本稿では,2つのクラスタリングアルゴリズムについて述べる。
さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
論文 参考訳（メタデータ） (2021-10-06T13:14:44Z) - Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。
従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
論文 参考訳（メタデータ） (2021-05-12T06:47:34Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。