論文の概要: Triangle and Four Cycle Counting with Predictions in Graph Streams

• arxiv url: http://arxiv.org/abs/2203.09572v1
• Date: Thu, 17 Mar 2022 19:26:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-22 09:39:12.868703
• Title: Triangle and Four Cycle Counting with Predictions in Graph Streams
• Title（参考訳）: グラフストリームの予測を伴う三角形と四サイクル数
• Authors: Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
• Abstract要約: 三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。 従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。 提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
• 参考スコア（独自算出の注目度）: 59.05440236993604
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, (Hsu 2018) and (Jiang 2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms that did not use oracles. In this paper, we explore the power of a "heavy edge" oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.
• Abstract（参考訳）: グラフデータストリームの文献で広く研究されているグラフ解析における2つの基本的な問題である,三角形の数と4サイクルを推定するための,データ駆動のワンパスストリーミングアルゴリズムを提案する。 最近(Hsu 2018)と(Jiang 2020)は、他のデータストリーム問題に機械学習技術を適用し、トレーニングされたオラクルを使用して、ストリーム要素の特定の特性を予測し、オークルを使用しない以前の"古典的"アルゴリズムを改善する。 本稿では,複数のグラフエッジストリーミングモデルにおける「重いエッジ」オラクルのパワーについて検討する。 隣接リストモデルでは、そのようなオラクルを使わずに以前の空間上界を改良した1パス三角形カウントアルゴリズムを提案する。 任意の順序モデルにおいて、従来のアルゴリズムよりも少ないパスと同じ空間複雑性を持つ三角および4サイクル推定のアルゴリズムを示し、これらの境界のいくつかが最適であることを示す。 我々は,複数のノイズモデルの下でアルゴリズムを解析し,オラクルが乱れてもアルゴリズムがよく動作することを示す。 従来のマルチパスおよびランダム順序のストリーミングアルゴリズムは、我々のアルゴリズムの特別な場合と見なすことができ、ヘビーエッジのオラクルを実装するために最初のパスまたはランダム順序を用いた。 最後に,提案手法の利点を最先端のストリーミングアルゴリズムと比較した。

関連論文リスト

• Fast and Accurate Triangle Counting in Graph Streams Using Predictions [4.000869978312742]
  本稿では, グラフストリーム中の三角形の数を予測した最初の効率的かつ実用的なアルゴリズムを提案する。 提案アルゴリズムは,待機室サンプリングと貯水池サンプリングと,エッジの重み,すなわちエッジが関与する三角形の数の予測器を組み合わせる。
  論文  参考訳（メタデータ） (2024-09-23T16:52:11Z)
• Recommendation of data-free class-incremental learning algorithms by simulating future data [10.309079388745753]
  クラスインクリメンタルな学習は、クラスのバッチで構成されるシーケンシャルなデータストリームを扱う。 本稿では,将来的なデータストリームをシミュレートするアルゴリズムレコメンデーション手法を提案する。 シミュレーションストリーム上の最近のアルゴリズムを評価し,ユーザ定義のインクリメンタルな設定において,最高のパフォーマンスを示すアルゴリズムを推奨する。
  論文  参考訳（メタデータ） (2024-03-26T22:26:39Z)
• Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
  データストリームに現れる要素の頻度を推定することは、大規模データ分析において重要なタスクである。 理論的には,Hsu等の学習に基づくアルゴリズムを,予測を使わずに上回る新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-12T18:59:06Z)
• Compressed online Sinkhorn [3.2534959204741085]
  我々は最近導入された[Mensch and Peyr'e, 2020]オンラインシンクホーンアルゴリズムを再考する。 我々は、オンラインシンクホーンアルゴリズムの収束解析を改善し、パラメータ選択によって得られる新しいレートは、以前のレートよりも高速である。 次に, オンラインシンクホーン法と, オンラインシンクホーン法を組み合わせた圧縮オンラインシンクホーン法を提案する。
  論文  参考訳（メタデータ） (2023-10-08T05:33:32Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Biclustering and Boolean Matrix Factorization in Data Streams [12.005731086591139]
  データストリームにおける二部グラフのクラスタリングとブール行列の分解について検討する。 ストリームを渡った後、サブ線形空間を用いてグラフの右側のクラスタの集合を復元するアルゴリズムを提案する。 合成データと実世界のデータに対するアルゴリズムの実装を評価する。
  論文  参考訳（メタデータ） (2020-12-05T23:02:43Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。 エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。 これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
  論文  参考訳（メタデータ） (2020-09-15T17:28:42Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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