  Network alignment (NA) compares networks with the goal of finding a node
mapping that uncovers highly similar (conserved) network regions. Existing NA
methods are homogeneous, i.e., they can deal only with networks containing
nodes and edges of one type. Due to increasing amounts of heterogeneous network
data with nodes or edges of different types, we extend three recent
state-of-the-art homogeneous NA methods, WAVE, MAGNA++, and SANA, to allow for
heterogeneous NA for the first time. We introduce several algorithmic
novelties. Namely, these existing methods compute homogeneous graphlet-based
node similarities and then find high-scoring alignments with respect to these
similarities, while simultaneously maximizing the amount of conserved edges.
Instead, we extend homogeneous graphlets to their heterogeneous counterparts,
which we then use to develop a new measure of heterogeneous node similarity.
Also, we extend $S^3$, a state-of-the-art measure of edge conservation for
homogeneous NA, to its heterogeneous counterpart. Then, we find high-scoring
alignments with respect to our heterogeneous node similarity and edge
conservation measures. In evaluations on synthetic and real-world biological
networks, our proposed heterogeneous NA methods lead to higher-quality
alignments and better robustness to noise in the data than their homogeneous
counterparts. The software and data from this work is available upon request.
