論文の概要: Online Dense Subgraph Discovery via Blurred-Graph Feedback

• arxiv url: http://arxiv.org/abs/2006.13642v1
• Date: Wed, 24 Jun 2020 11:37:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 10:00:19.296913
• Title: Online Dense Subgraph Discovery via Blurred-Graph Feedback
• Title（参考訳）: ブラインドグラフフィードバックによるオンラインDense Subgraph Discovery
• Authors: Yuko Kuroki, Atsushi Miyauchi, Junya Honda, Masashi Sugiyama
• Abstract要約: 我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 87.9850024070244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dense subgraph discovery aims to find a dense component in edge-weighted graphs. This is a fundamental graph-mining task with a variety of applications and thus has received much attention recently. Although most existing methods assume that each individual edge weight is easily obtained, such an assumption is not necessarily valid in practice. In this paper, we introduce a novel learning problem for dense subgraph discovery in which a learner queries edge subsets rather than only single edges and observes a noisy sum of edge weights in a queried subset. For this problem, we first propose a polynomial-time algorithm that obtains a nearly-optimal solution with high probability. Moreover, to deal with large-sized graphs, we design a more scalable algorithm with a theoretical guarantee. Computational experiments using real-world graphs demonstrate the effectiveness of our algorithms.
• Abstract（参考訳）: Dense Subgraph Discoveryは、エッジ重み付きグラフに高密度なコンポーネントを見つけることを目的としている。 これは様々なアプリケーションで基本的なグラフマイニングタスクであり、近年多くの注目を集めています。 既存の手法の多くは、個々のエッジウェイトが容易に得られると仮定するが、実際にはそのような仮定は必ずしも有効ではない。 本稿では,学習者が単一エッジではなくエッジサブセットをクエリし,クエリされたサブセットのエッジ重みのノイズ和を観測する,高密度サブグラフ探索のための新しい学習問題を提案する。 この問題に対して,まず,高確率の最適解を求める多項式時間アルゴリズムを提案する。 さらに,大規模グラフを扱うために,理論的保証付きよりスケーラブルなアルゴリズムを設計する。 実世界のグラフを用いた計算実験により,アルゴリズムの有効性が示された。

関連論文リスト

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams [35.943447765433774]
  完全動的グラフストリームにおける部分グラフ数を推定するための重み付きサンプリングアルゴリズムWSDを提案する。 強化学習に基づく新しい手法を用いて,エッジの重みをデータ駆動方式で決定する。
  論文  参考訳（メタデータ） (2022-11-13T03:01:34Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。 LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
  論文  参考訳（メタデータ） (2022-05-20T11:54:03Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。 本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
  論文  参考訳（メタデータ） (2021-12-08T08:23:37Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか? 本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
  論文  参考訳（メタデータ） (2021-06-08T16:10:36Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。 我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。 我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
  論文  参考訳（メタデータ） (2021-06-02T02:58:35Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods [44.007522460918565]
  密度の高い部分グラフをマイニングすることは、グラフマイニングタスクのスペクトルにおいて重要なプリミティブである。 実世界のグラフから非自明な大きさのクランプと準クランプをマイニングすることは、しばしば難しい問題ではないことを示す。
  論文  参考訳（メタデータ） (2020-08-18T15:50:25Z)

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

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