論文の概要: Efficient Estimation of Shortest-Path Distance Distributions to Samples in Graphs

• arxiv url: http://arxiv.org/abs/2502.15890v1
• Date: Fri, 21 Feb 2025 19:21:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:52:12.078316
• Title: Efficient Estimation of Shortest-Path Distance Distributions to Samples in Graphs
• Title（参考訳）: グラフ中のサンプルに対する最短パス距離分布の効率的な推定法
• Authors: Alan Zhu, Jiaqi Ma, Qiaozhu Mei,
• Abstract要約: 本稿では,最短経路距離の分布を推定するための高精度かつ効率的なフレームワークを提案する。 我々のフレームワークは経験的手法よりも高速で、次数分布の仕様しか必要としない。
• 参考スコア（独自算出の注目度）: 14.492861079799516
• License:
• Abstract: As large graph datasets become increasingly common across many fields, sampling is often needed to reduce the graphs into manageable sizes. This procedure raises critical questions about representativeness as no sample can capture the properties of the original graph perfectly, and different parts of the graph are not evenly affected by the loss. Recent work has shown that the distances from the non-sampled nodes to the sampled nodes can be a quantitative indicator of bias and fairness in graph machine learning. However, to our knowledge, there is no method for evaluating how a sampling method affects the distribution of shortest-path distances without actually performing the sampling and shortest-path calculation. In this paper, we present an accurate and efficient framework for estimating the distribution of shortest-path distances to the sample, applicable to a wide range of sampling methods and graph structures. Our framework is faster than empirical methods and only requires the specification of degree distributions. We also extend our framework to handle graphs with community structures. While this introduces a decrease in accuracy, we demonstrate that our framework remains highly accurate on downstream comparison-based tasks. Code is publicly available at https://github.com/az1326/shortest_paths.
• Abstract（参考訳）: 大規模なグラフデータセットが多くの分野にまたがって一般的になるにつれて、グラフを管理可能なサイズに縮小するためにサンプリングがしばしば必要となる。 この手順は、サンプルが元のグラフのプロパティを完璧に捉えることができず、グラフの異なる部分が損失に均等に影響されないため、代表性に関する批判的な疑問を提起する。 近年の研究では、非サンプリングノードからサンプリングノードまでの距離が、グラフ機械学習におけるバイアスと公平性の定量的指標であることが示されている。 しかし,本研究では,サンプリング手法がサンプリングと最短パス計算を実際に行わずに,最短パス距離の分布にどのように影響するかを評価する方法がない。 本稿では,サンプルに対する最短経路距離の分布を推定するための,高精度かつ効率的なフレームワークについて述べる。 我々のフレームワークは経験的手法よりも高速で、次数分布の仕様しか必要としない。 グラフとコミュニティ構造を扱うためのフレームワークも拡張しています。 これは精度の低下をもたらすが、下流比較に基づくタスクにおいて、我々のフレームワークが極めて正確であることを実証する。 コードはhttps://github.com/az1326/shortest_pathsで公開されている。

関連論文リスト

• GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
  グラフニューラルネットワークは、隣人からの情報を集約することでノードを表現することを学ぶ。 いくつかの既存手法では、ノードの小さなサブセットをサンプリングし、GNNをもっと大きなグラフにスケールすることで、この問題に対処している。 本稿では,GNNのトレーニングに不可欠なノードの集合を識別する適応サンプリング手法であるGRAPESを紹介する。
  論文  参考訳（メタデータ） (2023-10-05T09:08:47Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。 トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。 仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
  論文  参考訳（メタデータ） (2023-08-16T13:10:27Z)
• Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams [35.943447765433774]
  完全動的グラフストリームにおける部分グラフ数を推定するための重み付きサンプリングアルゴリズムWSDを提案する。 強化学習に基づく新しい手法を用いて,エッジの重みをデータ駆動方式で決定する。
  論文  参考訳（メタデータ） (2022-11-13T03:01:34Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。 ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。 我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
  論文  参考訳（メタデータ） (2022-10-15T08:01:08Z)
• From Spectral Graph Convolutions to Large Scale Graph Convolutional Networks [0.0]
  グラフ畳み込みネットワーク(GCN)は、様々なタスクにうまく適用された強力な概念であることが示されている。 古典グラフ理論の関連部分を含むGCNの定義への道を開いた理論を考察する。
  論文  参考訳（メタデータ） (2022-07-12T16:57:08Z)
• Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
  リンク予測はグラフ構造化データ計算の基本的な問題である。 本稿では,スパース囲み部分グラフを用いて予測を行うScaLedというスケーラブルな解を提案する。 より小さなサンプルサブグラフを活用することで、ScaLedは高い精度を維持しながらオーバーヘッドをはるかに少なく大きなグラフにスケールすることができる。
  論文  参考訳（メタデータ） (2022-06-23T22:48:44Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。 粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
  論文  参考訳（メタデータ） (2021-10-06T16:58:34Z)
• Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks [3.075766050800645]
  隣のノードからデータを集約する必要があるため、トレーニンググラフ畳み込みネットワーク(GCN)は高価です。 先行研究では,少数の隣人を対象に,収集結果を推定する様々な近傍サンプリング手法が提案されている。 本稿では, 局所サンプリング確率を判定し, スクイード隣りのサンプリングがトレーニングの収束度に大きく影響しないことを確かめるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-19T16:12:44Z)
• Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
  グラフ畳み込みネットワーク(GCN)の訓練を高速化するために, ばらつきを低減したサンプリングアルゴリズムが提案されている。 これらのサンプリングアルゴリズムは、グラフ注意ネットワーク(GAT)のような固定重みよりも学習重量を含む、より一般的なグラフニューラルネットワーク(GNN)には適用できない。
  論文  参考訳（メタデータ） (2020-06-10T12:48:37Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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