The graph alignment problem explores the concept of node correspondence and its optimality. We focus on purely geometric graph alignment methods, namely our newly proposed Ricci Matrix Comparison (RMC) and its original form, Degree Matrix Comparison (DMC). We attempt to incorporate curvatures into the context of graph alignment. We review classic ideas of tiling the torus, and then move on to introduce the RMC with theoretical motivations. Lastly, we will present experimental results that indicate the potential of applying a differential-geometric view to graph alignment. The results show that a direct variation of the DMC using the Ricci curvature can help identify holes in the tori and align the line graphs of a complex network with 80–90+% accuracy. This paper contributes a new perspective to the field of graph alignment and shows the validity of the DMC.

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

Ricci Matrix Comparison: A Curvature-Based Graph Alignment Method

  • Ashley Wang,
  • Peter Chin

摘要

The graph alignment problem explores the concept of node correspondence and its optimality. We focus on purely geometric graph alignment methods, namely our newly proposed Ricci Matrix Comparison (RMC) and its original form, Degree Matrix Comparison (DMC). We attempt to incorporate curvatures into the context of graph alignment. We review classic ideas of tiling the torus, and then move on to introduce the RMC with theoretical motivations. Lastly, we will present experimental results that indicate the potential of applying a differential-geometric view to graph alignment. The results show that a direct variation of the DMC using the Ricci curvature can help identify holes in the tori and align the line graphs of a complex network with 80–90+% accuracy. This paper contributes a new perspective to the field of graph alignment and shows the validity of the DMC.