論文の概要: Random Search Neural Networks for Efficient and Expressive Graph Learning

• arxiv url: http://arxiv.org/abs/2510.22520v1
• Date: Sun, 26 Oct 2025 04:03:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 19:54:32.528415
• Title: Random Search Neural Networks for Efficient and Expressive Graph Learning
• Title（参考訳）: 効率的なグラフ学習のためのランダム探索ニューラルネットワーク
• Authors: Michael Ito, Danai Koutra, Jenna Wiens,
• Abstract要約: ランダムウォークニューラルネットワーク(RWNN)は、グラフ表現学習の有望なアプローチとして登場した。 本稿では,ランダムな検索を行ない,ノードの完全カバレッジを保証したテキストテトラノム探索ニューラルネットワーク(RSNN)を提案する。 我々の研究は、ランダムウォークに基づくアプローチの理論的および実践的な進歩を橋渡しし、スパースグラフを学習するための効率的かつ表現力のあるフレームワークを提供する。
• 参考スコア（独自算出の注目度）: 20.25231362547659
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random walk neural networks (RWNNs) have emerged as a promising approach for graph representation learning, leveraging recent advances in sequence models to process random walks. However, under realistic sampling constraints, RWNNs often fail to capture global structure even in small graphs due to incomplete node and edge coverage, limiting their expressivity. To address this, we propose \textit{random search neural networks} (RSNNs), which operate on random searches, each of which guarantees full node coverage. Theoretically, we demonstrate that in sparse graphs, only $O(\log |V|)$ searches are needed to achieve full edge coverage, substantially reducing sampling complexity compared to the $O(|V|)$ walks required by RWNNs (assuming walk lengths scale with graph size). Furthermore, when paired with universal sequence models, RSNNs are universal approximators. We lastly show RSNNs are probabilistically invariant to graph isomorphisms, ensuring their expectation is an isomorphism-invariant graph function. Empirically, RSNNs consistently outperform RWNNs on molecular and protein benchmarks, achieving comparable or superior performance with up to 16$\times$ fewer sampled sequences. Our work bridges theoretical and practical advances in random walk based approaches, offering an efficient and expressive framework for learning on sparse graphs.
• Abstract（参考訳）: ランダムウォークニューラルネットワーク(RWNN)がグラフ表現学習の有望なアプローチとして登場し、シーケンスモデルの最近の進歩を活用してランダムウォークを処理する。 しかし、現実的なサンプリング制約の下では、RWNNは不完全なノードとエッジカバレッジのため、小さなグラフであってもグローバルな構造を捕捉できず、その表現性を制限する。 そこで本稿では,ランダムな検索を行う‘textit{random search Neural Network} (RSNNs) を提案する。 理論的には、スパースグラフでは、完全なエッジカバレッジを達成するために$O(\log |V|)$サーチしか必要とせず、RWNNが要求するウォーキング(グラフサイズによるウォーキング長のスケールを仮定する)に比べてサンプリングの複雑さを著しく低減することを示した。 さらに、ユニバーサルシーケンスモデルと組み合わせると、RSNNはユニバーサル近似器となる。 最後に、RSNNがグラフ同型に確率的に不変であることを示し、それらの期待が同型不変グラフ関数であることを保証する。 経験的に、RSNNは分子とタンパク質のベンチマークでRWNNを一貫して上回り、最大16$\times$より少ないサンプルシーケンスで同等または優れたパフォーマンスを達成した。 我々の研究は、ランダムウォークに基づくアプローチの理論的および実践的な進歩を橋渡しし、スパースグラフを学習するための効率的かつ表現力のあるフレームワークを提供する。

関連論文リスト

• Non-convolutional Graph Neural Networks [46.79328529882998]
  畳み込み演算子を完全に含まない単純なグラフ学習モジュールを設計し、RUMニューラルネットワークを用いたランダムウォークを作成した。 RUMは競合する性能を実現するが、より堅牢で、メモリ効率が高く、スケーラブルで、最も単純な畳み込みGNNよりも高速である。
  論文  参考訳（メタデータ） (2024-07-31T21:29:26Z)
• EIGNN: Efficient Infinite-Depth Graph Neural Networks [51.97361378423152]
  グラフニューラルネットワーク(GNN)は多くのアプリケーションでグラフ構造化データのモデリングに広く利用されている。 この制限により、無限深度GNNモデルを提案し、これをEIGNN(Efficient Infinite-Depth Graph Neural Networks)と呼ぶ。 EIGNNは、最近のベースラインよりも長距離依存関係をキャプチャする能力が優れており、常に最先端のパフォーマンスを実現していることを示す。
  論文  参考訳（メタデータ） (2022-02-22T08:16:58Z)
• On the Universality of Graph Neural Networks on Large Random Graphs [22.720758067273195]
  グラフニューラルネットワーク(GNN)の潜在位置乱数グラフに対する近似能力について検討する。 大きなグラフ極限では、GNNはc-GNNとして知られるある種の連続的なモデルに収束することが知られている。 我々は,c-SGNNが連続限界におけるc-GNNよりも厳格に強力なことを示す。
  論文  参考訳（メタデータ） (2021-05-27T12:52:36Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)

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

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