{'fraction_non_alphanumeric': 0.06381835281472524, 'fraction_numerical': 0.01474539836087599, 'mean_word_length': 3.8083010335917313, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Graph Matching Using Generalized Seed Side-Information

In this paper, matching pairs of stocahstically generated graphs in the presence of generalized seed side-information is considered. The graph matching problem emerges naturally in various applications such as social network de-anonymization, image processing, DNA sequencing, and natural language processing. A pair of randomly generated labeled Erdos-Renyi graphs with pairwise correlated edges are considered. It is assumed that the matching strategy has access to the labeling of the vertices in the first graph, as well as a collection of shortlists -- called ambiguity sets -- of possible labels for the vertices of the second graph. The objective is to leverage the correlation among the edges of the graphs along with the side-information provided in the form of ambiguity sets to recover the labels of the vertices in the second graph. This scenario can be viewed as a generalization of the seeded graph matching problem, where the ambiguity sets take a specific form such that the exact labels for a subset of vertices in the second graph are known prior to matching. A matching strategy is proposed which operates by evaluating the joint typicality of the adjacency matrices of the graphs. Sufficient conditions on the edge statistics as well as ambiguity set statistics are derived under which the proposed matching strategy successfully recovers the labels of the vertices in the second graph. Additionally, Fano-type arguments are used to derive general necessary conditions for successful matching.


I. Introduction
Graphical representations capture pairwise relationships among sets of entities of interest. In are captured by the graph edges. In many applications, we are given a collection of graphs, each capturing a subset of the relationships among the same set of entities. A crucial step in analyzing such graphical data is the identification of vertices corresponding to the same entity across the graphs, i.e. to perform graph matching (Fig. 1). Graph matching techniques find application in social network de-anonymization, image processing, DNA sequencing, and natural language processing [1]- [4].
There has been extensive research on establishing the conditions for reliable graph matching [5]- [16], and constructing computationally efficient matching algorithms [17]- [20]. A number of these works focus on deriving the necessary and sufficient conditions for reliable matching of pairs of graphs under random graph generation models, where the graph edges are generated stochastically and in a correlated fashion [5]- [16]. This edge correlation is leveraged by the graph matching technique to uncover the underlying vertex alignment. Prior works have considered the problem under a variety of stochastic models. Graph isomorphism, considered in [5]- [8], studies matching two structurally equivalent graphs, i.e. graphs with the same set of vertices and edges. In this scenario, tight necessary and sufficient conditions for successful matching have been derived when the graph edges are generated based on the Erdös-Rényi (ER) model, i.e. when the graph edges are generated independently, and based on an identical distribution [5]. A more general stochastic model is considered in [10]- [15], where the graph edges are not exactly equal, rather they are generated based on the correlated ER stochastic model. Under this model, pairs of edges connecting corresponding vertices across the graph are generated based on a joint probability distribution, independently of all other edges. Necessary and sufficient conditions for successful graph matching have been derived. However, characterizing tight necessary and sufficient conditions remains an open problem.
A variant of the graph matching problem -called seeded graph matching -considers the scenario where the correct matching for a subset of vertices is known prior to the start of the matching process [6], [10], [12], [20]- [23]. The vertices for which the correct matching is known are called the seed vertices. An instance of this scenario is de-anonymization of users over multiple social networks, where the objective is to match the user profiles belonging to the same users over multiple online social networks such as Facebook, Twitter, Google+, LinkedIn, etc. In practice, a fraction of individuals publicly link their accounts across multiple networks. It turns out, that in many cases, these linked accounts may be leveraged as seeds to identify a large fraction of the users in the network [6], [10], [20]- [23]. In this work, we generalize the notion 1 2 Fig. 1. The graphs g 1 (red) and g 2 (gray) each capture a subset of the relationships among entities represented by their vertices.
A graph matching strategy finds a bijective correspondence (dotted lines) across the vertices of the two graphs based on their link structure.
of seed side-information, and consider a scenario in which rather than a set of seed vertices in g 1 (the de-anonymized graph) and g 2 (the anonymized graph), the matching algorithm has access to a collection of shortlists -called ambiguity sets. To elaborate, for each vertex v s in g 2 the matching algorithm is given an ambiguity set consisting of candidate labels L s , one of which is the correct label for v s . Seeded graph matching is a special instance of this scenario, where the ambiguity sets corresponding to the seed vertices have a single element (the correct label), whereas all other ambiguity sets contain all possible labels. Graph matching using ambiguity set side-information arises naturally in a wide range of real-world scenarios. For instance, in social network de-anonymization, such ambiguity sets can be generated based on the user's online fingerprint, i.e. 'liked pages', 'group memberships', etc. [24], [25]. Another application is image recognition [3], where a 'coarse matching algorithm' can be used to construct a collection of ambiguity sets containing the labels of possible matches for each image segment, followed by a 'fine matching algorithm' which completes the matching of segments using the ambiguity sets as side-information.
The contributions of this work are summarized below: • We provide a stochastic model for the ambiguity sets. The proposed formulation allows for correlation among elements in each ambiguity set, as well as correlation across different ambiguity sets.
• We propose the typicality matching (TM) strategy for matching pairs of correlated graphs generated under the Erdös-Rènyi model with ambiguity set side-information. This strategy build upon prior work in [23], [26], [27].
• We consider several graph matching scenarios under the proposed stochastic ambiguity set model, including seeded graph matching, equiprobable ambiguity sets, and specific scenarios with correlated ambiguity sets; and to use information theoretic analysis to derive sufficient conditions for the success of the TM strategy in each scenario.
• We use Fano-type arguments to derive necessary conditions for success of matching algorithms in the presence of ambiguity set side-information.
Notation: Random variables are represented by capital letters such as X, U, and their realizations by small letters such as x, u. Sets are denoted by calligraphic letters such as X, U. The probability of the event A ⊆ X is denoted by P X (A), and the subscript X is omitted when there is no ambiguity. The expected value of X is written as E(X). The set of natural numbers, and real numbers are shown by N, and R, respectively. The random variable 1(E) is the indicator function of the event E. The set of numbers {n, n + 1, · · · , m}, n, m ∈ N is represented by [n, m].
Furthermore, for the interval [1, m], we sometimes use the shorthand notation [m]. For a given n ∈ N, the n-length vector (x 1 , x 2 , . . . , x n ) is written as x n .

II. Problem Formulation
A weighted graph g = (V, E) is characterized by a vertex set V = {v 1 , v 2 , · · · , v n }, and an where g σ,i, j , i j is the attribute of the edge between v σ −1 (i) and v σ −1 ( j) , and g σ,i,i 0, i ∈ [1, n].
The structure U = [g σ,i, j ] i< j is called the upper triangle (UT) of the adjacency matrix.
In this paper, we consider stochastic graphs generated under the correlated ER model, where it is assumed that the edges connecting similarly labeled vertices across the graphs are generated based on an identical distribution, independently of all other edges. The correlated ER model is formally introduced in the following definitions.
Definition 1 (ER Model). A random graph under the ER model is parametrized by the tuple (n, , P X ), where n is the number of vertices, is the number of possible edge attributes, and P X is a probability distribution on the alphabet [0, − 1]. We have: where x s,t ∈ [0, − 1] and x s,s = 0, s ∈ [1, n].
In this paper, we consider matching of pairs of correlated ER graphs as defined below.
Definition 2 (Correlated ER Graphs). A pair of correlated ER graphs (g 1 ,g 2 ) is parametrized by the tuple (n, , σ 1 , σ 2 , P X,Y ), where σ 1 and σ 2 are the labeling functions forg 1 andg 2 , respectively, Let v 1 , w 1 and v 2 , w 2 be two pairs of vertices with the same labels ing 1 andg 2 , respectively, i.e. σ 1 (v 1 ) = σ 2 (v 2 ) = i 1 and σ 1 (w 1 ) = σ 2 (w 2 ) = i 2 . Then, the pair of edges between (v 1 , w 1 ) and (v 2 , w 2 ) are generated according to P X,Y , independently of all other edges. Alternatively, In graph matching under the correlated ER model, [12]- [15], a pair of correlated ER graphs (g 1 ,g 2 ) are considered. The objective is to design a matching strategy which takes the labeled graphg 1 , and unlabeled graph g 2 as input, and outputs the reconstructionσ 2 of the labeling function σ 2 . In this paper, we assume that the matching strategy has access to additional side information in the form of ambiguity sets containing a set of candidate labels for each vertex in g 2 . To elaborate, the strategy has access to a collection of ambiguity sets L s , s ∈ [1, n], where L s ⊆ [1, n], such that the label σ 2 (s) is in the ambiguity set L s , for each s ∈ [1, n]. This is a generalization of the seeded graph matching model [6], [10], [20]- [23], where it is assumed that the correct labeling for a subset of vertices in g 2 are provided beforehand. The matching strategy is said to succeed if the fraction of the correctly labeled vertices 1 n {s ∈ [1, n] :σ 2 (s) = σ 2 (s)} approaches 1 as n → ∞.
In this work, we consider stochastically generated ambiguity sets. We use bold calligraphic typeset, e.g. L s , s ∈ [1, n], to denote random ambiguity sets, and the calligraphic typeset, e.g. L s , s ∈ [1, n], to denote their realizations. Let B s,i be the indicator that the label i is in the ambiguity set of vertex v s , i.e. B s,i 1(i ∈ L s ). Note that each ambiguity set L s must contain the correct label σ 2 (s) of v s . Alternatively, we must have B s,i s = 1, where i s = σ 2 (s). In the most general scenario, the n × n binary matrix B = [B s,i ] s,i∈ [1,n] is generated randomly based on a joint distribution P B , with the condition that P(B s,σ 2 (s) = 1) = 1, s ∈ [1, n].
Definition 3 (Random Ambiguity Sets). Consider the pair (n, P B ), where n ∈ N, and P B is a probability distribution on binary n×n matrices such that P B s,is (1) = 1 for i s = σ 2 (s). A collection of ambiguity sets L s , s ∈ [1, n] are generated based on parameters (n, P B ) as follows: For a given collection of ambiguity sets L 1 , L 2 , · · · , L n , we often write P B (b) instead of [1,n] is the binary matrix of indicator variables corresponding Remark 1. We have assumed that the ambiguity sets are generated independently of the graph edges. However, this may not hold in many practical applications. Graph matching with correlated ambiguity set and edge set generation is an interesting avenue for future work.
Remark 2. The ambiguity set model described in Definition 3 captures the seeded graph matching problem as a special case. This is investigated in Section IV-B.
The following formally defines a strategy for graph matching in the presence of ambiguity set side-information.
Definition 4 (Matching Strategy). Consider a family of pairs of correlated ER graphsg 1 n = (g 1 n , σ 1 n ) andg 2 n = (g 2 n , σ 2 n ), n ∈ N, parameterized by the tuple (n, , σ 1 n , σ 2 n , P n,X,Y ), n ∈ N. Furthermore, consider a family of collections of ambiguity sets L n,s , s ∈ [1, n] generated according to P n,B (·), where P n,B , n ∈ N is a family of distributions defined on binary n×n martrices. A matching strategy is a sequence of functions f n : (g 1 , g 2 , (L n,s ) s∈ [1,n] ) →σ 2 , n ∈ N. Let I n be distributed uniformly over [n]. The matching strategy is said to succeed if P σ 2 (I n ) =σ 2 (I n ) → 1 as Our objective is to investigate the necessary and sufficient conditions on sequences of edge statistics P n,X,Y , n ∈ N and ambiguity set statistics P n,B , n ∈ N such that a successful matching strategy exists.

III. Permutations of Pairs of Sequences
In [26], we have proposed typicality based graph matching strategies under the seedless and seeded correlated ER model, and evaluated the success conditions. In this section, we introduce some of the results on typicality of permuted sequences which are used in our analysis in the subsequent sections. A more complete description of these tools is provided in [26].
Definition 5 (Strong Typicality [28]). Let the pair of random variables (X, Y) be defined on the probability space (X × Y, P X,Y ), where X and Y are finite alphabets. The -typical set of sequences of length n with respect to P X,Y is defined as: where t is the joint type of (x n , y n ), > 0, and n ∈ N.
Theorem 1 (Typicality of Permutation of Correlated Sequences [26]). Let ∈ [0, 1 2 min x,y∈X×Y P X,Y (x, y)], and consider (X n , Y n ) a pair of i.i.d sequences defined on finite alphabets X and Y, respectively.
Let π be a permutation of vectors of length n, with m ∈ [n] fixed points. Then, where α

IV. Sufficient Conditions for Successful Matching
In this section, we consider several stochastic models on the ambiguity set distribution P B , and derive sufficient conditions on the edge statistics P X,Y and the ambiguity set statistics P B under which a successful matching strategy exists. In particular, we consider the typicality matching strategy, described in the following, and evaluate its success conditions.

A. Typicality Matching Strategy
Given a correlated pair of ER graphs (g 1 , g 2 ) with joint edge distribution P X,Y , where only the labeling forg 1 is given, and the collection of ambiguity sets L s , s ∈ [1, n] generated according to P B , the TM strategy operates as follows. It finds a labelingσ 2 consistent with the ambiguity sets, for which the pair of UT's U 1 σ 1 and U 2 σ 2 are jointly typical with respect to P X,Y when viewed as vectors of length n(n−1) 2 . The strategy fails if no such labeling exists. Alternatively, it finds an elementσ 2 in the set: where = ω( 1 n ). Note that the set Σ may have more than one element. In that case, the strategy chooses one of these elements randomly and uniformly as the output. We will show that under certain conditions on the joint edge distribution and ambiguity set statistics, all of the elements of Σ satisfy the criteria for successful matching given in Definition 4. In other words, for all of the elements of Σ the probability of incorrect labeling for any given vertex is arbitrarily small for large n. Formally, the TM strategy is a sequence of functions f n : (g 1 n , g 2 n ) × (L s ) s∈[1,n] → (g 1 n ,ĝ 2 n ), n ∈ N, where for any given n ∈ N, the labelingσ 2 n ofĝ 2 n is chosen randomly and uniformly from the set Σ defined previously.

B. Seeded Graph Matching
In this scenario, it is assumed that for a given γ = k n , k ∈ {0, 1, · · · , n}, the correct label of a randomly chosen subset of γn vertices in g 2 are known prior to start of the matching process. The scenario can be viewed as a special case of graph matching with ambiguity set side-information described in Section II. To elaborate, let S = {v S 1 , v S 2 , · · · , v S γn } be the seed vertices chosen randomly and uniformly from V. Then, the seeded graph matching scenario can be posed as follows: where P S γn (s 1 , s 2 , · · · , s γn ) = 1 ( n γn ) , s γn ∈ [1, n] γn , s i s j is the joint distribution imposed on the indices S 1 , S 2 , · · · , S γn of the seed vertices in S; and given the seed vertices S, we have Alternatively, the ambiguity set B is deterministically given by: The following theorem provides sufficient conditions for successful graph matching in the seeded scenario.

Proof. Please see A.
Remark 3. A number of prior works consider a variation of the seeded scenario, where instead of the seed set S, we are given a labelingσ 2 for which the labels of γn vertices are correct, but it is not known which vertices are correctly matched byσ 2 (e.g. witness based algorithms in [29]). It follows from the proof of Theorem 2 shows that, given the conditions in (4), the TM strategy is successful under this scenario as well.

C. Equiprobable Ambiguity Sets
In this scenario, it is assumed that for each vertex v s , s ∈ [1, n], an index i σ 2 (s) is in L s with probability p ∈ [0, 1] independently of all other ambiguity set elements: Note that in this case, for large n, each ambiguity set has roughly np elements chosen independently of all each other and independently of other ambiguity sets.
Theorem 3. Given sequences of edge distributions P (n) X,Y , n ∈ N, and p n ∈ [0, 1], n ∈ N, the TM strategy succeeds if: and max (x,y): where α n → 1 as n → ∞, and E α 2 is defined in Theorem 1.

Proof. Please see B.
Remark 4. Let p n = n −α , α > 0, so that each ambiguity set has roughly n 1−α elements. Then, if α = 0, the ambiguity sets are trivially equal to [1, n], and condition (5) recovers the one in [26] for matching graphs without ambiguity set side-information. On the other hand, if α > 1, then, with high probability each ambiguity set contains a single element, the correct labeling, and from (5) we see that the matching strategy is always successful regardless of edge statistics.

D. Randomly Generated Ambiguity Set Distribution
A generalization of the previous scenario is as follows: where f P (·) is an arbitrary probability distribution function (pdf) over the unit interval [0, 1]. In other words, for each vertex v s and index i σ 2 (s), the probability P(i ∈ L s ) = P i is a random value in the unit interval chosen according to f P (·) independent of all P j , j i. Note that this allows for a specific form of correlation among elements of B in contrast with the equiprobable case considered in Section IV-C. More precisely, under the model considered here, for each i ∈ [1, n], the variables B s,i , s ∈ [1, n] may be correlated with each other.
Theorem 4. Given sequences of edge distributions P (n) X,Y , and probability distribution functions f n,P , where P is a random variable defined on the unit interval, the TM strategy succeeds if: and max (x,y):P (n) X,Y (x,y) 0 | log X,Y (x,y) | + = o(log n), where α n → 1 as n → ∞, E α 2 is defined in Theorem 1, and E n,P (P) is the expected value of P with respect to f n,P .
Proof. Please see C.
Remark 5. The scenario in Section IV-C can be viewed as a limiting special case, where f P (·) corresponds to a truncated Gaussian(p, σ 2 ) over the unit interval and σ 2 is taken to be infinitesimally small.

E. Symmetrically Correlated Ambiguity Sets
In many applications, the ambiguity sets are symmetrically correlated such that if the label of vertex v s is in the ambiguity set L t for some s, t ∈ [1, n], then it is more likely than usual for the label of v t to be in L s , i.e. P(B s, j = 1|B t,i = 1) > P(B s, j = 1), where i = σ 2 (s) and j = σ 2 (t). For instance, in social network de-anoymization -where the ambiguity sets may be generated based on user fingerprints [24], [25], [30] -the ambiguity set for each user consists of the labels of users which have similar online behavior. If the label corresponding to user 's' is in the ambiguity set of user 't', then this implies that they have a similar online behavior, consequently, the label corresponding to user 't' is also likely to be in the ambiguity set of user 's'. To model this correlation, we consider the following stochastic ambiguity set model: where P U,V is a joint distribution on binary variables U and V, and we assume that P U (·) = P V (·).
The distribution P U,V can be viewed as a model parameter, where the value of P(U = V) controls how correlated the pairs of variables (B s,σ 2 (t) , B t,σ 2 (s) ), s, t ∈ [1, n] are with each other.

Remark 6.
Note that if we take P n,U,V such that U and V are independent of each other and P n,U (1) = P n,V (1) = p n , then we recover the conditions described in Equation (5).

V. Necessary Conditions for Successful Matching
To evaluate the necessary conditions for successful matching, let us assume that the ambiguity sets are generated randomly based on the distribution P B , and the labeling function (σ 1 , σ 2 ) are chosen randomly and uniformly among the set of all labeling pairs which are consistent with the ambiguity sets, i.e. labeling pairs for which B s,σ 2 (s) = 1, s ∈ [1, n]. Theorem 6. The following conditions are necessary for successful matching: • Seeded Matching: Let γ n ∈ [0, 1], n ∈ N: • Equiprobable Ambiguity Sets: Let p n = n −α , 0 < α < 1: • Randomly Generated Ambiguity Set Distribution: 2 log n n ≤ I(X; Y) − 2 log E n,P (P) n + o( log n n ) • Symmetrically Correlated Ambiguity Sets: Assume that θ n = max(P n,U,V (1, 1), P n,U (1)P n,V (1)) = n −ζ , 0 < ζ < 1, 2 log n n ≤ I(X; Y) − log θ n n + o( log n n ).
Proof Outline: The uncertainty in σ 2 is H(σ 2 |B) = E(log |Σ|), where Σ is the set of labelings which are consistent with the ambiguity sets. Consequently, using Fano's inequality, the information provided by (σ, g, g , B) regarding σ 2 , which is quantified as the mutual information I(σ 2 ; σ, g, g , B), must be larger than E(log |Σ|). The complete proof is provide in E.

VI. Conclusion
Matching of pair of correlated ER graphs in the presence of ambiguity set side-information was considered. Several stochastic models for ambiguity set generation were proposed. The TM strategy was proposed and sufficient conditions for its success were derived under several stochastic models on the ambiguity sets. Furthermore, converse results in the form of necessary conditions for successful matching on the edge statistics and ambiguity set statistics were derived.

Appendix A
Proof of Theorem 2 The proof builds upon the proof of Theorem 4 in [26]. For the correct labeling, the two UTs are jointly typical with probability approaching one as n → ∞: So, P( Σ = φ) → 0 as n → ∞ since the correct labeling is a member of the set Σ. We will show that the probability that a labeling in Σ labels n(1 − α n ) vertices incorrectly goes to 0 as n → ∞.
Define the following: where || · || 0 is the L 0 -norm. The set E is the set of all consistent labelings which match more than nα n vertices incorrectly. We show the following: Note that: where (a) follows from the union bound and the assumption of independence of edges and shortlist elements, (b) follows from the definition of Σ, and the fact that P(σ (s) ∈ L s , s ∈ [1, n]) = s∈[1,n] 1(σ 2 (s) = σ 2 (s)), in (c) we have used Theorem 1 and the fact that ||σ 2 − σ 2 || 0 = n − i so that Π σ 2 ,σ 2 has i(i−1) 2 fixed points, and in (d) we have denoted the number of derangement of sequences of length i by !i. Note that the right hand side in the last inequality approaches 0 as n → ∞ as long as: where we have defined α = i n . The last equation is satisfied by the theorem assumption for small enough and large enough n by noting that ζn(n−1) P X 1 ,X 2 (x 1 ,x 2 ) | + = o(log n) by assumption and n can be taken to go to infinity arbitrarily slowly for the probability of the typical set to approach one asymptotically.

Appendix B
Proof of Theorem 3 Following the arguments in the proof of Theorem 2, we have: where (a) follows from the union bound and the assumption of independence of edges and shortlist elements, (b) follows from the definition of Σ, and the fact that P(σ (s) ∈ L s , s ∈ [1, n]) = s∈[1,n] P(σ (s) ∈ L s ) = p n−i since ||σ 2 − σ 2 || 0 = n − i, in (c) we have used Theorem 1 and the fact that ||σ 2 − σ 2 || 0 = n − i so that Π σ 2 ,σ 2 has i(i−1) 2 fixed points, and in (d) we have denoted the number of derangement of sequences of length i by !i. Note that the right hand side in the last inequality approaches 0 as n → ∞ as long as: where we have defined α = i n . The last equation is satisfied by the theorem assumption for small enough and large enough n by noting that ζn(n−1) 2 = O( log n n 2 ) and δ = o(log n) = o( log n n ) since max (x 1 ,x 2 ):P (n) X 1 ,X 2 (x 1 ,x 2 ) 0 | log P X 1 (x 1 )P X 2 (x 2 ) P X 1 ,X 2 (x 1 ,x 2 ) | + = o(log n).

Appendix C
Proof of Theorem 4 Following the arguments in the proof of Theorem 2, we have: where (a) follows from the union bound and the assumption of independence of edges and shortlist elements, (b) follows from the definition of Σ, and the fact that P(σ (s) ∈ L s , s ∈ [1, n]) = s∈[1,n] P(σ (s) ∈ L s ) = E n−i (P) since for i j, P i and P j are independent and ||σ 2 − σ 2 || 0 = n − i, in (c) we have used Theorem 1 and the fact that ||σ 2 − σ 2 || 0 = n − i so that Π σ 2 ,σ 2 has i(i−1) 2 fixed points, and in (d) we have denoted the number of derangement of sequences of length i by !i. Note that the right hand side in the last inequality approaches 0 as n → ∞ as long as: where we have defined α = i n . The last equation is satisfied by the theorem assumption for small enough and large enough n by noting that ζn(n−1) 2 = O( log n n 2 ) and δ = o(log n) = o( log n n ) since max (x 1 ,x 2 ):P (n)

Appendix D Proof of Theorem 5
Following the arguments in the proof of Theorem 2, we have: where (a) follows from the union bound and the assumption of independence of edges and shortlist elements, (b) follows from the definition of Σ, and the fact that P(σ (s) ∈ L s , s ∈ [1, n]) = s∈[1,n] P(σ (s) ∈ L s ) ≤ max(P U,V (1, 1), P U (1)P V (1)) since if two indices are transposed by a labeling they would contribute P U,V (1, 1) and if they are not transposed, they would contribute P U (1)P V (1) and ||σ 2 −σ 2 || 0 = n−i, in (c) we have used Theorem 1 and the fact that ||σ 2 −σ 2 || 0 = n − i so that Π σ 2 ,σ 2 has i(i−1) 2 fixed points, and in (d) we have denoted the number of derangement of sequences of length i by !i. Note that the right hand side in the last inequality approaches 0 as n → ∞ as long as: where we have defined α = i n . The last equation is satisfied by the theorem assumption for small enough and large enough n by noting that ζn(n−1) 2 = O( log n n 2 ) and δ = o(log n) = o( log n n ) since max (x 1 ,x 2 ):P (n) The proof builds upon the arguments provided in the proof Theorem 9 in [26]. Let n ∈ N, and g and g be the adjacency matrices of the two graphs under a pre-defined labeling. Letσ be the output of the matching algorithm. Let 1 C be the indicator of the event that the matching algorithm mislabels at most n fraction of the vertices, and assume that the event 1 C = 1 has probability at least 1 − P e , where n , P e → 0 as n → ∞. Note thatσ is a function of σ , g, g , B. So: ≥ H(σ ,σ, 1 C |σ, g, g , B) − n n log n − P e n log n − 1 (d) ≥ H(σ |σ, g, g , B) − ( n + P e )n log n − 1, where in (a) we have used the chain rule of entropy, in (b) we have used the fact that 1 C is binary, in (c) we define the probability of mismatching more than n fraction of the vertices by P e , and (d) follows from the fact that entropy is non-negative. As a result, H(σ |σ, g, g , B) ≤ ( n + P e )n log n + 1 = o(n log n), where ( n + P e )n log n is o(n log n) since n , P e go to 0 as n → ∞. Consequently, where in (a) we have used the assumption that σ is chosen randomly and uniformly from the set of all labelings Σ b which are consistent with the ambiguity sets corresponding to b, and in (b) we have used the fact that , P e → 0 as n → ∞. We have: where (a) follows from σ , B | = g since the edges are assumed to be independent of the ambiguity sets as mentioned in Remark 1, (b) follows from the fact that σ , B | = g, g by Remark 1, (c) is true due to the non-negativity of the mutual inforamtion, (d) follows from σ, σ , B | = G, and (e) follows from the fact that the edges whose vertices have different labels are independent of each other given the labels, and that the edges with similarly labeled vertices are generated according to P X,Y . To complete the proof, we need to evaluate E(log Σ B ). We proceed by considering each of the stochastic models for ambiguity set generation separately: Seeded Graph Matching: In this case |Σ B | = (n(1 − γ n ))! irrespective of the choice of the seed set, where γ n is the fraction of the seed vertices. So, Combining (8) and (9) completes the proof in this case.
Equiprobable Ambiguity Sets: Fix > 0, and define E as the event that |Σ B | − E(|Σ B |) ≥ n E(|Σ B |). Furthermore, for a given labeling σ , let 1(σ ∈ Σ B ) be the event that σ is consistent with B so that |Σ B | = σ 1(σ ∈ Σ B ) and E(Σ B ) = σ P(σ ∈ Σ B ) = p n n!. Then, where in (a) we have used the Chebychev inequality. Note that n!k!p n+k ≤ n!p n n k=0 (pk) k , note that by assumption, p = n −α . So, where the last ineqluality holds for large enough n. So, from (10), we have: Consequently, P(E ) → 0 as n → ∞ for any > 0. We have: ≤ o(n log n) + log (p n n!(1 + n )) = n log n + n log p + o(n log n), where we have used the fact that E log |Σ B | E ≤ n!. This along with Equation (8) completes the proof for this case.