T HE graph alignment problem, also referred to as the graph matching or noisy graph isomorphism problem, is the problem of finding the correspondence between the vertices of two correlated graphs. This problem has been given increasing attention for its applications in social network de-anonymization. For instance, datasets of social networks are typically anonymized for privacy protection. However, an attacker may be able to de-anonymize the dataset by aligning its user-user connection graph with that of publicly available data. Attributed graph alignment is a variant of graph alignment in which side information, referred to as attributes of vertices, is also publicly available in addition to the user-user connection information. This variant is motivated by the fact that there might exist publicly available attribute information in social networks. For example, the anonymized network Netflix has users' movie-watching history and ratings publicly available. Moreover, the examination of the proposed model provides both achievability and converse results for various well-known variations of the Erdős-Rényi graph alignment problems. These variations include the traditional graph alignment problem without attributes, the seeded graph alignment problem, and the bipartite alignment problem. Consequently, the study of attributed graph alignment introduces a novel perspective for investigating these problems within an integrated framework.
In this paper, we focus on the attributed graph alignment problem under the attributed Erdős-Rényi pair model G(n, p, s u ; m, q, s a ), first proposed in [1]. In this model, a base graph G is generated on the vertex set [n + m] where the vertices from the set [n] represent users and the rest of the vertices represent attributes. Between each pair of users, an edge is generated independently and identically with probability p to represent their connection. For each user-attribute pair, an edge is generated independently and identically with probability q to represent their association. Note that there are no edges between attributes. The graph G is then independently subsampled to two graphs G 1 and G 2 , where each user-user edge is subsampled with probability s u and each user-attribute edge is subsampled with probability s a . To model the anonymization procedure, a random permutation ⇧ ⇤ chosen uniformly at random is applied to the users in G 2 to generate an anonymized version G 0 2 . Our goal in this model is to achieve exact alignment, i.e., to exactly recover the permutation ⇧ ⇤ using G 1 and G 0 2 . For the attributed graph alignment problem, and the graph alignment problem in general, two often asked questions are the following. First, for what region of graph statistics is exact alignment feasible with unlimited computational power? This region is usually referred to as the information-theoretically feasible region or the information-theoretic limits. Second, for what region of graph statistics is exact alignment feasible with polynomial-time algorithms? This region is usually referred to as the feasible region of polynomial-time algorithms. Characterizing these two feasible regions and their relationship is of Fig. 1. Comparison between the feasible regions of the proposed algorithms and the information-theoretic limits: the shaded area ( 1 + 2 + 3 ) represents the information-theoretically feasible region given in [1]; area 2 is the feasible region for Algorithm ATTRRICH and area 3 is the feasible region for Algorithm ATTRSPARSE; area 4 is the information-theoretically infeasible region given in [1].
utmost importance to developing a fundamental understanding of the graph alignment problem.
There has been extensive studies on these two questions under the Erdős-Rényi pair model without attributes. A line of research focuses on the information-theoretic limits of exact alignment [2], [3], [4], [5]. Roughly speaking, it is shown that exact alignment is information-theoretically feasible when the intersection graph is dense enough. A sharp threshold of exact alignment has been established, while there still exists some gap between the converse and the achievability results. Another line of research focuses on polynomial-time algorithms for exact alignment [6], [7], [8], [9], [10]. Compared to the information-theoretic limits, the existing polynomial-time algorithms further require higher edge correlation between the pair of graphs to achieve exact alignment. The question of whether there exists polynomial-time algorithms that achieve the known information-theoretic limits is still left open.
For the attributed graph alignment problem, the information-theoretic limit has been studied in [1], where the feasible region (achievability results) and infeasible region (converse results) are characterized with a gap in between in some regimes. However, the feasible region of polynomial-time algorithms for attributed graph alignment has not been studied before, and it is the focus of this paper. In this work, we propose two polynomial-time algorithms for attributed graph alignment and characterize their feasible regions. The two algorithms are designed for two different regimes of parameters based on the richness of attribute information: the algorithm ATTRRICH is designed for the regime where mqsfoot_1 a = ⌦(log n), referred to as the attribute-information rich regime; and the algorithm ATTRSPARSE is designed for the regime where mqs 2 a = o(log n), referred to as the attribute-information sparse regime. In both algorithms, we first explore the user-attribute connections to align a set of anchor users, and then utilize the user-user connections to the anchors to align the rest of users. Due to the regime difference, ATTRRICH is able to generate a much larger set of anchors in the first step than ATTRSPARSE. Therefore, ATTRRICH and ATTRSPARSE make use of the anchors differently in the second step: ATTRRICH explores one-hop user-user connections to align the rest of users, while ATTRSPARSE explores one-hop or multiple-hop user-user connections to align the rest of users depending on the sparsity of user-user connections. This idea of matching vertices based on common neighbor witnesses has been explored to construct efficient graph alignment algorithms under the context of seeded graph alignment [11], [12], [13], [14]. In this work, we employ this idea in a two-step procedure under the setting of attributed graphs, and analyze its performance through a careful treatment of the dependency between the two steps.
Our characterizations of the feasible regions of ATTRRICH and ATTRSPARSE are illustrated in Figure 1 as areas 2 and 3 , respectively. The information-theoretically feasible and infeasible regions given in [1] are also illustrated in the figure for comparison. We can see that there is a gap between the feasible region achieved by ATTRRICH and ATTRSPARSE and the known information-theoretically feasible region. It is left open whether this gap is a fundamental limit of polynomialtime algorithms 1In addition, we specialize the feasible region of the proposed algorithms to the context of the seeded Erdős-Rényi graph alignment problem, and demonstrate that the specialized feasible region includes certain range of parameters that is not known to be achievable in the literature.
Our results reveal that attributes possibly facilitate graph alignment in a much more significant way when computational efficiency is a priority. We demonstrate this possible impact of attributes under the sparse regime np = ⇥(log n) in Figure 2. In Figure 2a, we let mqs 2 a = 0 so there is no information from the attributes, which is equivalent to the graph alignment problem without attributes; in Figure 2b, we let mqs 2 a = 0.1 log n. We keep p = o(1), and assume the value of nps u / log n can be an arbitrarily large constant but not tending to infinity in both settings for ease of comparison. Comparing these two figures, we can see that when mqs 2 a increases from 0 to 0.1 log n, the information-theoretic limits in terms of user-user parameters (n, p and s u ) improve a bit as expected. However, a more fundamental improvement is in the feasible region achievable by polynomial-time algorithms. In Figure 2a, the green region above s u = p ↵ is achievable by a polynomial-time algorithm proposed in [10], where ↵ ⇡ 0.338 is known as the Otter's constant. The red region below s u = p ↵ is not known to be achievable by any polynomial-time algorithms. Moreover, in [18], this red region is conjectured to be infeasible by any polynomial-time algorithm. 2 In comparison, in Figure 2b, the green region above the information theoretic limit, which is presented as the dotted curve, is achievable by our proposed polynomial-time algorithm ATTRRICH (assuming q = o(1) and s a = ⇥(1)). Therefore, if p ↵ is indeed the right threshold between achievable and impossible under polynomial-time algorithms for graph alignment without attributes in the sparse regime, a small amount of attribute information lowers this threshold to an arbitrarily small constant.
In this section, we describe a random process that generates a pair of correlated graphs, which we refer to as the attributed Erdős-Rényi pair model G(n, p, s u ; m, q, s a ). Under this model, we define the exact alignment problem.
We first generate a base graph G, whose vertex set V(G) consists of two disjoint sets, the user vertex set V u = {1, 2, . . . , n} and the attribute vertex set V a = {n + 1, n + 2, . . . , n + m}. There are two types of edges in the base graph G, the user-user edges (edges connecting a pair of users) and the user-attribute edges (edges connecting a user vertex and an attribute vertex). The user-user edges are generated independently and identically with probability p, and the user-attribute edges are generated independently and identically with probability q. Throughout this paper, we assume that p = o(1) and q = o(1). We write i G ⇠ j if vertices i and j are connected in graph G.
From the base graph G, we obtain two correlated graphs G 1 and G 2 by subsampling the edges in G independently. More specifically, we get G 1 and G 2 by independently including each user-user edge in G with probability s u and independently including each user-attribute edge with probability s a . Throughout this paper, we assume that s u = ⇥(1) and s a = ⇥(1).
From the G 2 generated as above, we get an anonymized graph G 0 2 by applying an unknown permutation ⇧ ⇤ on the user vertices of G 2 , where ⇧ ⇤ is drawn uniformly at random from the set of all possible permutations on V u . We use V u 2 to denote the user vertex set of G 0 2 and use V u 1 to denote the user vertex set of G 1 . Finally, we remark that this subsampling process is a special case of an earlier described attributed Erdős-Rényi pair model in [1].
Given an observable pair (G 1 , G 0 2 ), our goal is to recover the unknown permutation ⇧ ⇤ , which allows us to recover the original labels of user vertices in the anonymized graph G 0 2 . We say exact alignment is achieved with high probability (w.h.p.) if lim n!1 P( ⇧ 6 = ⇧ ⇤ ) = 0. It is worth mentioning that P( ⇧ 6 = ⇧ ⇤ ) = P( ⇧ 6 = ⇧ ⇤ |⇧ ⇤ = ⇡ id ) due to the symmetry among user vertices. Thus, we later assume without loss of generality that the underlying true permutation is the identity permutation.
A closely related graph generation model is the correlated stochastic block model [20], [21], [22]. In this model, the base graph G is instead generated from the stochastic block model, where vertices are grouped into latent blocks, and edges are formed between blocks with specific probabilities, capturing the underlying community structure in the network. The base graph G is then subsampled into the two generated graphs G 1 and G 2 . In the proposed attributed Erdős-Rényi graph pair models, users and attributes can be viewed as two communities in the correlated stochastic block model. However, a key distinction lies in the fact that the attributed Erdős-Rényi graph pair model specifies the correspondence between attributes in the two graphs, whereas the correlated stochastic block model does not disclose such information.
Another well-studied graph alignment model with side information is the seeded Erdős-Rényi graph pair model [11], [12], [13], [14], where we have access to part of the true correspondence between user vertices. To make a comparison between the seeded Erdős-Rényi graph pair model and the proposed model, here we describe the seeded Erdős-Rényi pair model G(N, ↵, p, s) in detail. We first sample a base graph G from the Erdős-Rényi graph on N vertices with edge probability p. Then two correlated copies G 1 and G 2 are obtained by independently subsampling the edges in the base graph where each edge is preserved with probability s. The anonymized graph G 0 2 is obtained by applying an unknown permutation ⇧ ⇤ on G 2 , where ⇧ ⇤ is drawn uniformly at random. Let V(G 1 ) and V(G 0
2 ) denote the vertex sets of G 1 and G 0 2 respectively. Then, a subset V s ⇢ V(G 1 ) of size bN↵c is chosen uniformly at random and we define the vertex pairs
2 ) together with the seed set I 0 are given and the goal of the exact alignment is to recover the underlying permutation for the remaining vertices w.h.p.
Comparing the seeded Erdős-Rényi pair model and the attributed Erdős-Rényi pair model, we can see that the seed set and the attribute set both provide side information to assist the alignment of the remaining vertices. Nevertheless, there are two main differences between the two models. First, in the attributed Erdős-Rényi pair model, we allow different edge probabilities and subsampling probabilities for user-user edges and user-attribute edges, whereas in the seeded Erdős-Rényi pair model, the edge probability is identical for all edges and so is the subsampling probability. Second, while there are edges between seeds in seeded Erdős-Rényi pair model, there are no attribute-attribute edges in the attributed Erdős-Rényi pair model. However, it can be shown that the existence of edges between seeds has no influence on the information-theoretic limits for exact alignment in the seeded Erdős-Rényi pair model (see Lemma 1 in [23]). This further suggests that regarding the task of exact alignment, the information-theoretic limits on attributed graph alignment recover the information-theoretic limits on seeded Erdős-Rényi graph alignment if we specialize p = q and s u = s a in the attributed Erdős-Rényi pair model G(n, p, s u ; m, q, s a ). Fig. 3. An illustration of attributed Erdős-Rényi pair model. We first sample a base graph G. Then we get G 1 and G 2 through edge subsampling G. The anonymized graph G 0 2 is obtained through apply the permutation ⇧ ⇤ on the user vertex set of G 2 .
Our algorithms rely on exploring the neighborhood similarity of user vertices in G 1 and G 0 2 . Here we introduce our notation of local neighborhoods. We define N a 1 (i) , {j 2 V a 1 : i G1 ⇠ j} as the set of attribute neighbors of a user vertex i in
⇠ j} as the set of attribute neighbors of a user vertex i in G 0 2 . For two user vertices i and j in the same graph, let d(i, j) be the length of the shortest path connecting i and j via user-user edges. For a user vertex i 2 V u 1 , we define the set of l-hop user neighbors of vertex i as N u 1 (i, l) , {j 2 V u 1 : d(i, j) l} for any positive integer l. By convention, when l = 1, we simply write
Reminder of the Landau notation.
Notation Definition
In this section, we propose two polynomial-time algorithms for the attributed graph alignment problem. Their feasible regions are characterized in the following two theorems.
Theorem 1: Consider the attributed Erdős-Rényi pair G(n, p, s u ; m, q, s a ) with p = o(1), q = o(1), s u = ⇥(1), and s a = ⇥(1). Assume that
and that there exists some constant ✏ > 0 such that
Then there exists a polynomial-time algorithm, namely, Algorithm ATTRRICH with the parameters chosen in ( 8) and ( 9), that achieves exact alignment w.h.p. Theorem 2: Consider the attributed Erdős-Rényi pair G(n, p, s u ; m, q, s a ) with p = o(1), q = o(1), s u = ⇥(1), and s a = ⇥(1). Assume that
and that there exists some constant ⌧ > 0 such that
Then there exists a polynomial-time algorithm, namely, Algorithm ATTRSPARSE with the parameters chosen in ( 11), ( 12) and ( 13), that achieves exact alignment w.h.p.
The proofs of Theorems 1 and 2 are deferred to Sections V and VI respectively.
In this subsection, we propose the first algorithm that leads to the achievable region in Theorem 1. This algorithm is designed for the attribute-information rich regime, hence named ATTRRICH.
• Input: The graph pair (G 1 , G 0
2 ) and thresholds x and y. • Step 1: Align through attribute neighbors. In this step, we only consider the edge connections between users and attributes, and use these information to find the matching for a set of vertices which will be later referred to as anchors. For each pair of users i 2 V u 1 and j 2 V u 2 , compute the number of common attribute neighbors
If
We refer to vertex pairs in the set S 1 as anchor. If there exists conflicting pairs in S 1 , i.e., two distinct pairs (i 1 , j 1 ) and (i 2 , j 2 ) with i 1 = i 2 or j 1 = j 2 , set S 1 = ; and declare failure. Otherwise, set ⇡(i) = j for all pairs (i, j) 2 S 1 .
• Step 2: Align through user neighbors. In the previous step, we have aligned the anchors using the edges between users and attributes. In this step, we will align the non-anchor vertices by their edge connections to the anchors. Let
For each unmatched pair i 2 U 1 and j 2 U 2 , consider the user neighbors of i and the user neighbors of j that are matched as pairs in S 1 , and compute the number of such matched pairs for (i, j)
For
The estimated permutation ⇡. In this algorithm, there are two threshold parameters x and y. In the following analysis, we choose
where
where 1 y = y log 1 p with constant y 2. Remark 1 (Complexity of Algorithm ATTRRICH): In Algorithm ATTRRICH, the time complexity for computing
) since there are n 2 pairs and for each pair, there are m attributes to consider. Similarly, the time complexity for computing W ij for all pairs
In this subsection, we propose the second algorithm that leads to the achievable region in Theorem 2. This algorithm is designed for the attribute-information sparse regime, hence named ATTRSPARSE. In Step 2 of this algorithm, we consider two different cases. In the case when the user-user connection is dense, we perform a similar process as in Step 2 of Algorithm ATTRRICH. In the case when the user-user connections is sparse, we call a seeded alignment algorithm proposed in [13], which is restated in Subsection III-C.
• Input: The graph pair (G 1 , G 0
2 ), three thresholds y, z and ⌘, an integer l, and the model parameters n and p.
• Step 1: Align through attribute neighbors. Similar to
Step 1 of Algorithm ATTRRICH, for each pair of users i 2 V u 1 and j 2 V u 2 , we compute the quantity
Unlike Step 1 of Algorithm ATTRRICH, we create an anchor set using a different threshold z.
We refer to vertex pairs in the set S 2 as anchors. If there exists conflicting pairs in S 2 , i.e., two distinct pairs (i 1 , j 1 ) and (i 2 , j 2 ) with i 1 = i 2 or j 1 = j 2 , set S 2 = ; and declare failure. • Step 2: Align through user-user edges.
-If np > n 1/7 , we perform the similar process as in
Step 2 of Algorithm ATTRRICH to align the nonanchor vertices. Define
-If np n 1/7 , run Algorithm III-C with the induced subgraphs on user vertices V u 1 and V u 2 , the seed set I 0 = S 2 , and parameters l and ⌘.
• Output: The estimated permutation ⇡. In this algorithm, there are four parameters y, z, l and ⌘ that we can choose. In the following analysis, we choose y to be the same value as in (9),
and
Remark 2 (Complexity of Algorithm ATTRSPARSE): In Algorithm ATTRSPARSE, the time complexity for computing
since there are n 2 pairs and for each pair, there are m attributes to consider. The time complexity of computing W ij for all pairs (i, j) 2 U 3 ⇥ U 4 is O(n 3 ) and that of Algorithm III-C is O(n 37/7 ) as given in [13], which can be improved with better data structures. Therefore, if np > n 1/7 , the complexity of
C. Seeded Alignment in the Sparse Regime [13, Algorithm 3] Except for the two graphs G 1 and G 0 2 , this algorithm takes a seed set I 0 as input. The seed set I 0 consists of vertex pairs (i, j) such that ⇡ ⇤ (i) = j. The algorithm utilizes this seed set to align the rest of vertices.
• Input: The graph pair (G 1 , G 0
2 ), the seed set I 0 , a threshold ⌘, and an integer l.
• Align high-degree vertices. Let
For each pair of unseeded vertices u 2 J 1 and v 2 J 2 , and for each pair of their neighbors i 2 N u 1 (u) \ {u} and
2 \{v,y} (j, l)}|}, where N u G\S (i 1 , l) denotes the set of user vertices i 2 such that d(i 1 , i 2 ) l in the induced subgraph G with the set of vertices S removed. Let
⌘|I0|} .
If Z u,v log n/ log log n 1, add (u, v) into set T . Add all the vertex pairs from I 0 to T . If there exists conflicting pairs in T , i.e., two distinct pairs (i 1 , j 1 ) and (i 2 , j 2 ) with i 1 = i 2 or j 1 = j 2 , set T = ; and declare failure.
• Align low-degree vertices. Let
2 )}, and
For all pairs of unmatched vertices i 1 2 J 3 and i 2 2 J 4 , if i 1 is adjacent to a user vertex j 1 in G 1 and i 2 is adjacent to a user vertex j 2 in G 0 2 such that (j 1 , j 2 ) 2 T , then set ⇡(i 1 ) = i 2 .
• Finalize and output: For each vertex pair (i, j) 2 T , set
2 ), output ⇡, otherwise declare failure.
In this section, we compare the feasible region in Theorems 1 and 2 to existing works. In Section IV-A, we compare the feasible region with the information-theoretic limits in [1]. It is shown that there still exists a gap between the feasible region of the proposed algorithms and the informationtheoretic limit. In Section IV-B, we specialize the feasible region of the proposed algorithm to the context of seeded graph alignment problem, and compare the specialized feasible region to the information-theoretic limits as well as the best-known feasible regions by polynomial-time algorithms for exact alignment in literature given in [13] and [14]. It is shown that while having a gap to the information-theoretic limit, the proposed Algorithms ATTRRICH and ATTRSPARSE achieves exact recovery in certain range of parameters that is unknown to be feasible by any existing efficient algorithms. In Section IV-C, we consider the bipartite alignment problem which is another special case. We show that the proposed Algorithm ATTRRICH provides an alternative polynomial-time algorithm to the theoretically optimal Hungarian Algorithm [24], with a slightly lower complexity.
The information-theoretic limits of attributed graph alignment were established in [1]. The version for the subsampling model is stated as follows.
Theorem 3 (Theorem 1 in [1]): Consider the attributed graph pair G(n, p, s u ; m, q, s a ) with 1 p = ⇥(1), 1 q = ⇥(1), s u = ⇥(1), and s a = ⇥(1).
Achievability: In the regime where
then exact alignment is achievable w.h.p.
In the regime where
where a n , m ⇣ p qs 2 a (1 q + q(1 s a ) 2 ) qs a (1 s a )
⌘ 2 mqs 2 a = O(mq 3/2 ), then exact alignment is achievable w.h.p.
, then no algorithm achieves exact alignment w.h.p.
From Theorem 3 we can see that when
, the achievability and converse differ by at most some constant times mq 3/2 ; when
, the achievability and converse are tight, because in this regime we have mq 3/2 = !(1). We visualize the information-theoretic limits and the computation feasible regions in Fig. 1.
In this subsection, we specialize the feasible region of proposed algorithm to the seeded Erdős-Rényi graph alignment problem, and compare the feasible region with that of the existing algorithms. Consider an attributed Erdős-Rényi graph pair (G 1 , G 0
2 ) ⇠ G(n, p, s u ; m, q, s a ) with p = q and s a = s u , s. Then these m attributes can be viewed as m seeds and (G 1 , G 0
2 ) can be viewed as a graph pair generated from a seeded Erdős-Rényi pair model G(n + m, m m+n , p, s), and the edges between the these m vertices are all removed. 3For simplicity, we write N , m + n and ↵ , m m+n later on. In our comparisons, we always assume that (1
and that there exists some constant ✏ > 0 such that
Then there exists a polynomial time algorithm, namely, Algorithm ATTRRICH with parameters x = (1 x )↵N ps 2 and y = (1 y )ps 2 that achieves exact alignment w.h.p. Here,
and that there exists some constant ⌧ > 0 such that
Then there exists a polynomial time algorithm, namely, Algorithm ATTRSPARSE with parameters
that achieves exact alignment w.h.p. Remark 3: As expected, the feasible region of proposed algorithms ATTRRICH and ATTRSPARSE is a strict subset of the information-theoretic feasible region established in [1]. We postpone the detailed comparison to Section VIII-A. Now we compare the proposed algorithms to the best known polynomial-time algorithms in the literature [13] and [14]. The comparison of their feasible regions is summarized in the following theorem, the proof of which is postponed to Section VIII-B.
Theorem 4 (Comparison of polynomial-time algorithms): Consider the seeded Erdős-Rényi pair model G(N, ↵, p, s) with p = o(1), s = ⇥(1) and (1 ↵)N = !(1). Assume that parameters N, ↵, p, and s satisfy any of the following four sets of conditions:
for some positive constant ✏. Then the proposed algorithms achieve exact alignment w.h.p., while none the of existing algorithms in [13] ad [14] is known to achieve exact alignment w.h.p. On the other hand, when
the feasible region of the proposed algorithms is a strict subset of that in [13].
Remark 4: The polynomial-time algorithms for graph alignment under the unseeded Erdős-Rényi graph pair model proposed in [9] and [10] trivially imply polynomial-time algorithm for seeded graph alignment. However, the feasible regions of algorithms in [9] and [10] both require additional conditions on the subsampling probability s. Therefore, we do not include them to the comparison in this section.
Remark 5: As shown in Corollaries 1 and 2, the two proposed algorithms achieve exact alignment in two mutually exclusive regimes. Theorem 4 summarizes the comparison between the union of the feasible regions of the two proposed algorithms and the union of the feasible regions in [13] and [14]. Regions 1 , 2 , and 3 in Theorem 4 correspond Fig. 4. Comparison of the feasible region of Corollaries 1 and 2 to the feasible region in [13] and [14]. On the top-left corner and bottom-right corner, the two blue regions are feasible for the proposed algorithms but not for any existing works. The red region is feasible for existing works, but not for the proposed algorithms. The green region is the overlap of our feasible region with the feasible region in the existing works.
to the top left blue area in Fig. 4. Region 4 in Theorem 4 corresponds to the bottom right blue area in Fig. 4.
As stated in Theorem 4, Corollaries 1 and 2 introduce some new feasible region in the regime Np > s 16(2 s) 2 N 1/2 (the top-left blue corner in Fig. 4). To understand the improvement over the feasible region in [13], recall that the proposed algorithms in this work align vertices two steps: initially aligning a group of anchor vertices by exploring the seeds within their one-hop neighborhood, and subsequently aligning the remaining unmatched vertices with the assistance of the anchors in their respective one-hop neighborhood. In contrast, the algorithm proposed in [13] for this scenario aligns all vertices by exploring the one-hop seed neighbors of the nonseed vertices, which closely resembles the first step of the proposed algorithms. This is why the proposed algorithms expand the feasible region introduced in [13]. To grasp the improvements made over the feasible region in [14], note that the algorithm introduced in [14] performs a similar two-step process as the algorithms in this work. The primary distinction lies in the second step of matching. In [14], the matched vertices from the first step, along with the seeds, act as anchors in the second step. In contrast, our proposed algorithms utilize only the matched vertices from the first step as anchors. We comment that the improvement of the proposed algorithms over the algorithm in [14] mainly comes from the tightness of analysis.
For completeness of the comparison, we restate the feasible regions of algorithms in [13] and [14] as follows.
Theorem 5 (Theorem 4 in [13]): Consider the seeded Erdős-Rényi pair model G(N, ↵, p, s). Suppose Np can be written as Np = bN a for some constants a and b such that
Then there exists a polynomial-time algorithm, namely, Algorithm 2 in [13], that achieves exact alignment w.h.p. Moreover, the algorithm runs in O(N 3 ) time. Theorem 6 (Theorem 3 in [13]): Consider the seeded Erdős-Rényi pair model G(N, ↵, p, s) with Np N for a fixed constant < 1/6, and s = ⇥(1). Assume that
and
and
where I(p, s) , 2ps log 1 ps +(2 2ps) log 1 1 ps +ps 2 log ps 2 + 2ps(1 s) log(ps ps 2 )+(1+ps 2 2ps) log(1+ps 2 2ps) = (1 + o(1))s 2 p log 1 p denotes the mutual information between a pair of correlated edges in G 1 and G 0 2 . Then there exists a polynomial-time algorithm, namely, the TMS algorithm in [14], that achieves exact alignment w.h.p.
Consider an attributed Erdős-Rényi graph pair (G 1 , G 2 ) ⇠ G(n, p, s u ; m, q, s a ) with p = 0 or s u = 0. Then G 1 and G 2 reduce to two bipartite graphs with edges connected only between users and attributes. In this special case, conditions (1) and ( 2) reduce to a single condition: If there exists some positive constant ✏ > 0 such that
then Algorithm ATTRRICH achieves exact alignment w.h.p. In contrast, Corollary 1 in [1] implies that the maximum likelihood estimator exactly recovers ⇡ ⇤ w.h.p if
Moreover, the maximum likelihood estimator can be computed in polynomial time by first computing the similarity score for each pair of vertices
| and then solving the balanced assignment problem using the famous Hungarian Algorithm first proposed in [24]. From conditions (24) and ( 25), we can see that the feasible region of Algorithm ATTRRICH is completely covered by the feasible region of the Hungarian Algorithm. By the above argument, the maximum likelihood estimator requires O(n 2 m)
time complexity to compute the similarity score for all pairs of vertices and the Hungarian Algorithm can be implemented with O(n 3 ) time complexity [25]. Therefore, if m = !(n), the time complexity of the maximum likelihood estimator is O(n 2 m) and if m = O(n), the time complexity of the maximum likelihood estimator is O(n 3 ). In comparison, the time complexity of Algorithm ATTRRICH in this special case is always O(n 2 m).
Recall that our algorithm consists of the following two steps: Step 1 (Align through attribute neighbors) produces a set S 1 that we refer to as the set of anchor pairs based on the C ij defined in (6); Step 2 (Align through user neighbors) aligns the remaining vertices based on the W ij defined in (7). Moreover, recall that we assume without generality that the true underlying permutation ⇡ ⇤ is the identity permutation. Our proof of Theorem 1 analyzes the following corresponding error events.
The event E c 1 guarantees that the anchor set found in the first step only contains correctly matched pairs.
In the special case that U 1 ⇥ U 2 = ;, i.e., all the vertices are matched in Step 1, we set events E 2 and E 3 to be empty by convention and thus P(E 2 ) = P(E 3 ) = 0. In the case that
2 \ E c 3 corresponds to the event that all non-anchor vertices are correctly matched through their user neighbors. We first show that E c 1 \E c 2 \E c 3 implies that Algorithm ATTR-RICH does not declare failure and it outputs ⇡ = ⇡ ⇤ . Under event E c 1 , it follows that there exists no conflicting pairs in S 1 , so Algorithm ATTRRICH does not declare failure at Step 1 and for each vertex
1 implies that U 1 = U 2 . Now we consider two different cases to complete the proof.
• U 1 = U 2 = ;: In this case, all the vertices are correctly aligned through attribute neighbors. Therefore, Algorithm ATTRRICH terminates at Step 1 and outputs ⇡ = ⇡ ⇤ .
• U 1 = U 2 6 = ;: In this case, not all the vertices are aligned through attribute neighbors. Then event E c 2 \ E c 3 guarantees that for each i 2 U 1 , we have
Thus, the algorithm does not declare failure at Step 2 and we have for each i 2 U 1 , ⇡(i) = i. Finally, it follows that ⇡ is a bijection and ⇡ = ⇡ ⇤ .
Next, to prove Theorem 1, it suffices to show that
. However, both events E 2 and E 3 are based on two random sets U 1 and U 2 . If we apply the union bound to upper bound the probability of E 2 and E 3 without any restriction on the size of U 1 and U 2 , the bound will be very loose. Our key idea of the proof is to analyze the error events of Step 2 by conditioning on a carefully chosen event. Specifically, let the set of vertex pairs correctly matched through attribute neighbors be denoted as
1 only counts the correctly matched pairs. Then we consider the following auxiliary event:
where c , max n 1
1 guarantees that the anchor set found in the first step only contains correctly matched pairs. It follows that event E c 1 implies S 1 = S 0 1 . Therefore, event A \ E c 1 restricts the size of the set U 1 ⇥ U 2 , so we can apply a much tighter union bound to upper bound the probability of E 2 and E 3 if we condition on the event A \ E c 1 .
where (26) follows by the union bound. With Lemmas 1-4 below, it is easy to see that
. Lemma 1: Consider G(n, p, s u ; m, q, s a ) with q = o(1) and
Lemma 2: Consider G(n, p, s u ; m, q, s a ) with q = o(1) and
Lemma 3: Consider G(n, p, s u ; m, q, s a ) with p = o(1) and
. Assume there exists some constant ✏ > 0 such that 1) . Lemma 4: Consider G(n, p, s u ; m, q, s a ) with p = o(1) and s u = ⇥(1). Assume there exists some constant ✏ > 0 such that
Lemma 11 (Approximation of KL-Divergence): Assume that ✓ = o(1), s = ⇥(1), and = ⇥(1). Then we have
With the three technical lemmas above, we are ready to prove Lemmas 1-8.
Recall that we defined error event
Here we prove P(E 1 ) = o(n 1/2 ) under the assumption that mqs 2 a = ⌦(log n). To bound the probability of E 1 , we first consider distribution of random variable C ij . For two different vertices i 2 V u 1 and j 2 V u 2 such that i 6 = j, it follows from the definition of the model G(n, p, s u ; m, q, s a ) that C ij ⇠ Binom(m, q 2 s 2 a ). Moreover, notice that 1) and q = o(1). Now, we can upper bound the probability of error event E 1 as
where (34) follows from the union bound, (35) follows from Lemma 9, (36) follows from Lemma 11 and (37) follows since constant x 3 log n mqs 2 a .
Recall that we defined auxiliary event
Here we prove P(A) = 1 o(1) under the assumption that mqs 2 a = ⌦(log n). To show this, we first consider the distribution of random variable C ii and upper bound the probability of event {C ii x}. For each vertex i 2 V u 1 , it follows from the definition of the model G(n, p, s u ; m, q, s a ) that C ii ⇠ Binom(m, qs 2 a ). Notice that
because q = o(1) and x = ⇥(1). We can upper bound the probability of the tail event {C ii x} using Lemma 9:
(38) follows from Lemma 11. For simplicity, we denote exp ⇣ mD KL ⇣ x log 1 q qs 2 a ||qs 2 a ⌘⌘ by from this point. By (38)
and the assumption that mqs 2 a = ⌦(log n), we have = o(1). Furthermore, notice that for each different i 2 V u 1 , the random variable C ii are independent and identically distributed. Therefore, the number of vertices i 2 V u 1 with C ii x is distributed according to the Binomial distribution
. By the upper bound (38), for any positive number z, we have
Recall that c , max n 1
, where ✏ is a positive constant. We have
where (40) follows from (38), and (41) follows since mqs 2 a = ⌦(log n). Finally, we can upper bound the probability of event A c as
where (42) follows from (39), (43) follows from Lemma 9, (44) follow from the Taylor expansion of the function log x and the fact that n c 1 = o(1) and = o(1), (45) follows since n c 1 = !( ) and finally, (46) follows from the fact that c 0.
Here we prove that the conditions ( 27) and (28) imply 1) . Recall that we defined events G(n, p, s u ; m, q, s a ) that C ij ⇠ Binom(m, q 2 s 2 a ). Moreover, notice that
. Therefore, we can upper bound the probability of error event E 4 as 1) , where (71) follows by the union bound, (72) follows from Lemma 9, and (73) follows since in (5) we assume that mq log 1 q ⌧ s 2 a 2 log n and ⌧ = ⇥(1).
Recall that we defined error event
Here we prove P(E 5 ) = o(1) under the assumption that mqs 2 a = o(log n). To show this, we first consider the distribution of random variable C ii and lower bound the probability of event {C ii z}. For each vertex i 2 V u 1 , it follows from the definition of the model G(n, p, s u ; m, q, s a ) that C ii ⇠ Binom(m, qs 2 a ). Notice that
We can lower bound the probability of the tail event {C ii z} using Lemma 10 as
where (74) follows since mqs 2 a = o(log n) and that ⌧ = ⇥(1). Furthermore, notice that for each different i 2 V u 1 , the random variable C ii are independent and identically distributed. Therefore, the number of vertices i 2 V u 1 with C ii z is distributed according to the Binomial distribution
. By the lower bound (75), for any positive number w, we have
Finally we can upper bound the probability of event E 5 as
1 n 1/9 ◆ = exp ✓ 1 72 n 7/8 log n (1 + o(1))n 8/9 ◆ = o(1), where (77) follows from (76) and (78) follows from Lemma 9. I. Proof of Lemma 11 (1) Proof for equation (32): From the definition of the KL-divergence between Bern ⇣ log 1/✓ ✓s 2 ⌘ and Bern(✓s 2 ), we have We therefore have
Here, the last equality (80) follows because ✓ = o(1).
(
Proof for equation (33): From the definition of the KL-divergence between Bern ⇣ log 1/✓ ✓s 2 ⌘ and Bern(✓ 2 s 2 ), we have
= ✓s 2 log + log 1/✓ log log 1/✓ log 1/✓ + o(✓)
Here (81) follows from the Taylor expansion of log(1 + x). Equation (82) follows because log 1/✓ = o(1). Equation (83) follows because = ⇥(1) and log 1/✓ = !(1).
In this section, we provide further details on the discussion in the seeded graph alignment problem in Section IV-B. We prove Remark 3 and Theorem 4 by comparing the feasible regions in Corollaries 1 and 2 to the information theoretic feasible region and the best known feasible region by efficient algorithms in literature.
Let us first compare the feasible region of Algorithms ATTRRICH and ATTRSPARSE to the information theoretic limit of seeded alignment. The next corollary follows readily from Theorem 3.
Corollary 3 (Information-Theoretic Limits on Seeded Graph Alignment): Consider the seeded Erdős-Rényi pair model G(N, ↵, p, s), with 1 p = ⇥(1), s = ⇥(1), and (1 ↵)N = !(1).
Achievability: In the regime where
then exact alignment is achievable w.h.p.
In the regime where
where a N , ↵N ⇣ p ps 2 (1 p + p(1 s) 2 ) ps(1 s)
N↵ps 2 = O(N↵p 3/2 ), then exact alignment is achievable w.h.p. Converse: If
then no algorithm achieves exact alignment w.h.p.
To compare the feasible region of Corollary 3 to the feasible regions of Corollaries 1 and 2, we consider two different regimes for p.
. In this regime, the feasible region in Corollary 3 is given by condition (84): Nps 2 log(N (1 ↵)) + !(1). In Corollary 1, condition (15) requires that Nps 2 (1 + ✏) log((1 ↵)N ). Since we assume that n = (1 ↵)N = !(1), we can see that condition (15) implies condition (84). Therefore, the feasible region in Corollary 1 is a subset of the feasible region in Corollary 3. Similarly, in Corollary 2, condition (17) can be written as Nps 2 log((1 ↵)N )+!(1)
1 ↵
, which also implies condition (84) since 1 ↵ < 1. Therefore, the feasible region in Corollary 2 is also a subset of the feasible region in Corollary 3.
2
. In this regime, the feasible region in Corollary 3 is given by condition (85):
, it follows that Nps 2 = !(log(N (1 ↵))). Moreover, since p = o(1) and a N = O(N↵p 3/2 ), we have Nps 2 = !(a N ). Therefore, condition (85) is satisfied and thus Corollary 3 applies in this regime while Corollaries 1 and 2 requires further conditions to apply. Therefore, the feasible regions in Corollaries 1 and 2 are both subsets of the feasible region in Corollary 3.
In this subsection, we prove Theorem 4 by thoroughly comparing the feasible region of the proposed algorithms in Corollaries 1 and 2 to that of the existing algorithms in Theorems 5, 6 and 7. We discuss three regimes for m.
Case 1: m = o(n). Recall that ↵ , m m+n . Therefore, we have ↵ = o(1) in this regime. For the discussion in this regime, we first show that both Corollaries 1 and 2 apply in this regime.
We then show that the feasible region in Corollaries 1 and 2 extends the feasible region for exact alignment in Theorems 5, 6 and 7.
To see Corollary 1 applies in this regime, note that when
(1 + ✏) log((1 ↵)N ). Therefore, the feasible region in Corollary 1 simplifies to condition (14), which is non-empty when p, s and ↵ are large enough. To see Corollary 2 applies in this regime, we notice that conditions (16) ↵N ps 2 = o(log((1 ↵)N )) and ( 17)
!(1) together imply that ↵ = o(1) which is exactly the case in this regime. Now we move on to compare the feasible region in Corollaries 1 and 2 to that in Theorems 5, 6 and 7. We consider three different regimes for Np.
Case 1.1: Np N 1/7 . For this regime of Np, both Theorems 5 and 6 apply. We will show that the feasible regions in Corollaries 1 and 2 are covered by the feasible region in Theorem 6 to illustrate that the proposed algorithms do not introduce any new feasible region in this regime. In this and all later cases, we always set = 1/7 when we apply Theorem 6. We first argue that the feasible region in Corollary 1 is a subset of that in Theorem 6. This is because condition ( 14) Case 1.2: N 1/7 < Np s 16(2 s) 2 N 1/2 . In this case, both Theorems 5 and 6 apply. We will show that the feasible regions in Corollaries 1 and 2 are covered by the feasible region in Theorem 5 to illustrate that the proposed algorithms do not introduce any new feasible region in this regime.
Firstly, we argue that the feasible region in Corollary 1 is a subset of that in Theorem 5. Note that because N 1/7 < Np Case 1.3: Np > s 16(2 s) 2 N 1/2 . In this regime, Theorem 6 does not apply since Np = ⌦(N 1/2 ). We compare the feasible regions in Corollaries 1 and 2 to those in Theorems 5 and 7 to show that the proposed algorithms strictly improve the best known feasible region in this regime.
To compare with the existing results, we first consider the feasible region achieved by the proposed algorithms. Because we are in the dense regime Np = ⌦(N 1/2 ), conditions (15) Nps 2
(1 + ✏) log((1 ↵)N ) and ( 17) Nps 2 . Then the bottleneck condition is condition (87). Therefore, if condition (86) is satisfied and ↵ < 300 log N Nps 2 , the proposed algorithms achieve exact alignment w.h.p while the algorithms in [13] and [14] do not. Such ↵ exists because log((1 ↵)N ) Nps 2 log 1 p = o( 300 log N Nps 2 ).
To summarize, in the regime of m = o(n), the proposed Algorithms ATTRRICH and ATTRSPARSE together strictly improve the best known feasible region for exact alignment when Np > s 16(2 s) 2 N 1/2 . In the other two regimes for Np, the feasible region of the proposed algorithms is a strict subset of that in [13].
Case 2: m = ⌦(n) and m = O(n 1+✏ 0 ) for some positive constant ✏ 0 that satisfies ✏ 0 < ✏ and ✏ ✏ 0 = ⇥(1) (cf. the constant ✏ in Corollary 1). In this regime, we have ↵ = ⇥(1). For the discussion in this regime, we first show that Corollary 1 applies in this regime while Corollary 2 does not.
We then show that the feasible region in Corollary 1 is a subset of the feasible regions in Theorems 5 and 6 from existing work [13].
Since we have ↵ = ⇥(1), it follows that Nps 2 (1 + ✏) log((1 ↵)N ) implies ↵N ps 2 = ⌦(log((1 ↵)N )), i.e., condition (15) implies (14). Therefore, the feasible region in Corollary 1 simplifies to condition (15) which holds true when p and s are large enough. As we argued in Case 1, Corollary 2 requires ↵ = o(1), so Corollary 2 does not apply in this regime. Now we move on to compare the feasible region in Corollary 1 to that in Theorems 5 and 6. We further consider two different regimes for Np. 300 log N (Nps 2 ) b1/ac . We can see that all the conditions in Theorem 5 are satisfied in this regime without any further assumptions.
For Corollary 1, we have Nps 2 = exp(⌦(log N )) (1 + ✏) log((1 ↵)N ), i.e., condition (15) is satisfied. We can see that all conditions in Corollary 1 are also satisfied in this regime without any further assumptions.
To summarize, in the regime m = ⌦(n) and = O(n 1+✏ 0 ), the feasible region of the proposed algorithms is a subset of the feasible region given by existing work [13].
Case 3: m = ⌦(n 1+✏ ). In this regime, we have ↵ = 1 o(1). For the same reason as in Case 2, Corollary 1 applies while Corollary 2 does not.
We will show that the feasible region in Corollary 1 extends the best known region for exact alignment in Theorems 5, 6 and 7. We discuss two regimes for Np.
Case 3.1: Np = exp(o(log N )). We first point out that Theorem 7 does not apply in this regime. This is because I(p, s) = ( 1 (1 + ✏) log((1 ↵)N ) the proposed Algorithm ATTRRICH achieves exact alignment w.h.p., while the algorithms in [13] does not.
Case 3.2: Np = exp(⌦(log N )). This case is included in the feasible region of both Corollary 1 and Theorem 5 for the same reason as in Case 2. Theorem 7 further requires conditions (22) and (23) to apply in this regime.
To summarize, in the regime m = ⌦(n 1+✏ ), the proposed Algorithm ATTRRICH strictly improves the best known feasible region for exact alignment in the case when Np = exp(o(log N )). In the case when Np = exp(⌦(log N )), the feasible region by the proposed algorithms is a subset of that in existing literature [13].
From the above discussion, when specialized to the seeded Erdős-Rényi graph pair model, the feasible region in Corollaries 1 and 2 strictly improves the best known feasible region in [13] and [14], as shown in the blue area in Fig. 4. We note, however, that there is also some region that is feasible by existing results but not feasible by the proposed algorithms in this paper, as shown in the red area in Fig. 4.
We comment that in the line of work[15],[16],[17], the authors have explored efficient algorithms for a closely-related problem known as attributed network alignment. In this problem, attributes are attached to both vertices and edges, in contrast to the exclusive association with vertices in attributed graph alignment. The focus in this line of work is the empirical performance rather than the theoretical feasible region.
We note that the conjecture presented in[18] pertains to the sparse regime where np = ⇥(log n). In contrast, for the dense regime, it is conjectured in[19] that no polynomial-time algorithm can achieve exact alignment if su 1/polylog(n).Authorized licensed use limited to: Carnegie Mellon University Libraries. Downloaded on April 01,2025 at 21:02:03 UTC from IEEE Xplore. Restrictions apply.
Authorized licensed use limited to: Carnegie Mellon University Libraries. Downloaded on April 01,2025 at 21:02:03 UTC from IEEE Xplore. Restrictions apply.
The information theoretic limit of exact alignment in the seeded graph alignment problem remains the same after removing the edges between attributes (see Lemma 1 in[23]).