Graph Matching Methods — gm • iGraphMatch

gm is used to match a pair of given graphs, with specifications of the adjacency matrices of for a pair of graphs, possible prior knowledge, and a graph matching method.

Usage

gm(A, B, seeds = NULL, similarity = NULL, method = "indefinite", ...)

Arguments

A: A matrix, igraph object, or list of either.
B: A matrix, igraph object, or list of either.
seeds: A vector of integers or logicals, a matrix or a data frame. If the seed pairs have the same indices in both graphs then seeds can be a vector. If not, seeds must be a matrix or a data frame, with the first column being the indices of \(G_1\) and the second column being the corresponding indices of \(G_2\).
similarity: A matrix. An n-by-n matrix containing vertex similarities. Mandatory for the "IsoRank" method.
method: Choice for graph matching methods. One of "indefinite", "convex", "PATH", "percolation", "IsoRank", "Umeyama", or a user-defined graph matching function. Please check Details and Examples sections for instructions on how to define your own function.
...: Arguments passed to graph matching methods. Please refer to Details section for more information.

Value

gm returns an object of class "graphMatch". See graphMatch-class and links therein for details on the graphMatch class.

Please also refer to the help page for each implemented method, i.e. "indefinite", "convex", "PATH", "percolation", "IsoRank", and "Umeyama"

for details on the corresponding returned list.

Details

If method is a function, it should take two matrices or igraph objects, seeds and similarity scores as arguments for minimum. Additionally, it can also take other arguments if needed. The self-defined function should return a graphMatch class object with matching correspondence, sizes of two input graphs, matching formula, and other algorithm hyperparameter details.

The method argument can also take one of the implemented algorithms, including "indefinite", "convex", "PATH", "percolation", "IsoRank", and "Umeyama". In this case, one can pass additional arguments to the gm function according to the specified method. For a detailed list of additional arguments for each one of the implemented method, please click on the corresponding method name for its help page.

Most graph matching functions include as list elements additional details about the match. Call names() on a graphMatch object to see the available details. As an example, PATH, IsoRank, Umeyama, Indefinite, and Convex each include soft, which is the matrix found by the algorithm prior to projection onto the set of permutation matrices. Similarly, PATH, Indefinite, and Convex return iter, the number of iterations, and IsoRank (with greedy LAP) and Percolation return match_order, the order that the node-pairs were added to the match.

Examples

# match G_1 & G_2 with some known node pairs as seeds
set.seed(123)
cgnp_pair <- sample_correlated_gnp_pair(n = 10, corr =  0.5, p =  0.5)
g1 <- cgnp_pair$graph1
g2 <- cgnp_pair$graph2
seeds <- 1:10 <= 4

m_rds <- gm(g1, g2, seeds, method = "indefinite", start = "rds", max_iter = 20)
summary(m_rds, g1, g2, true_label = 1:10)
#> Call: gm(A = g1, B = g2, seeds = seeds, method = "indefinite", start = "rds", 
#>     max_iter = 20)
#> 
#> # Matches: 6
#> # True Matches:  6, # Seeds:  4, # Vertices:  10, 10
#>                         
#>   common_edges 16.000000
#>  missing_edges  4.000000
#>    extra_edges  5.000000
#>          fnorm  4.242641


# match two multi-layer graphs
set.seed(123)
gp_list <- replicate(3, sample_correlated_gnp_pair(20, .3, .5), simplify = FALSE)
A <- lapply(gp_list, function(gp)gp[[1]])
B <- lapply(gp_list, function(gp)gp[[2]])

m_perco <- gm(A, B, seeds, method = "percolation", ExpandWhenStuck = FALSE)
summary(m_perco, A, B)
#> Call: gm(A = A, B = B, seeds = seeds, method = "percolation", ExpandWhenStuck = FALSE)
#> 
#> # Matches: 16, # Seeds:  4, # Vertices:  20, 20
#>          layer        1        2        3
#>   common_edges 76.00000 61.00000 57.00000
#>  missing_edges 27.00000 41.00000 29.00000
#>    extra_edges 38.00000 30.00000 37.00000
#>          fnorm 11.40175 11.91638 11.48913

sim <- as.matrix(init_start(start = "bari", nns = 20, soft_seeds = 1:5))
m_Iso <- gm(A, B, similarity = sim, method = "IsoRank", lap_method = "greedy")
summary(m_Iso, A, B)
#> Call: gm(A = A, B = B, similarity = sim, method = "IsoRank", lap_method = "greedy")
#> 
#> # Matches: 20, # Seeds:  0, # Vertices:  20, 20
#>          layer        1        2  3
#>   common_edges 73.00000 56.00000 54
#>  missing_edges 30.00000 46.00000 32
#>    extra_edges 41.00000 35.00000 40
#>          fnorm 11.91638 12.72792 12

# customized graph matching algorithm
graph_match_rand <- function(A, B, seeds = NULL, similarity = NULL, rand_seed){
  nm <- min(nrow(A), nrow(B))
  set.seed(rand_seed)
  m <- data.frame(sample(nrow(A), nm), corr_B = sample(nrow(B), nm))
  m <- as.graphMatch(m)
  m$rand_seed <- rand_seed
  m
}

m_self <- gm(g1, g2, method = graph_match_rand, rand_seed = 123)
summary(m_self, g1, g2)
#> Call: gm(A = g1, B = g2, method = graph_match_rand, rand_seed = 123)
#> 
#> # Matches: 10, # Vertices:  10, 10
#>                         
#>   common_edges 10.000000
#>  missing_edges 10.000000
#>    extra_edges 11.000000
#>          fnorm  6.480741