論文の概要: Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold

• arxiv url: http://arxiv.org/abs/2205.11677v4
• Date: Wed, 28 Feb 2024 02:45:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-29 19:30:40.920611
• Title: Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold
• Title（参考訳）: スパースグラフの半教師付きクラスタリング:情報理論閾値を越えて
• Authors: Junda Sheng and Thomas Strohmer
• Abstract要約: ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
• 参考スコア（独自算出の注目度）: 3.6052935394000234
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition at the Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied standpoint. It states that no estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. Nevertheless, if we slightly extend the horizon to the ubiquitous semi-supervised setting, such a fundamental limitation will disappear completely. We prove that with an arbitrary fraction of the labels revealed, the detection problem is feasible throughout the parameter domain. Moreover, we introduce two efficient algorithms, one combinatorial and one based on optimization, to integrate label information with graph structures. Our work brings a new perspective to the stochastic model of networks and semidefinite program research.
• Abstract（参考訳）: 確率ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 この問題に関する広範な研究は、ケステン・スティグム閾値における相転移が数学的および応用的な観点から特に興味深い、多くの重要な結果を生み出している。 ネットワークトポロジに基づく推定器は,モデルパラメータが一定のしきい値以下であれば,スパースグラフの確率よりも大幅に向上する。 それでも、地平線をユビキタスな半教師付き設定に少し拡張すれば、そのような基本的な制限は完全に消える。 ラベルの任意の割合が明らかにされると、検出問題はパラメータ領域全体で実現可能であることが証明される。 さらに,ラベル情報をグラフ構造と統合するために,組合せと最適化に基づく2つの効率的なアルゴリズムを導入する。 我々の研究は、ネットワークと半定値プログラム研究の確率モデルに新しい視点をもたらす。

関連論文リスト

• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。 ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。 BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
  論文  参考訳（メタデータ） (2023-07-28T00:44:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models [5.933030735757292]
  ラプラシア正規化成層モデル(Laplacian regularized Stratified Model、LRSM)は、サブプロブレムの明示的または暗黙的なネットワーク構造を利用するモデルである。 本稿では,LRSMにおけるグラフ重みの重要性と感度を示し,その感度が任意に大きいことを示す。 本稿では,1つの最適化問題を解くことで,モデルパラメータを適合させながらグラフを共同学習する汎用的手法を提案する。
  論文  参考訳（メタデータ） (2023-05-04T06:06:29Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。 提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。 第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
  論文  参考訳（メタデータ） (2022-12-01T11:49:07Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。 提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。 この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
  論文  参考訳（メタデータ） (2022-06-06T14:26:34Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph Convolutional Neural Networks [0.6236890292833384]
  本稿では,近隣ランダムウォークサンプリング(BGCN-NRWS)を用いたベイジアングラフ畳み込みネットワーク(Bayesian Graph Convolutional Network)を提案する。 BGCN-NRWSは、グラフ構造を利用したマルコフ・チェイン・モンテカルロ(MCMC)に基づくグラフサンプリングアルゴリズムを使用し、変分推論層を用いてオーバーフィッティングを低減し、半教師付きノード分類における最先端と比較して一貫して競合する分類結果を得る。
  論文  参考訳（メタデータ） (2021-12-14T20:58:27Z)
• Crime Prediction with Graph Neural Networks and Multivariate Normal Distributions [18.640610803366876]
  グラフ畳み込みネットワーク(GCN)のフレキシブルな構造を利用して,高分解能領域における疎結合問題に取り組む。 グラフ畳み込みGated Recurrent Units (Graph-ConvGRU) を用いてモデルを構築し,空間的・時間的・カテゴリー的関係を学習する。 モデルが生成性だけでなく,正確性も示しています。
  論文  参考訳（メタデータ） (2021-11-29T17:37:01Z)
• T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs [0.0]
  グラフ構造化データでは、構造化されたスパーシリティと滑らかさが団結する傾向にある。 グラフィカルな関係を持つ高次元パラメータに先立って提案する。 構造された空間と滑らかさを同時に検出するために使用します。
  論文  参考訳（メタデータ） (2021-07-06T10:10:03Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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