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

Incremental Low-Rank SDP Approach to Finding Graph Embeddings

Seppo Pulkkinen, Incremental Low-Rank SDP Approach to Finding Graph Embeddings. TUCS Technical Reports 1069, TUCS, 2013.

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. By utilizing an interior-point algorithm for solving the quadratic problems, we demonstrate by numerical experiments on MVU problems that our approach scales well to very large graphs.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tPulkkinen_Seppo13a,
  title = {Incremental Low-Rank SDP Approach to Finding Graph Embeddings},
  author = {Pulkkinen, Seppo},
  number = {1069},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2013},
  keywords = {graph embedding, dimensionality reduction, maximum variance unfolding, semidefinite programming, concave quadratic programming, interior-point methods},
  ISBN = {978-952-12-2859-9},
}

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

Edit publication