論文の概要: Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms

• arxiv url: http://arxiv.org/abs/2501.11139v3
• Date: Mon, 27 Jan 2025 17:38:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-28 13:52:33.256947
• Title: Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms
• Title（参考訳）: 文脈LSBMのコミュニティ検出:誤分類率と効率的なアルゴリズムの理論的限界
• Authors: Dian Jin, Yuqian Zhang, Qiaosheng Zhang,
• Abstract要約: 文脈ラベルブロックモデル(BM)におけるコミュニティ検出の検討 まず、任意のアルゴリズムに対して保持する最適な誤分類率の低い境界を確立する。 CLSBMに適した効率的なスペクトルベースアルゴリズムを提案し,その誤分類率の上限を導出する。
• 参考スコア（独自算出の注目度）: 12.966642086709147
• License:
• Abstract: The integration of network information and node attribute information has recently gained significant attention in the community detection literature. In this work, we consider community detection in the Contextual Labeled Stochastic Block Model (CLSBM), where the network follows an LSBM and node attributes follow a Gaussian Mixture Model (GMM). Our primary focus is the misclassification rate, which measures the expected number of nodes misclassified by community detection algorithms. We first establish a lower bound on the optimal misclassification rate that holds for any algorithm. When we specialize our setting to the LSBM (which preserves only network information) or the GMM (which preserves only node attribute information), our lower bound recovers prior results. Moreover, we present an efficient spectral-based algorithm tailored for the CLSBM and derive an upper bound on its misclassification rate. Although the algorithm does not attain the lower bound, it serves as a reliable starting point for designing more accurate community detection algorithms (as many algorithms use spectral method as an initial step, followed by refinement procedures to enhance accuracy).
• Abstract（参考訳）: 近年,ネットワーク情報とノード属性情報の統合がコミュニティ検出文献で注目されている。 本研究では,ネットワークがLSBMに従い,ノード属性がガウス混合モデル(GMM)に従うような,文脈ラベル付き確率ブロックモデル(CLSBM)のコミュニティ検出について検討する。 我々の主な焦点は誤分類率であり、これはコミュニティ検出アルゴリズムによって誤分類されるノード数の期待値を測定する。 まず、任意のアルゴリズムに対して保持する最適な誤分類率の低い境界を確立する。 我々の設定をLSBM(ネットワーク情報のみを保存する)やGMM(ノード属性情報のみを保存する)に専門化すると、下限は以前の結果を回復する。 さらに,CLSBMに適したスペクトルに基づく効率的なアルゴリズムを提案し,その誤分類率の上限を導出する。 アルゴリズムは下位境界に達しないが、より正確なコミュニティ検出アルゴリズムを設計するための信頼性の高い出発点として機能する(多くのアルゴリズムはスペクトル法を最初のステップとして使用し、その後精度を高めるための改良手順が続く)。

関連論文リスト

• Rethinking Clustered Federated Learning in NOMA Enhanced Wireless Networks [60.09912912343705]
  本研究では,新しいクラスタ化フェデレーション学習(CFL)アプローチと,非独立かつ同一に分散した(非IID)データセットを統合することのメリットについて検討する。 データ分布における非IIDの度合いを測定する一般化ギャップの詳細な理論的解析について述べる。 非IID条件によって引き起こされる課題に対処する解決策は、特性の分析によって提案される。
  論文  参考訳（メタデータ） (2024-03-05T17:49:09Z)
• Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks [9.57586103097079]
  多層ネットワークが存在する場合のクラスタリングネットワークの基本的限界について検討する。 混合多層ブロックモデル (MMSBM) では, 最適ネットワーククラスタリング誤差率の最小値が指数関数形式であることを示す。 本稿では,ノード分割とサンプル分割の両方を含むテンソルベースアルゴリズムを含む,新しい2段階ネットワーククラスタリング手法を提案する。
  論文  参考訳（メタデータ） (2023-11-27T07:48:50Z)
• Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model [0.16385815610837165]
  本稿では,コミュニティラベルの正確な回復のための情報理論的基準を提案する。 ネットワークと属性情報をどのように交換して正確なリカバリを行うかを示す。 また、共同確率を最大化する反復的クラスタリングアルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-10-30T16:46:05Z)
• Optimal Inference in Contextual Stochastic Block Models [0.0]
  属性グラフの教師なしコミュニティ検出のために,文脈ブロックモデル (cSBM) を提案した。 cSBMは、半教師付きノード分類のためのグラフニューラルネットワーク(GNN)の性能を評価するための合成データセットとして広く利用されている。 本稿では,本アルゴリズムが到達した精度と,本論文で提案したGNNアーキテクチャの性能との間には,かなりのギャップが存在することを示す。
  論文  参考訳（メタデータ） (2023-06-06T10:02:57Z)
• Neural-prior stochastic block model [0.0]
  我々は,コミュニティを,逆ではなくノード属性によって決定されるものとしてモデル化することを提案する。 本稿では,信念伝播と近似メッセージパッシングを組み合わせた統計物理に基づくアルゴリズムを提案する。 提案したモデルとアルゴリズムは理論とアルゴリズムのベンチマークとして利用できる。
  論文  参考訳（メタデータ） (2023-03-17T14:14:54Z)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  本稿では,正規化によるGNNの性能向上に焦点をあてる。 グラフ中のノード次数の長期分布を調べることにより、GNNの新しい正規化法を提案する。 ResNormの$scale$操作は、尾ノードの精度を向上させるために、ノード単位の標準偏差(NStd)分布を再設定する。
  論文  参考訳（メタデータ） (2022-06-16T13:49:09Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。 提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。 この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
  論文  参考訳（メタデータ） (2022-06-06T14:26:34Z)
• ClusterQ: Semantic Feature Distribution Alignment for Data-Free Quantization [111.12063632743013]
  本稿では,ClusterQと呼ばれるデータフリーな量子化手法を提案する。 意味的特徴のクラス間分離性を高めるために,特徴分布統計をクラスタ化し,整列する。 また、クラス内分散を組み込んで、クラスワイドモードの崩壊を解決する。
  論文  参考訳（メタデータ） (2022-04-30T06:58:56Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。 グラフが現在の勾配を混合する能力を定量化する計量法を提案する。 そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
  論文  参考訳（メタデータ） (2022-04-13T15:54:35Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)
• Reliable Time Prediction in the Markov Stochastic Block Model [0.0]
  成長するグラフの依存構造をMSBMを用いて検出する方法を示す。 本稿では,いわゆるリンク予測と協調フィルタリングの問題を解決する方法を提案する。
  論文  参考訳（メタデータ） (2020-04-09T07:58:02Z)

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

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