Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
share
Graph alignment refers to the task of finding the vertex correspondence between two positively correlated graphs. Extensive study has been done on polynomial-time algorithms for the graph alignment problem under the Erdős–Rényi graph pair model, where the two graphs are Erdős–Rényi graphs with edge probability q_u, correlated under certain vertex correspondence. To achieve exact recovery of the vertex correspondence, all existing algorithms at least require the edge correlation coefficient ρ_u between the two graphs to satisfy ρ_u > √(α), where α≈ 0.338 is Otter's tree-counting constant. Moreover, it is conjectured in [1] that no polynomial-time algorithm can achieve exact recovery under weak edge correlation ρ_u<√(α). In this paper, we show that with a vanishing amount of additional attribute information, exact recovery is polynomial-time feasible under vanishing edge correlation ρ_u≥ n^-Θ(1). We identify a local tree structure, which incorporates one layer of user information and one layer of attribute information, and apply the subgraph counting technique to such structures. A polynomial-time algorithm is proposed that recovers the vertex correspondence for all but a vanishing fraction of vertices. We then further refine the algorithm output to achieve exact recovery. The motivation for considering additional attribute information comes from the widely available side information in real-world applications, such as the user's birthplace and educational background on LinkedIn and Twitter social networks.
READ FULL TEXT