Scholarlink

<p>Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the “local representation, global alignment” paradigm, and present a new “global representation and alignment” paradigm to resolve the mismatch between the two phases in the alignment process. We then propose <Emphasis Type="Underline">Gl</Emphasis>obal representation and <Emphasis Type="Underline">o</Emphasis>ptimal transport-<Emphasis Type="Underline">b</Emphasis>ased <Emphasis Type="Underline">Align</Emphasis>ment (<Emphasis FontCategory="NonProportional">GlobAlign</Emphasis>), and its variant, <Emphasis FontCategory="NonProportional">GlobAlign-E</Emphasis>, for better <Emphasis Type="Underline">E</Emphasis>fficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, <Emphasis FontCategory="NonProportional">GlobAlign-E</Emphasis> successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT’s cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, <Emphasis FontCategory="NonProportional">GlobAlign-E</Emphasis> achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Towards effective and efficient graph alignment without supervision

  • 期刊论文

  • 发表日期：

    2026年1月1日

查看全文
  • Songyang Chen,
  • Youfang Lin,
  • Yu Liu,
  • Shuai Zheng,
  • Lei Zou

摘要

Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the “local representation, global alignment” paradigm, and present a new “global representation and alignment” paradigm to resolve the mismatch between the two phases in the alignment process. We then propose Global representation and optimal transport-based Alignment (GlobAlign), and its variant, GlobAlign-E, for better Efficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, GlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT’s cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, GlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.