論文の概要: Learning from one graph: transductive learning guarantees via the geometry of small random worlds
- arxiv url: http://arxiv.org/abs/2509.06894v1
- Date: Mon, 08 Sep 2025 17:13:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-09 14:07:04.278566
- Title: Learning from one graph: transductive learning guarantees via the geometry of small random worlds
- Title（参考訳）: 1つのグラフからの学習:小さなランダム世界の幾何学によるトランスダクティブ学習保証
- Authors: Nils Detering, Luca Galimberti, Anastasis Kratsios, Giulia Livieri, A. Martina Neuman,
- Abstract要約: 我々は,低次元メートル法埋め込みによる大規模グラフの幾何正則性を活用する新しい集中度測定ツールを開発した。
まず、任意の決定論的 $k$-vertex グラフと、ErdHos-R'enyi グラフ $mathbfG=mathbfG(k,p)$ in the regime $p in the MathcalO((log (k)/k)1/2) で鍵幾何学的性質を共有するランダムグラフについて述べる。
- 参考スコア（独自算出の注目度）: 8.781923502647055
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Since their introduction by Kipf and Welling in $2017$, a primary use of graph convolutional networks is transductive node classification, where missing labels are inferred within a single observed graph and its feature matrix. Despite the widespread use of the network model, the statistical foundations of transductive learning remain limited, as standard inference frameworks typically rely on multiple independent samples rather than a single graph. In this work, we address these gaps by developing new concentration-of-measure tools that leverage the geometric regularities of large graphs via low-dimensional metric embeddings. The emergent regularities are captured using a random graph model; however, the methods remain applicable to deterministic graphs once observed. We establish two principal learning results. The first concerns arbitrary deterministic $k$-vertex graphs, and the second addresses random graphs that share key geometric properties with an Erd\H{o}s-R\'{e}nyi graph $\mathbf{G}=\mathbf{G}(k,p)$ in the regime $p \in \mathcal{O}((\log (k)/k)^{1/2})$. The first result serves as the basis for and illuminates the second. We then extend these results to the graph convolutional network setting, where additional challenges arise. Lastly, our learning guarantees remain informative even with a few labelled nodes $N$ and achieve the optimal nonparametric rate $\mathcal{O}(N^{-1/2})$ as $N$ grows.
- Abstract（参考訳）: 2017年のKipfとWellingによる紹介以来、グラフ畳み込みネットワークの第一の用途はトランスダクティブノード分類であり、欠落したラベルは単一の観測されたグラフとその特徴行列内で推論される。
ネットワークモデルが広く使われているにもかかわらず、標準的な推論フレームワークは単一のグラフではなく複数の独立したサンプルに依存しているため、トランスダクティブ学習の統計的基盤は依然として限られている。
本研究は,低次元メートル法埋め込みによる大規模グラフの幾何学的正則性を活用した新しい集中度測定ツールを開発することで,これらのギャップに対処する。
創発正則性はランダムグラフモデルを用いて取得されるが、その方法は一度観測された決定論的グラフに適用できる。
私たちは2つの主要な学習結果を確立します。
第1の問題は任意の決定論的$k$-頂点グラフであり、第2の問題は、Erd\H{o}s-R\'{e}nyi graph $\mathbf{G}=\mathbf{G}(k,p)$ で鍵幾何学的性質を共有するランダムグラフを、体制 $p \in \mathcal{O}((\log (k)/k)^{1/2})$ で扱うことである。
第1結果は第2の照明の基礎となる。
次に、これらの結果をグラフ畳み込みネットワーク設定に拡張し、そこでさらなる課題が発生します。
最後に、いくつかのラベル付きノードが$N$であっても、学習保証は情報的であり、N$が成長するにつれて、最適な非パラメトリックレート$\mathcal{O}(N^{-1/2})$を達成する。
関連論文リスト
- Graph Semi-Supervised Learning for Point Classification on Data Manifolds [13.02854405679453]
データ多様体上の分類タスクのためのグラフ半教師付き学習フレームワークを提案する。
多様体仮説により、低次元 $mathcalM 部分集合 mathbbRF$ からサンプリングされた点としてデータをモデル化する。
我々は、$mathcalM$から一様サンプリングを行うと、半教師付きタスクの一般化ギャップはグラフサイズの増加とともに減少することを示す。
論文 参考訳（メタデータ） (2025-06-13T19:52:54Z) - Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions [84.01980526069075]
幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。
我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。
複数の実世界のデータセットに対する実験により、この理論結果を検証する。
論文 参考訳（メタデータ） (2024-09-08T18:55:57Z) - Two Heads Are Better Than One: Boosting Graph Sparse Training via
Semantic and Topological Awareness [80.87683145376305]
グラフニューラルネットワーク(GNN)は、様々なグラフ学習タスクに優れるが、大規模グラフに適用した場合、計算上の課題に直面している。
データレベルで空間を動的に操作するグラフスパーストレーニング(GST)を提案する。
GSTは、最大位相整合性と性能劣化のないスパースグラフを生成する。
論文 参考訳（メタデータ） (2024-02-02T09:10:35Z) - A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph
Coarsening [19.09507367362567]
この研究はグラフの粗大化を別の観点から研究し、グラフ距離を保存する理論を発展させた。
幾何学的アプローチは、グラフ分類や回帰のようなグラフの集合を扱う際に有用である。
この差を最小化するには、一般的な重み付きカーネル$K$-means法を用いる。
論文 参考訳（メタデータ） (2023-06-15T04:47:26Z) - Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。
本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
論文 参考訳（メタデータ） (2023-06-14T13:09:38Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - Effects of Graph Convolutions in Deep Networks [8.937905773981702]
多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。
単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。
ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
論文 参考訳（メタデータ） (2022-04-20T08:24:43Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
グラフニューラルネットワーク(GNN)の人気が高まっており、グラフで表されるデータに対して非常に有望な結果を示している。
本稿では,3つの選択された長さに基づいて,グラフのランダムなウォークデータ処理を提案する。すなわち,グラフ上の局所的および大域的ダイナミクスを捉えるために,長さ1,2の(正規)ウォークと長さ0,1$の分節ウォークを提案する。
本手法は, 処理ノードの特徴をネットワークに渡すことによって, 様々な分子データセット上で検証し, 分類および回帰処理を行う。
論文 参考訳（メタデータ） (2021-09-15T20:04:01Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。