4 R functions and usage
The R package iGraphMatch offers versatile options for graph matching and subsequent analysis.
Here we describe the usage of the package including sampling random correlated graph pairs, graph matching, and evaluating matching results.
4.2 Graph matching methods
The graph matching methods share the same basic syntax:
gm(A, B, seeds = NULL, similarity = NULL, method = "indefinite",
***algorithm parameters***)| Parameter | Type | Description | Functions |
|---|---|---|---|
start |
Matrix or character | Initialization of the start matrix for iterations. | FW, convex |
lap_method |
Character | Method for solving linear assignment problem. | FW, convex, PATH, IsoRank |
max_iter |
Number | Maximum number of iterations. | FW, convex, PATH, IsoRank |
tol |
Number | Tolerance of edge disagreements. | FW, convex, PATH |
r |
Number | Threshold of neighboring pair scores. | percolation |
ExpandWhenStuck |
Boolean | TRUE if performs ExpandWhenStuck algorithm. |
percolation |
The first two arguments for graph matching algorithms represent two networks which can be matrices, igraph objects, or two lists of either form in the case of multi-layer matching.
The seeds argument contains prior information on the known partial correspondence of two graphs.
It can be a vector of logicals or indices if the seed pairs have the same indices in both graphs.
In general, the seeds argument takes a matrix or a data frame as input with two columns indicating the indices of seeds in the two graphs respectively.
The similarity parameter is for a matrix of similarity scores between the two vertex sets, with larger scores indicating higher similarity.
Notably, one should be careful with the different scales of the graph topological structure and the vertex similarity information in order to properly address the relative importance of each part of the information.
The method argument specifies a graph matching algorithm to use, and one can choose from “indefinite” (default), “convex”, “PATH”, “percolation”, “IsoRank”, “Umeyama”, or a self-defined graph matching function which enables users to test out their own algorithms while remaining compatible with the package.
If method is a function, it should take at least two networks, seeds and similarity scores as arguments.
Users can also include additional arguments if applicable.
The self-defined graph matching function should return an object of the “graphMatch” class with matching correspondence, sizes of two input graphs, and other matching details.
As an illustrative example, graph_match_rand defines a new graph matching function which matches by randomly permuting the vertex label of the second graph using a random seed rand_seed.
We then apply this self-defined GM method to matching the correlated graphs sampled earlier with a specified random seed:
graph_match_rand <- function(A, B, seeds = NULL,
similarity = NULL, rand_seed){
totv1 <- nrow(A[[1]])
totv2 <- nrow(B[[1]])
nv <- max(totv1, totv2)
set.seed(rand_seed)
corr <- data.frame(corr_A = 1:nv,
corr_B = c(1:nv)[sample(nv)])
graphMatch(
corr = corr,
nnodes = c(totv1, totv2),
detail = list(
rand_seed = rand_seed
)
)
}
match_rand <- gm(cgnp_g1, cgnp_g2,
method = graph_match_rand, rand_seed = 123)Other arguments vary for different graph matching algorithms with an overview given in Table \(\ref{tab:gm-alg}\).
The start argument for the FW methodology with “indefinite” and “convex” relaxations takes any \(nns\text{-by-}nns\) matrix or an initialization method including “bari”, “rds” or “convex”.
These represent initializing the iterations at a specific matrix, the barycenter, a random doubly stochastic matrix, or the doubly stochastic solution from “convex” method on the same graphs, respectively.
Moreover, sometimes we have access to side information on partial correspondence with uncertainty.
If we still treat such prior information as hard seeds and pass them through the seeds argument for “indefinite” and “convex” methods, incorrect information can yield unsatisfactory matching results.
Instead, we provide the option of soft seeding by incorporating the noisy partial correspondence into the initialization of the start matrix.
The core function used for initializing the start matrix with versatile options is the init_start function.
Suppose the first two pairs of nodes are hard seeds and another pair of incorrect seed \((3,4)\) is soft seeds:
We generate a start matrix incorporating soft seeds initialized at the barycenter:
## [,1] [,2] [,3]
## [1,] 0.0 1 0.0
## [2,] 0.5 0 0.5
## [3,] 0.5 0 0.5An alternative is to generate a start matrix that is a random doubly stochastic matrix incorporating soft seeds as follow
set.seed(1)
as.matrix(start_rds <- init_start(start = "rds", nns = 3,
ns = 2, soft_seeds = soft_seeds))## [,1] [,2] [,3]
## [1,] 0.00 1 0.00
## [2,] 0.52 0 0.48
## [3,] 0.48 0 0.52Then we can initialize the Frank-Wolfe iterations at any of the start matrix by specifying the start parameter.
When there are no soft seeds, we no longer need to initialize the start matrix by using init_start first. Instead we can directly assign an initialization method to the start argument in the gm function:
Below use solution from the convex relaxation as the initialization for the indefinite relaxation.
set.seed(123)
match_convex <- gm(cgnp_g1, cgnp_g2, seeds = hard_seeds,
method = "indefinite", start = "convex")Now let’s match the sampled pair of graphs from the stochastic block model by using Percolation algorithm. Apart from the common arguments for all the graph matching algorithms, Percolation has another argument representing the minimum number of matched neighbors required for matching a new qualified vertex pair. Here we adopt the default value which is 2. Also, at least one of similarity scores and seeds is required for Percolation algorithm to kick off. Let’s utilize the same set of hard seeds and assume there is no available prior information on similarity scores.
sbm_g1 <- sbm_pair$graph1
sbm_g2 <- sbm_pair$graph2
match_perco <- gm(sbm_g1, sbm_g1, seeds = hard_seeds,
method = "percolation", r = 2)
match_perco## gm(A = sbm_g1, B = sbm_g1, seeds = hard_seeds, method = "percolation",
## r = 2)
##
## Match (5 x 5):
## corr_A corr_B
## 1 1 1
## 2 2 2Without enough prior information on partial correspondence, Percolation couldn’t find any qualifying matches. Suppose in addition to the current pair of sampled graphs, the above sampled correlated homogeneous and heterogeneous graphs are different layers of connectivity for the same set of vertices. We can then match the nonseed vertices based on the topological information in all of these three graph layers. To be consistent, let’s still use the Percolation algorithm with threshold equal to 2 and the same set of seeds.
matrix_lA <- list(sbm_g1, ieg_pair$graph1, cgnp_g1)
matrix_lB <- list(sbm_g2, ieg_pair$graph2, cgnp_g2)
match_perco_list <- gm(A = matrix_lA, B = matrix_lB, seeds = hard_seeds,
method = "percolation", r = 2)
match_perco_list## gm(A = matrix_lA, B = matrix_lB, seeds = hard_seeds, method = "percolation",
## r = 2)
##
## Match (5 x 5):
## corr_A corr_B
## 1 1 1
## 2 2 2
## 3 3 3
## 4 4 4
## 5 5 5With the same amount of available prior information, we are now able to match all the nodes correctly.
Finally, we will give an example of matching multi-layers of graphs using IsoRank algorithm. Unlike the other algorithm, similarity scores are required for IsoRank algorithm. Without further information, we adopt the barycenter as the similarity matrix here.
set.seed(1)
sim <- as.matrix(init_start(start = "bari", nns = 5,
soft_seeds = hard_seeds))
match_IsoRank <- gm(A = matrix_lA, B = matrix_lB,
seeds = hard_seeds, similarity = sim,
method = "IsoRank", lap_method = "LAP")Graph matching functions return an object of class “graphMatch” which contains the details of the matching results, including a list of the matching correspondence, a call to the graph matching function and dimensions of the original two graphs.
## corr_A corr_B
## 1 1 1
## 2 2 2
## 3 3 5
## 4 4 4
## 5 5 3## gm(A = cgnp_g1, B = cgnp_g2, seeds = hard_seeds, method = "indefinite",
## start = "convex")## [1] 5 5Additionally, “graphMatch” also returns a list of matching details corresponding to the specified method.
Table \(\ref{tab:gm-value}\) provides an overview of returned values for different graph matching methods.
With the seeds information, one can obtain a node mapping for non-seeds accordingly
## corr_A corr_B
## 3 3 5
## 4 4 4
## 5 5 3| Parameter | Description | Functions |
|---|---|---|
seeds |
A vector of logicals indicating if the corresponding vertex is a seed | All the functions |
soft |
The functional similarity score matrix with which one can extract more than one matching candidates | FW, convex, PATH, IsoRank, Umeyama |
lap_method |
Choice for solving the LAP. | FW, convex, Umeyama, IsoRank |
iter |
Number of iterations until convergence or reaches the max_iter. | FW, convex, PATH |
max_iter |
Maximum number of replacing matches. | FW, convex |
match_order |
The order of vertices getting matched. | percolation, IsoRank |
The “graphMatch” class object can also be flexibly used as a matrix. In addition to the returned list of matching correspondence, one can obtain the corresponding permutation matrix in the sparse form.
## 5 x 5 sparse Matrix of class "dgCMatrix"
##
## [1,] 1 . . . .
## [2,] . 1 . . .
## [3,] . . . . 1
## [4,] . . . 1 .
## [5,] . . 1 . .Notably, multiplicity is applicable to the “graphMatch” object directly without converting to the permutation matrix. This enables obtaining the permuted second graph, that is \(PBP^T\) simply by
## IGRAPH 8187cd4 UN-- 5 5 -- Erdos-Renyi (gnp) graph
## + attr: name_1 (g/c), name_2 (g/c), type_1 (g/c), type_2 (g/c), loops_1
## | (g/l), loops_2 (g/l), p_1 (g/n), p_2 (g/n), name (g/c), type (g/c),
## | loops (g/l), p (g/n), name (v/n)
## + edges from 8187cd4 (vertex names):
## [1] 5--3 2--5 2--3 1--5 1--24.3 Evaluation of goodness of matching
Along with the graph matching methodology, iGraphMatch has many capabilities for evaluating and visualizing the matching performance.
After matching two graphs, the function summary can be used to get a summary of the overall matching result in terms of commonly used measures including the number of matches, the number of correct matches, common edges, missing edges, extra edges and the objective function value.
The edge matching information is stored in a data frame named edge_match_info.
Note that summary outputs the number of correct matches only when the true correspondence is known by specifying the true_label argument with a vector indicating the true correspondence in the second graph.
Applying the summary function on the matching result match_convex with true_label = 1:5, indicating the true correspondence is the identity that provides these summaries.
## Call: gm(A = cgnp_g1, B = cgnp_g2, seeds = hard_seeds, method = "indefinite",
## start = "convex")
##
## # Matches: 3
## # True Matches: 1, # Seeds: 2, # Vertices: 5, 5
##
## common_edges 4.0
## missing_edges 0.0
## extra_edges 1.0
## fnorm 1.4Applying the summary function to a multi-layer graph matching result returns edge statistics for each layer.
## Call: gm(A = matrix_lA, B = matrix_lB, seeds = hard_seeds, similarity = sim,
## method = "IsoRank", lap_method = "LAP")
##
## # Matches: 3, # Seeds: 2, # Vertices: 5, 5
## layer 1 2 3
## common_edges 2.0 6.0 4.0
## missing_edges 0.0 1.0 0.0
## extra_edges 1.0 0.0 1.0
## fnorm 1.4 1.4 1.4In realistic scenarios, the true correspondence is not available.
As introduced in section \(\ref{sec:background}\), the user can use vertex level statistics to evaluate match performance.
The best_matches function evaluates a vertex-level metric and returns a sorted data.frame of the vertex-matches with the metrics.
The arguments are the two networks, a specific measure to use, the number of top-ranked vertex-matches to output, and the matching correspondence in the second graph if applicable.
As an example here, we apply best_matches to rank the matches from above with the true underlying alignment
best_matches(cgnp_g1, cgnp_g2, match = match_convex,
measure = "row_perm_stat", num = 3,
true_label = 1:igraph::vcount(cgnp_g1))## A_best B_best measure_value precision
## 1 4 4 -1.4 1.00
## 2 3 5 -1.2 0.50
## 3 5 3 -1.2 0.33Note, best_matches uses seed information from the match parameter and only outputs non-seed matches.
Without the true correspondence, true_label would take the default value and the output data frame only contains the first three columns.
To visualize the matches of smaller graphs, the function plot displays edge discrepancies of the two matched graphs by an adjacency matrix or a ball-and-stick plot, depending on the input format of two graphs.
Figure 4.1: Match visualizations. Grey, blue, and red colors indicate common edges, missing edges present only in the first network, and extra edges present only in the second network, respectively.
The plots for visualizing matching performance of match_convex are shown in Figure 4.1.
Grey edges and pixels indicate common edges, red ones indicate edges only in the second graph.
If they were present, blue pixels and edges represent missing edges that only exist in the first graph.
The corresponding linetypes are solid, short dash, and long dash.
