Embed graph in euclidean space

Want the minimum dimensional embedding.

Formulation as matrix factorization

(Shconberg). Take weighted adj matrix W. $W_{i,j}={\parallel x_i-x_j\parallel }^2=x_i^T{x}_i+x_j^T{x}_j-2x_i^T{x}_j$. Take $X=(x_i)$; Gram matrix $G=X^{T}X$ normalized to have $g_{i,i}=1$; then $W={2.11}^T-2G$. Then solve for G; then solve $G=X^{T}X$ 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=\sum _{(i,j)}(f(d_{i,j})-g(d_{i,j}))$. Minimize over $R^D$.

Clustering postulate and constraint

Require $d_{min}=w(1/C{)}^{\lambda }$ in attempting to place clusters $c_1,c_2$ with coupling C at distance w; so we want $\frac{1}{C}=(\frac{d}{w}{)}^{1/\lambda }$. Then, $U=f(d)-\frac{1}{C}g(d)$. Set derivative to 0, get constraint: $f^{\prime }(d)=(\frac{d}{w}{)}^{1/\lambda }{g}^{\prime }(d)$.

Box Cox family of energy fn

$U=\sum _{i,j}B{C}_{\mu +\frac{1}{\lambda }}(d_{i,j})+D_{i,j}^{1/\lambda }B{C}_{\mu }(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=\sum _{(i,j)\in E}f(d_{i,j})-\sum _{i,j}g(d_{i,j})$ then find minimum energy configuration in $R^D$.

Clustering postulate and constraint

Constrain range of choices for these forces with clustering postulates.

Take graph with 2 clusters $c_1,c_2$ with coupling $C=\frac{E(c_1,c_2)}{E(c_1)E(c_2)}$. Require $d_{min}={\frac{1}{C}}^{\lambda }$ be minimum energy configuration; $\lambda$ is clustering power.

Setting $U^{\prime }(c_1,c_2)\approx f^{\prime }(d_{min})-(1/C)g^{\prime }(d_{min})=0$, yields the clustering constraint: $f^{\prime }(d)=d^{1/\lambda }{g}^{\prime }(d)$.

Box Cox family of energy functions

Want to allow cases where $f(d)=d,g(d)=\log d$; so use Box-Cox transformations for f, g: $d>0:B{C}_p(d)=\frac{d^p-1}{p}$ if $p\ne 0$, else $\log d$; with $B{C}_p^{\prime }(d)=d^{p-1}$. So, use $g(d)=B{C}_{\mu }(d)$, get $f(d)=B{C}_{\mu +{\lambda }^{-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.