IRMA: Iterative Repair for graph MAtching

In the simplest form of graph matching (GM - often denoted also Graph Alignment), one is given two graphs $G_{1}$ and $G_{2}$ known to model the same data (i.e., there is an equivalence between the graphs vertices). For example, $G_{1}$ may be the friendship graph from the Facebook social network and $G_{2}$ the friendship graph from the Twitter social network for the same people. In both cases, the vertices are users and there is an edge between two vertices if the corresponding users are friends in the relevant social network. An assumption common to all GM algorithms is that a friend in one network has a higher than random probability of being a friend in the second network.

The goal of GM is to create a bijection $M:V_{1}\rightarrow V_{2}$, such that $M$ maps a vertex in $V_{1}$ to a vertex in $V_{2}$ if they represent the same real-world entities. In the example above, $M$ should connect the profiles in Facebook and Twitter of the same person. We note by $R$ the ground-truth, i.e., the set of all vertices pairs that represent the same entity in both graphs. Given a bijection $M$, if $M(v_{1})=v_{2}$, and $M(v_{3})=v_{4}$, and the edge $(v1,v3)\in E_{1}$, and $(v2,v4)\in E_{2}$, the common edge will be defined as a shared edge. The quality measure for the quality of $M$ is usually the number of shared edges.

Finding a full bijection is not always optimal, since some vertices may be absent from one of the two graphs. We thus look for a partial bijection: $M:\tilde{V_{1}}\subset V_{1}\rightarrow\tilde{V_{2}}\subset V_{2}$, such that the fraction of shared edges is maximal. A single edge bijection is obviously a simple solution to that. Thus, a trade-off between the number of shared edges and the fraction of mapped vertices is often required. Such a trade-off is obtained by adding constraints on the number of elements in $\tilde{V_{1}}$.

In the presence of limited initial information on the bijection, one can use seeded GM. In seeded GM, the input contains beyond $(G_{1},G_{2})$ also a small $seed\subset V_{1}\times V_{2}$, which is a group of vertices pairs known to represent the same real-world entities in $G_{1}$ and in $G_{2}$. A similar problem emerges when the vertices have additional information named labels or meta-data (malhotra2012studying(16), ; nunes2012resolving(20), ). For example, the users on Facebook and Twitter may have additional attributes, such as age, address, and user names. It is obvious that a user named “Bob Marley” in Facebook is much more likely to represent the same person as a user with the same name on Twitter than a user named “Will Smith”. Pairs of vertices with unique and similar attributes can be used as a seed. Even a very small seed can simplify the matching. Here, we focus on seeded GM based, with no labels over the vertices. We propose an iterative approach to seeded GM, which improves the accuracy of existing approaches. Specifically, we improve the ExpandWhenStuck algorithm (further denoted EWS) (EXPAND, ) using an Iterative Repair for graph MAtching (IRMA) algorithm. We show that the results are not only better than EWS, but also of all current seeded GM solvers.

We use precision and recall to evaluate the performance of algorithms: (i) Precision refers to the fraction of true matches in the set of matched vertices (i.e., pairs in $M$ that are in $R$) - $Precision=\dfrac{|M\cap R|}{|M|}$, and (ii) Recall is the size of the intersect of $M$ and $R$ out of the size of $R$ - $Recall=\dfrac{|M\cap R|}{|R|}$, where $R$ is the set of all pairs of vertices that represent the same entity in both of the graphs. To compare the performance of GM algorithms, we also report the F1–score. To approximate the quality of a solution during the run time, assuming no known ground truth - namely, given an input to the seeded-GM problem and two possible maps $M,M^{\prime}:V_{1}\rightarrow V_{2}$, we use $weight(M)$ as a score to compare the quality of their mapping - $Weight(M)=|\{(u,v)|(u,v)\in E_{1},(M(u),M(v))\in E_{2}\}|.$

For fully simulated graphs, we use the above sampling method over $G(n,p)$ Erdos-Renyi graphs (Erdos-Renyi, ), defined as a graph with $n$ vertices, where every edge of the possible $n\choose 2$ exists with a probability of $p$. It is common to mark two graphs created by sampling from an Erdos-Renyi graph as $G_{1},G_{2}=G(n,p,s)$ (pedarsani2011privacy, ). To test our algorithm on graphs that better represent real-world data, yet to control their level of similarity, we used sampling over the following real-world graphs (further denoted as graph 1, graph 2, and so on, according to their order here (Table 1)).

