Network Alignment (NA), which aims to find the nodes that represent the same entity (i.e., anchor nodes) across different networks, is a fundamental problem in many cross-network researches. Recent advances in network embedding have inspired various auspicious approaches for addressing the NA task, and embedding-based NA technology has become the main research trend. Most embedding-based NA methods follow the consistency assumption explicitly or implicitly, where anchor nodes across different networks tend to have similar local structures/neighbors. However, through the detailed statistical analysis across networks, we observe that anchor nodes have high heterogeneity, i.e., they have different local structures across different networks. Hence, in this paper, we present the formal definition of the heterogeneity of anchor nodes and propose a network alignment framework that combines heterogeneity, which can simultaneously consider the case of heterogeneity and consistency of anchor nodes. In our approach, we propose to use a variational autoencoder to learn node embeddings, and design an effective dual constraint mechanism–Laplacian regularization and heterogeneity constraint to balance the consistency and heterogeneity for network alignment across different networks respectively. Finally, to verify the effectiveness of our proposed method, we conduct extensive experiments on several real-world datasets. Experimental results show that the proposed model achieves better performance than state-of-the-art methods.