graph_match_convex | R Documentation |
Match two given graphs, returns a list of graph matching
results, including matching correspondence vector of G_2
with respect
to G_1
, doubly stochastic matrix and permutation matrix.
graph_match_convex(
A,
B,
seeds = NULL,
similarity = NULL,
start = "bari",
max_iter = 100,
tol = 1e-05,
lap_method = NULL
)
graph_match_indefinite(
A,
B,
seeds = NULL,
similarity = NULL,
start = "bari",
max_iter = 20,
lap_method = NULL
)
graph_match_PATH(
A,
B,
seeds = NULL,
similarity = NULL,
epsilon = 1,
tol = 1e-05,
max_iter = 20,
lap_method = NULL
)
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 |
similarity |
A matrix. An |
start |
A matrix or a character. Any |
max_iter |
A number. Maximum number of replacing matches. |
tol |
A number. Tolerance of edge disagreements. |
lap_method |
Choice for lap method. One of "lapjv", "lapmod", or "clue". |
epsilon |
A small number |
graph_match_indefinite
, graph_match_convex
and graph_match_PATH
return an object of class "graphMatch
" which is a list containing the following
components:
matching correspondence in G_1
matching correspondence in G_2
the doubly stochastic matrix from the last iteration with which one can extract more than one matching candidates
number of iterations until convergence or reaches the max_iter
Maximum number of replacing matches
Choice for solving the LAP
a vector of logicals indicating if the corresponding vertex is a seed
Y. Aflalo and A. Bronstein and R. Kimmel (2014), On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, pages 2942-2947.
V. Lyzinski and D. E. Fishkind and M. Fiori and J. T. Vogelstein and C. E. Priebe and G. Sapiro (2016), Graph Matching: Relax at Your Own Risk. IEEE TPAMI, pages 60-73.
V. Lyzinski and D. E. Fishkind and C. E. Priebe (2014), Seeded Graph Matching for Correlated Erdos-Renyi Graphs.J. Mach. Learn. Res., pages 3513-3540.
M. Zaslavskiy, F. Bach and J. Vert (2009), A Path following algorithm for the graph matching problem. IEEE Trans Pattern Anal Mach Intell, pages 2227-2242.
cgnp_pair <- sample_correlated_gnp_pair(n = 10, corr = 0.9, p = 0.5)
g1 <- cgnp_pair$graph1
g2 <- cgnp_pair$graph2
# match G_1 & G_2 with no seeds
gm(g1, g2, method = "convex", max_iter = 10)
seeds <- 1:10 <= 3
gm(g1, g2, seeds, method = "convex", max_iter = 10)
# match G_1 & G_2 with some known node pairs as seeds
cgnp_pair <- sample_correlated_gnp_pair(n = 10, corr = 0.3, p = 0.5)
g1 <- cgnp_pair$graph1
g2 <- cgnp_pair$graph2
seeds <- 1:10 <= 3
GM_bari <- gm(g1, g2, seeds, method = "indefinite", start = "bari")
GM_bari
GM_bari[!GM_bari$seeds] # matching correspondence for non-seeds
summary(GM_bari, g1, g2, true_label = 1:10)
# match G_1 & G_2 with some incorrect seeds
hard_seeds <- matrix(c(4,6,5,4),2)
seeds <- rbind(as.matrix(check_seeds(seeds, nv = 10)$seeds),hard_seeds)
GM_badseed <- gm(g1, g2, seeds, method = "indefinite")
GM_badseed[] # get the corresponding permutation matrix
GM_badseed %*% g2 # permute the second graph according to match result: PBP^T
GM_badseed$soft # doubly stochastic matrix from the last step of Frank-Wolfe iterations
GM_badseed$iter # number of iterations
GM_badseed$max_iter # preset maximum number of iterations: 20
# match two multi-layer graphs
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]])
match_multi_layer <- gm(A, B, seeds = 1:10, method = "indefinite", start = "bari", max_iter = 20)
summary(match_multi_layer, A, B)
# match G_1 & G_2 using PATH algorithm
gm(g1, g2, method = "PATH")
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.