論文の概要: Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs

• arxiv url: http://arxiv.org/abs/2607.02603v1
• Date: Wed, 01 Jul 2026 13:11:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:29.346381
• Title: Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs
• Title（参考訳）: GPUを用いた大量グラフへのWeisfeiler-Leman表現性解析のスケーリング
• Abstract要約: グラフニューラルネットワークはWeisfeiler-Leman (1-WL)の安定着色に基づいている 古典的なアルゴリズムは本質的にシーケンシャルであり、現代の大規模並列ハードウェアを活用できない。 1-WL安定色付けの線形代数的解釈を活用し、2つの重要な寄与を導入する。 初めて、300億のエッジを持つWebスケールのグラフ上で、CPUベースラインがタイムアウトまたはフェールする安定した色付けをうまく計算する。
• 参考スコア（独自算出の注目度）: 0.4396860522241306
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The stable coloring of the Weisfeiler-Leman (1-WL) test is a cornerstone of Graph Neural Networks because it provides an upper bound to the expressive power of message-passing architectures. Unfortunately, computing it presents two fundamental bottlenecks. First, classic algorithms are inherently sequential and cannot exploit modern massively parallel hardware. Second, these are \emph{global} algorithms, i.e., they require availability in memory of the full graph, severely limiting applicability to real-world instances. We leverage a linear-algebraic interpretation of 1-WL stable coloring and introduce two key contributions: (i)~a randomized refinement algorithm with tight probabilistic guarantees and (ii)~a correctness-preserving batching scheme that decomposes the graph into independently processable subgraphs while provably returning a stable coloring of the original graph. This approach maps directly to GPU-efficient primitives. In numerical experiments, our CUDA implementation delivers speedups up to two orders of magnitude over classical CPU-based partition refinement and, for the first time, successfully computes stable colorings on web-scale graphs with over 30 billion edges, where CPU baselines time out or fail.
• Abstract（参考訳）: Weisfeiler-Leman (1-WL) テストの安定な色付けは、メッセージパッシングアーキテクチャの表現力に上限を与えるため、グラフニューラルネットワークの基盤となる。 残念ながら、計算には2つの基本的なボトルネックがある。 第一に、古典的なアルゴリズムは本質的にシーケンシャルであり、現代の大規模並列ハードウェアを活用できない。 第二に、これらは 'emph{global}' アルゴリズムであり、すなわち、フルグラフのメモリの可用性が必要であり、現実世界のインスタンスに適用性を大幅に制限する。 1-WL安定着色における線形代数的解釈を活用し,2つの重要な貢献点を紹介する。 (i)~厳密な確率的保証とランダム化精製アルゴリズム (ii)~グラフを独立に処理可能なサブグラフに分解し、元のグラフの安定な色付けを確実に返却する正当性保存バッチ方式。 このアプローチはGPU効率の良いプリミティブに直接マップする。 数値実験では,従来のCPUベースの分割処理よりも最大2桁の高速化を実現し,300億以上のエッジを持つWebスケールグラフ上で,CPUベースラインがタイムアウトあるいはフェールする安定した色付けを初めて計算した。

関連論文リスト

• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。 局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。 粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
  論文  参考訳（メタデータ） (2026-05-13T05:24:35Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  SWING: Space Walks for Implicit Network Graphsはグラフ上のグラフランダム特徴を含む計算アルゴリズムの新しいクラスである。 SWINGの詳細な解析を行い、様々なiグラフのクラスで徹底的な実験を行い、それを補完する。
  論文  参考訳（メタデータ） (2026-02-13T08:12:38Z)
• Efficient Learning on Large Graphs using a Densifying Regularity Lemma [7.2134828716289645]
  交差する二部体成分の組み合わせに基づいて、大きな有向グラフの低ランク分解を導入する。 グラフ,スパース,あるいは密度を高密度IBGで効率的に近似する方法を示す。
  論文  参考訳（メタデータ） (2025-04-25T11:34:44Z)
• Boosting Graph Neural Network Expressivity with Learnable Lanczos Constraints [7.605749412696919]
  グラフニューラルネットワーク(GNN)はグラフ構造化データの処理に優れるが、リンク予測タスクでは性能が劣ることが多い。 グラフラプラシア行列の固有基底に誘導された部分グラフを埋め込むことによりGNNの表現性を高める新しい手法を提案する。 本研究では,2-WLで区別できないグラフを,効率的な時間的複雑性を維持しながら識別できることを実証する。
  論文  参考訳（メタデータ） (2024-08-22T12:22:00Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。 まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。 次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
  論文  参考訳（メタデータ） (2023-08-03T07:00:04Z)
• Malware Analysis with Symbolic Execution and Graph Kernel [2.1377923666134113]
  機械学習に基づく分類のためのオープンソースのツールチェーンを提案する。 グラフ間の局所的な類似性を捉えることができる1次元Weisfeiler-Lehmanカーネルに焦点を当てる。
  論文  参考訳（メタデータ） (2022-04-12T08:52:33Z)
• Boosting Graph Embedding on a Single GPU [3.093890460224435]
  大規模グラフを最小限のハードウェア制約で埋め込むためのGPUベースのツールであるGOSHを提案する。 更新の影響を高め、埋め込み作業を最小限にするため、新しいグラフ粗化アルゴリズムを採用している。 また、任意の任意の大きなグラフを単一のGPUで埋め込むことができる分解スキーマも組み込まれている。
  論文  参考訳（メタデータ） (2021-10-19T15:25:04Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale(GAS)は、任意のメッセージパスGNNを大規模グラフにスケールするためのフレームワークである。 ガスは、前回のトレーニングの繰り返しから過去の埋め込みを利用して計算グラフのサブツリー全体を掘り起こします。 ガスは大規模グラフ上で最先端のパフォーマンスに達する。
  論文  参考訳（メタデータ） (2021-06-10T09:26:56Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。 本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。 実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
  論文  参考訳（メタデータ） (2020-10-29T08:55:33Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
  ヘテロジニアスCPU+GPUアーキテクチャの深層学習のためのトレーニングアルゴリズムについて検討する。 私たちの2倍の目標 -- 収束率と資源利用を同時に最大化する -- は、この問題を難しくします。 これらのアルゴリズムの実装は,複数の実データセットよりも高速な収束と資源利用の両立を実現していることを示す。
  論文  参考訳（メタデータ） (2020-04-19T05:21:20Z)

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

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