論文の概要: Distance-Preserving Embeddings in Inhomogeneous Random Graphs

• arxiv url: http://arxiv.org/abs/2607.10074v1
• Date: Sat, 11 Jul 2026 01:59:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-14 15:40:48.28802
• Title: Distance-Preserving Embeddings in Inhomogeneous Random Graphs
• Title（参考訳）: 不均一ランダムグラフにおける距離保存埋め込み
• Abstract要約: 非均一なランダムグラフ上のランドマークベースの埋め込みによる最短パス近似を解析する。 これらの保証は、大域的、コンポーネント全体の平均に拡張し、有限型および連続潜在空間における解析を統一する。 本稿では,厳密で計算コストのかかる最短パスクエリを,柔軟で構造を意識したニューラルサロゲートに置き換えるGNN拡張型を提案する。
• 参考スコア（独自算出の注目度）: 9.290757451344671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph machine learning provides powerful tools for understanding complex networks and learning meaningful node representations. A central challenge, however, is designing embeddings with minimal distortion of both local and global functionals, such as shortest path lengths. Prior distortion guarantees for distance-preserving embeddings are worst-case in nature, producing overly pessimistic bounds that fail to capture the structure of typical large-scale networks. To address this, we analyze shortest-path approximation via landmark-based embeddings on inhomogeneous random graphs, a general model with type-dependent edge probabilities. By retaining shortest paths to a small set of reference nodes called landmarks, landmark-based methods effectively function as virtual graph spanners, where structural heterogeneity and controlled neighborhood expansion modeled via multi-type branching processes enable significantly tighter dimension-distortion trade-offs than classical worst-case bounds. We extend these guarantees to global, component-wide averages and unify the analysis across finite-type and continuous latent spaces through a novel metric sandwiching framework, establishing universal distortion bounds for general $L^2$ kernel models, including heavy-tailed and power-law networks. Finally, we introduce a GNN-augmented variant that replaces rigid, computationally expensive exact shortest-path queries with flexible, structure-aware neural surrogates. By leveraging the inherent alignment between graph neural message-passing and the dynamic programming principles of shortest-path algorithms, our approach demonstrates that models trained on small-scale random graphs learn to extract universal distance-preserving features, achieving robust generalization to large-scale, real-world networks that match or exceed the fidelity of classical, exact landmark-based embeddings.
• Abstract（参考訳）: グラフ機械学習は、複雑なネットワークを理解し、意味のあるノード表現を学習するための強力なツールを提供する。 しかし、重要な課題は、最短経路長などの局所関数と大域関数の両方の歪みを最小限に抑えた埋め込みを設計することである。 距離保存埋め込みに対する事前の歪み保証は、本質的に最悪のケースであり、典型的な大規模ネットワークの構造を捉えるのに失敗する過度に悲観的な境界を生み出す。 そこで本研究では,非同次乱数グラフへのランドマークベース埋め込みによる最短パス近似を,タイプ依存エッジ確率の一般モデルとして解析する。 ランドマークと呼ばれる小さな参照ノードへの最短経路を保持することで、ランドマークベースの手法は仮想グラフスパンナーとして効果的に機能する。 これらの保証を大域的, コンポーネント全体の平均に拡張し, 有限型および連続潜在空間をまたいだ解析を新しい計量サンドイッチフレームワークにより統一し, 重み付きネットワークやパワーローネットワークを含む一般の$L^2$カーネルモデルに対する普遍的歪み境界を確立する。 最後に,厳密で計算コストのかかる最短パスクエリを,柔軟で構造を意識したニューラルサロゲートに置き換えるGNN拡張型を提案する。 提案手法は,グラフニューラルメッセージパッシングと最短パスアルゴリズムの動的プログラミング原理との相似性を利用して,小規模ランダムグラフで訓練されたモデルが普遍的な距離保存特徴を抽出し,古典的かつ正確なランドマークベースの埋め込みの忠実さに適合または超越した大規模実世界のネットワークへの堅牢な一般化を実現することを実証する。

関連論文リスト

• Convergence of Gradient Descent for General Neural Network Architectures Beyond the NTK Regime [24.053364183688874]
  トレーニングダイナミクスはニューラルネットワークを理解する上で中心的な存在だ。 本稿では,ニューラルネットワークアーキテクチャの幅広いファミリ下での勾配降下ダイナミクス解析のための収束フレームワークを提案する。
  論文  参考訳（メタデータ） (2026-06-22T14:00:26Z)
