--- title: "A Survey on Network Alignment: Approaches, Applications and Future Directions" authors: - "Shruti Saxena" - "Joydeep Chandra" doi: "10.24963/ijcai.2024/908" url: "https://ijcai.org/proceedings/2024/908" pdf: "https://ijcai.org/proceedings/2024/0908.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "8216-8224" track: "Survey Track" keywords: - "Machine Learning: ML: Sequence and graph learning" - "Machine Learning: ML: Adversarial machine learning" - "Data Mining: DM: Applications" - "Data Mining: DM: Mining graphs" - "Machine Learning: ML: Representation learning" - "Knowledge Representation and Reasoning: KRR: Applications" - "Data Mining: DM: Networks" - "Machine Learning: ML: Applications" - "Machine Learning: ML: Active learning" --- # A Survey on Network Alignment: Approaches, Applications and Future Directions Shruti Saxena, Joydeep Chandra *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 8216-8224. DOI: [10.24963/ijcai.2024/908](https://doi.org/10.24963/ijcai.2024/908) ## Abstract Network alignment, the task of mapping corresponding nodes across networks, is attracting more attention for cross-network analysis in diverse domains, including social, biological, and co-authorship networks. Although a variety of methods have been proposed, we lack a holistic understanding of the approaches and applications. Our survey aims to bridge this gap by first proposing a taxonomy of network alignment, characterizing existing approaches, and then systematically summarizing and reviewing their performance and highlighting their scopes for future development. Finally, we discuss some important applications and give directions for future research within this domain. ## Full text ## 1 Introduction In the era of Big Data, graphs have emerged as powerful means for representing and analyzing large-scale networks, encompassing diverse domains such as social, biological, coauthorship, and traffic networks. The coexistence of multiple networks within the same domain is evident in social platforms like Twitter, Facebook, and Instagram or co-authorship networks like DBLP and AMiner. Integrating information across these related networks is essential for comprehensive analysis. Network alignment (NA) focuses on a pivotal aspect of comparative analysis, which is the task of mapping corresponding nodes across networks. NA plays a pivotal role in distilling entity information and addresses the sparsity and data insufficiency issues associated with analyzing a single network [Heimann et al., 2018]. It is considered a pre-requisite for various inter-network applications, including cross-site friend recommendation, product recommendation [Zhao et al., 2023], fraud detection [Zhang et al., 2023a], and uncovering novel interaction patterns in protein networks [Maskey and Cho, 2019]. However, NA comes with various challenges. These span from dealing with the inherent heterogeneity of multi-sourced networks, each characterized by distinct structural patterns, to navigating the intricate variability caused by platform disparities in real-world networks. Additionally, dealing with noisy and incomplete data arising due to missing information or errors in data collection introduces a layer of uncertainty into the alignment process. Moreover, the ever-growing size and complexity of real networks bring the critical challenge of achieving scalable and efficient alignment. In recent years, numerous methods have been proposed to address the challenges associated with NA and construct comprehensive end-to-end frameworks. These methods span a broad spectrum, including matrix optimization-based approaches [Zhang and Tong, 2016; Heimann et al., 2018] and representation learning methods [Trung et al., 2020b; Yan et al., 2021]. Moreover, advanced frameworks like adversarial learning [Derr et al., 2021], contrastive learning [Xiong et al., 2021], active learning [Zhou et al., 2021b], and pre-training [Yu et al., 2023] have emerged, each targeting specific challenges. Despite the recent advancements, a comprehensive overview of the methodologies, summarizing their key characteristics and applications, is currently missing. While [Trung et al., 2020a] performs a comparative study on a few NA methods, it falls short of covering the breadth of the existing works. This survey paper aims to fill this gap by presenting a taxonomy of network alignment. To the best of our knowledge, this work represents the first systematic categorization of different methods used for NA. In our survey, we begin by introducing the basic architecture of NA, dividing the process into four functional modules. Subsequently, we present a novel taxonomy to offer a broad perspective on recent advancements. Within each categorization, we conduct a comparative analysis of existing methods, contrasting their strengths and weaknesses and discussing their open challenges and future prospects. Additionally, we highlight the overall performance of existing NA methods in the face of some key challenges. We conclude by discussing future research directions within this domain. ## 2 Network Alignment Architecture Recent NA methodologies share a common architecture consisting of several key steps. Firstly, real-world networks are represented as graphs, encompassing nodes, edges, and attributes. Subsequently, vector representations of graph nodes are obtained, capturing vital features and relationships. Then, iterative training processes are applied to refine the initial node representations. The refined node representations are then utilized to assess the similarity between nodes in the two networks, facilitating the identification of potential correspondences. Figure 1 depicts the four major components, which are detailed below. Figure 1: Network Alignment Architecture: Gs and Gt are the graphs to align, with bold nodes as anchors A′ . The encoding module generates node representations (node colors). Training iteratively refines representations, showing the gradual convergence of anchors' representations (similar colors). After training, the inference module generates alignments using a similarity measure. Dashed lines indicate optional components. ![Image](https://ijcai.org/proceedings/2024/fulltext/908/image_000000_0d8bd93bd6920794800f473452de1ca34c75b66908d9b8c38b4e421efd0a70c2.png) 1. The networks to be aligned, which are represented as graphs. Without the loss of generality, we have a source network Gs = (Vs,Es,Xs) and a target network Gt = (Vt,Et,Xt). Here V = {v1v2, ..., vn} is the set of nodes, E is the set of edges between nodes, and X = [ ⃗ x1, ⃗ x2, · · · , ⃗ xn]T ∈ Rn×m is the node attribute matrix. Note that the number of nodes and node attribute categories in Gs and Gt can be different, i.e., (|Vs| = ns,Xs ∈ Rns×ms ), and (|Vt| = nt,Xt ∈ Rnt×mt ). 2. An encoding module that generates embeddings ( vector representations) of the nodes from each network. The encoding module can employ any encoder architecture. The encoders can process different types of network information, most commonly network structure and attributes. The generated embeddings of the two graphs are often projected into a common subspace for 2. fair comparison. 3. An alignment training module that updates the generated representations such that the representations of the corresponding nodes become more similar to each other. Most of the approaches rely on the pre-known aligned nodes, A′ = {(ui, vj) | ui ∈ Vs, vj ∈ Vt}, known as anchors, to guide the training process by pulling them closer in the embedding space. They are called supervised approaches. Other approaches are semisupervised, which iteratively labels anchors from the inferred alignment results as training data, and unsupervised, which does not use any labeled data. Some approaches also employ different learning frameworks like contrastive learning, adversarial learning, etc. Most existing methods essentially optimize the pairwise discrepancy (e.g., Frobenius norm, ranking-based loss, and Wasserstein distance) between the two networks. 4. An alignment inference module that identifies node alignments between the two networks. This is the final module that uses a measure of similarity between the node embeddings to determine the set of most probable alignments between the source network and the target network, A = {(ui, vj) | ui ∈ Vs, vj ∈ Vt}. This is often formulated as the learning of an alignment matrix S, where S(u, v) represents the similarity between nodes u ∈ Vs and v ∈ Vt. Some of the most common measures of similarity used are Nearest Neighbor Search (NNS), Euclidean distance, and cosine similarity. ## 3 Taxonomy Various NA methods have been proposed in recent years. They generally have the same basic architecture (as depicted in Figure 1) but still differ from one another in their approaches and goals. The most variations are in the encoding module and the training module. Hence, to better understand the developing venation and future scopes, we identify some representative and influential works and analyze the similarities and the complementary information of their contributions. As illustrated in Figure 2, we establish a taxonomy that divides the comprehensive research on network alignment into approaches and applications. The approaches comprise two major modules: representation generation and alignment learning. We divide the representation generation based on the different encoding techniques used and understand their advantages and shortcomings. Next, we categorize the different alignment learning frameworks and strategies that can be plugged into an alignment training module. NA applications are further divided into alignment in biological networks, recommendations, ontology, etc. Our survey mainly focuses on the NA approaches, and we only briefly discuss the applications for fostering practical innovations. Corresponding to our taxonomy, some representative papers, together with their characteristics, have been listed in Table 1 for a comprehensive comparison. ## 4 Representation Generation We categorize representation generation methods into three groups: traditional methods utilizing matrix optimization, embedding-based methods encompassing random walk, GNNs, and geometric approaches, and optimal transportbased methods. ## 4.1 Traditional Methods The traditional methods formulate network alignment as a graph-matching problem, which considers one network as a noisy permutation of the other. These methods directly compute the alignment matrix S. Their objective is to minimize a loss function L = ||PAsP T - At||, where As and At are the adjacency matrices, and P is a variable permutation matrix. These methods are built upon following the structural and attribute consistency constraints across the networks. Structural consistency maintains topological relationships, ensuring close connections in one network are preserved in aligned anchor nodes, and attribute consistency states that corresponding nodes shall share the same attribute values. IsoRank [Singh et al., 2008] only applies the structural consistency constraint, BigAlign [Koutra et al., 2013] leverages only attribute consistency, whereas FINAL [Zhang and Tong, 2016] and REGAL [Heimann et al., 2018] assume both structural and attribute consistency and employ low-rank matrix approximation to speed up calculation. Figure 2: Taxonomy of Network Alignment. ![Image](https://ijcai.org/proceedings/2024/fulltext/908/image_000001_f7bd6652dbd0679b155051cd58a46da5d620368537fad00c6cee7087b3398c85.png) ## 4.2 Embedding BasedMethods ## Random Walk Based Methods Various NA methods use random-walk based embeddings to preserve the graph's structural properties, mainly the positional proximities of nodes. CENA [Du et al., 2019] proposes a biased cross-network random walk-based strategy with α jumping probability (switching probability between the original graph or across graph) and generates the node embeddings by training a skip-gram model with negative sampling. CEGA [Tang et al., 2023] extends CENA by making the α trainable and including a differentiable SVD to train it via backpropagation. BRIGHT [Yan et al., 2021] uses Random Walk with Restart (RWR) on two graphs separately, assisted by anchor node pairs. Treating anchor node pairs as a shared landmark, the walks encode positional information relative to these landmarks, constructing a unified RWR embedding space. ## Graph Neural Network Based Methods Graph Neural Networks (GNNs) have gained immense attention in NA with their power to capture non-linear relationships and their design that naturally integrates both structural and attribute information. However, a major challenge when extending traditional GNN frameworks (like Graph Convolution Networks (GCNs) ) is that they aren't well equipped to capture higher-order information. Specifically, a K-layer GCN encodes information from the K-order neighborhood, i.e., nodes that are at most K hops away from the current node. As the value of K increases, i.e., we capture the broader node neighborhood, the representations begin to collapse, which is known as the oversmoothing issue. However, for the alignment task, higher-order information is necessary as the local consistency constraints are often violated. Hence, NA methods fabricate the GNN architectures to address this challenge. Some methods incorporate higher-order structures like graphlets so as to distinguish local topology around a node to a greater extent. GraphletAlign [Almulhim et al., 2019] treats the graphlet degree vector as node attributes, HTC [Sun et al., 2023] creates an orbit matrix and injects it into the aggregation process of GCN such that the edges playing different roles in each high-order structure get different weights when passing messages, and SAlign [Saxena and Chandra, 2023] additionally proposes an inter-network higher-order attention mechanism. To overcome the oversmoothing issue, unsupervised methods like GAlign [Trung et al., 2020b] and WAlign [Gao et al., 2021], instead of using the embeddings of the final GCN layer, concatenate the embeddings of all layers to capture both local and global topology patterns. GAlign also introduces a perturbation mechanism to increase model robustness to noise and consistency violations. Some works define GCNs on hypergraphs extracted from original networks to provide richer information of non-pairwise relations through hyperedges along with local topology [Sun et al., 2021]. Other works like NeXtAlign [Zhang et al., 2021] incorporate positional information of nodes (w.r.t to anchor nodes via RWR) in an attention-based architecture that rescales the relative position after each iteration. ## Geometric Embedding Methods Most of the existing NA methods primarily operate in Euclidean space, and though it has led to some promising results, they tend to render reconstruction errors when embedding real-world networks. Also, it has been observed that real-world networks (like social networks and co-authorship networks) have characteristics of hierarchical structure (or scale-free) that need to be taken into account and, in fact, play a crucial role in user alignment. Recognizing these issues, there is a recent shift towards hyperbolic space due to its ability to express hierarchical structures efficiently and accommodate large social networks with reduced parameter complexity. HUIL [Wang et al., 2020] employs the Lorentz model for hyperbolic representation learning. Similarly, PERFECT [Sun et al., 2020] employs the Poincare model and considers user-community correlation, proposing a unified approach for refining user and community embeddings in a common hyperbolic subspace. Both these methods, however, fail to incorporate attribute information. HGENA [Zhou et al., 2021a] and HCNA [Saxena et al., 2022] employ the Hyperbolic Graph Convolutional Networks (HGCN) for network embedding. GINA [Wang et al., 2022] learns node representations in Euclidean and hyperbolic space for each network, establishes a common space using a reconciliation mapping based on anchor links, and predicts potential anchor links by merging the representations for nodes within a single network. ## 4.3 Optimal Transport BasedMethods Unlike random walk and GNN-based methods that capture individual nodes' neighborhoods, Optimal Transport (OT) based methods work on the distribution level. These methods aim to align graphs by minimizing the cost of transporting one distribution to another. The objective is to identify a transport plan between the two data distributions (e.g., node sets of graphs) that minimizes the matching cost (i.e., transport distance). Existing works represent graphs as continuous distributions [Petric Maretic et al., 2019] (multivariate Gaussian distribution with a graph Laplacian-like covariance matrix) or discrete distributions [Xu et al., 2019] (discrete uniform distribution over its node-set). These methods minimize the Wasserstein-like discrepancy between graph distributions and optimize distribution matching. More recent works argue that including position-aware information along with minimizing Gromov-Wasserstein discrepancy proves beneficial for finding precise node correspondences [Zeng et al., 2023a; Zeng et al., 2023b]. FGW [Zeng et al., 2023a] adopts a position-aware cost tensor generated based on the unified RWR and decomposes the problem into significantly smaller cluster-level and node-level alignment subproblems. PARROT [Zeng et al., 2023b] performs RWR on separated and product graphs and designs regularization terms to incorporate alignment consistency. Recently proposed GALOPA [Wang et al., 2023] combines optimal transport problem with GNN to form a novel self-supervised learning paradigm. ## 4.4 Discussion The traditional NA methods integrate complete information from the network structure and are easy to comprehend. However, these methods are more equipped to capture the global structures than node-level relations, potentially overlooking the underlying geometry of graph data. Additionally, they are computationally expensive and lack scalability when applied to large networks. On the other hand, embeddingbased methods well capture non-linear graph structures, are scalable and can also handle heterogeneous information. A recent work combines the merits of node embedding and spectral-based traditional methods and designs a more sophisticated alignment framework [Hermanns et al., 2023] Random walk-based methods focus more on the node's position or significance in the graph structure, whereas GNNbased methods capture information about the node's relationships, connectivity, and local or global structural features within the graph. Methods such as NeXtAlign and CEGA are designed to integrate both positional and structural information, aiming to enhance alignment results. Embeddings in hyperbolic space additionally preserve the hierarchical graph structures with lesser distortion. Optimal transport-based methods claim to filter out noise that comes from first deriving embeddings for each graph and then learning a transformation between the embeddings, thus providing more deterministic alignment results. However, these methods depend highly on the choice of transport plan and distance and are computationally expensive for large networks. Therefore, it still remains an open problem regarding how to make a tradeoff and exploit the advantages of these lines of research. ## 5 Alignment Learning According to the learning goals, alignment learning is divided into two categories: learning frameworks (e.g., adversarial, active, contrastive learning) and learning strategies (e.g., integrated, joint, hierarchical learning). Frameworks encapsulate the fundamental approaches and models governing NA, while strategies focus on specific methodologies within chosen frameworks to optimize model performance. This classification streamlines the analysis and comparison of NA methods. ## 5.1 Alignment Learning Frameworks ## Adversarial Learning Adversarial learning-based NA methods learn node alignments by iterative training that jointly matches the distribution of the two graphs in an end-to-end framework. It involves a generator-discriminator setup, where the generator creates alignments, and the discriminator evaluates their quality. This iterative training process aims for the generator to produce alignments indistinguishable from true alignments while the discriminator classifies alignments as real or generated. SNNA [Li et al., 2019] represents graphs as discrete probability distributions and employs Wasserstein distance (WD) to measure distribution distance. SNNA uses a discriminator to estimate WD and a linear projection function as a generator to minimize approximated WD through competitive training. The process gradually reduces WD, grouping corresponding nodes together with the guidance of a few anchors. Through this process, the WD gradually reduces, grouping the corresponding nodes together. SNNA utilizes a few anchors to guide the training process. Some methods like DANA [Derr et al., 2021], WAlign [Gao et al., 2021], and HackGAN [Yang et al., 2022] propose harnessing the power of network embedding and adversarial techniques. They obtain node embeddings and use adversarial-based methods to learn a complex mapping for aligning embedding distributions of two networks simultaneously. However, standard GAN-based alignment frameworks may face mode collapse issues, resulting in many-to-one alignment and decreased performance. To address this, DANA introduces cyclic consistency (transitive learning), and HackGAN uses CycleGAN. ## Active Learning Although the labeled anchor information plays a critical role in building an effective NA model, it is often costly and timeconsuming as it requires human labor. Hence, in order to reduce the dependency on anchors, active learning aims to maximize the alignment performance by labeling as few samples from the whole training data as possible. To achieve this, it designs a query function that identifies the most useful node to query that maximizes performance and minimizes the number of queries. The existing active NA methods differ in their choices of query functions. [Malmi et al., 2017] defines a certainty measure that quantifies the confidence of the current model in its outcome and queries the node with the highest uncertainty. It uses the marginal distribution of some sampled mappings and cross-entropy to quantify certainty. DAULAP [Cheng et al., 2019] proposes that anchor user pairs are more valuable and informative for labeling than non-anchor user pairs and designs two strategies, crossnetwork information entropy, and cosine similarity, to find user pairs that are more likely to be anchor ones. ATTENT Table 1: Summary of some representative network alignment work. Note: ✓if it uses attributes/anchors: otherwise �. NNS: Nearest Neighbor Search. ATTENT and CAPER are plug-and-play methods that can be applied on any NA architecture. | Method | Representation generation - Encoding | Representation generation - Attributes | Alignment learning - Anchors | Alignment learning - Framework and Strategy | Alignment inference - Similarity measure | |-----------------------------------|----------------------------------------|------------------------------------------|--------------------------------|--------------------------------------------------|--------------------------------------------| | REGAL [Heimann et al., 2018] | matrix optimization | ✓ | ✓ | JointL | Euclidean distance | | CENA [Du et al., 2019] | random walk | ✓ | ✓ | JointL (cross-net.), Aux. task - Link prediction | cosine sim. | | Got [Petric Maretic et al., 2019] | optimal transport | � | � | JointL | Wasserstein dist. | | GAlign [Trung et al., 2020b] | GCN | ✓ | � | JointL (parameter sharing) | cosine sim. | | PERFECT [Sun et al., 2020] | randomwalk (Poincare ball model) | � | � | HierarchicalL (community) | Riemannian dist. | | BRIGHT [Yan et al., 2021] | random walk, GCN | ✓ | � | JointL (cross-net) | L1 norm | | DANA [Derr et al., 2021] | random walk | � | � | AdversarialL | K-d tree, NNS | | ATTENT [Zhou et al., 2021b] | | | | ActiveL | | | HCNA [Saxena et al., 2022] | Hyperbolic GCN | ✓ | � | ContrastiveL | cosine sim. | | DAWN [Gao et al., 2022a] | GCN | ✓ | ✓ | AdversarialL, AdaptL (domain generalization) | cosine sim. | | CAPER [Zhu et al., 2022] | | | | HierarchicalL | | | MINING [Zhang et al., 2023b] | GNN | ✓ | � | HierarchicalL, ContrastiveL, JointL | mutual info. | | SeedGNN [Yu et al., 2023] | GCN | � | ✓ | AdaptL (knowledge distillation) | Hungarian algo. | | GALOPA [Wang et al., 2023] | optimal transport, GNN | ✓ | � | ContrastiveL, JointL(cross net.) | Wasserstein dist. | | HTC [Sun et al., 2023] | GCN | ✓ | � | HierarchicalL | Pearson corr. | [Zhou et al., 2021b] first quantifies the influence of a query on the current model and then proposes a generic algorithm to select a node to query. ## Contrastive Learning The primary objective of contrastive learning-based alignment methods is to derive rich structural representations directly from the data itself, eliminating the reliance on sparsely labeled data (anchors) that might not be extensive enough for comprehensive learning. To achieve this, it creates two views of a given graph via structural and/or attribute augmentation. Considering the same nodes in the two views as positive pairs and different as negative pairs it maximizes the similarity between the positive pairs and minimizes the similarity between the negative pairs. This augmented views learning strategy also helps in increasing the model's robustness towards noise. Existing contrastive NA approaches vary in their view creation, augmentation, and strategies. cM 2NE [Xiong et al., 2021] employs random walk and personalized PageRanks to create structural views. HCNA [Saxena et al., 2022] emphasizes the need for tailored augmentation strategies due to unique structural variations in different real-world networks and augments on the basis of network features such as centrality scores, assortativity, and shortest path lengths. Methods like MINING [Zhang et al., 2023b] and ICLEA [Zeng et al., 2022] consider Gs and Gt as their noisy permutations of each other and treat them as two views of samples. HCNA and cM 2NE capture the local and global structures via node-level (intra-network) and graph-level(inter-network) contrasting, with cM 2NE introducing inter-layer contrasting for aligning multiplex networks. HCNA also captures hierarchical structures by operating in the hyperbolic space. MINING proposes an intra and inter-level contrasting framework for learning uniquely identifiable node features and distinguishable alignment patterns, respectively, along with modeling hierarchical information across different granularities (coarser to finer) of networks. ICLEA designs an interactive contrasting learning mechanism by constructing pseudoaligned entity pairs as virtual pivots to establish a direct information interaction channel for the two networks. ## Discussion Recent adversarial learning-based NA methods tackle alignment at both distributional and node levels using embedding learning. However, despite using CycleGAN, mode collapse remains a concern, as the learned one-to-one mappings may be just a random solution within a large feasible solution space, making its convergence difficult. Addressing this challenge effectively remains a significant issue. Both contrastive and active learning frameworks share a common objective of minimizing reliance on supervision in NA methods, with contrastive learning adding to the model's robustness. However, they exhibit sensitivity to the selection of augmentation and query strategies. While it is straightforward to identify a few anchors (e.g., well-known personalities on social media) for learning facilitation, the dependency on such anchors could be seen as a limitation. Consequently, there is potential for enhancing performance by focusing on weakly-supervised contrastive frameworks. Additionally, active learning methods could benefit from improvements in query strategies, particularly in evaluating the direct impact of queries on alignment results. ## 5.2 Alignment Learning Strategies ## Adaptive Learning To address the scarcity of labeled data, some of the existing methods aim to enhance knowledge acquisition by learning from labeled data and applying that knowledge adaptively to unlabeled data. MetaNA [Zhou et al., 2020], for instance, utilizes meta-learning to extrapolate general alignment patterns from anchor nodes to non-anchor nodes, improving overall alignment performance. DAWN [Gao et al., 2022a] uses adversarial training to extract domain-invariant features and domain-invariant alignment patterns and then generalizes these patterns to an unseen testing domain. Recent methods like REBORN [Gao et al., 2022b] and SeedGNN [Yu et al., 2023] design frameworks for leveraging the knowledge of two aligned networks for aligning unseen networks. REBORN uses a transfer learning approach, whereas seedGNN uses knowledge distillation. ## Joint Learning In representation learning-based NA methods, although the source and target networks are encoded by the same embedding technique, these embeddings often belong to different and incomparable vector spaces. Hence, supervised methods try to match the embedding space with the help of anchors [Zhang et al., 2021; Yan et al., 2021] and the unsupervised methods by model parameter sharing [Trung et al., 2020b; Jiang, 2021; Saxena et al., 2022] or frameworks like adversarial training. Some supervised methods propose to jointly learn and transfer the complementary information across the networks. They assume that anchors across networks can have some similar structural patterns as well as distinctive connection relationships due to the networks' different semantic meanings. Following this, CENALP [Du et al., 2019] and BRIGHT [Yan et al., 2021] capture the structural properties from separate graphs using a cross-network embedding method employing random walks. CrossMNA [Chu et al., 2019] expresses network differences through layer vectors and uses a linear transformation between nodes across networks. CCALP [Lan et al., 2021], in addition, models community-level inter-network relationships. SAlign [Saxena and Chandra, 2023] focuses on more discriminative subgraphs within and across networks by transferring higherorder graphlet information via anchors by an attention-based mechanism. Some contrastive learning frameworks like MINING and ICLEA also introduce cross-network information through their inter-network contrasting strategies. ## Hierarchical Learning The process of aligning large-scale networks can be demanding in terms of time and resources. To address this challenge, some methods suggest a hierarchical alignment strategy, ranging from coarse to fine resolutions, for more efficient and effective results [Sun et al., 2020; Zhu et al., 2022; Zhang et al., 2023b; Zeng et al., 2023a]. These methods adopt a divide-and-conquer approach, creating multiple levels of granularity and utilizing information at coarser levels (such as subnetworks or communities) to assist in identifying nodes at finer levels (individual nodes). The core idea is to follow the consistency constraints across various graph resolutions; nodes that are matched at finer granularities should also align at coarser granularities. Some works propose to meet this constraint by explicitly capturing the hierarchical information via higher-order structures such as orbits and graphlets [Saxena and Chandra, 2023; Sun et al., 2023]. Other works combine auxiliary tasks such as link prediction [Du et al., 2019] and network completion [Zhang et al., 2020] along with network alignment for building high-quality alignment models. Table 2: Dataset statistics | Dataset | |V| | |E| | #Attributes | #Anchors | |------------------|-----------------|---------------------|---------------|------------| | Flickr - Myspace | 6,714 - 10,733 | 7,333 - 11,081 | 3 | 267 | | Lastfm - Flickr | 15,436 - 12,974 | 32,638 - 32,298 | 3 | 452 | | Douban | 3,906-1,118 | 8,164-1,511 | 538 | 1,118 | | Foresq - Twitter | 5,313 - 5,120 | 76,972 - 1,64,919 | 0 | 1,609 | | DBLP | 2,151-2,151 | 6,306-5,699 | 8 | 2,151 | | ACM - DBLP | 9,916 - 9,872 | 44,808 - 39,561 | 17 | 6,325 | | Allmovie - IMDB | 6,011-5,713 | 1,24,709 - 1,19,073 | 14 | 5,176 | ## Discussion Jointly learning by transferring information across the networks can easily lead to over-smoothing of the representations, making alignment more difficult. Model parametersharing techniques, where two networks share the same parameters, face challenges in learning optimal parameters and struggle to capture intra-network proximities effectively. The task of representing two structurally heterogeneous networks in the same vector space based on a unified network remains challenging. The concept of adaptive learning is relatively new, and many challenges persist. Firstly, differences in attribute distributions and structures between source and target graphs often lead to poor generalization in knowledge transfer. Realworld graphs are frequently contaminated by unpredictable and severe noise, including attribute and edge pollution, which exist simultaneously. Handling various forms of complex noise poses a significant challenge. Secondly, identifying which features are captured in these embeddings and recognizing when to explicitly identify or attenuate them if they are undesired remains a challenge. The ability to discern and manage the impact of captured features is crucial for the effectiveness of the learning process. Hierarchical learning methods focus on very large-scale graphs, introducing a trade-off between alignment accuracy and runtime. Increasing coarsening levels for faster runtime leads to smaller graphs but at the cost of some accuracy. Additionally, more theoretical proof is needed to ensure effective knowledge transfer between granularities for the NA task. ## 6 Evaluation of NAMethods ## 6.1 Datasets Existing NA methods evaluate their performance on diverse networks such as social networks (Twitter, Foursquare, etc.), movie guide service networks (AllMovie, IMDB), and academic networks (DBLP, ACM). Nodes in these networks represent users, films, and authors, respectively. Dataset statistics are summarized in Table 2. ## 6.2 EvaluationMetrics The alignment performance is evaluated using Acc@q, which indicates if a node's true anchor match is present in a list of top-q potential anchors. It is given as where (u∗s , u∗t ) ∈ A′ and R(us) is a list of highest q values in the row S(us). Note that Acc@1 is the number of correctly identified node pairs w.r.t. to the known anchors. Apart from this, the MAP and AUC scores are also observed. ## 6.3 Performance Analysis In the above sections, we analyzed the advantages and shortcomings of individual encoding techniques, training frameworks, and strategies. Now, we evaluate the overall performance of some of the recent works based on the following parameters: 1. Efficacy, Efficiency and Scalability: Traditional methods such as REGAL and FINAL demonstrate efficiency and accuracy on small networks but struggle with tractability on large-scale networks. Embedding-based methods exhibit scalability but may experience increased run time. Methods like MINING and CAPER offer reduced run time at the expense of some accuracy. 2. Heterogeneity: Methods like FINAL, DANA, PERFECT, and SeedGNN rely solely on structural information, while CENA and CrossMNA focus on nodes' local relationships, making them suitable for structurally similar networks. SAlign and HTC, capturing higher-order structures, are more effective in handling network heterogeneity. 3. Robustness to noise: All methods, particularly traditional ones, experience decreased performance in the presence of structural and/or attribute noise. HCNA, MINING, GAlign, and DAWN exhibit better performance with training strategies that incorporate noise. DANA and HackGAN, employing CycleGAN, are more robust among other adversarial methods. 4. Sensitivity to supervision: The performance of all NA methods improves with supervision. Among supervised methods, Meta-NA, SNNA, and ATTENT deliver more consistent results even with varying levels of supervision. ## 7 Applications Network alignment has various applications across different domains. Some notable applications include in the fields of: 1. Biology: NA is crucial in biology for understanding conserved patterns and functional relationships. It reveals conserved interactions in protein-protein networks, regulatory mechanisms in gene networks, and aids in studying evolutionary relationships. NA finds applications in drug discovery, neuroscience, and other related fields [Maskey and Cho, 2019]. NA methods that focus on local as well as global alignment find more importance in biology. 2. Ontology: NA in ontology involves aligning the structures of two ontologies to identify corresponding or equivalent concepts, relationships, and entities. It has several applications in improving the interoperability, integration, and consistency of ontologies [He et al., 2022]. NA methods that best capture the semantic relationships in networks are helpful for ontology alignment. 3. Recommender Systems: NA in recommender systems aligns user-item interaction networks from different domains to enhance the recommendation process. For instance, aligning social network interactions with movie preferences for more comprehensive suggestions. It also addresses challenges like the cold start problem, data scarcity, and heterogeneity for more accurate, diverse, and personalized recommendations [Zhao et al., 2023]. NA methods that primarily deal with the structural and attribute heterogeneity of networks are best suited for this task. 4. Misinformation: NA in misinformation detection entails aligning and comparing information propagation networks to identify patterns of misinformation spread across diverse platforms. This allows for the identification of shared sources of misinformation, facilitating more targeted and effective efforts to combat the dissemination of false information [Zhang et al., 2023a]. 5. Others: NA finds unbounded applications in interdisciplinary domains. In recent developments, it has been applied to video person re-identification, aligning long audio interviews and questions, and even in e-commerce for user alignment in online bookstores. ## 8 Conclusion and Future Directions In this survey, we present a systematic overview and discussion of the recent advances in network alignment. We introduce a novel taxonomy that categorizes existing works from various perspectives. We find that most existing efforts are aimed at handling heterogeneity across networks, reducing supervision, increasing robustness towards noise, and scaling to large-scale networks. Despite the appreciable achievements, NA offers many opportunities and directions for future research and development: Explainability and Interpretability: In NA, this could involve clarifying why certain nodes are aligned, providing insights into the features or relationships that drive the alignment decisions, and answering questions like what mistakes the models tend to make and why. Incremental NA: Developing methods for incremental network alignment, where alignment is updated as new data becomes available or as the network structure evolves. Some NA methods study the alignment of dynamic networks; however, they are not well equipped to handle continuously incoming data. Fairness and Privacy: The alignment of networks often involves sharing or comparing sensitive information. Methods that prioritize data privacy, offer secure alignment protocols, and adhere to ethical considerations become essential. Interdisciplinary collaboration: Collaboration across different disciplines like biology, sociology, and linguistics could enhance the overall impact and creativity of network alignment. ## References 1. [Almulhim et al., 2019] Aljohara Almulhim, Vachik S Dave, and Mohammad Al Hasan. Network alignment using graphlet signature and high order proximity. In Machine Learning, Optimization, and Data Science: 5th Interna- tional Conference, LOD 2019, Siena, Italy, September 10- 13, 2019, Proceedings 5, pages 130-142. Springer, 2019. 2. [Cheng et al., 2019] Anfeng Cheng, Chuan Zhou, Hong Yang, Jia Wu, Lei Li, Jianlong Tan, and Li Guo. Deep active learning for anchor user prediction. arXiv preprint arXiv:1906.07318, 2019. 3. [Chu et al., 2019] Xiaokai Chu, Xinxin Fan, Di Yao, Zhihua Zhu, Jianhui Huang, and Jingping Bi. Cross-network em- bedding for multi-network alignment. In The world wide web conference, pages 273-284, 2019. 4. [Derr et al., 2021] Tyler Derr, Hamid Karimi, Xiaorui Liu, Jiejun Xu, and Jiliang Tang. Deep adversarial network alignment. In Proceedings of the 30th ACM interna- tional conference on information & knowledge manage- ment, pages 352-361, 2021. 5. [Du et al., 2019] Xingbo Du, Junchi Yan, and Hongyuan Zha. Joint link prediction and network alignment via cross-graph embedding. In IJCAI, 2019. 6. [Gao et al., 2021] Ji Gao, Xiao Huang, and Jundong Li. Un- supervised graph alignment with wasserstein distance dis- criminator. In Proceedings of the 27th ACM SIGKDD, pages 426-435, 2021. 7. [Gao et al., 2022a] Shuai Gao, Zhongbao Zhang, and Sen Su. Dawn: Domain generalization based network align- ment. IEEE Transactions on Big Data, 2022. 8. [Gao et al., 2022b] Shuai Gao, Zhongbao Zhang, Sen Su, and S Yu Philip. Reborn: Transfer learning based social network alignment. Information Sciences, 589:265-282, 2022. 9. [He et al., 2022] Yuan He, Jiaoyan Chen, Denvar Antonyra- jah, and Ian Horrocks. Bertmap: a bert-based ontology alignment system. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5684-5691, 2022. 10. [Heimann et al., 2018] Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation learning- based graph alignment. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 117-126, 2018. 11. [Hermanns et al., 2023] Judith Hermanns, Konstantinos Skitsas, Anton Tsitsulin, Marina Munkhoeva, Alexander Kyster, Simon Nielsen, Alexander M Bronstein, Da- vide Mottin, and Panagiotis Karras. Grasp: Scalable graph alignment by spectral corresponding functions. ACM Transactions on Knowledge Discovery from Data, 17(4):1-26, 2023. 12. [Jiang, 2021] Meng Jiang. Cross-network learning with par- tially aligned graph convolutional networks. In Proceed- ings of the 27th ACM SIGKDD, pages 746-755, 2021. 13. [Koutra et al., 2013] Danai Koutra, Hanghang Tong, and David Lubensky. Big-align: Fast bipartite graph align- ment. In 2013 IEEE 13th international conference on data mining, pages 389-398. IEEE, 2013. 14. [Lan et al., 2021] Lintao Lan, Huailiang Peng, Chaodong Tong, Xu Bai, and Qiong Dai. Cross-network community sensing for anchor link prediction. In 2021 International Joint Conference on Neural Networks. IEEE, 2021. 15. [Li et al., 2019] Chaozhuo Li, Senzhang Wang, Yukun Wang, Philip Yu, Yanbo Liang, Yun Liu, and Zhoujun Li. Adversarial learning for weakly-supervised social network alignment. In Proceedings of the AAAI conference on ar- tificial intelligence, volume 33, pages 996-1003, 2019. 16. [Malmi et al., 2017] Eric Malmi, Aristides Gionis, and Evi- maria Terzi. Active network alignment: A matching-based approach. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 1687- 1696, 2017. 17. [Maskey and Cho, 2019] Sawal Maskey and Young-Rae Cho. Survey of biological network alignment: cross- species analysis of conserved systems. In 2019 IEEE Inter- national Conference on Bioinformatics and Biomedicine (BIBM), pages 2090-2096. IEEE, 2019. 18. [Petric Maretic et al., 2019] Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. Got: an optimal transport framework for graph comparison. Advances in Neural Information Processing Systems, 32, 2019. 19. [Saxena and Chandra, 2023] Shruti Saxena and Joydeep Chandra. Salign: A graph neural attention framework for aligning structurally heterogeneous networks. Journal of Artificial Intelligence Research, 77:949-969, 2023. 20. [Saxena et al., 2022] Shruti Saxena, Roshni Chakraborty, and Joydeep Chandra. Hcna: Hyperbolic contrastive learn- ing framework for self-supervised network alignment. In- formation Processing & Management, 59:103021, 2022. 21. [Singh et al., 2008] Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application to functional orthology detec- tion. Proceedings of the National Academy of Sciences, 105(35):12763-12768, 2008. 22. [Sun et al., 2020] Li Sun, Zhongbao Zhang, Jiawei Zhang, Feiyang Wang, Yang Du, Sen Su, and S Yu Philip. Per- fect: A hyperbolic embedding for joint user and commu- nity alignment. In 2020 IEEE international conference on data mining (ICDM), pages 501-510. IEEE, 2020. 23. [Sun et al., 2021] Xiangguo Sun, Hongzhi Yin, Bo Liu, Hongxu Chen, Qing Meng, Wang Han, and Jiuxin Cao. Multi-level hyperedge distillation for social linking pre- diction on sparsely observed networks. In Proceedings of the Web Conference 2021, pages 2934-2945, 2021. 24. [Sun et al., 2023] Qingqiang Sun, Xuemin Lin, Ying Zhang, Wenjie Zhang, and Chaoqi Chen. Towards higher-order topological consistency for unsupervised network align- ment. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 177-190. IEEE, 2023. 25. [Tang et al., 2023] Wei Tang, Haifeng Sun, Jingyu Wang, Qi Qi, Huangxun Chen, and Li Chen. Cross-graph embed- ding with trainable proximity for graph alignment. IEEE Transactions on Knowledge and Data Engineering, 2023. 26. [Trung et al., 2020a] Huynh Thanh Trung, Nguyen Thanh Toan, Tong Van Vinh, Hoang Thanh Dat, Duong Chi Thang, Nguyen Quoc Viet Hung, and Abdul Sattar. A comparative study on network alignment techniques. Ex- pert Systems with Applications, 140:112883, 2020. 27. [Trung et al., 2020b] Huynh Thanh Trung, Tong Van Vinh, Nguyen Thanh Tam, Hongzhi Yin, Matthias Weidlich, and Nguyen Quoc Viet Hung. Adaptive network align- ment with unsupervised and multi-order convolutional net- works. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 85-96. IEEE, 2020. 28. [Wang et al., 2020] Feiyang Wang, Li Sun, and Zhongbao Zhang. Hyperbolic user identity linkage across social net- works. In GLOBECOM 2020-2020 IEEE Global Commu- nications Conference, pages 1-6. IEEE, 2020. 29. [Wang et al., 2022] Yinghui Wang, Wenjun Wang, Zixu Zhen, Qiyao Peng, Pengfei Jiao, Wei Liang, Minglai Shao, and Yueheng Sun. Geometry interaction network align- ment. Neurocomputing, 501:618-628, 2022. 30. [Wang et al., 2023] Yejiang Wang, Yuhai Zhao, Daniel Zhengkui Wang, and Ling Li. Galopa: Graph transport learning with optimal plan alignment. In Thirty- seventh Conference on Neural Information Processing Systems, 2023. 31. [Xiong et al., 2021] Hao Xiong, Junchi Yan, and Li Pan. Contrastive multi-view multiplex network embedding with applications to robust network alignment. In Proceedings of the 27th ACM SIGKDD, pages 1913-1923, 2021. 32. [Xu et al., 2019] Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserstein learning for graph partitioning and matching. Advances in neural informa- tion processing systems, 32, 2019. 33. [Yan et al., 2021] Yuchen Yan, Si Zhang, and Hanghang Tong. Bright: A bridging algorithm for network align- ment. In Proceedings of the Web Conference 2021, pages 3907-3917, 2021. 34. [Yang et al., 2022] Linyao Yang, Xiao Wang, Jun Zhang, Jun Yang, Yancai Xu, Jiachen Hou, Kejun Xin, and Fei-Yue Wang. Hackgan: Harmonious cross-network mapping using cyclegan with wasserstein-procrustes learning for unsupervised network alignment. IEEE Transactions on Computational Social Systems, 10(2):746-759, 2022. 35. [Yu et al., 2023] Liren Yu, Jiaming Xu, and Xiaojun Lin. Seedgnn: graph neural network for supervised seeded graph matching. In International Conference on Machine Learning, pages 40390-40411. PMLR, 2023. 36. [Zeng et al., 2022] Kaisheng Zeng, Zhenhao Dong, Lei Hou, Yixin Cao, Minghao Hu, Jifan Yu, Xin Lv, Lei Cao, Xin Wang, Haozhuang Liu, et al. Interactive contrastive learn- ing for self-supervised entity alignment. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 2465-2475, 2022. 37. [Zeng et al., 2023a] Zhichen Zeng, Boxin Du, Si Zhang, Yinglong Xia, Zhining Liu, and Hanghang Tong. Hierar- chical multi-marginal optimal transport for network align- ment. arXiv preprint arXiv:2310.04470, 2023. 38. [Zeng et al., 2023b] Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. Parrot: Position-aware regularized optimal transport for network alignment. In Proceedings of the ACM Web Conference 2023, pages 372-382, 2023. 39. [Zhang and Tong, 2016] Si Zhang and Hanghang Tong. Fi- nal: Fast attributed network alignment. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1345-1354, 2016. 40. [Zhang et al., 2020] Si Zhang, Hanghang Tong, Jie Tang, Jiejun Xu, and Wei Fan. Incomplete network alignment: Problem definitions and fast solutions. ACM Transactions on Knowledge Discovery from Data, 14(4):1-26, 2020. 41. [Zhang et al., 2021] Si Zhang, Hanghang Tong, Long Jin, Yinglong Xia, and Yunsong Guo. Balancing consistency and disparity in network alignment. In Proceedings of the 27th ACM SIGKDD, pages 2212-2222, 2021. 42. [Zhang et al., 2023a] Yizhou Zhang, Karishma Sharma, and Yan Liu. Capturing cross-platform interaction for identi- fying coordinated accounts of misinformation campaigns. In European Conference on Information Retrieval, pages 694-702. Springer, 2023. 43. [Zhang et al., 2023b] Zhongbao Zhang, Shuai Gao, Sen Su, Li Sun, and Ruiyang Chen. Mining: Multi-granularity network alignment based on contrastive learning. IEEE Transactions on Knowledge and Data Engineering, 2023. 44. [Zhao et al., 2023] Yi Zhao, Chaozhuo Li, Jiquan Peng, Xi- aohan Fang, Feiran Huang, Senzhang Wang, Xing Xie, and Jibing Gong. Beyond the overlapping users: cross- domain recommendation via adaptive anchor link learn- ing. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1488-1497, 2023. 45. [Zhou et al., 2020] Fan Zhou, Chengtai Cao, Goce Tra- jcevski, Kunpeng Zhang, Ting Zhong, and Ji Geng. Fast network alignment via graph meta-learning. In IEEE IN- FOCOM 2020-IEEE Conference on Computer Communi- cations, pages 686-695. IEEE, 2020. 46. [Zhou et al., 2021a] Fan Zhou, Ce Li, Xovee Xu, Leyuan Liu, and Goce Trajcevski. Hgena: A hyperbolic graph embedding approach for network alignment. In 2021 IEEE Global Communications Conference (GLOBE- COM), pages 1-6. IEEE, 2021. 47. [Zhou et al., 2021b] Qinghai Zhou, Liangyue Li, Xintao Wu, Nan Cao, Lei Ying, and Hanghang Tong. Attent: Active attributed network alignment. In Proceedings of the Web Conference 2021, pages 3896-3906, 2021. 48. [Zhu et al., 2022] Jing Zhu, Danai Koutra, and Mark Heimann. Caper: Coarsen, align, project, refine-a gen- eral multilevel framework for network alignment. In Pro- ceedings of the 31st ACM International Conference on In- formation & Knowledge Management, pages 4747-4751, 2022.