out-of-sample embedding for adjacency.spectral.embedding

[youngser]

Gabor, Could you please add this Minh's "oos" function to igraph? Note that he used the latest git clone (0.7.0-pre). For the earlier version than this, you have to uncomment the line of ## Xhat.insample <- Xhat.insample$V %*% diag(sqrt(Xhat.insample$D))

Thanks,

• Minh and Youngser

library("igraph")

## The code for oos currently works with matrices and not igraph graph object
## The input is a matrix A12 of size nxm where
## n = # of in-sample points
## m = # of out-of-sample points
## and a matrix Xhat of size nxd containing
## the embedding of the in-sample points.
## The output is a matrix of size mxd containing the
## embedding of the out-of-sample points.

## The oos algorithm itself is nothing more than a least square regression, i.e.,
## Yhat = \argmin \| A12 - Xhat Y^{\top} \|_{F}
oos <- function(A12, Xhat){
    Yhat <- t(solve(t(Xhat)%*%Xhat, t(Xhat) %*% A12))
    return(Yhat)
}

## The following is an example where
## (1) we generate a dot product graph G
## (2) we embed a subset of the vertices of G via adjacency spectral embedding
## (3) we out-of-sample embed the remaining vertices using the
##     connectivity between the in-sample vertices and the out-of-sample vertices
##
oos.ase.example <- function(n,m){
    X <- matrix(runif(2*(n+m), max = 1/sqrt(2)), nrow = 2)
    g <- dot.product.game(X)
    g.insample <- induced.subgraph(g, 1:n)
    Xhat.insample <- adjacency.spectral.embedding(g.insample, 2)
    ## Xhat.insample <- Xhat.insample$V %*% diag(sqrt(Xhat.insample$D))

    ## The oos code works on matrices so for now we have to explicitly
    ## convert the graph to an adjacency matrix
    A <- get.adjacency(g)
    A.insample.oos <- A[1:n,(n+1):(n+m)]

    ## Call the oos function
    Xhat.oos <- oos(A.insample.oos, Xhat.insample)

    return(Xhat.oos)
}

[gaborcsardi]

Why don't you add it yourself?

[itmfl]

We can. It is just that there is a slight issue of the discrepancy between the representations in igraph and the current representation as matrices in our oos code, so we don't know how you want to handle it.

However, I will just use the implicit representation that a rectangular "submatrix" of a graph is a rectangular matrix in the function definition then.