Enhanced graph-based dimensionality reduction with repulsion Laplaceans

E. Kokiopoulou, Yousef Saad

Research output: Contribution to journalArticle

29 Scopus citations


Graph-based methods for linear dimensionality reduction have recently attracted much attention and research efforts. The main goal of these methods is to preserve the properties of a graph representing the affinity between data points in local neighborhoods of the high-dimensional space. It has been observed that, in general, supervised graph-methods outperform their unsupervised peers in various classification tasks. Supervised graphs are typically constructed by allowing two nodes to be adjacent only if they are of the same class. However, such graphs are oblivious to the proximity of data from different classes. In this paper, we propose a novel methodology which builds on 'repulsion graphs', i.e., graphs that model undesirable proximity between points. The main idea is to repel points from different classes that are close by in the input high-dimensional space. The proposed methodology is generic and can be applied to any graph-based method for linear dimensionality reduction. We provide ample experimental evidence in the context of face recognition, which shows that the proposed methodology (i) offers significant performance improvement to various graph-based methods and (ii) outperforms existing solutions relying on repulsion forces.

Original languageEnglish (US)
Pages (from-to)2392-2402
Number of pages11
JournalPattern Recognition
Issue number11
StatePublished - Nov 1 2009


  • Face recognition
  • Graph Laplacean
  • Linear dimensionality reduction
  • Orthogonal projections
  • Supervised learning

Fingerprint Dive into the research topics of 'Enhanced graph-based dimensionality reduction with repulsion Laplaceans'. Together they form a unique fingerprint.

  • Cite this