Want the minimum dimensional embedding.
Formulation as matrix factorization
(Shconberg). Take weighted adj matrix W.
Energy minimization techniques
See section on incomplete graphs with similarity measures for intro to notation.
Use energy fn:
Clustering postulate and constraint
Require
Box Cox family of energy fn
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:
Clustering postulate and constraint
Constrain range of choices for these forces with clustering postulates.
Take graph with 2 clusters
Setting
Box Cox family of energy functions
Want to allow cases where
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.