論文の概要: The Generalized Mean Densest Subgraph Problem
- arxiv url: http://arxiv.org/abs/2106.00909v2
- Date: Fri, 4 Jun 2021 01:31:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-07 10:51:08.514302
- Title: The Generalized Mean Densest Subgraph Problem
- Title（参考訳）: 一般化平均密度最密部分グラフ問題
- Authors: Nate Veldt and Austin R. Benson and Jon Kleinberg
- Abstract要約: 1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
- 参考スコア（独自算出の注目度）: 30.33731479053404
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding dense subgraphs of a large graph is a standard problem in graph
mining that has been studied extensively both for its theoretical richness and
its many practical applications. In this paper we introduce a new family of
dense subgraph objectives, parameterized by a single parameter $p$, based on
computing generalized means of degree sequences of a subgraph. Our objective
captures both the standard densest subgraph problem and the maximum $k$-core as
special cases, and provides a way to interpolate between and extrapolate beyond
these two objectives when searching for other notions of dense subgraphs. In
terms of algorithmic contributions, we first show that our objective can be
minimized in polynomial time for all $p \geq 1$ using repeated submodular
minimization. A major contribution of our work is analyzing the performance of
different types of peeling algorithms for dense subgraphs both in theory and
practice. We prove that the standard peeling algorithm can perform arbitrarily
poorly on our generalized objective, but we then design a more sophisticated
peeling method which for $p \geq 1$ has an approximation guarantee that is
always at least $1/2$ and converges to 1 as $p \rightarrow \infty$. In
practice, we show that this algorithm obtains extremely good approximations to
the optimal solution, scales to large graphs, and highlights a range of
different meaningful notions of density on graphs coming from numerous domains.
Furthermore, it is typically able to approximate the densest subgraph problem
better than the standard peeling algorithm, by better accounting for how the
removal of one node affects other nodes in its neighborhood.
- Abstract（参考訳）: 大きなグラフの密度の高い部分グラフを見つけることはグラフマイニングの標準的な問題であり、理論的な豊かさと多くの実用的応用の両方について広く研究されてきた。
本稿では,グラフの次数列の計算一般化に基づく1つのパラメータ$p$でパラメータ化された,高密度なサブグラフ対象の新たなファミリーを紹介する。
我々の目標は、標準密度のサブグラフ問題と最大$k$-coreを特別なケースとして捉え、他の密度のサブグラフの概念を探す際に、これらの2つの目的の間を補間し、外挿する方法を提供する。
アルゴリズム的貢献の観点で、我々はまず、繰り返しサブモジュラー最小化を用いて、すべての$p \geq 1$の多項式時間で目標を最小化できることを示した。
我々の研究の大きな貢献は、理論と実践の両方において密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
標準的な剥離アルゴリズムは、一般化された目的に対して任意に不利な動作をすることができることを証明するが、$p \geq 1$に対して少なくとも1/2$の近似保証を持ち、$p \rightarrow \infty$として1に収束するより洗練された剥離法を設計する。
実際、このアルゴリズムは最適解に対して極めて優れた近似値を求め、大きなグラフにスケールし、多くの領域から来るグラフの密度に関する様々な意味のある概念を強調する。
さらに、あるノードの除去が近隣の他のノードにどのように影響するかをよりよく説明することで、標準的な剥離アルゴリズムよりも最も密度の高い部分グラフ問題を近似することができる。
関連論文リスト
- Faster Algorithms for Generalized Mean Densest Subgraph Problem [26.3881083827734]
標準的な剥離アルゴリズムは、0p 1$の場合にも21/p$-近似が得られることを示す。
本稿では,新しいより高速な一般化剥離アルゴリズム(GENPEEL++)を提案する。
論文 参考訳（メタデータ） (2023-10-17T16:21:28Z) - Jaccard-constrained dense subgraph discovery [2.4511852052357628]
大きい対のジャカード類似係数を持つ高密度部分グラフを探索する。
我々は,我々のアルゴリズムが効率的であることを実験的に示し,合成データセットに基底真理を見つけ,実世界のデータセットから解釈可能な結果を提供する。
論文 参考訳（メタデータ） (2023-08-30T10:33:02Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Verification and search algorithms for causal DAGs [11.038866111306728]
クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。
我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。
この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-30T15:52:30Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。
我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
論文 参考訳（メタデータ） (2020-03-13T20:03:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。