論文の概要: Attributed Network Alignment: Statistical Limits and Efficient Algorithm
- arxiv url: http://arxiv.org/abs/2604.04365v1
- Date: Mon, 06 Apr 2026 02:27:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-07 15:49:19.06697
- Title: Attributed Network Alignment: Statistical Limits and Efficient Algorithm
- Title（参考訳）: 分散ネットワークアライメント:統計的限界と効率的なアルゴリズム
- Authors: Dong Huang, Chenyang Tian, Pengkun Yang,
- Abstract要約: エッジ重みとノード特徴の両方が観測された場合, 2つの相関グラフ間の隠れ対応を復元する問題について検討する。
本稿では,2次プログラミング緩和に基づくアルゴリズムQPAlignを提案する。
- 参考スコア（独自算出の注目度）: 11.625288483661883
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the problem of recovering a hidden vertex correspondence between two correlated graphs when both edge weights and node features are observed. While most existing work on graph alignment relies primarily on edge information, many real-world applications provide informative node features in addition to graph topology. To capture this setting, we introduce the featured correlated Gaussian Wigner model, where two graphs are coupled through an unknown vertex permutation, and the node features are correlated under the same permutation. We characterize the optimal information-theoretic thresholds for exact recovery and partial recovery of the latent mapping. On the algorithmic side, we propose QPAlign, an algorithm based on a quadratic programming relaxation, and demonstrate its strong empirical performance on both synthetic and real datasets. Moreover, we also derive theoretical guarantees for the proposed procedure, supporting its reliability and providing convergence guarantees.
- Abstract（参考訳）: 本稿では,エッジ重みとノード特徴の両方が観測された場合に,2つの相関グラフ間の隠れ頂点対応を復元する問題について検討する。
グラフアライメントに関する既存の研究は主にエッジ情報に依存しているが、多くの実世界のアプリケーションはグラフトポロジに加えて情報的ノード機能を提供している。
この設定を捉えるために、2つのグラフが未知の頂点置換によって結合され、ノード特徴が同じ置換の下で相関する特徴付きガウスウィグナーモデルを導入する。
我々は,潜伏写像の正確な回復と部分回復のための最適情報理論しきい値を特徴付ける。
本稿では,2次プログラミング緩和に基づくアルゴリズムQPAlignを提案する。
さらに,提案手法の理論的保証も導き,信頼性と収束保証を提供する。
関連論文リスト
- Contextual Graph Matching with Correlated Gaussian Features [2.497926557563177]
エッジ重みとノード特徴が2つのネットワークで相関するガウス的設定における文脈グラフマッチングについて検討する。
我々は、正確な回復のための正確な情報理論しきい値を導き、ほぼ正確な回復が可能であるか不可能である条件を特定する。
本研究は, グラフマッチングにおける構造的・文脈的情報がどのように相互作用するかを, より厳密に評価し, 効率的なアルゴリズム設計のためのベンチマークを構築した。
論文 参考訳（メタデータ） (2026-03-24T15:11:04Z) - DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
本稿では,ラベル付きグラフ上での信頼度,関係インフォームド最適化のためのDREAM(Dual-Standard Semantic Homogeneity with Dynamic Optimization)を提案する。
具体的には、グラフ内の各ラベル付きノードの信頼性を反復的に再評価するリレーショナルインフォームド動的最適化フレームワークを設計する。
論文 参考訳（メタデータ） (2026-01-24T12:54:18Z) - Covariate-assisted graph matching [1.4466802614938332]
そこで我々は,シードと呼ばれるノードの集合の部分的アライメントが知られている2つの新しいグラフマッチング法を提案する。
本手法の有効性は,数値実験および統計学系譜と協調ネットワークのマッチングへの応用を通じて実証された。
論文 参考訳（メタデータ） (2025-12-12T18:12:56Z) - Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach [5.235925587710112]
本稿では,グラフを用いた行列補完の問題について,変数間の相互関係を表す側情報として考察する。
本稿では,事前条件付き投射降下法に基づくGSGDと呼ばれるグラフ正規化行列補完アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-02-12T16:21:01Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳（メタデータ） (2023-10-05T02:58:29Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。