• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Finding Graph Embeddings by Incremental Low-Rank Semidefinite Programming

Seppo Pulkkinen, Finding Graph Embeddings by Incremental Low-Rank Semidefinite Programming. Optimization Methods and Software 30(5), 1050–1076, 2015.

http://dx.doi.org/10.1080/10556788.2015.1014553

Abstract:

Finding a low-dimensional embedding of a graph of n nodes in R^d is an essential task in many applications. For instance, maximum variance unfolding (MVU) is a well-known dimensionality reduction method that involves solving this problem. The standard approach is to formulate the embedding problem as a semidefinite program (SDP). However, the SDP approach does not scale well to large graphs. In this paper, we exploit the fact that many graphs have an intrinsically low dimension, and thus the optimal matrix resulting from the solution of the SDP has a low rank. This observation leads to a quadratic reformulation of the SDP that has far fewer variables, but on the other hand, is a difficult convex maximization problem. We propose an approach for obtaining a solution to the SDP by solving a sequence of smaller quadratic problems with increasing dimension. Utilizing an augmented Lagrangian and an interior-point method for solving the quadratic problems, we demonstrate with numerical experiments on MVU problems that the proposed approach scales well to very large graphs.

BibTeX entry:

@ARTICLE{jPulkkinen_Seppo15b,
  title = {Finding Graph Embeddings by Incremental Low-Rank Semidefinite Programming},
  author = {Pulkkinen, Seppo},
  journal = {Optimization Methods and Software},
  volume = {30},
  number = {5},
  pages = {1050–1076},
  year = {2015},
  ISSN = {1055-6788},
}

Belongs to TUCS Research Unit(s): Turku Optimization Group (TOpGroup)

Publication Forum rating of this publication: level 1

Edit publication