論文の概要: Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient
Algorithms
- arxiv url: http://arxiv.org/abs/2401.08197v2
- Date: Wed, 17 Jan 2024 13:42:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 11:14:38.344690
- Title: Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient
Algorithms
- Title（参考訳）: ハイパーグラフによる行列補完:シャープ閾値と効率的なアルゴリズム
- Authors: Zhongtian Ma, Qiaosheng Zhang and Zhen Wang
- Abstract要約: 本稿では,ソーシャルグラフやハイパーグラフだけでなく,サブサンプル行列のエントリにもとづく評価行列の完成問題を考察する。
評価行列を正確に完遂するタスクに対して,サンプル確率にエンフシャープしきい値が存在することを示す。
我々は,観測されたグラフやハイパーグラフを効果的に活用する計算効率の良い行列補完アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 5.405890484609721
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the problem of completing a rating matrix based on
sub-sampled matrix entries as well as observed social graphs and hypergraphs.
We show that there exists a \emph{sharp threshold} on the sample probability
for the task of exactly completing the rating matrix -- the task is achievable
when the sample probability is above the threshold, and is impossible otherwise
-- demonstrating a phase transition phenomenon. The threshold can be expressed
as a function of the ``quality'' of hypergraphs, enabling us to \emph{quantify}
the amount of reduction in sample probability due to the exploitation of
hypergraphs. This also highlights the usefulness of hypergraphs in the matrix
completion problem. En route to discovering the sharp threshold, we develop a
computationally efficient matrix completion algorithm that effectively exploits
the observed graphs and hypergraphs. Theoretical analyses show that our
algorithm succeeds with high probability as long as the sample probability
exceeds the aforementioned threshold, and this theoretical result is further
validated by synthetic experiments. Moreover, our experiments on a real social
network dataset (with both graphs and hypergraphs) show that our algorithm
outperforms other state-of-the-art matrix completion algorithms.
- Abstract（参考訳）: 本稿では,ソーシャルグラフやハイパーグラフだけでなく,サブサンプル行列のエントリにもとづく評価行列の完成問題を考察する。
評価行列を完全完了させるタスクのサンプル確率に \emph{sharp threshold} が存在することを示す。 サンプル確率がしきい値以上であればそのタスクは達成可能であり、それ以外の場合は不可能である - 位相遷移現象を示す。
閾値はハイパーグラフの `quality'' の関数として表すことができ、ハイパーグラフの利用によるサンプル確率の減少の量を \emph{quantify} することができる。
これはまた、行列補完問題におけるハイパーグラフの有用性を強調する。
シャープしきい値を発見するために,観測されたグラフやハイパーグラフを効果的に活用する計算効率の良い行列補完アルゴリズムを開発した。
理論的解析により,サンプル確率が上記しきい値を超える限り,本アルゴリズムは高い確率で成功し,この理論結果は合成実験によりさらに検証された。
さらに、実際のソーシャルネットワークデータセット(グラフとハイパーグラフの両方)における実験では、アルゴリズムは他の最先端の行列補完アルゴリズムよりも優れています。
関連論文リスト
- Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - Matrix Completion from General Deterministic Sampling Patterns [28.116011361245224]
我々は、精度よく近似した低ランク行列完備問題の理論的保証を確立する。
観測グラフが十分に接続されており、類似ノード次数を持つため、このアルゴリズムが成功することを示す。
論文 参考訳（メタデータ） (2023-06-04T07:01:31Z) - Bures-Wasserstein Means of Graphs [60.42414991820453]
本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。
この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。
我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-05-31T11:04:53Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Sparse random hypergraphs: Non-backtracking spectra and community
detection [10.503525445174464]
我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。
これは、一般的な対称確率テンソルに従って$r$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2022-03-14T17:45:03Z) - Matrix Completion with Hierarchical Graph Side Information [39.00971122472004]
ソーシャルグラフやアイテム類似性グラフを副次情報として活用する行列補完問題を考える。
我々は階層的なグラフクラスタリングから始まる普遍的でパラメータフリーで計算効率のよいアルゴリズムを開発した。
我々は、我々の理論的結果を裏付けるために、合成および実世界のデータセットに関する広範な実験を行う。
論文 参考訳（メタデータ） (2022-01-02T03:47:41Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2021-12-15T01:45:32Z) - HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。
提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2021-08-17T22:20:23Z) - Bayesian matrix completion with a spectral scaled Student prior:
theoretical guarantee and efficient sampling [0.30458514384586394]
スペクトルスケールされた学生プリエントは、データマトリックスの下位低ランク構造を好むために利用される。
提案手法は,本手法がモデル不特定条件下でうまく機能することを保証し,極小最適オラクル不等式を満足することを示す。
論文 参考訳（メタデータ） (2021-04-16T16:03:43Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。