論文の概要: Scalable Graph Coreset Selection via Greedy Sampling

• arxiv url: http://arxiv.org/abs/2607.27602v1
• Date: Thu, 30 Jul 2026 02:45:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.368535
• Title: Scalable Graph Coreset Selection via Greedy Sampling
• Title（参考訳）: グレディサンプリングによるスケーラブルグラフコアセットの選択
• Authors: Zhaiming Shen, Alexander Cloninger,
• Abstract要約: 最小内部積グリーディ選択規則に基づく,単純かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。 ブロックモデルに基づいてアルゴリズムを解析し,次数分布がノード間で均衡している場合,クラスタサイズに対する比例サンプリングを実現する。
• 参考スコア（独自算出の注目度）: 48.91894218306487
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sampling representative nodes from large graphs is fundamental to graph signal processing and network analysis, yet existing methods require access to the full graph Laplacian, making them impractical at scale. We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule. At each iteration, the algorithm accesses only a small random subset of Laplacian columns, requiring no eigendecomposition or global graph traversal, making it well-suited for large-scale graphs where the full Laplacian cannot be stored in memory. We analyze the algorithm under the stochastic block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves sampling proportional to cluster size, and that the resulting mean estimate is controlled for band-limited graph signals in the Paley-Wiener space, with the error decaying as inter-cluster connectivity weakens. Numerical experiments on both synthetic and real-world data validate the effectiveness of the proposed method.
• Abstract（参考訳）: 大きなグラフから代表ノードをサンプリングすることは、グラフ信号処理とネットワーク解析に基本的であるが、既存の手法では全グラフラプラシアンへのアクセスが必要であり、大規模に非実用的である。 最小内部積グリーディ選択規則に基づく簡易かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。 各イテレーションにおいて、アルゴリズムはラプラシアン列の小さなランダムな部分集合のみにアクセスし、固有分解や大域グラフのトラバーサルを必要としないため、ラプラシアン全体をメモリに格納できない大規模グラフに適している。 確率ブロックモデルを用いてアルゴリズムを解析し,次数分布がノード間でバランスをとると,クラスタサイズに比例したサンプリング値が得られ,その結果の平均推定値がPaley-Wiener空間の帯域制限グラフ信号に対して制御され,クラスタ間接続が弱まると誤差が低下することを示す。 合成データと実世界のデータの両方に関する数値実験により,提案手法の有効性が検証された。

関連論文リスト

• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  本稿では,グラフ畳み込みフィルタが生成するノイズ測定から有向ネットワークを推定する問題に対処する。 また、上記のステップを交互に交互に組み合わせて、サンプルの複雑さを向上する結合グラフフィルタとトポロジー同定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-06-25T18:25:57Z)
• Efficient graph-diagonal characterization of noisy states distributed over quantum networks via Bell sampling [0.10486135378491267]
  グラフ状態は、量子ネットワークにおける分散情報処理と通信の鍵となる、絡み合った状態の重要なクラスである。 本稿では,Bellサンプリングサブルーチンを用いて,ネットワークに分散したノイズグラフ状態のグラフベースにおける対角要素を特徴付けるプロトコルを提案する。
  論文  参考訳（メタデータ） (2025-12-07T04:19:09Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。 コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。 この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
  論文  参考訳（メタデータ） (2025-07-17T10:02:57Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。 エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。 本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
  論文  参考訳（メタデータ） (2023-11-03T16:50:26Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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