論文の概要: Phase transition for detecting a small community in a large network

• arxiv url: http://arxiv.org/abs/2303.05024v1
• Date: Thu, 9 Mar 2023 04:09:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 16:12:53.443381
• Title: Phase transition for detecting a small community in a large network
• Title（参考訳）: 大規模ネットワークにおける小コミュニティ検出のための位相遷移
• Authors: Jiashun Jin, Zheng Tracy Ke, Paxton Turner, Anru R. Zhang
• Abstract要約: 単純度に基づく$chi2$-testは、ErdHos-Renyiバックグラウンドの存在下で強力であることが示されている。 我々は、$chi2$-testによって取得された信号がモデリングアーティファクトであり、より広範なネットワークモデルによってErdHos-Renyiモデルを置き換えると、消滅する可能性があることを示す。
• 参考スコア（独自算出の注目度）: 5.429166905724047
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: How to detect a small community in a large network is an interesting problem, including clique detection as a special case, where a naive degree-based $\chi^2$-test was shown to be powerful in the presence of an Erd\H{o}s-Renyi background. Using Sinkhorn's theorem, we show that the signal captured by the $\chi^2$-test may be a modeling artifact, and it may disappear once we replace the Erd\H{o}s-Renyi model by a broader network model. We show that the recent SgnQ test is more appropriate for such a setting. The test is optimal in detecting communities with sizes comparable to the whole network, but has never been studied for our setting, which is substantially different and more challenging. Using a degree-corrected block model (DCBM), we establish phase transitions of this testing problem concerning the size of the small community and the edge densities in small and large communities. When the size of the small community is larger than $\sqrt{n}$, the SgnQ test is optimal for it attains the computational lower bound (CLB), the information lower bound for methods allowing polynomial computation time. When the size of the small community is smaller than $\sqrt{n}$, we establish the parameter regime where the SgnQ test has full power and make some conjectures of the CLB. We also study the classical information lower bound (LB) and show that there is always a gap between the CLB and LB in our range of interest.
• Abstract（参考訳）: 大規模ネットワーク内の小さなコミュニティを検出する方法は興味深い問題であり、特に、Urd\H{o}s-Renyiバックグラウンドの存在下では、単純度に基づく$\chi^2$-testが強力であることが示されている。 Sinkhorn の定理を用いて、$\chi^2$-test で得られた信号はモデリングアーティファクトであり、より広いネットワークモデルによって Erd\H{o}s-Renyi モデルを置き換えると消える可能性があることを示す。 最近のSgnQテストはそのような設定に適していることを示す。 このテストは、ネットワーク全体のサイズに匹敵する大きさのコミュニティを検出するのに最適なものですが、私たちの設定での研究は行われていません。 次数補正ブロックモデル(DCBM)を用いて,小規模・大規模コミュニティにおける小コミュニティの大きさとエッジ密度に関するテスト問題の相転移を確立する。 小さなコミュニティのサイズが$\sqrt{n}$より大きい場合、sgnqテストは、多項式計算時間を可能にする方法の情報ローバウンドである計算ローバウンド(clb)を達成するために最適である。 小コミュニティのサイズが$\sqrt{n}$より小さいとき、SgnQテストがフルパワーを持つパラメータ構造を確立し、CLBのいくつかの予想を行う。 また、古典情報下界(LB)について検討し、CLBとLBの間には常にギャップがあることを示す。

関連論文リスト

• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods [43.32546195968771]
  本研究では,スムーズなアクティベーションを有するニューラルネットワークに対する勾配法におけるデータ依存収束と一般化挙動について検討する。 我々の結果は、よく確立されたRadecher複雑性に基づく境界の欠点を改善した。 XOR分布の分類において、NTK体制の結果に対して大きなステップサイズが大幅に改善されることが示されている。
  論文  参考訳（メタデータ） (2024-10-13T21:49:29Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  本研究では,2次損失を持つ1層多変量ReLUネットワークをトレーニングする際に,勾配勾配勾配が収束する解のタイプについて検討する。 我々は、浅いReLUネットワークが普遍近似器であるにもかかわらず、安定した浅層ネットワークは存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-06-30T09:17:39Z)
• On the Role of Entanglement and Statistics in Learning [3.729242965449096]
  我々は,絡み合った,分離可能な,統計的に測定された学習モデルと学習モデルとの関係を理解することを進める。 我々は、QSQ学習と量子学習を交絡測定で指数関数的に分離するクラスC$を示す。 我々は,純度テスト,シャドウトモグラフィ,アベリア隠れ部分群問題,次数2$関数,植込み双斜め状態,クリフォード深度回路の出力状態について,超ポリノミカルQSQの下界を証明した。
  論文  参考訳（メタデータ） (2023-06-05T18:16:03Z)
• How Predictable Are Large Language Model Capabilities? A Case Study on BIG-bench [52.11481619456093]
  実験記録におけるBIGベンチの性能予測問題について検討する。 95%以上のR2$スコアは、実験記録の中に学習可能なパターンが存在することを示している。 BIG-bench Hardのように新しいモデルファミリーを評価できるサブセットが3倍程度小さくなっています。
  論文  参考訳（メタデータ） (2023-05-24T09:35:34Z)
• The Onset of Variance-Limited Behavior for Networks in the Lazy and Rich Regimes [75.59720049837459]
  無限幅挙動からこの分散制限状態への遷移をサンプルサイズ$P$とネットワーク幅$N$の関数として検討する。 有限サイズ効果は、ReLUネットワークによる回帰のために、$P* sim sqrtN$の順序で非常に小さなデータセットに関係があることが分かる。
  論文  参考訳（メタデータ） (2022-12-23T04:48:04Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)
• Adjusted chi-square test for degree-corrected block models [13.122543280692641]
  次数補正ブロックモデル(DCSBM)の適合性テストを提案する。 単純な調整により、$d_i$ の調和平均が無限に成長する限り、統計は null の下で分布に収束する。 我々の分布結果は漸近的ではなく、明示的な定数を持ち、目標分布へのコルモゴロフ-スミルノフ距離の有限サンプル境界を与える。
  論文  参考訳（メタデータ） (2020-12-30T05:20:59Z)
• Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent [25.589302381660453]
  また,2乗空間分布に対する勾配勾配勾配を用いた場合,時間的誤差が小さいことを示す。 分類では,任意の統計的クエリ(SQ)が時間内に小さなテストエラーを達成できないという,より強力な結果が得られる。
  論文  参考訳（メタデータ） (2020-06-22T05:15:06Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• OSLNet: Deep Small-Sample Classification with an Orthogonal Softmax Layer [77.90012156266324]
  本稿では,ニューラルネットワークのサブスペースを見つけることを目的としている。 そこで本研究では,Orthogonal Softmax Layer (OSL) を提案する。 実験結果から,提案OSLは4つの小サンプルベンチマークデータセットとの比較に用いた手法よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2020-04-20T02:41:01Z)

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

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