Embed graph in euclidean space

Want the minimum dimensional embedding.

Formulation as matrix factorization

(Shconberg). Take weighted adj matrix W. Wi,j=xixj2=xiTxi+xjTxj2xiTxj. Take X=(xi); Gram matrix G=XTX normalized to have gi,i=1; then W=2.11T2G. Then solve for G; then solve G=XTX for X with min number of columns.

Energy minimization techniques

See section on incomplete graphs with similarity measures for intro to notation.

Use energy fn: U=(i,j)(f(di,j)g(di,j)). Minimize over RD.

Clustering postulate and constraint

Require dmin=w(1/C)λ in attempting to place clusters c1,c2 with coupling C at distance w; so we want 1C=(dw)1/λ. Then, U=f(d)1Cg(d). Set derivative to 0, get constraint: f(d)=(dw)1/λg(d).

Box Cox family of energy fn

U=i,jBCμ+1λ(di,j)+Di,j1/λBCμ(d).

Encompasses energy fn used in multidimensional scaling.

Applications

If nodes represent sample-points, can infer the dimensionality of the sample space. Then can measure distance distance between arbitrary sample points. Eg: Maybe can sample some hyenas, observe their interactions, conclude that Hyenas are 5 dimensional.

Embedding Incomplete Graph G

Can view this as matrix completion problem; perhaps with additional constraints enforcing symmetry and traingle inequality for the distance metric.

Energy minimization techniques for G with similarity wts

Put attractive forces f() between verteces connected by edges, and repulsive forces g() between all vertex pairs, define energy: U=(i,j)Ef(di,j)i,jg(di,j) then find minimum energy configuration in RD.

Clustering postulate and constraint

Constrain range of choices for these forces with clustering postulates.

Take graph with 2 clusters c1,c2 with coupling C=E(c1,c2)E(c1)E(c2). Require dmin=1Cλ be minimum energy configuration; λ is clustering power.

Setting U(c1,c2)f(dmin)(1/C)g(dmin)=0, yields the clustering constraint: f(d)=d1/λg(d).

Box Cox family of energy functions

Want to allow cases where f(d)=d,g(d)=logd; so use Box-Cox transformations for f, g: d>0:BCp(d)=dp1p if p0, else logd; with BCp(d)=dp1. So, use g(d)=BCμ(d), get f(d)=BCμ+λ1.

Eigenmap

Take laplacian L of the graph G, and take its ev corresponding to bottom few ew, which are functions over V which are smooth over E.

G with distance wts D

This can be reduced to a complete graph: calculate distance for all pairs by finding shortest paths.