AlgorithmOptimization: Given a graph , with vertex set , and an integer , we attempt to solve the following non-convex problem: where , and . We use block-coordiate ascent, where at each step we maximize over the vector . Namely at each step, we draw uniformly at random and update to given by where denotes the set of neighbors of in . Projection: Once an (approximate, local) maximizer is obtained, we construct an embedding of vertices as follows.
We observe empirically that is often smaller than . The dimension of the embedding can be further reduced by only using the first dimensions (for some chosen by the user). How to choose the input parameters: The user must specify three parameters:
|