論文の概要: Semidefinite Programming for Community Detection with Side Information
- arxiv url: http://arxiv.org/abs/2105.02816v1
- Date: Thu, 6 May 2021 17:00:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-07 13:31:08.669584
- Title: Semidefinite Programming for Community Detection with Side Information
- Title（参考訳）: 側情報を用いたコミュニティ検出のための半確定プログラミング
- Authors: Mohammad Esmaeili and Hussein Metwaly Saad and Aria Nosratinia
- Abstract要約: 本稿では,非グラフデータを含むコミュニティ検出のための効率的なソリューションを提案する。
ノードラベルの最大確率推定のための半定値緩和を定式化する。
sdpは, 側情報と側情報との最大確率において, 側情報の存在において, 全く同じ回復しきい値を持つことがわかった。
- 参考スコア（独自算出の注目度）: 24.824173873217447
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper produces an efficient Semidefinite Programming (SDP) solution for
community detection that incorporates non-graph data, which in this context is
known as side information. SDP is an efficient solution for standard community
detection on graphs. We formulate a semi-definite relaxation for the maximum
likelihood estimation of node labels, subject to observing both graph and
non-graph data. This formulation is distinct from the SDP solution of standard
community detection, but maintains its desirable properties. We calculate the
exact recovery threshold for three types of non-graph information, which in
this paper are called side information: partially revealed labels, noisy
labels, as well as multiple observations (features) per node with arbitrary but
finite cardinality. We find that SDP has the same exact recovery threshold in
the presence of side information as maximum likelihood with side information.
Thus, the methods developed herein are computationally efficient as well as
asymptotically accurate for the solution of community detection in the presence
of side information. Simulations show that the asymptotic results of this paper
can also shed light on the performance of SDP for graphs of modest size.
- Abstract（参考訳）: 本稿では,非グラフデータを組み込んだコミュニティ検出のための,効率的な半有限計画法(SDP)を提案する。
SDPはグラフ上の標準コミュニティ検出のための効率的なソリューションである。
グラフデータと非グラフデータの両方を観測し,ノードラベルの最大度推定のための半定値緩和を定式化する。
この定式化は標準コミュニティ検出のsdpソリューションとは異なっているが、望ましい性質を維持している。
本稿では,3種類の非グラフ情報の正確な回復しきい値を計算し,これを側情報 (side information) と呼ぶ: 部分的なラベル, ノイズラベル, ノードごとの複数の観測(特徴) を任意だが有限な濃度で行う。
また, SDP は, サイド情報が存在する場合と, サイド情報が存在する場合と同程度の精度で回復できることがわかった。
このようにして開発された手法は計算効率が良く、また、サイド情報の存在下でのコミュニティ検出の解に対して漸近的に正確である。
シミュレーションにより,本論文の漸近的な結果は,小さめのグラフに対するsdpの性能にも光を当てることができた。
関連論文リスト
- DPGAN: A Dual-Path Generative Adversarial Network for Missing Data Imputation in Graphs [17.847551850315895]
本稿では,DPGAN(Dual-Pathrative Adversarial Network)と呼ばれる新しいフレームワークを提案する。
DPGANは、欠落したデータと同時に処理し、過度にスムースな問題を回避することができる。
さまざまなベンチマークデータセットにわたる総合的な実験は、DPGANが既存の最先端の計算アルゴリズムよりも優れていなくても、一貫して競合していることを裏付けている。
論文 参考訳（メタデータ） (2024-04-26T05:26:10Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - Graph Out-of-Distribution Generalization with Controllable Data
Augmentation [51.17476258673232]
グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。
トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。
仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
論文 参考訳（メタデータ） (2023-08-16T13:10:27Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳（メタデータ） (2023-06-05T00:01:17Z) - Optimality of Message-Passing Architectures for Sparse Graphs [13.96547777184641]
スパース設定における特徴デコレーショングラフ上のノード分類問題、すなわちノードの期待次数がノード数で$O(1)$である場合について検討する。
局所ベイズ最適性(英語版)と呼ばれるノード分類タスクに対するベイズ最適性(英語版)の概念を導入する。
最適なメッセージパッシングアーキテクチャは,低グラフ信号のレギュレーションにおける標準と高グラフ信号のレギュレーションにおける典型とを補間することを示す。
論文 参考訳（メタデータ） (2023-05-17T17:31:20Z) - A fast topological approach for predicting anomalies in time-varying
graphs [0.0]
トポロジカルデータ解析(TDA)からの永続化ダイアグラム(PD)は、点間距離が明確に定義されたデータ形状記述法として人気がある。
本稿では,グラフデータから形状情報を抽出する計算効率の良いフレームワークを提案する。
実際のデータアプリケーションでは、暗号取引ネットワークの異常な価格予測において、我々のアプローチは最大で22%上昇する。
論文 参考訳（メタデータ） (2023-05-11T01:54:45Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Learning non-Gaussian graphical models via Hessian scores and triangular
transport [6.308539010172309]
連続分布と非ガウス分布のマルコフ構造を学習するアルゴリズムを提案する。
このアルゴリズムは三角トランスポートマップによって誘導される決定論的結合を用いて密度を推定し、グラフのスパース性を明らかにするために地図内のスパース構造を反復的に活用する。
論文 参考訳（メタデータ） (2021-01-08T16:42:42Z) - Graph Information Bottleneck for Subgraph Recognition [103.37499715761784]
本稿では,深層グラフ学習における部分グラフ認識問題に対するグラフ情報ブートネック(GIB)の枠組みを提案する。
この枠組みの下では、最大情報でありながら圧縮的な部分グラフ(IB-subgraph)を認識できる。
IB-サブグラフの特性を3つのアプリケーションシナリオで評価する。
論文 参考訳（メタデータ） (2020-10-12T09:32:20Z) - Evaluating representations by the complexity of learning low-loss
predictors [55.94170724668857]
下流タスクの解決に使用されるデータの表現を評価することの問題点を考察する。
本稿では,関心のあるタスクにおける低損失を実現する表現の上に,予測器を学習する複雑性によって表現の質を測定することを提案する。
論文 参考訳（メタデータ） (2020-09-15T22:06:58Z) - Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for
Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。
本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
論文 参考訳（メタデータ） (2020-08-03T08:48:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。