Skip to content

Instantly share code, notes, and snippets.

@oir oir/hgfc.R
Last active Dec 15, 2015

Embed
What would you like to do?
Hierarchical Graph Factorization (Soft) Clustering. See: Yu, Kai, Shipeng Yu, and Volker Tresp. "Soft clustering on graphs." Advances in Neural Information Processing Systems 18 (2006): 1553.
# Ozan Irsoy, 2013
# Graph factorization.
# W: adjacency matrix
# m: # clusters (# vertices in U)
gfact = function(W, m) {
n = dim(W)[1]
H = matrix(runif(n*m,1,2),n,m)
L = diag(runif(m,1,2))
for (iter in 1:100) {
denom = H %*% L %*% t(H)
W_ = W/denom
W_[is.nan(W_)] = 1 # Let 0/0 = 1 because of divergence loss
H_ = H*(W_ %*% H %*% L)
H_ = scale(H_, center=F, scale=colSums(H_))
L_ = L*(t(H)%*%W_%*%H)
L_ = L_ / (sum(L_)/sum(W))
H = H_
L = L_
#diver = sum(W*log(W_)-W+denom, na.rm=T) # let 0*-Inf = 0
#print(diver)
}
return( list(B = H%*%L, L=L) )
}
# Hierarchical graph factorization clustering.
# W: adjacency matrix
# m: either the final # clusters, or an array of decreasing
# # clusters for each level
# list.Bs: boolean. if true, will list B's for each level and
# return.
hgfc = function(W, m=NULL, list.Bs=FALSE) {
n = dim(W)[1]
if (is.null(m)) {m=(n-1):1}
else if (length(m)==1) {m=(n-1):m} # this line needs to be modified
Bs = list()
for (l in 1:length(m)) {
B = gfact(W, m[l])$B
D = diag(rowSums(B))
# TODO: sometimes D has a 0 entry in the diagonal, which means
# there is an unused cluster. Fix!
W = t(B)%*%solve(D)%*%B
if (l==1) {B_ = B}
else {B_ = B_%*%solve(D)%*%B}
if (list.Bs) {Bs[[l]] = B}
}
if (list.Bs) {return (list(B=B_,Bs=Bs))}
else {return(B_)}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.