• Plain Transformers are Surprisingly Powerful Link Predictors [57.01966734467712]
  リンク予測はグラフ機械学習における中核的な課題であり、リッチで複雑なトポロジ的依存関係をキャプチャするモデルを必要とする。 グラフニューラルネットワーク(GNN)が標準的なソリューションであるのに対して、最先端のパイプラインは明示的な構造やメモリ集約的なノードの埋め込みに依存していることが多い。 本報告では,手作りのプリミティブに置き換えるエンコーダのみのプレーントランスであるPENCILについて,サンプリングしたローカルサブグラフに注目する。
  論文  参考訳（メタデータ） (2026-02-02T02:45:52Z)
• Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization [13.021238902084647]
  グラフニューラルネットワーク(GNN)のオーバースムース化は、異なるノード機能で崩壊を引き起こす。 SGPC (Sheaf GNNs with PAC-Bayes) は,セルラーシェーフメッセージパッシングと複数のメカニズムを組み合わせた統一アーキテクチャである。 9つのホモ親和性およびヘテロ親和性ベンチマークの実験により、SGPCは最先端スペクトルおよび層ベースGNNよりも優れた性能を示した。
  論文  参考訳（メタデータ） (2025-08-01T06:39:28Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  スケーラブルで効果的なグラフ学習のためのマルチホップノード機能を適応的に融合する新しいフレームワークであるScaleGNNを提案する。 予測精度と計算効率の両面で,ScaleGNNは最先端のGNNよりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-22T14:05:11Z)
• DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
  グラフニューラルネットワーク(GNN)は、メッセージパッシングプロセスの近傍集約を通じてグラフ構造化データを処理するように設計されている。 メッセージパッシングにより、GNNは短距離空間的相互作用を理解できるだけでなく、過度なスムーシングや過度なスカッシングに悩まされる。 本稿では,線形計算オーバーヘッドを伴うオーバー・スムーシングとオーバー・スキャッシングに対処するための,emph情報フロー制御機構を提案する。 さまざまなサイズ、トポロジ、密度、ホモフィリック比のグラフを含む10の実世界のデータセットを対象に、我々のモデルをベンチマークし、優れたパフォーマンスを示す。
  論文  参考訳（メタデータ） (2025-01-10T14:34:20Z)
• DepGraph: Towards Any Structural Pruning [68.40343338847664]
  我々は、CNN、RNN、GNN、Transformersのような任意のアーキテクチャの一般的な構造解析について研究する。 本稿では,階層間の依存関係を明示的にモデル化し,包括的にグループ化してプルーニングを行う汎用かつ完全自動な手法であるemphDependency Graph(DepGraph)を提案する。 本研究では,画像用ResNe(X)t,DenseNet,MobileNet,Vision Transformer,グラフ用GAT,3Dポイントクラウド用DGCNN,言語用LSTMなど,さまざまなアーキテクチャやタスクに関する手法を広範囲に評価し,言語用LSTMと並行して示す。
  論文  参考訳（メタデータ） (2023-01-30T14:02:33Z)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  不均一グラフニューラルネットワーク(HGNN)は、不均一グラフの豊富な構造的および意味的な情報をノード表現に埋め込む強力な能力を持つ。 既存のHGNNは、同種グラフ上のグラフニューラルネットワーク(GNN)から多くのメカニズム、特に注意機構と多層構造を継承する。 本稿では,これらのメカニズムを詳細に検討し,簡便かつ効率的なヘテロジニアスグラフニューラルネットワーク(SeHGNN)を提案する。
  論文  参考訳（メタデータ） (2022-07-06T10:01:46Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。 我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
  論文  参考訳（メタデータ） (2022-05-18T16:57:10Z)
• Geodesic Length Distribution in Sparse Network Ensembles [0.0]
  超臨界状態における巨大成分の測地線長の解析的分布を導出する。 ブロックモデルやドット積グラフ,ランダムな幾何グラフ,グラフなど,広く使用されているネットワークモデルに対して,結果を提供する。
  論文  参考訳（メタデータ） (2021-11-03T16:25:39Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)
• Graph Neural Networks Inspired by Classical Iterative Algorithms [28.528150667063876]
  我々は、2つの古典的反復アルゴリズムの更新ルールを模倣し、統合するために設計された新しいGNNレイヤーのファミリーを考える。 新しい注意機構は、基礎となるエンドツーエンドエネルギー関数に明示的に固定され、エッジの不確かさに関する安定性に寄与する。
  論文  参考訳（メタデータ） (2021-03-10T14:08:12Z)
• Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics [50.83356836818667]
  本稿では,ディープラーニングの最適化を一般化誤差と関連づけて解析する理論フレームワークを提案する。 ニューラルネットワーク最適化分析のための平均場理論やニューラル・タンジェント・カーネル理論のような既存のフレームワークは、そのグローバル収束を示すために、ネットワークの無限幅の限界を取る必要がある。
  論文  参考訳（メタデータ） (2020-07-11T18:19:50Z)

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

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