論文の概要: Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams

• arxiv url: http://arxiv.org/abs/2211.06793v1
• Date: Sun, 13 Nov 2022 03:01:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 20:03:03.285352
• Title: Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams
• Title（参考訳）: 強化学習による重み付きサンプリングによる完全動的グラフストリームの高精度サブグラフ計測
• Authors: Kaixin Wang, Cheng Long, Da Yan, Jie Zhang, H. V. Jagadish
• Abstract要約: 完全動的グラフストリームにおける部分グラフ数を推定するための重み付きサンプリングアルゴリズムWSDを提案する。 強化学習に基づく新しい手法を用いて,エッジの重みをデータ駆動方式で決定する。
• 参考スコア（独自算出の注目度）: 35.943447765433774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As the popularity of graph data increases, there is a growing need to count the occurrences of subgraph patterns of interest, for a variety of applications. Many graphs are massive in scale and also fully dynamic (with insertions and deletions of edges), rendering exact computation of these counts to be infeasible. Common practice is, instead, to use a small set of edges as a sample to estimate the counts. Existing sampling algorithms for fully dynamic graphs sample the edges with uniform probability. In this paper, we show that we can do much better if we sample edges based on their individual properties. Specifically, we propose a weighted sampling algorithm called WSD for estimating the subgraph count in a fully dynamic graph stream, which samples the edges based on their weights that indicate their importance and reflect their properties. We determine the weights of edges in a data-driven fashion, using a novel method based on reinforcement learning. We conduct extensive experiments to verify that our technique can produce estimates with smaller errors while often running faster compared with existing algorithms.
• Abstract（参考訳）: グラフデータの人気が高まるにつれ、様々なアプリケーションにおいて、関心のあるサブグラフパターンの発生をカウントする必要性が高まっている。 多くのグラフは大規模であり、(エッジの挿入や削除を含む)完全に動的であり、これらの数値の正確な計算は不可能である。 一般的なプラクティスは、小さなエッジセットをサンプルとして使用してカウントを見積もることである。 完全動的グラフの既存のサンプリングアルゴリズムは、一様確率でエッジをサンプリングする。 本稿では,それぞれの特性に基づいてエッジをサンプリングすれば,より優れた処理ができることを示す。 具体的には,全動的グラフストリームにおける部分グラフ数を推定するためのwsdと呼ばれる重み付きサンプリングアルゴリズムを提案する。 本研究では,強化学習に基づく新しい手法を用いて,エッジの重み付けをデータ駆動方式で決定する。 我々は,既存のアルゴリズムと比較して高速に動作しながら,誤差を小さくして推定できることを示すため,広範囲な実験を行った。

関連論文リスト

• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。 エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。 本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
  論文  参考訳（メタデータ） (2023-11-03T16:50:26Z)
• Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
  リンク予測はグラフ構造化データ計算の基本的な問題である。 本稿では,スパース囲み部分グラフを用いて予測を行うScaLedというスケーラブルな解を提案する。 より小さなサンプルサブグラフを活用することで、ScaLedは高い精度を維持しながらオーバーヘッドをはるかに少なく大きなグラフにスケールすることができる。
  論文  参考訳（メタデータ） (2022-06-23T22:48:44Z)
• Ordered Subgraph Aggregation Networks [19.18478955240166]
  グラフ強化グラフニューラルネットワーク(GNN)が登場し、標準(メッセージパス)GNNの表現力を確実に向上させている。 本稿では, 理論的枠組みを導入し, サブグラフ強化GNNの表現性を拡張した。 部分グラフサイズの増加は常に表現力を高め、それらの制限をよりよく理解することを示します。
  論文  参考訳（メタデータ） (2022-06-22T15:19:34Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation [53.95297550117153]
  本稿では,大規模な視覚データテンソルの処理を行うエンドツーエンドのトレーニング可能なフレームワークを提案する。 提案手法は大規模多次元グリッドデータや,大規模受容領域上のコンテキストを必要とするタスクに特に有用である。
  論文  参考訳（メタデータ） (2021-05-29T08:39:57Z)
• EGL++: Extending Expected Gradient Length to Active Learning for Human Pose Estimation [2.0305676256390934]
  最先端の人間のポーズ推定モデルは、堅牢なパフォーマンスのために大量のラベル付きデータに依存する。 EGL++は、予測勾配長を離散ラベルが利用できないタスクに拡張する新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2021-04-19T17:56:59Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• 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)

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

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