1. (1)

   Fb-pages-media - Data collected about Facebook pages (November 2017). (http://networkrepository.com/fb-pages-media.php).

2. (2)

   Soc-brightkite - Brightkite is a location-based social networking service provider where users shared their locations by checking-in. (http://networkrepository.com/soc-brightkite.php).

3. (3)

   Soc-epinions - Controversial Users Demand Local Trust Metrics: An Experimental Study on epinions.com Community (http://networkrepository.com/soc-epinions.php).

4. (4)

   Soc-gemsec-HU - The data was collected from the music streaming service Deezer (November 2017). These datasets represent friendship graphs of users from 3 European countries. (http://networkrepository.com/soc-gemsec-HU.php).

5. (5)

   Soc-sign-Slashdot081106 - Slashdot Zoo signed social network from November 6 2008. It is noteworthy that this graph was also used in (EXPAND, ) (http://networkrepository.com/soc-sign-Slashdot081106.php).

6. (6)

   Deezer_europe_edges - A social network of Deezer users which was collected from the public API in March 2020. (http://snap.stanford.edu/data/feather-deezer-social.html).

The EWS is greedy. At step $t$, it adds to $M$ the pair maximizing $score_{t}(p)$. If at time $t$ the algorithm chooses some wrong pair $[u^{\prime},v]$ that obeys $score_{t}([u^{\prime},v])>score_{t}([u,v])$ for the correct pair $[u,v]$, $[u,v]$ may receive many marks from neighbors later in the algorithm, such that $score_{\infty}([u^{\prime},v])<score_{\infty}([u,v])$ . We argue that such a scenario is highly likely, yet, $[u,v]$ will never get into $M$ as it conflicts with another pair already in $M-[u^{\prime},v]$.

We thus propose to use the scores at the end of the algorithm ($score_{\infty}([u^{\prime},v])<score_{\infty}([u,v])$) to improve the matching. We suggest an iterative improvement of the match, using the final score of the previous iteration. $mark_{i,t}(p)$ is defined as the number of marks gained by pair $p$ during the $i$-th iteration until time $t$; $score_{i,t}(p)$ is defined accordingly as

Based on these scores, one can establish:

and,

IRMA starts with the initialization of $M$ to be the seed set, then it performs a standard EWS iteration (See pseudo code for the Repairing-Iteration and IRMA in Figures 2 and 3, respectively). In the following iterations, at time $t$, while there is a candidate pair with $\bar{mar}k_{t}(p)>1$, IRMA adds to $M$ the pair $p$ maximizing $\bar{score}_{t}(p)$ and does not conflict $M$, and spread marks out of it.

IRMA stops the iterations when the mapping quality stops increasing. Formally, the $i$-th iteration starts by initializing $M=seed$, then, at time $t$, it adds to $M$ the candidate pair obeying: $p=argmax_{p}\{\bar{score}_{i,t}(p)\}$, and spread marks out of it - updating $mark_{i,t}$. The iteration ends when no candidate pair $p$, that does not conflicts $M$, satisfies: $\bar{mar}k_{i,t}(p)>1$.

Since in real-life scenario, we do not know the real mapping, we use $weight(M)$ to estimate the quality of the score at the current iteration (Section 5.1). We compute $weight(M_{i})$ $\forall i$ where $M_{i}$ is the matching at the end of the $i$-th iteration. Whenever $weight(M_{i})\leq weight(M_{i-1})$, IRMA stops and returns $M_{i-1}$. In practice, IRMA stops when $weight(M)\leq(1+\delta)*weight(M_{i-1})$, where $\delta$ was empirically set to $0.01$. Note that this does not ensure convergence of the mapping, only of its score.

Each IRMA iteration ends, when there are no pairs left with at least $2$ marks, that do not conflict $M$. This threshold is a trade-off between the precision and the recall. If one sets the threshold to a high value, $M$ will only contain pairs with high confidence, yet the percolation will stop early - leading to high precision but low recall. Similarly, setting the threshold to one will increase recall at the expense of precision.

However, in scale free distribution, many vertices have a low degree and mya never be reached. We thus suggest performing a “exploration iteration” with a threshold of $1$ mark, once IRMA converged. This leads to a drop in precision, but an increase in the recall. Then, one can run regular ”repairing” iterations again to gradually restore the precision. The idea is that while wrong pairs could not comply with the next iterations’ threshold of $2$ marks, correct pairs might lead to unexplored areas of the graphs. Such pairs gain marks by their newly revealed neighbors, a-posteriori justifying their insertion to $M$.

In order to develop a GPU version of IRMA, we propose a parallel version. The bottleneck of EWS is in spreading out marks from $[u,v]$, which costs $deg_{1}(u)*deg_{2}(v)$ updates to the queue of marks. Ideally, we would like to perform multiple mark spreading steps in parallel. However, this impossible since the pair chosen at time $t$ depends on the marks spread out in the previous step. Section 6.3 in (EXPAND, ) presents a paralleled version where the main loop has been split into epochs. This version of EWS starts by spreading out marks from the seed, then at each epoch the algorithm greedily takes all possible pairs from the queue one by one - without spreading any mark. When the queue is eventually empty, it simultaneously spread marks from all pairs selected at the current epoch, creating the queue to the next epoch. This method has the advantage of being extremely fast, allowing input graphs with millions of vertices, and has been argued not to fundamentally affect the performance of the algorithm.

We expand this logic to parallelize IRMA. The $i$-th iteration gets $queue_{i-1}$ as input and starts by greedily adding all possible pairs from the queue into $M_{i}$ one by one - without spreading any mark. Then, when the queue is empty, we simultaneously spread out marks from all pairs in $M_{i}$ creating $queue_{i}$. Iteration $i$ returns $M_{i}$ and $queue_{i}$.

For each graph (See Section 5.2), we use different graphs-overlap ($s$) values in the range of $[0.4-0.8]$, and various combinations of seed size, and $s$ value to test that our results are robust to the graph choice, the value of $s$ and the seed size.

When comparing the performance along with different seed sizes, we start with seed sizes of $25,200,50,150,25$ and $60$ respectively for graphs $1-6$. The first seed size is then multiplied by $2,4,8$ and $16$ (see figures 4, 5, 8). We report for each graph the precision, the recall or the F1 score for each realization. There is no division to training and test, nor parameter hypertuning, since there are no free parameters, and no ground truth used except for the seed in IRMA.

To examine the performance of seeded GM algorithms, one needs a pair of graphs, where at least a part of the vertices correspond to the same entities. Given $G=(V,E)$ and $s$, we generate $G_{1}=(V_{1},E_{1})$, and $G_{2}=(V_{2},E_{2})$ by twice randomly and independently removing edges $e\in E$ with a probability of $1-s$. We then remove vertices with no edges in $G_{1}$ and in $G_{2}$ separately. The edge overlap between $G_{1}$ and$G_{2}$ increases with $s$. We name $s$ the ‘graphs-overlap’.

IRMA can be applied to any percolation algorithm. We here use EWS (EXPAND, ) for each iteration, but any other algorithms can be used. We first tested the accuracy of EWS on a set of real-world graphs (section 5.2). We use each of those graphs to create two partially overlapping graphs by twice removing edges from the same graph. The fraction of edges from the original graph ($G$) maintained in each of the partially overlapping graphs $G_{1},G_{2}$ is denoted $s$. We use values of $s$ in the range of $[0.4,0.8]$.

We computed the precision, recall and F1-score of EWS over all the graphs with graphs overlap ($s$) value of $0.5,0.6,0.7$ as a function of seed size (Figure 4 a-c, respectively for graph 2, Other graphs are similar). Lower values of $s$, produced recall values of less than 0.3 even for a very large seed. All accuracy measures are highly sensitive to $s$. The reason is that a correct pair $[u,v]\in G_{1}\times G_{2}$, corresponding to vertex $w\in G$ with degree $d$, has an expected number of $s^{2}d$ common neighbors, which is approximately the number of marks it will get. In random $G(n,p)$ graphs, most vertices have similar degree (a normal distribution of degrees), and if $s^{2}*E(d)>2$, EWS typically works. More precisely, (EXPAND, ) present a simplified version to the EWS and show that the high accuracy in $G(n,p,s)$ requires an average degree of above $O(\dfrac{log(n)}{s^{2}})$. However, in scale free degree distributions, the vast majority of vertices obey $d<E(d)$. As such, low graphs-overlap values prevent most vertices from gaining enough marks.

The precision (and also recall and F1) is typically a monotonic non-decreasing function of the seed size, with no clear threshold (Figure. 4). The ratio between the precision and the recall as defined here are equal to the ratio between $|M|$ and $G$, i.e., the algorithm fails to percolate through the entire graph. Again, in scale free degree distributions, many low-degree vertices will never collect enough marks. As a result, $M$ often contains only part of the possible pairs to match.

The parallel version of EWS splits each iteration into epochs, in which it adds to $M$ every possible candidate pair without spreading out marks, and then spreads out marks simultaneously for the next epoch (Figure 7 for some graphs. Other graphs are similar). The parallel version requires a larger seed in order to achieve results similar to the original version. Together with the former findings, we can conclude that while EWS has an excellent accuracy in $G(n,p)$, it has two main limitations: A) Significantly lower performances on real-world graphs than in $G(N,p)$, and difficulty to handle graphs-overlap lower than $0.7$ in real-world networks. B) A large difference in real-world networks between the parallel and sequential versions.

We here propose that an iterative version of EWS can reduce these limitations.

IRMA is an iterative Graph Matching solver (section 5.3). We first run EWS, and then perform repairing iterations. In each iteration, IRMA uses the marks received at the end of the former iteration to build a new and better map (Figures 2 and 3). The intuition to keep adding recommendations to mapped pairs and use them on the next iteration is simple. Correct pairs share more common neighbors than the wrong ones in the average case, therefore correct pairs are more likely to gain more recommendations, even if they initially contradict another assignment.

$score_{t}(p)$ is defined by $marks_{t}(p)$ (the number of marks $p$ gained until time $t$) and uses the difference in the vertices degree to break ties (Eq. 1). While the often in real time a wrong pairing obtains a higher score than a real pairing, consistently, the score of wrong pairs at infinity (or the end of the analysis) is lower (Data not shown).

IRMA builds $M_{i}$ during the $i$-th iteration using

It then uses the advantage of each iteration over the previous one. We have shown the expected advantage of the first Repairing-Iteration over EWS, so $score_{2,\infty}(p)$ is more accurate than $score_{1,\infty}(p)$ on average. The proof above did not use any assumption on the way the initial marks were produced. Thus, the same logic should apply to all following iterations. Thus, $\bar{score}_{3,t}(p)$ is expected to be more accurate than $\bar{score}_{2,t}(p)$, and the same holds for all following iterations.

To test the improvement in accuracy, we computed the F1 score for all the real-world networks above (Figure 5). Sub-plots a and b consists of several runs of IRMA with different sizes of seeds, with a fixed graph and graphs-overlap ($s$). Each value is the average of 5 repetitions. The iterations are colored from green to blue. The lowest values are always of EWS, and the results keeps improving until they converge. Using the same experiment over other graphs, we generated sub-plot c, where each line is one IRMA run and it represents the difference in F1 (axis y) between following iterations as a function of the iteration (axis x). All positive values (as they all are) represent an improvement.

The first, most noticeable observation is that IRMA indeed gradually repairs the output map of EWS. In fact, the F1-score results are a monotonic non-decreasing function of the iterations. Moreover, the convergence is very rapid, and it rarely takes more than 5 or 6 iterations until convergences is obtained. Finally, the most interesting thing is that IRMA is less sensitive to initial seed. EWS often achieves lower performances on a larger seeds following fluctuations in the seed composition (see sub-figure a for such a case). Despite accepting EWS’s output as an initial map, IRMA exhibits a dependency on the problem properties (as the input graph and the graphs-overlap) rather than the output of EWS, and has much smoother F1 values. Importantly, the recall (and thus the F1 value) of IRMA, as presented here, does not rise to 1. Instead, it rises to the maximal number of vertices that can have at least two marks. However, it does so even for small seeds.

The Seeded GM problem is a variant of the Maximum Common Edges Subgraph (MCES) problem, with the twist that in seeded GM the target is to use the edge match as a tool to discover an a priori existing match and not the maximal sub-graph. Thus, in contrast with MCES, in seeded GM, one tries to maximize not only the recall, but also the precision. Hence, at some stage, IRMA does not add low-probability pairs.

In IRMA, we use a threshold of 2 marks to add a candidate pair into $M$. Since the Repairing-Iteration method filters wrong matched pairs, it is possible to allow the algorithm to make mistakes in some cases to find new correct pairs. We thus suggest to perform an exploration iteration with a threshold of 1 mark, after convergence, followed by regular repairing iterations to restore the precision.

Since repairing iterations filter out many wrong pairs, $weight(M_{i})$ is no longer a good condition for testing the convergence. We tested three possible break conditions to the second stage of IRMA: A) The quality of a bijection can be defined through $Weight(M_{i})/|M_{i}|$, where $|M_{i}|$ is the number of pairs in the set of matched pairs at the end of the $i$ iteration - $M_{i}$, and $Weight(M_{i})$ is the number of edges among members of $M_{i}$ shared by $G1$ and $G2$.B) As the target is to reduce $M$ down, we tested the condition $|M_{i}|\geq(1-\delta)*|M_{i-1}|$ to avoid many redundant iterations. C) Empirically after a few iterations there is no significant improvement from $M_{i}$ to $M_{i+1}$. We tested a constant number of iterations.

We computed the difference in accuracy along snapshots after the exploration iteration and compared it to these different measures (Figure 6). We used graphs 1,2,5 and 6 with seed size of 50, 400, 300 and 120 respectively and with all $s$ value in $[0.5,0.6,0.7,0.8]$ and fixed 6 repairing iterations. Sub-plots a and b represent the difference in precision as a function of the difference in $|weight(M_{i})|/|M_{i}|$ and $|M_{i}|$, respectively. A clear correlation between the measures can be observed, yet the variance around the origin (i.e., when IRMA converges) is relatively large. Sub-plot d indicates that the most reliable prediction to the convergence of precision is the number of iteration. We use that as the stopping criteria after the exploration iteration.

We used these additional standard IRMA iterations after the exploration iteration, and tested the precision, recall and F1-score along IRMA’s iterations on graphs 1-3 with seed size of 50, 400 and 800 respectively and with $s$ value of $0.6,0.5$ and $0.4$ respectively (Figure 7). The relation between the precision and the recall is the ratio between $R$ and $M$. Both recall and precision are monotonic non decreasing up to the exploration iteration, followed by a drop in precision together with the increase in recall in the exploration iteration, and the restoration of the precision in 3-4 iterations. Note that while precision is fully restored (and some times even improves), the recall stays higher than before the exploration iteration. In theory, one could repeat the process of doing exploration and repair iterations. However, in practice, the $F1$ gain of multiple cycles is very small.

Current state of the art seeded GM for scale free graphs include beyond EWS two main methods. Yu et al (yu2021power, ) proposed The D-hop method based on diffusing the seed more than one neighbor away (denoted as PLD). Chiasserini et al (chiasserini2016social, ) published the DDM de-anonymization algorithm (which is equivalent to seed GM) based on parallel graph partitioning. The two studies report different measures on different graphs.

To show that IRMA obtains better results than both algorithms, we repeated their analysis using the setting used in each algorithm, and the accuracy measure. The analysis was performed on the FaceBook and AS datasets (Figure 9). PLD uses a cutoff on the vertices degree that depends on the details of the algorithm, but in their setting is higher than 3. WE thus show our results on vertices of degree above 2 or above 3. In all cases, the precision of IRMA is higher on the same set of verices.

In the parallel version to EWS. The main idea is to split the algorithm into epochs such that marks are spread out only between the epochs, allowing parallel spreading. Using the same concept, we developed a parallel version to Repairing-Iteration in which $M$ is rebuilt based only on the marks of the former iteration. The parallel version of IRMA starts by running Parallel-EWS and then performs iterations of Parallel-Repairing-Iteration (see section 5.3).

When comparing (Figure. 8) the parallel-EWS, Parallel-IRMA and regular IRMA (both use exploring iteration). The parallel-IRMA has much better precision and recall than the Parallel-EWS. In sub-plot E, one can see an extreme case where Parallel-IRMA with a seed of 25 pairs is more accurate than Parallel-EWS with 400 pairs in the seed. The Parallel-IRMA and the standard IRMA have very similar recall and precision, making the parallel IRMA an excellent trade-off between run-time and performances. Note that the parallel IRMA has the same run time as the parallel EWS up to multiplication by a small constant, and is much faster, yet much more accurate than the non-parallel EWS.