Paper deep dive
Towards Effective and Efficient Graph Alignment without Supervision
Songyang Chen, Youfang Lin, Yu Liu, Shuai Zheng, Lei Zou
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/13/2026, 12:51:22 AM
Summary
The paper introduces 'GlobAlign' and 'GlobAlign-E', a new unsupervised graph alignment framework that replaces the traditional 'local representation, global alignment' paradigm with a 'global representation and alignment' approach. By utilizing self-attention mechanisms and a hierarchical cross-graph transport cost, the methods capture long-range node dependencies and improve both accuracy and computational efficiency, with GlobAlign-E reducing the time complexity of optimal transport-based methods from cubic to quadratic.
Entities (5)
Relation Signals (3)
GlobAlign → implements → global representation and alignment paradigm
confidence 95% · To implement our proposed paradigm, we introduce an effective and efficient unsupervised graph alignment framework... named GlobAlign.
GlobAlign-E → reducescomplexityof → Optimal Transport
confidence 95% · GlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT's cubic complexity to quadratic terms.
GlobAlign → utilizes → Self-attention
confidence 95% · Our model leverages the self-attention mechanism to derive node representations encoded with global graph information
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the ``local representation, global alignment'' paradigm, and present a new ``global representation and alignment'' paradigm to resolve the mismatch between the two phases in the alignment process. We then propose \underline{Gl}obal representation and \underline{o}ptimal transport-\underline{b}ased \underline{Align}ment (\texttt{GlobAlign}), and its variant, \texttt{GlobAlign-E}, for better \underline{E}fficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, \texttt{GlobAlign-E} successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT's cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20\% accuracy improvement over the best competitor. Meanwhile, \texttt{GlobAlign-E} achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.
Tags
Links
- Source: https://arxiv.org/abs/2603.08526v1
- Canonical: https://arxiv.org/abs/2603.08526v1
Trouble viewing inline? Open PDF directly →
Full Text
63,319 characters extracted from source content.
Expand or collapse full text
Towards Effective and Efficient Graph Alignment without Supervision Songyang Chen 1 , Youfang Lin 1 , Yu Liu 1* , Shuai Zheng 1 , Lei Zou 2 1* Beijing Jiaotong University, Beijing, 100044, P.R. China. 2 Peking University, Beijing, 100871, P.R. China. *Corresponding author(s). E-mail(s): yul@bjtu.edu.cn; Contributing authors: songyangchen@bjtu.edu.cn; yflin@bjtu.edu.cn; shuaizheng@bjtu.edu.cn; zoulei@pku.edu.cn; Abstract Unsupervised graph alignment aims to find the node correspondence across dif- ferent graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy- efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the “local representation, global alignment” paradigm, and present a new “global representation and alignment” paradigm to resolve the mismatch between the two phases in the alignment process. We then propose Gl obal representation and optimal transport-based Alignment (GlobAlign), and its variant, GlobAlign-E, for better Efficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross- graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, GlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based meth- ods, reducing OT’s cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, GlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods. Keywords: Unsupervised graph alignment, Alignment paradigm, Global interactions, Optimal transport 1 arXiv:2603.08526v1 [cs.LG] 9 Mar 2026 1 Introduction The graph alignment problem aims to predict node correspondence between two attributed graphs based on their topological structure and node features. It has a wide range of applications, such as matching scholar profiles across multiple academic platforms [1, 2], linking the same identity across different social networks for recom- mendation systems [3–5], and identifying functionally similar proteins across species in protein-protein interaction networks [6, 7]. Since the graphs to be aligned might come from different domains, the problem is particularly challenging in the unsupervised scenario, where no observed node correspondence are available. Recently, it has witnessed the blossom of deep learning-based approaches [5, 8–13] for unsupervised graph alignment. These methods predict an alignment matrix repre- senting the probabilities of node correspondence between the source and target graphs. A line of research [8–10], namely, the embedding-based method, follows the “embed- then-cross-compare” approach [5]. They first obtain node embeddings through graph neural networks (GNNs). Then two nodes are deemed matched if their embeddings are sufficiently close, as determined by a specified metric such as cosine similarity [9]. Another category of existing solutions [5, 6, 11, 12] treats graphs as probability distri- butions embedded in a specific metric space. By exploiting the Gromov-Wasserstein distance (GWD) [14], the graph alignment problem is reformulated as an optimal transport (OT) problem by minimizing the total cost of transporting distributions, and the key challenge lies in the specification of transport cost function. We refer to them as optimal transport (OT)-based methods. Both types of solutions have their advantages as well as limitations. The embedding-based models are simple and efficient, how- ever, it is non-trivial to formulate the graph alignment problem in the unsupervised setting, leading to suboptimal performance. In contrast, OT-based methods share a well-defined optimization objective and achieve promising accuracy, but usually incurs excessive running time due to its complexity. GAlignWAlignGTCAlignGWDSLOTAlignUHOT-GMGlobAlignGlobAlign-E 1101001000 Running Time (second) 0.0 0.2 0.4 0.6 0.8 1.0 Accuracy (Hits@1) 100100010000 Running Time (second) 0.5 0.6 0.7 0.8 0.9 1.0 Accuracy (Hits@1) 100100010000 Running Time (second) 0.50 0.55 0.60 0.65 0.70 0.75 0.80 Accuracy (Hits@1) (a) Douban(b) Allmv-Imdb(c) ACM-DBLP Fig. 1 Running time (s) vs. accuracy (Hits@1) on three widely-adopted datasets [5, 6, 9–11]. Existing embedding and OT-based methods show similar performance in terms of efficiency-accuracy tradeoff. Our GlobAlign model significantly surpasses existing solutions in accuracy, while our GlobAlign-E model achieves up to one order of magnitude speedup with comparable performance 2 1.1 Challenges In this paper, we observe two major issues overlooked by both types of studies, which hinder model performance. Firstly, for both categories, the representative methods [5, 6, 8–11] can be sum- marized as a “local representation, global alignment” paradigm. To be specific, the alignment procedure is decomposed into the local representation phase and the fol- lowing alignment phase. The alignment phase is global in nature because the model predicts an alignment probability for each pair of nodes across graphs. However, the local representation phase, which is crucial for node embedding and transport cost computation, relies on GNNs [15, 16] with local receptive fields [8–10], local propaga- tion [5, 6, 17], or simply the adjacency information [11]. We note that the mismatch between two phases results in model accuracy and robustness issues (Cf. Section 5, e.g., Figure 7), as these models struggle to capture long-range node dependencies and those beyond the explicit graph structure. Secondly, despite the recent efforts (e.g., [5, 10]) to enhance prediction accuracy, unfortunately, they essentially trade model efficiency for accuracy improvement as shown in our experimental study (see Figure 1). Take Allmv-Imdb as an example, with progressively more sophisticated transport cost design, OT-based methods (i.e., GWD [11], SLOTAlign [5], and UHOT-GM [6]) indeed demonstrate enhancement in pre- diction accuracy. Nonetheless, from the viewpoint of accuracy-efficiency tradeoff, the improvement is less prominent. This calls for a new perspective to resolve the issue. 1.2 Our Contributions To address the aforementioned challenges, we present the following contributions. Formalization of Alignment Paradigm. We first investigate existing embedding and OT-based methods by focusing on the amount of graph information exploited in the alignment process. We formalize them as the two-phase “local representation, global alignment” paradigm (see Table 2), proposing formal definitions for both phases to establish a clear understanding of model behavior. To the best of our knowledge, we are the first to analyze the limitations of local node interactions in existing meth- ods for addressing the graph alignment problem. Then, we theoretically analyze the mismatch between local representation and global alignment, and present a novel “global representation and alignment” paradigm to capture long-range and implicit node dependencies. The GlobAlign Method. To implement our proposed paradigm, we introduce an effective and efficient unsupervised graph alignment framework based on optimal transport, named GlobAlign. Gl obal representation and optimal transport-based Alignment, GlobAlign. Our model leverages the self-attention mechanism [18, 19] to derive node representations encoded with global graph information, facilitating the relationship modeling between arbitrary node pairs. This approach effectively addresses the challenge of capturing long-range dependencies and mitigates the issues arising from structure inconsis- tency [5, 17]. Based on the global representation, we devise a hierarchical cross-graph transport cost module following the OT-based problem formation. It is composed of 3 both the Wasserstein distance and Gromov-Wasserstein distance-based cost model- ing which integrates global information from different perspectives. They interact in a complementary manner to improve model performance. GlobAlign is optimized with the well-defined OT-based objective. GlobAlign for better Efficiency, i.e., GlobAlign-E. To bridge the time complex- ity gap between representative embedding and OT-based methods, we propose a more scalable model variant named GlobAlign-E with the help of our hierarchical cost design. By properly exploiting global information, it retains comparable accuracy to GlobAlign but reduces the cubic time complexity of OT-based solutions [5, 6, 11], demonstrating orders of magnitude speedup. GlobAlign-E has asymptotically iden- tical complexity compared to the embedding-based approaches [8, 10] under mild assumptions and achieves even better practical efficiency. Comprehensive Experimental Study. We conduct extensive experiments, in which the contribution is two-fold. On the one hand, we demonstrate the limitations of existing approaches, particularly under the accuracy-efficiency tradeoff (also see Figure 1). On the other hand, the advantage of GlobAlign and GlobAlign-E is val- idated in terms of prediction accuracy and model efficiency, while the improvements are both significant. Besides, the robustness analysis and ablation study show the effectiveness of our model. To sum up, our contributions are briefed as follows: • A new alignment paradigm. As far as we know, we are the first to formalize graph alignment via the exploitation of (local and global) graph information and present a new “global representation and alignment” paradigm. • GlobAlign leveraging global information. We propose two model variants, GlobAlign and GlobAlign-E, using not only local graph structure but also long- range and implicit node relations. Furthermore, GlobAlign-E closes the complexity gap between embedding and OT-based approaches. • Superior effectiveness and efficiency. Our models demonstrate superior per- formance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, GlobAlign-E is the fastest method in comparison, with an order of magnitude speedup against existing OT-based methods. 2 Preliminary and Problem Problem Statement. In alignment with existing research efforts [5, 6, 8–10], we focus on the challenge of node alignment between a pair of attributed graphs in the unsupervised scenario. We denote an undirected and attributed graph asG = (V,E, X) with node set V of size n, edge set E represented by the adjacency matrix A ∈ 0, 1 n×n , and node features X∈R n×d . We list frequently used notations in Table 1. Definition 1 (Unsupervised Graph Alignment). Given source graph G s and tar- get graph G t , we assume that n s = |V s |,n t = |V t |, and n s ≤ n t w.l.o.g. Without any observed node correspondences (i.e., anchors), the unsupervised graph alignment problem returns an n s × n t -sized alignment matrix T, where T(i,k) represents the probability that node u i ∈G s is aligned to node v k ∈G t . 4 Table 1 Table of notations. NotationDescription G s ,G t The source and target graph A p ,X p Adjacency matrix and node feature matrix (p = s, t) u i , u j , v k , v l Nodes with u i , u j ∈G s and v k , v l ∈G t D s ,D t The relation matrices of source graph and target graph TThe alignment matrix Cost gwd ,Cost wd The cross-graph transport cost S s ,S t The similarity matrices of node feature P s ,P t The PPR matrices of source and target graph M s ,M t The mask matrices Optimal Transport for Graph Alignment. Due to its favorable properties, a line of studies [5, 6, 11] employ optimal transport (OT) to formulate the graph align- ment problem. More specifically, it supposes that two samples (i.e., the node sets), V s = u i n s i=1 and V t = v k n t k=1 , are generated from the probability distributions μ ∈ ∆ n s −1 and ν ∈ ∆ n t −1 respectively, where ∆ n−1 denotes the (n− 1)-Simplex. Optimal transport (OT) and the associated Wasserstein Distance (WD) [20] are then employed to quantify the discrepancy between μ and ν given that they lie in the same space [21], as depicted by OT’s Kantorovich formulation [22]: W(μ,ν) =min T∈Π(μ,ν) ⟨C, T⟩.(1) Here, Π(μ,ν) = T∈R n s ×n t + : T1 n t = μ, T ⊺ 1 n s = ν is the set of joint probability distributions. and it holds that P n s i=1 P n t k=1 T(i,k) = 1. For the graph alignment problem, the (i,k)-th entry of T represents the probability that node u i ∈V s is aligned to v k ∈ V t , with C ∈R n s ×n t specifying the pairwise transport cost across two node sets. Gromov-Wasserstein (GW) Learning. When μ and ν lie in different spaces, which is common for cross-domain graph alignment, optimal transport cannot be applied directly as it is hard to define the transport cost C. To overcome this limitation, the Gromov-Wasserstein Distance (GWD) is introduced [14, 23] to measure the discrep- ancy between two samples by comparing their structural similarity, which is defined within each space separately by two relation matrices D s ∈R n s ×n s and D t ∈R n t ×n t . We have GWD ((D s ,μ), (D t ,ν)) =min T∈Π(μ,ν) X i,j,k,l L (D s (u i ,u j ), D t (v k ,v l )) T(i,k)T(j,l). (2) Let L :R ×R 7→R be the ground cost function, e.g., the ℓ 2 loss, we have L (D s (u i ,u j ), D t (v k ,v l )) = |D s (u i ,u j )− D t (v k ,v l )| 2 . This term measures the struc- tural similarity between u i ,u j ∈G s and v k ,v l ∈G t . In other words, for likely matched node pairs (u i ,v k ) and (u j ,v l ) with large values of T(i,k) and T(j,l), the values of D s (u i ,u j ) and D t (v k ,v l ) should be close [5, 11, 23]. 5 Table 2 Comparison of GlobAlign against state of the art: alignment paradigms and time complexity. Note that all methods share a space complexity of O(n 2 ), which is dominated by the output size. MethodAlignment ParadigmTime Complexity GAlign [8] Local Representation, Global Comparison O(n 2 d) WAlign [9]O(n 2 d) GTCAlign [10]O(n 2 d) GWD [11] Local Propagation, Global Transport O(n 3 ) SLOTAlign [5]O(n 3 ) UHOT-GM [6]O(n 3 ) GlobAlign Global Representation, Global Transport O(n 3 ) GlobAlign-EO(n 2 d + nm) Following [23], we reformulate Equation 2 as min T∈Π(μ,ν) ⟨L(D s , D t ) ⊙ T, T⟩, where (L(D s , D t )⊙ T) i,k = P j,l L (D s (u i ,u j ), D t (v k ,v l )) T(j,l). As a result, the term L(D s , D t )⊙ T ∈R n s ×n t can be interpreted as the transport cost (i.e., C) in Equation 1 [23]. To efficiently solve the OT problem, an additional entropic regular- ization term [24] is introduced into Equation 1, which transforms the problem into a strongly convex and smooth optimization problem [21, 25, 26]. For GWD, directly computation of Equation 2 incurs O(n 4 ) time. When the ground cost L is decompos- able [21, 23], L(D s , D t )⊙ T can be calculated as D 2 s μ1 ⊺ n t + 1 n s ν ⊺ D ⊺2 t − 2D s TD ⊺ t with O(n 3 ) time for better scalability [5, 11]. 3 The Alignment Paradigm: Local vs. Global We formalize the graph alignment process of recently proposed learning-based solu- tions, including embedding-based [8–10] and OT-based ones [5, 6, 11], into a two-phase representation-alignment paradigm (also see Table 2). We then point out that there exists a mismatch between the two steps within the current “local representation, global alignment” approach, and propose a“global representation and transport” solution to tackle this problem. 3.1 Formalizing Existing Alignment Paradigms Both the existing embedding (e.g., [8]) and OT-based (e.g., [5]) methods can be decomposed into the following two phases. 3.1.1 Local Representation/Propagation For existing approaches, this phase computes the node-wise representation (for embedding-based methods) or intra-graph node relation matrices (for OT-based methods) only based on the local graph information of each node. Definition 2 (Local Representation). Let N k (v) be the k-hop neighbors of node v for k = 0, 1,...,K, with N 0 (v) = v and N 1 (v) = N (v) (i.e., nodes adjacent to v). Let 6 R(v)∈R r be an r-dimensional representation calculated by a (learnable) function f : R(v) = f (N 0 (v),N 1 (v),...,N K (v)).(3) We say R(v) is a local representation of v since it contains the structural/feature information of nodes within K-hops from v, given that K is smaller than the graph diameter (e.g., K = 2 or 3). Note that the above definition adapts to both categories of learning-based align- ment methods. For embedding-based ones, e.g., [9], we set R(v) = Z(v) ∈R d , which can be computed using graph neural networks (GNNs). The function f is specified as GNN Θ accordingly in which Θ stands for the learnable parameters of GNN. To avoid over-smoothing [27] and over-squashing problems [28], long-range interactions with large K are prohibited. As for existing OT-based solutions [5, 6, 11], we have R(v) = D(v,·) ∈R n where D(v,·) denotes the v-th row of the relation matrix D. Particularly, GWD [11] directly sets D(v,·) = A(v,·) [5], while [5, 6] compute D(v,·) = ⟨Z ′ (v), Z ′ (·)⟩ by employing the inner product. Here, Z ′ (v) is calculated in a way similar to the embedding-based approaches but with a non-learnable func- tion g, which is commonly implemented as local feature propagation, for example, Z ′ (v) = g(N 0 (v),N 1 (v),...,N K (v)) = P K k=0 A k (v,·)· X. 3.1.2 Global Comparison/Transport In this phase, each node in the source graph is compared to every node in the target graph according to the node representation or the transport cost, resulting in a global comparison/transport procedure. Definition 3 (Global Alignment). Given R s ∈R n s ×r and R t ∈R n t ×r , the global alignment process is formulated as T(i,k) = h(R s (u i ), R t (v k )),(4) where h :R r ×R r 7→R is a learnable function (or procedure). This phase is global, because for each u i ∈G s , we compute T(i,k) for each v k ∈G t to find the one with the largest alignment probability. Existing embedding-based methods either adopt simple functions (e.g., h(R s (u i ), R t (v k )) = R s (u i ) ⊺ R t (v k )) [8, 10] or sophisticated learnable procedures such as generative adversarial network (GAN) [9] for the global comparison of node embed- dings, which can be viewed as predicting S∈R n s ×n t , the unnormalized form of T. For OT-based models, this global transport step is implemented by GW learning, given that the GWD-based transport cost Cost gwd (u i ,v k ) is computed from R s (u i ) and R t (v k ). 3.2 Mismatch between Local Representation and Global Alignment We claim that there is a mismatch between the local representation phase and the global alignment phase since the former encodes only local graph information which is 7 A a b c B C ... ... 퐺 푠 퐺 푡 Fig. 2 A toy example to show the limitation of local representation for graph alignment 퐃 푠 (푢 푖 ,∙) 푥 퐓(푥,푦) 퐃 푡 (푣 푘 ,∙) 푦 푢 푖 푣 푘 퐺 푠 퐺 푡 푢 푥 푣 푦 푢 푥′ 푣 푦′ 퐃 푠 (푢 푖 ,∙) 푥 퐓(푥,푦) 퐃 푡 (푣 푘 ,∙) 푦 푢 푖 푣 푘 퐺 푠 퐺 푡 푢 푥 푣 푦 푢 푥′ 푣 푦′ (a) Matrix formation(b) Graph formation Fig. 3 Illustration of node alignment from OT perspective later consumed by the latter phase. Subsequently, the global alignment process cannot achieve its full potential. We have the following lemmas. Lemma 1. Local representation (e.g., using GNNs) is insufficient for embedding-based alignment. Proof. Suppose that for a matched node pair (u i ,v k ), we have Z s (u i ) = GNN Θ (N 0 s (u i ),N 1 s (u i ),...,N K s (u i )), Z t (v k ) = GNN Θ (N 0 t (v k ),N 1 t (v k ),...,N K t (v k )). (5) When N k s (u i ) significantly differs from N k t (v k ) (also see Figure 2) and GNN Θ has sufficient discriminative power, e.g., with learnable injective functions [16], it is possible to have h(Z s (u i ), Z t (v k )) < h(Z s (u i ), Z t (v k ′ )) for some v k ′ . In general, graphs to be aligned are broadly similar but with structure inconsistency at a fine-grained level [5] (e.g., matched node pairs may display different topological relationships). For instance, consider the toy example in Figure 2, where nodes with the same letter but different cases are aligned. In particular, node u A and u B are first- order neighbors, whereas their aligned counterparts, v a and v b , are at a long distance. According to the structural similarity (e.g., rooted subtrees [16]), it is more proper to have Z s (u B ) ⊺ Z t (v a ) > Z s (u B ) ⊺ Z t (v b ), namely, S(u B ,v a ) > S(u B ,v b ), resulting in a false alignment. Lemma 2. Computing the relation matrices with local representation (or propagation) is insufficient for OT-based alignment via GW learning. Proof. Recall that GW learning assumes D s (u i ,u j ) ≈ D t (v k ,v l ) for two matched pairs (u i ,v k ) and (u j ,v l ). Therefore, the effectiveness of relation matrices is crucial to the alignment quality. As demonstrated in Figure 3, predicting T(i,k) relates to the node-wise comparison on the whole set of nodes. When u i and u x (resp. v k and 8 Self-Attention OT-based Optimization 푢 푖 푢 푗 퐺 푡 퐀 푡 ,퐗 푡 퐺 푠 퐀 푠 ,퐗 푠 푣 푘 푣 푙 Hierarchical Cross-Graph Transport Cost 퐺 푡 푢 푖 푣 푘 Θ-update Global Repres- entation Graph Structure min<퐂퐨퐬퐭,퐓> 퐓 퐺 푠 푢 푗 푣 푙 |퐃 푠 (푢 푖 ,푢 푗 ) -퐃 푡 (푣 푘 ,푣 푙 )| 푲(풖 풊 ,풗 풌 ) Fig. 4 The GlobAlign model framework v y ) are beyond 2K steps (e.g., v a and v b in Figure 2), a K-hop aggregation causes no information intersection and thus generates less effective D s (u i ,u x ) (resp. D t (v k ,v y )). This contradicts the original purpose of GWD utilizing intra-graph node similarity. Consider a special case where nodes are associated with different one-hot features. In this case, local propagation (e.g., [5, 6]) results in D s (u i ,u x ) = D t (v k ,v y ) = 0 for any u x and v y with more than 2K hops, and computes a sub-optimal transport cost. 3.3 Global Representation and Alignment To bridge the gap between the representation and the alignment phase, we pro- pose a “global representation and alignment” paradigm under the OT-based problem formation. Definition 4 (Global Representation). We say R(v)∈R r is node v’s representation with global information, if it is calculated as R(v) = f (X(w),∀w ∈V).(6) We opt for effective mechanisms such as self-attention that yield representation with global information. For two nodes u i ,u j ∈ G s (or similarly, v k ,v l ∈ G t ), their representations can be regarded as R s (u i ) = n s X x=1 α i,x X s (u x ), R s (u j ) = n s X y=1 α j,y X s (u y ).(7) Note that α x,y represents the attention weights, which can be properly learned to fulfill global interaction between u i and u j . Our approach is detailed in Section 4. Remark. We conjecture that it is non-trivial to apply the idea of global representa- tion to embedding-based approaches. We have substituted GNNs with Transformers for representative embedding-based methods but this leads to inferior performance, possibly due to their lack of well-defined objective in the unsupervised setting. We leave this as future work. 9 4 Our GlobAlign Model 4.1 Model Overview Our proposed model, GlobAlign, is illustrated in Figure 4. Given a pair of attribute graphs, we first employ a self-attention module (i.e., Transformers) to obtain node representation with global information. Next, we introduce a hierarchical cross-graph transport cost module considering both the overall structural similarity (i.e., GWD) and node-wise similarity (i.e., WD), which is crucial for both model accuracy and efficiency. Finally, we minimize the total transport cost by iteratively updating both the transport cost and the alignment probabilities. 4.2 Global Representation via Self-Attention Motivated by a series of studies on Transformers [18, 19, 29], we enable global inter- actions between nodes through the all-pair attention mechanism. We are particularly inspired by [19] and propose the following linear attention function: Q (i) = Norm(f (i) Q (Z (i−1) )),K (i) = Norm(f (i) K (Z (i−1) )),V (i) = f (i) V (Z (i−1) ), D (i) = diag 1 + 1 n Q (i) (K (i)⊺ 1) ,Z (i) = D (i)−1 V (i) + 1 n Q (i) (K i (i)⊺ V (i) ) , (8) where f (i) Q ,f (i) K , and f (i) V are linear feed-forward layers containing O(d 2 ) parameters, respectively. We denote by Norm(X) = X/∥X∥ F . Note that Z (i) is of dimension n×d, while we set Z (0) = MLP(X). We use two layers of linear attention, which is sufficient to capture implicit depen- dencies between arbitrary node pairs as shown by our experimental analysis, and exhibits much better efficiency than the softmax attention [18]. For each layer i, the above equation only incurs O(nd 2 ) time. In order to jointly attend to information from different representation subspaces, we apply multi-head attention to compute h embeddings Z 1 ,..., Z h , based on which the global representation R is derived: R = MHA(Z 1 ,..., Z h ) = Concat(Z 1 ,..., Z h )W O .(9) Here W O represents a hd× d-sized transformation matrix. 4.3 Hierarchical Cross-Graph Transport Cost To fully leverage the global representation in the alignment phase, we present a hierar- chical cross-graph transport cost design that efficiently integrates global information from different perspectives. Firstly, we use the Gromov-Wasserstein Distance (GWD) to model the overall structure similarity across two graphs. We have D s = β (1) s · A s + β (2) s · K(R s , R ⊺ s ), D t = β (1) t · A t + β (2) t · K(R t , R ⊺ t ), Cost gwd (i,k) = n s X j=1 n t X l=1 |D s (u i ,u j )− D t (v k ,v l )| 2 T(j,l),(10) 10 where β s = (β (1) s ,β (2) s ) ⊺ and β t = (β (1) t ,β (2) t ) ⊺ denote learnable weight parameters, while K(·,·) :R n×r ×R n×r 7→R n×n maps node representation to global node relations. For simplicity, we implement K(·,·) as the cosine similarity. Note that our node relation matrices also integrate the explicit graph structure A to achieve a balance between the topological inductive bias and the semantic similarity in latent space, while the latter addresses the challenge of long-range node dependencies that previous methods [5, 6, 8–11] struggle to capture. Secondly, we employ the Wasserstein Distance (WD) to directly formalize node- wise similarity with the help of global node embeddings R s and R t . We exploit the function K(·,·) and simply take the negative of node representation-based similarity since matched node pairs are with lower transport costs 1 : Cost wd (i,k) =−K(R s (u i ), R ⊺ t [v k ]).(11) Finally, we construct the hierarchical cross-graph transport cost matrix by combining the GWD and WD costs with α being the weight hyperparameter: Cost(u i ,v k ) = α· Cost gwd (u i ,v k ) + (1− α)· Cost wd (u i ,v k ).(12) Together, these two components establish a complementary relationship. While the GWD term exhibits more power in assessing the alignment cost, the WD term is com- putationally more efficient with only O(n 2 d) time as opposed to the O(n 3 ) complexity of GWD. 4.4 Improving Model Efficiency It is important to note the time complexity gap between embedding-based methods (e.g., [8, 10]) and OT-based solutions (e.g., [5, 11]), which are of O(n 2 d) and O(n 3 ) complexity, respectively. The complexity bottleneck of OT arises from the GWD cost computation (see Equation 2), more specifically, the D s TD ⊺ t term [11], which involves the multiplication of three n s ×n s , n s ×n t , and n t ×n t -sized matrices. Notably, when the relation matrices D s and D t are sparse, we can leverage sparse matrix multiplication to reduce computational complexity. In other words, we intend to close this complexity gap by employing a sparsified version of the hierarchical transport cost, the design of which presents non-trivial challenges to incorporate global information of the graphs. In this work, we propose a simple yet effective heuristic approach for the sparsifi- cation of the relation matrices (i.e., D s and D t ). Since the relation matrix represents pairwise metrics between nodes within a single domain, we sparsify it by preserving only the top-k (e.g., by setting k as the average degree) most relevant terms for each node, determined jointly by structure similarity and semantic proximity. Specifically, we adopt PageRank [30], a well adopted measure to model the structure similarity between nodes. In particular, we use its personalized version, i.e., the Personalized PageRank (PPR), in which the importance of node v from node u’s perspective, 1 As the initial features have been standardized, the similarity and cost values lie within the range of [−1, 1]. 11 denoted as PPR(u,v), is defined as follows: PPR(u,v) = γ· X w∈N (v) PPR(u,w) |N (w)| + (1− γ)· 1 v=u ,(13) where 1 v=u is the indicator variable which takes the value of 1 if the condition holds, and γ is the damping factor, typically set to 0.85 by default. For each node u, we compute the PPR values and only retain the top-k largest ones [31], based on which we obtain the structure-based mask matrices P s and P t for source and target graphs, namely, setting their matrix entries to 1 corresponding to the top-k items and 0 for others. To model the semantic proximity, we simply conduct feature-based similarity computation (i.e., with cosine similarity) for each graph. We sparsify the similarity matrices by only taking the row/column-wise top-k largest entries, and denote the resulting semantic-based mask matrices as S s and S t , respectively. Subsequently, we unify the structure-based (i.e., P s and P t ) and semantic- based (i.e., S s and S t ) matrices to obtain the final mask matrices M s and M t in Equation 14, thereby achieving complementary integration of both graph structural and feature information. Finally, the mask operation is selectively performed only on the K(R p , R ⊺ p ) term because of the intrinsic sparsity of the adjacency matrix. M p = max(P p , S p ), D p = A p + M p ⊙ K(R p , R ⊺ p ), p = s,t (14) We adopt the following cost design of Cost(u i ,v k ), which strikes a balance between the exploitation of global information and model efficiency: α· n s X j=1 n t X l=1 |D s (u i ,u j )− D t (v k ,v l )| 2 T(j,l) + (1− α)· (−K(R s (u i ), R t (v k ) ⊺ )). (15) Note that the global representation is explicitly adopted by the WD term, while the computational complexity of the GWD term is reduced thanks to the sparsification. More importantly, as both terms are unified to learn the alignment probability T, the model accuracy is still guaranteed. We refer to this model version as GlobAlign-E (GlobAlign for better Efficiency). 4.5 Optimization Algorithm Unsupervised graph alignment is solved by iteratively minimizing the inner product of the cost term Cost and the alignment matrix T: arg min T F (Cost, T),s.t.T1 n t = μ, T ⊺ 1 n s = ν.(16) Equation 16 is a nonconvex bi-quadratic problem [11, 23]. Let Θ = [Θ SA ,β s ,β t ] represent the learnable parameters, where Θ SA is for the self-attention module. The basic strategy here is to optimize the Cost (i.e., Θ-update) and the alignment matrix T 12 (i.e., T-update) in an alternating fashion. We adopt the proximal alternating linearized minimization strategy [32]. For the Θ-update, we have Θ (i+1) = arg min Θ ∇ Θ F (Θ (i) ) ⊺ Θ + 1 2τ ∥Θ− Θ (i)) ∥ 2 .(17) To update T, we follow the approach outlined in existing works [5, 6, 11], where entropic regularization is applied, and thus we can invoke the Sinkhorn algorithm [26] to tackle it efficiently: T (i+1) = arg min T n ⟨Cost (i)) , T (i) ⟩ + εKL(T∥T (i) ) o .(18) where the Kullback-Leibler (KL) divergence KL(T∥T (i) ) serves as a regularizer, whose significance is controlled by the weight hyperparameter ε. As the cost and T are itera- tively updated, the process terminates when the optimization objective in Equation 16 no longer decreases. The pseudocode is illustrated in Algorithm 1. 4.6 Complexity Analysis We provide a concise analysis of the time and space complexity of the proposed model. The complexity of calculating Cost wd , as defined in Equation 11, is O(n 2 d). The cost for GWD computation following Equation 10 results in a complexity of O(n 3 ), Thus the proposed GlobAlign has a complexity of O(n 3 ). For the efficient version, GlobAlign-E, as formulated in Equation 14, by setting k to the average node degree, the sparsified relation matrices contain O(kn + m) = O(m) non-zero entries, thus the D s TD ⊺ t term only has a complexity of O(nm). More precisely, since D s is a sparse matrix of O(m s ) non-zero items, multiplying it with each column of T has O(m s ) time complexity. Hence, D s times T results in O(m s n t ) complexity. Similarly, the multiplication of a dense matrix D s T with a sparse matrix D ⊺ t uses O(n s m t ) time. To this end, the GW learning process can be finished in O(nm) time. Thus the proposed GlobAlign-E has a complexity of O(n 2 d + nm). Note that real-world graphs are typically sparse, as shown in Table 3, we have m≤ nd in most cases, thus the complexity of GlobAlign-E is dominated by the O(n 2 d) term. It achieves identical asymptotic complexity to the state-of-the-art embedding- based methods [8–10]. Regarding space complexity, since the alignment matrix T is of size n s × n t , the overall space complexity is bounded by O(n 2 ). 5 Experiments 5.1 Experimental Setup 5.1.1 Datasets Our proposed methods are evaluated on five datasets (see Table 3), including three well-adopted real-world datasets in [5, 8–11]: the social network Douban Online- Offline [33], the co-author network ACM-DBLP [34], and the movie recommendation network Allmv-Imdb [8]. Additionally, we introduce two larger datasets: Coauthor CS [35] and Coauthor Physics [35], mainly for efficiency evaluation. For each graph, 13 Algorithm 1: The GlobAlign algorithm. Input: Attributed graphs G s (V s ,E s ,X s ),G t (V t ,E t ,X t ) Output: The alignment matrix T 1 Z (0) s ← MLP(X s ), Z (0) t ← MLP(X t ); 2 μ = 1 |V s | 1 |V s | , ν = 1 |V t | 1 |V t | , T (0) = μν T ; 3 for i = 1 to I do 4Compute R s , R t by Equations 8 and 9; // For GlobAlign 5Construct the hierarchical transport cost by Equations 10, 11, and 12; // For GlobAlign-E 6Construct the hierarchical transport cost by Equation 15; 7Update Θ (i+1) ← Θ (i) by Equation 17; 8Update T (i+1) ← T (i) by Equation 18; 9 return T; Table 3 Datasets and their statistics. Dataset|V s |,|V t | |E s |,|E t |FeaturesAnchors Douban 1,1183,022 5381,118 3,90616,328 Allmv-Imdb 5,713119,073 145,174 6,011124,709 ACM-DBLP 9,87239,561 176,325 9,91644,808 CS 18,333114,652 6,80518,333 18,333147,410 Physics 34,493347,147 8,41534,493 34,493446,332 we create a pair of graphs by perturbing 10% and 40% edges in the original graph, respectively. 5.1.2 Baselines We evaluate GlobAlign and GlobAlign-E against seven representative baselines, categorized as follows: (1) traditional method: kNN, (2) embedding-based meth- ods: GAlign [8], WAlign [9], and GTCAlign [10], (3) OT-based methods: GWD [11], SLOTAlign [5], and UHOT-GM [6]. We exclude approaches such as those presented in [12, 36–38], as they have been consistently outperformed by the baseline methods under consideration. Additionally, we omit methods (such as [39]) that impose strict constraints (e.g., requiring the graphs to be of identical size for alignment), or those 14 Table 4 Comparison of model performance against seven baselines on five datasets. DatasetsMetricskNN GAlign WAlign GTCAlign GWD SLOTAlign UHOT-GM GlobAlign GlobAlign-E Douban Hits@127.65± 0.23 45.33± 0.26 39.45± 0.37 60.89± 0.36 3.31± 0.27 51.41± 0.12 59.91± 0.35 77.10± 0.18 75.62± 0.16 Hits@542.33± 0.25 67.74± 0.17 62.41± 0.43 76.82± 0.21 8.35± 0.35 73.48± 0.23 71.50± 0.36 93.67± 0.21 91.88± 0.27 Hits@1049.30± 0.21 78.07± 0.23 71.52± 0.39 82.34± 0.25 9.98± 0.31 77.71± 0.19 77.33± 0.27 96.21± 0.25 94.34± 0.22 Hits@3063.23± 0.31 84.77± 0.29 83.21± 0.59 89.86± 0.23 12.91± 0.34 82.96± 0.21 84.74± 0.26 97.83± 0.23 95.19± 0.19 MRR35.04± 0.31 56.39± 0.23 46.23± 0.43 69.80± 0.13 5.81± 0.18 61.33± 0.21 67.42± 0.15 84.31± 0.17 81.52± 0.13 Allmv-Imdb Hits@130.41± 0.15 82.13± 0.19 52.69± 0.23 84.73± 0.16 87.82± 0.33 90.61± 0.11 91.63± 0.14 96.30± 0.13 94.82± 0.39 Hits@547.14± 0.20 86.39± 0.23 70.91± 0.32 89.89± 0.13 92.33± 0.25 92.81± 0.21 94.34± 0.18 97.69± 0.16 95.71± 0.31 Hits@1054.31± 0.41 90.01± 0.22 76.52± 0.53 91.34± 0.33 92.83± 0.23 93.14± 0.13 94.92± 0.16 97.88± 0.12 96.01± 0.36 Hits@3069.68± 0.33 93.33± 0.15 84.57± 0.24 93.71± 0.28 93.40± 0.18 94.72± 0.11 96.13± 0.13 98.79± 0.09 96.86± 0.14 MRR38.60± 0.37 84.98± 0.23 61.23± 0.11 87.14± 0.25 89.66± 0.19 91.61± 0.12 92.73± 0.16 97.32± 0.13 95.97± 0.23 ACM-DBLP Hits@136.31± 0.42 70.15± 0.13 63.41± 0.43 60.92± 0.14 56.45± 0.23 65.96± 0.11 TO78.25± 0.12 75.19± 0.23 Hits@566.81± 0.31 87.24± 0.12 83.12± 0.42 75.56± 0.21 77.11± 0.13 85.38± 0.16 TO93.89± 0.16 91.22± 0.26 Hits@1076.29± 0.32 91.44± 0.21 86.63± 0.33 80.04± 0.16 82.22± 0.22 87.89± 0.15 TO97.02± 0.10 95.21± 0.21 Hits@3084.68± 0.42 94.93± 0.22 93.67± 0.31 88.12± 0.14 85.23± 0.23 90.41± 0.16 TO98.38± 0.09 96.45± 0.17 MRR38.66± 0.28 77.57± 0.14 70.78± 0.53 67.71± 0.11 64.81± 0.19 73.78± 0.16 TO84.52± 0.13 81.96± 0.22 CS Hits@176.14± 0.23 86.71± 0.08 84.33± 0.25 92.11± 0.05 TOTOTO99.79± 0.04 98.53± 0.11 Hits@597.45± 0.12 98.42± 0.06 87.64± 0.17 97.56± 0.04 TOTOTO10099.34± 0.13 Hits@1098.81± 0.08 99.28± 0.13 88.28± 0.23 98.41± 0.09 TOTOTO10099.71± 0.08 Hits@3099.32± 0.06 99.78± 0.04 89.12± 0.13 99.27± 0.09 TOTOTO100100 MRR85.33± 0.11 92.89± 0.05 85.78± 0.14 97.35± 0.06 TOTOTO99.93± 0.02 99.21± 0.09 Physics Hits@180.59± 0.16 87.01± 0.23 88.26± 0.29 93.23± 0.11 TOTOTOTO99.03± 0.15 Hits@598.11± 0.15 98.19± 0.16 92.83± 0.23 98.47± 0.21 TOTOTOTO99.44± 0.19 Hits@1099.29± 0.09 98.41± 0.12 93.34± 0.18 99.35± 0.18 TOTOTOTO100 Hits@3099.56± 0.07 99.33± 0.11 94.11± 0.18 99.77± 0.18 TOTOTOTO100 MRR88.03± 0.15 97.56± 0.17 90.67± 0.11 98.58± 0.07 TOTOTOTO99.37± 0.11 1 The bold represents the best results, and the underlined numbers denote the second-best results. 2 TO (Time Out) stands for that the corresponding method could not finish within 3 hours. conducting exact alignment via bipartite graph matching, leading to a computational complexity of at least O(n 3 ) [39–41]. 5.1.3 Metrics. Following [5, 9, 10], we employ Hits@k with k = 1, 5, 10, 30 and Mean Reciprocal Rank (MRR) to evaluate the effectiveness of all methods. Given a node u ∈ G s , if the aligned node v ∈ G t is among the top-k nodes with the largest alignment probability, it is considered as a hit. For a dataset with |S ∗ | ground truth, Hits@k is defined as Hits@k = # of hits |S ∗ | . MRR is computed by averaging the inverse of the ground truth ranking, i.e., MRR = 1 |S ∗ | P (u,v)∈S ∗ 1 rank(u,v) . Notably, Hits@1 and MRR directly reflect the alignment accuracy. We also report each method’s running time to evaluate efficiency. For learning-based models, we define the running time as the total elapsed time until model convergence. Our codes will be made available after the review process. 5.2 Comparison of Model Performance 5.2.1 Model Accuracy The results are presented in Table 4. We conduct 10 runs of experiments for each method. Due to the high complexity of certain methods [5, 6, 11], experiments were ter- minated if they could not be completed within three hours. Our proposed algorithms GlobAlign and GlobAlign-E, demonstrate substantial accuracy gains over existing methods across all datasets. For instance, on the Douban dataset, the proposed meth- ods achieve notable improvements of 26.62% and 24.19% compared to GTCAlign, the best baseline, respectively. Similarly, on the DBLP dataset, the proposed approaches outperform the state-of-the-art method by 11.55% and 7.18%, respectively. On the 15 Douban 0 100 200 300 400 Running Time(s) GlobAlign-E WAlign GAlign GTCAlign GlobAlign GWD SLOTAlign UHOT-GM Allmv-Imdb 0 2000 4000 6000 8000 Running Time(s) GlobAlign-E WAlign GAlign GTCAlign GlobAlign GWD SLOTAlign UHOT-GM DBLP 0 2000 4000 6000 8000 10000 Running Time(s) GlobAlign-E WAlign GAlign GTCAlign GlobAlign GWD SLOTAlign UHOT-GM CS 0 2000 4000 6000 8000 10000 Running Time(s) GlobAlign-E WAlign GAlign GTCAlign GlobAlign GWD SLOTAlign UHOT-GM Physics 3000 5000 7000 9000 Running Time(s) GlobAlign-E WAlign GAlign GTCAlign GlobAlign GWD SLOTAlign UHOT-GM Fig. 5 Running time comparison. Vertical bars with diagonal lines represent methods that exceed the 3-hour time limit datasets CS and Physics, while all methods exhibit better performance, our methods consistently achieve further enhancements. These results highlight the effectiveness of our “global representation and alignment” paradigm, especially the critical role of global representation. For different versions of the proposed method, GlobAlign-E generally achieves comparable accuracy against GlobAlign. This also validates the effectiveness of our hierarchical transport cost design, particularly, Equation 15. For other OT-based methods including GWD, SLOTAlign, and UHOT-GM, we note that their performance demonstrates a gradual improvement along with the progressive incorporation of richer information into relation matrix design. Last but not least, we would like to point out that both embedding and OT-based baselines generally struggle with the accuracy-efficiency tradeoff on the real-world datasets (Cf. Figure 1 in Section 1). In other words, the improvement in prediction accuracy is achieved at the cost of less efficiency. By contrast, our methods significantly outperform them with respect to the tradeoff. 5.2.2 Model Efficiency As shown in Figure 5, We visualize the running time of all methods on datasets of varying sizes. When the number of nodes reaches 10 4 , as in the DBLP dataset, UHOT-GM first fails to complete the experiment within the three-hour limit due to its high computational complexity. As the dataset size continues to grow, other OT-based methods, GWD and SLOTAlign, also fail to complete the experiment in a reasonable time. Despite sharing the same theoretical time complexity, these methods exhibit running time discrepancies, potentially due to differences in model expressiveness, which may require varying numbers of epochs to achieve convergence. In contrast, embedding-based methods are generally faster, consistent with our theoretical analysis. For the proposed models, GlobAlign shows outstanding efficiency compared to other OT-based methods, whereas GlobAlign-E achieves orders of magnitude speedup over them. Besides, its running time improvement against embedding-based models is also remarkable. 5.3 Further Analysis of the Proposed Model 5.3.1 Robustness Analysis We evaluate the model’s performance across three real datasets under various noise levels. We select two representative methods SLOTAlign [5] and GAlign [8] for compar- ison. Our model exhibits significantly greater robustness under different noise levels (Figure 7). Notably, on the ACM-DBLP and Allmv-Imdb datasets, even when 50% 16 12163264128256 Feature Dim 50 60 70 80 90 100 Hits@1 Douban ACM-DBLP Allmv-Imdb 0.10.20.30.40.50.60.70.80.9 0 20 40 60 80 100 Hits@1 Douban ACM-DBLP Allmv-Imdb Fig. 6 Impact of hyperparameters 10%20%30%40%50% Noise Level 0 20 40 60 80 Hits@1 % GlobAlign SLOTAlign GAlign 10%20%30%40%50% Noise Level 40 50 60 70 80 Hits@1 % GlobAlign SLOTAlign GAlign 10%20%30%40%50% Noise Level 40 50 60 70 80 90 100 Hits@1 % GlobAlign SLOTAlign GAlign DoubanACM-DBLPAllmv-Imdb Fig. 7 Accuracy (Hits@1) vs. noise level of the edges are perturbed, our model surpasses the performance of GAlign and SLOTAlign under noise-free conditions. We believe that methods solely based on local graph information struggle to capture relationships between nodes when a certain percentage of edges are absent. 5.3.2 Sensitivity Analysis We also explore the model’s performance by varying feature dimensions and with different weight coefficients for Cost gwd and Cost wd . As shown in Figure 6, the model achieves stable performance across a wide range of feature dimensions. Additionally, as the weight parameter α in Equation 12 varies, the model’s performance exhibits slight fluctuations, which is dataset-specific, reflecting the different contributions of Cost gwd and Cost wd . In practice, we set α to 0.5, which strikes a balance between these two components. 5.3.3 Ablation Study To investigate the impact of different components, we conduct ablation studies on three real-world datasets with the following model variants. W/o Cost gwd (resp. W/o Cost wd ) represents that GlobAlign omits the GWD (resp. WD) term in Equation 12. W/o GR denotes that GlobAlign does not explicitly consider self-attention-based interactions in the GWD and WD terms, retaining only the local structural alignment in the GWD term. As shown in Figure 8, each component plays a crucial role, and the GWD- based cost is indispensable, without which GlobAlign cannot make a reasonable 17 DoubanACM-DBLPAllmv-Imdb 0 20 40 60 80 100 Hits@1 W/o Cost_gwd W/o Cost_wd W/o GR GlobAlign Fig. 8 Ablation study 6 4 2 0 2 4 1e8 4 2 0 2 4 1e9 (a) Offline Graph(b) Online Graph Fig. 9 The attention matrices for the Douban dataset prediction. This can be attributed to the superior properties of GWD in modeling cross-domain problems. Moreover, when the hierarchical cross-graph transport cost loses global interaction information (the W/o GR variant), the performance degrades significantly, demonstrating the critical importance of our proposed global repre- sentation and alignment strategy. Finally, by comparing the model complexity and accuracy between GlobAlign and GlobAlign-E, we validate the effectiveness of the sparsification strategy. 5.3.4 Analysis of Global Attention We visualize the attention matrix of Douban, as shown in Figure 9. In general, the attention matrix is more dense and shares less resemblance to the graph topological structure. Thus, we believe that our global representation with the self-attention mech- anism successfully extracts deeper influences between nodes for the graph alignment problem. 6 Related Work Early works typically formulate the graph alignment problem as the maximum common subgraph isomorphism problem [42–44] or the quadratic assignment prob- lem [45, 46], and return the exact alignment consisting a set of aligned node pairs. 18 However, in practice, it is difficult to achieve exact graph alignment because of its NP- hardness [11]. Some classical methods also employ spectral functions [39] and linear assignment algorithms [40, 41] to obtain matching results. These approaches typically have a computational complexity of at least O(n 3 ). In recent years, the research focus has shifted towards learning-based methods, which predict an alignment matrix indicating the alignment probability for every node pair across two graphs. These works can be roughly classified as embedding-based and Optimal Transport (OT)-based methods. Specifically, a line of research [8–10, 13, 37] follows the “embed-then-cross-compare” paradigm. First, node embeddings are gen- erated through graph representation learning and then mapped into a unified feature space using transformation functions [9] or weight-sharing mechanisms [8, 10]. Then the alignment matrix is derived by computing the similarity between node embeddings, with some methods [8, 13] further refining the results to improve prediction accuracy. Another popular approach is to model the graph alignment problem using optimal transport (OT). These methods [5, 6, 11, 47–49] treat graphs as distributions and use OT and its extended version in metric spaces, the Gromov-Wasserstein distance [14], to address cross-domain challenges. Based on the intra-graph costs that incorporate node- wise interactions, the cross-graph node correspondences are established by minimizing the total transport cost between the two distributions. Meanwhile, there exists a plethora of works [17, 33, 50–53] tackling the supervised graph alignment problem, in which a certain proportion of node correspondences is known in advance. In particular, consistency-based approaches [33, 51] usually assume the existence of a noisy permutation between the aligned graphs and put emphasis on local topology and attribute consistency. Embedding-based methods compute low- dimensional node embeddings through matrix factorization [52] or Random Walk with Restart (RWR) [53], ensuring anchor node pairs have close embeddings. A recently pro- posed method [17] formulates semi-supervised graph alignment as an optimal transport problem and devises transport cost inspired by RWR for the alignment process. We also find knowledge graph entity alignment a closely related research field with extensive literature [54–62], aiming to identify matching entities while incorporating richer semantic information, an extra ingredient compared to our studied problem. 7 Conclusion We propose GlobAlign, a global representation and optimal transport-based approach for graph alignment without supervision. Motivated by the limitations of the “local representation, global alignment” paradigm adopted by existing methods, GlobAlign follows a newly proposed “global representation and alignment” paradigm based on our problem formalization and theoretical analysis. It achieves superior performance by incorporating the global attention mechanism and a hierarchical cross-graph trans- port cost, whereas its variant targeting for better efficiency, i.e., GlobAlign-E, bridges the time complexity gap between representative embedding and OT-based methods, demonstrating significant speedup over both of them. Our solution advances unsuper- vised graph alignment for both accuracy and efficiency, which is prominent compared to recent studies. 19 Declarations Funding This work was supported by National Natural Science Foundation of China under grant 62202037 (Yu Liu) and 62372031 (Youfang Lin). Competing Interest The authors declare that they have no competing interest. Ethical Approval Not applicable. Availability of data and materials The source code and data will be made publicly available after the peer review process of the paper. Consent for publication We confirm that this manuscript has not been published elsewhere and is not under consideration by another journal. All authors have approved the manuscript and agree with its submission to World Wide Web. Author Contributions Songyang Chen and Yu Liu proposed the method and completed the manuscript writing. Songyang Chen conducted all the experiments for the paper, while Youfang Lin, Shuai Zheng, and Lei Zou provided valuable revision suggestions. Acknowledgement The authors gratefully acknowledge Prof. Dixin Luo and Prof. Hongteng Xu for their valuable contribution in providing the baseline code. References [1] Zhang, S., Tong, H., Jin, L., Xia, Y., Guo, Y.: Balancing consistency and disparity in network alignment. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, p. 2212–2222 (2021) [2] Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., Su, Z.: Arnetminer: extraction and mining of academic social networks. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 990–998 (2008) [3] Zhang, J., Philip, S.Y.: Multiple anonymized social networks alignment. In: 2015 IEEE International Conference on Data Mining, p. 599–608 (2015). IEEE [4] Li, C., Wang, S., Wang, H., Liang, Y., Yu, P.S., Li, Z., Wang, W.: Partially shared adversarial learning for semi-supervised multi-platform user identity link- age. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management, p. 249–258 (2019) [5] Tang, J., Zhang, W., Li, J., Zhao, K., Tsung, F., Li, J.: Robust attributed graph alignment via joint structure learning and optimal transport. In: 2023 IEEE 39th International Conference on Data Engineering (ICDE), p. 1638–1651 (2023). IEEE 20 [6] Cheng, H., Luo, D., Xu, H.: Dhot-gm: Robust graph matching using a differen- tiable hierarchical optimal transport framework. arXiv preprint arXiv:2310.12081 (2023) [7] Liu, Y., Ding, H., Chen, D., Xu, J.: Novel geometric approach for global alignment of ppi networks. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31 (2017) [8] Trung, H.T., Van Vinh, T., Tam, N.T., Yin, H., Weidlich, M., Hung, N.Q.V.: Adaptive network alignment with unsupervised and multi-order convolutional networks. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), p. 85–96 (2020). IEEE [9] Gao, J., Huang, X., Li, J.: Unsupervised graph alignment with wasserstein dis- tance discriminator. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, p. 426–435 (2021) [10] Wang, C., Jiang, P., Zhang, X., Wang, P., Qin, T., Guan, X.: Gtcalign: Global topology consistency-based graph alignment. IEEE Transactions on Knowledge and Data Engineering (2023) [11] Xu, H., Luo, D., Zha, H., Duke, L.C.: Gromov-wasserstein learning for graph matching and node embedding. In: International Conference on Machine Learn- ing, p. 6932–6941 (2019). PMLR [12] Titouan, V., Courty, N., Tavenard, R., Flamary, R.: Optimal transport for struc- tured data with application on graphs. In: International Conference on Machine Learning, p. 6275–6284 (2019). PMLR [13] Peng, J., Xiong, F., Pan, S., Wang, L., Xiong, X.: Robust network alignment with the combination of structure and attribute embeddings. In: 2023 IEEE International Conference on Data Mining (ICDM), p. 498–507 (2023). IEEE [14] M ́emoli, F.: Gromov–wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11, 417–487 (2011) [15] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016) [16] Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018) [17] Zeng, Z., Zhang, S., Xia, Y., Tong, H.: Parrot: Position-aware regularized optimal transport for network alignment. In: Proceedings of the ACM Web Conference 2023, p. 372–382 (2023) [18] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., 21 Kaiser, L., Polosukhin, I.: Attention is all you need. In: Advances in Neural Information Processing Systems, p. 5998–6008 (2017) [19] Wu, Q., Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., Yan, J.: Sim- plifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems 36 (2024) [20] Villani, C., et al.: Optimal Transport: Old and New vol. 338, (2009) [21] Li, M., Yu, J., Xu, H., Meng, C.: Efficient approximation of gromov-wasserstein distance using importance sparsification. Journal of Computational and Graphical Statistics 32(4), 1512–1523 (2023) [22] Kantorovich, L.: On the transfer of masses (in russian). In: Doklady Akademii Nauk, vol. 37, p. 227 (1942) [23] Peyr ́e, G., Cuturi, M., Solomon, J.: Gromov-wasserstein averaging of kernel and distance matrices. In: International Conference on Machine Learning, p. 2664– 2672 (2016). PMLR [24] Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems 26 (2013) [25] Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics 21(2), 343–348 (1967) [26] Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems 26 (2013) [27] Li, Q., Han, Z., Wu, X.-M.: Deeper insights into graph convolutional networks for semi-supervised learning. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32 (2018) [28] Alon, U., Yahav, E.: On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205 (2020) [29] Wu, Q., Yang, C., Zhao, W., He, Y., Wipf, D., Yan, J.: Difformer: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.09474 (2023) [30] Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Technical report, Stanford infolab (1999) [31] Bojchevski, A., Klicpera, J., Perozzi, B., Kapoor, A., Blais, M., R ́ozemberczki, B., Lukasik, M., G ̈unnemann, S.: Scaling graph neural networks with approximate pagerank. In: Gupta, R., Liu, Y., Tang, J., Prakash, B.A. (eds.) KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Vir- tual Event, CA, USA, August 23-27, 2020, p. 2464–2473. ACM, ??? (2020). https: 22 //doi.org/10.1145/3394486.3403296 . https://doi.org/10.1145/3394486.3403296 [32] Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming 146(1), 459–494 (2014) [33] Zhang, S., Tong, H.: Final: Fast attributed network alignment. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 1345–1354 (2016) [34] Zhang, S., Tong, H.: Attributed network alignment: Problem definitions and fast solutions. IEEE Transactions on Knowledge and Data Engineering 31(9), 1680– 1692 (2018) [35] Shchur, O., Mumme, M., Bojchevski, A., G ̈unnemann, S.: Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018) [36] Wang, Z., Lv, Q., Lan, X., Zhang, Y.: Cross-lingual knowledge graph alignment via graph convolutional networks. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, p. 349–357 (2018) [37] Heimann, M., Shen, H., Safavi, T., Koutra, D.: Regal: Representation learning- based graph alignment. In: Proceedings of the 27th ACM International Confer- ence on Information and Knowledge Management, p. 117–126 (2018) [38] Xu, H., Luo, D., Carin, L.: Scalable gromov-wasserstein learning for graph par- titioning and matching. Advances in neural information processing systems 32 (2019) [39] Hermanns, J., Skitsas, K., Tsitsulin, A., Munkhoeva, M., Kyster, A., Nielsen, S., Bronstein, A.M., Mottin, D., Karras, P.: Grasp: Scalable graph alignment by spectral corresponding functions. ACM Transactions on Knowledge Discovery from Data 17(4), 1–26 (2023) [40] Jonker, R., Volgenant, T.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. In: DGOR/NSOR: Papers of the 16th Annual Meeting of DGOR in Cooperation with NSOR/Vortr ̈age der 16. Jahrestagung der DGOR Zusammen Mit der NSOR, p. 622–622 (1988). Springer [41] Kuhn, H.W.: The hungarian method for the assignment problem. Naval research logistics quarterly 2(1-2), 83–97 (1955) [42] Bayati, M., Gerritsen, M., Gleich, D.F., Saberi, A., Wang, Y.: Algorithms for large, sparse network alignment problems. In: Wang, W., Kargupta, H., Ranka, S., Yu, P.S., Wu, X. (eds.) ICDM 2009, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009, p. 705–710. IEEE Computer Society, ??? (2009). https://doi.org/10.1109/ICDM.2009.135 . https: 23 //doi.org/10.1109/ICDM.2009.135 [43] Klau, G.W.: A new graph-based method for pairwise global network alignment. BMC Bioinform. 10(S-1) (2009) https://doi.org/10.1186/1471-2105-10-S1-S59 [44] Singh, R., Xu, J., Berger, B.: Pairwise global alignment of protein interac- tion networks by matching neighborhood topology. In: Speed, T.P., Huang, H. (eds.) Research in Computational Molecular Biology, 11th Annual International Conference, RECOMB 2007, Oakland, CA, USA, April 21-25, 2007, Proceed- ings. Lecture Notes in Computer Science, vol. 4453, p. 16–31. Springer, ??? (2007). https://doi.org/10.1007/978-3-540-71681-52 . https://doi.org/10.1007/ 978-3-540-71681-52 [45] Feizi, S., Quon, G.T., Mendoza, M.R., M ́edard, M., Kellis, M., Jadbabaie, A.: Spectral alignment of graphs. IEEE Trans. Netw. Sci. Eng. 7(3), 1182–1197 (2020) https://doi.org/10.1109/TNSE.2019.2913233 [46] Karakasis, P.A., Konar, A., Sidiropoulos, N.D.: Joint graph embedding and align- ment with spectral pivot. In: Zhu, F., Ooi, B.C., Miao, C. (eds.) KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Vir- tual Event, Singapore, August 14-18, 2021, p. 851–859. ACM, ??? (2021). https: //doi.org/10.1145/3447548.3467377 . https://doi.org/10.1145/3447548.3467377 [47] Chen, S., Liu, Y., Zou, L., Wang, Z., Lin, Y.: Combalign: Enhancing model expres- siveness in unsupervised graph alignment. IEEE Transactions on Knowledge and Data Engineering 38(2), 956–968 (2025) [48] Chen, S., Lin, Y., Liu, Y., Ouyang, Y., Guo, Z., Zou, L.: Enhancing robust semi- supervised graph alignment via adaptive optimal transport. World Wide Web 28(2), 22 (2025) [49] Chen, S., Lin, Y., Zeng, Z., Xue, M.: Leveraging attribute interaction and self- training for graph alignment via optimal transport. Mathematics 13(12), 1971 (2025) [50] Jiao, P., Liu, Y., Wang, Y., Zhang, G.: Cina: Curvature-based integrated network alignment with hypergraph. In: 2024 IEEE 40th International Conference on Data Engineering (ICDE), p. 2709–2722 (2024). IEEE [51] Zhang, S., Tong, H., Jin, L., Xia, Y., Guo, Y.: Balancing consistency and disparity in network alignment. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, p. 2212–2222 (2021) [52] Heimann, M., Shen, H., Safavi, T., Koutra, D.: Regal: Representation learning- based graph alignment. In: Proceedings of the 27th ACM International Confer- ence on Information and Knowledge Management, p. 117–126 (2018) 24 [53] Yan, Y., Zhang, S., Tong, H.: Bright: A bridging algorithm for network alignment. In: Proceedings of the Web Conference 2021, p. 3907–3917 (2021) [54] Wang, Z., Yang, J., Ye, X.: Knowledge graph alignment with entity-pair embed- ding. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), p. 1672–1680 (2020) [55] Sun, Z., Hu, W., Zhang, Q., Qu, Y.: Bootstrapping entity alignment with knowledge graph embedding. In: IJCAI, vol. 18 (2018) [56] Zeng, K., Li, C., Hou, L., Li, J., Feng, L.: A comprehensive survey of entity alignment for knowledge graphs. AI Open 2, 1–13 (2021) [57] Qi, Z., Zhang, Z., Chen, J., Chen, X., Xiang, Y., Zhang, N., Zheng, Y.: Unsu- pervised knowledge graph alignment by probabilistic reasoning and semantic embedding. arXiv preprint arXiv:2105.05596 (2021) [58] Liu, X., Hong, H., Wang, X., Chen, Z., Kharlamov, E., Dong, Y., Tang, J.: Selfkg: Self-supervised entity alignment in knowledge graphs. In: Proceedings of the ACM Web Conference 2022, p. 860–870 (2022) [59] Zeng, K., Dong, Z., Hou, L., Cao, Y., Hu, M., Yu, J., Lv, X., Cao, L., Wang, X., Liu, H., et al.: Interactive contrastive learning for self-supervised entity alignment. In: Proceedings of the 31st ACM International Conference on Information & Knowledge Management, p. 2465–2475 (2022) [60] Mao, X., Wang, W., Wu, Y., Lan, M.: From alignment to assignment: Frus- tratingly simple unsupervised entity alignment. arXiv preprint arXiv:2109.02363 (2021) [61] Mao, X., Wang, W., Wu, Y., Lan, M.: Lightea: A scalable, robust, and inter- pretable entity alignment framework via three-view label propagation. arXiv preprint arXiv:2210.10436 (2022) [62] Tang, J., Zhao, K., Li, J.: A fused gromov-wasserstein framework for unsupervised knowledge graph entity alignment. arXiv preprint arXiv:2305.06574 (2023) 25