論文の概要: Fast and Accurate Triangle Counting in Graph Streams Using Predictions
- arxiv url: http://arxiv.org/abs/2409.15205v1
- Date: Mon, 23 Sep 2024 16:52:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-26 14:02:53.158563
- Title: Fast and Accurate Triangle Counting in Graph Streams Using Predictions
- Title（参考訳）: 予測を用いたグラフストリームの高速かつ高精度な三角計数
- Authors: Cristian Boldrin, Fabio Vandin,
- Abstract要約: 本稿では, グラフストリーム中の三角形の数を予測した最初の効率的かつ実用的なアルゴリズムを提案する。
提案アルゴリズムは,待機室サンプリングと貯水池サンプリングと,エッジの重み,すなわちエッジが関与する三角形の数の予測器を組み合わせる。
- 参考スコア（独自算出の注目度）: 4.000869978312742
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we present the first efficient and practical algorithm for estimating the number of triangles in a graph stream using predictions. Our algorithm combines waiting room sampling and reservoir sampling with a predictor for the heaviness of edges, that is, the number of triangles in which an edge is involved. As a result, our algorithm is fast, provides guarantees on the amount of memory used, and exploits the additional information provided by the predictor to produce highly accurate estimates. We also propose a simple and domain-independent predictor, based on the degree of nodes, that can be easily computed with one pass on a stream of edges when the stream is available beforehand. Our analytical results show that, when the predictor provides useful information on the heaviness of edges, it leads to estimates with reduced variance compared to the state-of-the-art, even when the predictions are far from perfect. Our experimental results show that, when analyzing a single graph stream, our algorithm is faster than the state-of-the-art for a given memory budget, while providing significantly more accurate estimates. Even more interestingly, when sequences of hundreds of graph streams are analyzed, our algorithm significantly outperforms the state-of-the-art using our simple degree-based predictor built by analyzing only the first graph of the sequence.
- Abstract（参考訳）: 本研究では, グラフストリーム中の三角形の数を予測し, より効率的かつ実用的なアルゴリズムを提案する。
提案アルゴリズムは,待機室サンプリングと貯水池サンプリングと,エッジの重み,すなわちエッジが関与する三角形の数の予測器を組み合わせる。
その結果,提案アルゴリズムは高速で,使用メモリ量を保証するとともに,予測器が提供する付加情報を利用して高精度な推定を行うことができた。
また、ノードの度合いに基づいて、前もってストリームが利用可能なエッジのストリームに1回のパスで簡単に計算できる、単純でドメインに依存しない予測器を提案する。
解析結果から,予測器がエッジの重みに関する有用な情報を提供すると,予測が完璧ではない場合でも,最先端技術と比較してばらつきが小さくなることがわかった。
実験の結果,1つのグラフストリームを解析した場合,アルゴリズムは与えられたメモリ予算に対する最先端のアルゴリズムよりも高速であり,精度の高い推定値が得られることがわかった。
さらに興味深いのは、数百のグラフストリームのシーケンスが解析されると、このアルゴリズムは、そのシーケンスの最初のグラフだけを分析して構築した単純な次数ベースの予測器を用いて、最先端のアルゴリズムを著しく上回ります。
関連論文リスト
- Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
効率的かつ適応的な予測を実現するために,ワンショットサブグラフリンク予測を提案する。
設計原理は、KG全体に直接作用する代わりに、予測手順を2つのステップに分離する。
5つの大規模ベンチマークにおいて,効率の向上と性能の向上を実現している。
論文 参考訳（メタデータ） (2024-03-15T12:00:12Z) - Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
データストリームに現れる要素の頻度を推定することは、大規模データ分析において重要なタスクである。
理論的には,Hsu等の学習に基づくアルゴリズムを,予測を使わずに上回る新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-12T18:59:06Z) - Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph
Counting on Fully Dynamic Graph Streams [35.943447765433774]
完全動的グラフストリームにおける部分グラフ数を推定するための重み付きサンプリングアルゴリズムWSDを提案する。
強化学習に基づく新しい手法を用いて,エッジの重みをデータ駆動方式で決定する。
論文 参考訳（メタデータ） (2022-11-13T03:01:34Z) - Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
リンク予測はグラフ構造化データ計算の基本的な問題である。
本稿では,スパース囲み部分グラフを用いて予測を行うScaLedというスケーラブルな解を提案する。
より小さなサンプルサブグラフを活用することで、ScaLedは高い精度を維持しながらオーバーヘッドをはるかに少なく大きなグラフにスケールすることができる。
論文 参考訳（メタデータ） (2022-06-23T22:48:44Z) - Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。
従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。
提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
論文 参考訳（メタデータ） (2022-03-17T19:26:00Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Computing Graph Descriptors on Edge Streams [4.129847064263056]
約3種類のグラフ記述子を計算するために,ストリーミングアルゴリズムを提案する。
エッジストリームを操作することで、グラフ全体をメモリに格納するのを避けることができます。
私たちのスケーラブルなアルゴリズムは、数分で数百万のエッジを持つグラフの記述子を計算します。
論文 参考訳（メタデータ） (2021-09-02T06:21:47Z) - Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか?
本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
論文 参考訳（メタデータ） (2021-06-08T16:10:36Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Time series forecasting based on complex network in weighted node
similarity [12.246860992135783]
時系列解析において、可視性グラフ理論は時系列データをネットワークモデルに変換する。
予測アルゴリズムを最適化するための重み係数としてノード類似度指数を用いる。
この方法はより正確な予測能力を有し、時系列や実際のシーンの分野でより正確な予測を提供することができる。
論文 参考訳（メタデータ） (2021-03-14T01:01:41Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。