要旨: 本論文は、2つの相関グラフの間に潜在する頂点対応関係を復元する問題を扱う。これは、エッジ重みとノード特徴の両方が観測される場合である。既存の多くの研究がグラフ整列において主としてエッジ情報に依存している一方で、多くの実世界の応用ではグラフのトポロジに加えて有益なノード特徴が提供される。そこで、この状況を捉えるために、featured correlated Gaussian Wignerモデルを導入する。これは、未知の頂点置換を通じて2つのグラフを結合し、その置換のもとでノード特徴が相関するものである。潜在する写像の完全復元および部分復元に対する、最適な情報理論的しきい値を特徴付ける。アルゴリズム面では、2次計画法の緩和に基づくアルゴリズムQPAlignを提案し、合成データセットと実データセットの両方で強い経験的性能を示す。さらに、提案手順に対する理論的保証も導出し、その信頼性を裏付けるとともに、収束の保証も提供する。
属性付きネットワーク整合：統計的限界と効率的アルゴリズム
arXiv stat.ML / 2026/4/7
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、隠れた頂点対応を、相関を持つ2つのグラフ間から復元する方法を扱う。ここでは、エッジ重みとノード特徴の両方が利用可能である。
- 「特徴付き相関ガウス・ウィナー（featured correlated Gaussian Wigner）モデル」を導入し、未知の置換によって2つのグラフを結合し、同じ置換の下でノード特徴を相関付ける。
- 著者らは、潜在する写像の完全復元および部分復元の両方について、情報理論的な閾値を導出する。
- 二次計画法（QP）の緩和に基づくアルゴリズムであるQPAlignを提示し、合成データセットおよび実データセットで強力な実験結果を示す。
- 本論文では、QPAlignに関する理論的保証も提供しており、信頼性と収束に関する保証を含む。
