arXiv：cs.LG· Mohammad Hassan Ahmad Yarandi, Luca Ganassali·· 4 小时前
属性高斯图匹配的精确统计阈值
Sharp Statistical Thresholds for Attributed Gaussian Graph Matching
AI 导读
研究针对边权重与节点特征按特定节点对应关系相关联的网络匹配问题，推导出精确恢复、几乎精确恢复与部分恢复的信息论阈值，其表达式涉及图与特征相关强度、节点数量及特征维度。与标准图匹配的全有或全无相变不同，引入节点级上下文信息后，精确恢复阈值与几乎精确和部分恢复的共享阈值发生分离。该结果为高维场景下设计高效算法提供了基准。
正文
Abstract:We investigate the problem of matching networks where both edge weights and node features are correlated following a specific node correspondence. While prior work has established sharp thresholds for matching either graphs or features individually, the joint setting has been significantly less explored. In this study, we derive precise information-theoretic thresholds for exact recovery, almost-exact recovery, and partial recovery of the underlying alignment. These are expressed in terms of graph and feature correlation strengths, the number of nodes, and the dimension of the features. Interestingly, whereas an all-or-nothing phase transition is observed in the standard graph-matching scenario, the inclusion of contextual information at the node level introduces a richer structure: the exact-recovery threshold separates from the shared threshold for almost-exact and partial recovery. Closing gaps left by prior works, we provide a sharp characterization of the thresholds governing how structural and contextual information interact in graph matching, and thereby establish a benchmark for designing efficient algorithms in the high-dimensional setting.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2603.23305 [stat.ML] |
| (or arXiv:2603.23305v2 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2603.23305 arXiv-issued DOI via DataCite |
Submission history
From: Luca Ganassali [view email]
[v1]
Tue, 24 Mar 2026 15:11:04 UTC (48 KB)
[v2]
Wed, 14 Oct 2026 16:49:56 UTC (57 KB)
来源：arXiv：cs.LG · arxiv.org