algorithm - 行列補完アルゴリズムを使用したグラフ復元

Question

少数のエッジのみを使用してグラフを再構築するために使用できる行列補完アルゴリズムはありますか?

いくつかのサンプリングされたエントリしか利用できない未知のマトリックスを回復して完成させるための多くのアルゴリズムがあります。私の知る限り、これらのアルゴリズムの多くは、グラフ隣接行列には当てはまらない低ランク行列で機能します。SVTのように。

Answer 1

残念ながら、行列として表される自然なグラフタイプの多くは、高ランクであることがわかります（たとえば、ツリー、サイクル、グリッド）。この意味で、問題は行列補完の問題ではありません。たとえば、Cai、Candes、Shenの行列補完の特異値しきい値アルゴリズムで述べられています。

つまり、低ランクの制約がなければ、問題は線形代数の不適切な設定の見通しからのものであり、解決することはできません。