Initialize the start matrix for graph matching iteration.
Arguments
- start
A matrix, character, or function. A
nns-by-nnsmatrix, start method like "bari", "convex" or "rds", or a function to initialize the start matrix. If a function, it must have at least the arguments nns, ns, and softs_seeds.- nns
An integer. Number of non-seeds.
- ns
An integer. Number of seeds.
- soft_seeds
A vector, a matrix or a data frame indicating entries of the start matrix that will be initialized at 1 to indicate . See check_seeds.
- seeds
A vector, a matrix or a data frame. Indicating hard seeds. These are used for "convex" start but otherwise are ignored.
- ...
Arguments passed to other start functions. See details in Values section.
Value
init_start returns a nns-by-nns doubly stochastic matrix as the start
matrix in the graph matching iteration. If conduct a soft seeding graph matching, returns a
nns-by-nns doubly stochastic matrix with 1's corresponding to the soft seeds and values
at the other places are derived by different start method.
Details
When start is a character, there are five options.
"bari"initializes at the barycenter."rds_perm_bari"gives a random linear combination of barycenter and a random permutation matrix, (1-a) B + a P. The argumentgcontrols a with a being sampled asg * runif()."rds"gives a random doubly stochastic matrix. Users can specify a random deviates generator to thedistributionargument, and the default isrunif. A random matrix with iid entries fromdistributionand the the Sinkhorn algorithm is applied to produce the output."rds_from_sim"gives a random doubly stochastic matrix derived from similarity scores. One needs to input a similarity score matrix to thesimargument for this method. The procedure is the same as"rds"but before the Sinkhorn algorithm is applied, the entries of the random matrix are scaled bysim."convex"returns the doubly stochastic matrix from the last iteration of running the Frank- Wolfe algorithm with convex relaxation initialized at the barycenter. For this method, one needs to input two graphsAandB, as well asseedsif applicable.
Examples
ss <- matrix(c(5, 4, 4, 3), nrow = 2)
# initialize start matrix without soft seeds
init_start(start = "bari", nns = 5)
#> Sparse part
#> 5 x 5 sparse Matrix of class "dtCMatrix"
#>
#> [1,] . . . . .
#> [2,] . . . . .
#> [3,] . . . . .
#> [4,] . . . . .
#> [5,] . . . . .
#> plus left factor
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 1
#> [2,] 1
#> [3,] 1
#> [4,] 1
#> [5,] 1
#> times right factor transpose
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.2
#> [2,] 0.2
#> [3,] 0.2
#> [4,] 0.2
#> [5,] 0.2
init_start(start = "rds", nns = 3)
#> 3 x 3 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.3998906 0.2908486 0.3092609
#> [2,] 0.4605651 0.2378778 0.3015571
#> [3,] 0.1395443 0.4712736 0.3891820
init_start(start = "rds_perm_bari", nns = 5)
#> Sparse part
#> 5 x 5 sparse Matrix of class "dgCMatrix"
#>
#> [1,] . . 0.9526446 . .
#> [2,] . 0.9526446 . . .
#> [3,] . . . . 0.9526446
#> [4,] . . . 0.9526446 .
#> [5,] 0.9526446 . . . .
#> plus left factor
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.04735543
#> [2,] 0.04735543
#> [3,] 0.04735543
#> [4,] 0.04735543
#> [5,] 0.04735543
#> times right factor transpose
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.2
#> [2,] 0.2
#> [3,] 0.2
#> [4,] 0.2
#> [5,] 0.2
init_start(start = "rds_from_sim", nns = 3, sim = matrix(runif(9), 3))
#> 3 x 3 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.1258852 0.2815311 0.5925836
#> [2,] 0.4997791 0.2537421 0.2464788
#> [3,] 0.3743356 0.4647268 0.1609376
# initialize start matrix with soft seeds
init_start(start = "bari", nns = 5, ns = 1, soft_seeds = ss)
#> Sparse part
#> 5 x 5 sparse Matrix of class "dgCMatrix"
#>
#> [1,] . . . . .
#> [2,] . . . . .
#> [3,] . 1 . . .
#> [4,] . . 1 . .
#> [5,] . . . . .
#> plus left factor
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 1
#> [2,] 1
#> [3,] .
#> [4,] .
#> [5,] 1
#> times right factor transpose
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.3333333
#> [2,] .
#> [3,] .
#> [4,] 0.3333333
#> [5,] 0.3333333
init_start(start = "rds", nns = 5, soft_seeds = ss)
#> 5 x 5 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.1270208 0.4325422 . . 0.4404370
#> [2,] 0.3298594 0.3399201 . . 0.3302205
#> [3,] 0.5431198 0.2275377 . . 0.2293425
#> [4,] . . 1 . .
#> [5,] . . . 1 .
init_start(start = "rds_perm_bari", nns = 5, soft_seeds = ss)
#> Sparse part
#> 5 x 5 sparse Matrix of class "dgCMatrix"
#>
#> [1,] . 0.7932242 . . .
#> [2,] 0.7932242 . . . .
#> [3,] . . . . 0.7932242
#> [4,] . . 1 . .
#> [5,] . . . 1 .
#> plus left factor
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.2067758
#> [2,] 0.2067758
#> [3,] 0.2067758
#> [4,] .
#> [5,] .
#> times right factor transpose
#> 5 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.3333333
#> [2,] 0.3333333
#> [3,] .
#> [4,] .
#> [5,] 0.3333333
# \donttest{
# initialize start matrix for convex graph matching
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 <= 2
init_start(start = "convex", nns = 8, A = g1, B = g2, seeds = seeds)
#> Warning: Frank-Wolfe iterations reach the maximum iteration, convergence may not occur.
#> Sparse part
#> 6 x 6 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.09676176 0.14379966 0.1523425 . 0.04883263 0.1026742
#> [2,] 0.24396338 0.20208258 . 0.05848686 0.05944940 0.1239487
#> [3,] 0.02235561 . 0.2780643 0.20823372 0.16801942 0.1476918
#> [4,] 0.11436329 0.14354374 0.1819128 0.07153240 . 0.1498274
#> [5,] 0.25969662 0.20979364 . . 0.03174602 .
#> [6,] 0.07125127 0.02996218 0.1409496 . 0.39055273 0.2331440
#> plus left factor
#> 6 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.1341402
#> [2,] 0.1341402
#> [3,] 0.1341402
#> [4,] 0.1341402
#> [5,] 0.1341402
#> [6,] 0.1341402
#> times right factor transpose
#> 6 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.125
#> [2,] 0.125
#> [3,] 0.125
#> [4,] 0.125
#> [5,] 0.125
#> [6,] 0.125
# FW graph matching with incorrect seeds to start at convex start
init_start(start = "convex", nns = 8, ns = 2, soft_seeds = ss, A = g1, B = g2, seeds = seeds)
#> Warning: Frank-Wolfe iterations reach the maximum iteration, convergence may not occur.
#> Sparse part
#> 8 x 8 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.12198830 0.14607249 0.157678442 . 0.06429481 0.1127375
#> [2,] 0.23341457 0.23870508 0.020445592 0.07607659 0.07214470 0.1492380
#> [3,] 0.01891587 0.06202455 0.289295704 0.21472901 0.17454290 0.1572702
#> [4,] 0.12727185 0.16159995 0.176300298 0.08684848 . 0.1567839
#> [5,] 0.28696622 0.19860325 0.005618549 0.02201080 0.04880273 .
#> [6,] 0.10988048 0.03792362 0.149641871 . 0.39729826 0.2432312
#> [7,] 0.06295282 . 0.087544417 0.09073721 0.18089206 0.1187147
#> [8,] 0.03860990 0.15507107 0.051450576 0.44757335 . .
#>
#> [1,] 0.28661104 0.04859287
#> [2,] . 0.20997548
#> [3,] 0.02735853 0.05586327
#> [4,] 0.06314945 0.16602157
#> [5,] . 0.37597390
#> [6,] . .
#> [7,] 0.39713423 .
#> [8,] 0.16372220 0.08154836
#> plus left factor
#> 8 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 0.06202455
#> [2,] .
#> [3,] .
#> [4,] 0.06202455
#> [5,] 0.06202455
#> [6,] 0.06202455
#> [7,] 0.06202455
#> [8,] 0.06202455
#> times right factor transpose
#> 8 x 1 sparse Matrix of class "dgCMatrix"
#>
#> [1,] .
#> [2,] .
#> [3,] 0.1666667
#> [4,] 0.1666667
#> [5,] 0.1666667
#> [6,] 0.1666667
#> [7,] 0.1666667
#> [8,] 0.1666667
# }