論文の概要: Matrix Completion with Hierarchical Graph Side Information

• arxiv url: http://arxiv.org/abs/2201.01728v1
• Date: Sun, 2 Jan 2022 03:47:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-06 13:53:35.603420
• Title: Matrix Completion with Hierarchical Graph Side Information
• Title（参考訳）: 階層グラフ側情報を用いた行列補完
• Authors: Adel Elmahdy, Junhyung Ahn, Changho Suh, Soheil Mohajer
• Abstract要約: ソーシャルグラフやアイテム類似性グラフを副次情報として活用する行列補完問題を考える。 我々は階層的なグラフクラスタリングから始まる普遍的でパラメータフリーで計算効率のよいアルゴリズムを開発した。 我々は、我々の理論的結果を裏付けるために、合成および実世界のデータセットに関する広範な実験を行う。
• 参考スコア（独自算出の注目度）: 39.00971122472004
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering and then iteratively refines estimates both on graph clustering and matrix ratings. Under a hierarchical stochastic block model that well respects practically-relevant social graphs and a low-rank rating matrix model (to be detailed), we demonstrate that our algorithm achieves the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) that is derived by maximum likelihood estimation together with a lower-bound impossibility result. One consequence of this result is that exploiting the hierarchical structure of social graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. We conduct extensive experiments both on synthetic and real-world datasets to corroborate our theoretical results as well as to demonstrate significant performance improvements over other matrix completion algorithms that leverage graph side information.
• Abstract（参考訳）: ソーシャルやアイテムの類似性グラフをサイド情報として活用する行列補完問題を考える。 階層的グラフクラスタリングから始まり、グラフクラスタリングと行列評価の両方で見積を反復的に洗練する、普遍的でパラメータフリーで計算効率のよいアルゴリズムを開発した。 実有意なソーシャルグラフと低ランクの格付け行列モデル(詳細は)をよく尊重する階層的確率ブロックモデルの下で,本アルゴリズムが観測された行列エントリ数(すなわち最適サンプル複雑性)の情報理論的限界を達成し,その最大推定値と低バウンドな不定値結果の両方を導出することを示す。 この結果の1つの結果は、ソーシャルグラフの階層構造を利用すると、それらの間の関係構造に頼らずに、単に異なる群を識別するのに対して、サンプルの複雑さが大幅に向上するということである。 我々は、合成データと実世界のデータセットの両方で広範な実験を行い、理論結果とグラフサイド情報を利用する他の行列補完アルゴリズムよりも大幅に性能が向上することを示す。

関連論文リスト

• Graph Vertex Embeddings: Distance, Regularization and Community Detection [0.0]
  グラフ埋め込みは、低次元空間における複雑なネットワーク構造を表現する強力なツールとして登場した。 異なる頂点間の位相的距離を忠実に捉えるフレキシブル距離関数の族を示す。 ベンチマークデータセットのホスト上でコミュニティ検出を行うことにより,提案手法の有効性を評価する。
  論文  参考訳（メタデータ） (2024-04-09T09:03:53Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs [39.00971122472004]
  本稿では,階層的類似性グラフを推薦システムの側情報として活用する行列補完問題について検討する。 階層的ブロックモデルの下では、観測された行列成分の数に対する正確な情報理論の限界を特徴づける。 最適サンプルの複雑性を解析し,階層的類似性グラフの側情報の品質指標に依拠する特徴を同定する。
  論文  参考訳（メタデータ） (2021-09-12T02:38:54Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs [85.89744949820376]
  MC2Gは、ソーシャルグラフとアイテム類似性グラフの存在下で行列補完を行うアルゴリズムである。 スペクトルクラスタリングと局所的な精細化のステップに基づいている。 我々は、MC2Gが他の最先端行列補完アルゴリズムより優れている合成データセットと実データセットの両方に関する広範な実験を通して示す。
  論文  参考訳（メタデータ） (2020-06-08T06:11:37Z)
• Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information [12.836994708337144]
  最適なサンプルの複雑さにマッチするアルゴリズムを開発する。 我々のアルゴリズムはエラーをモデル化し、予測性能の点で既存のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2020-03-16T06:29:24Z)

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

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