Sample-dependent graph construction with application to dimensionality reduction

Bo Yang

doi:10.1016/j.neucom.2010.03.019

Return

Sample-dependent graph construction with application to dimensionality reduction

2010-12-01

PRE

Bo Yang

Songcan Chen (Songcan Chen) *

DOI：10.1016/j.neucom.2010.03.019

Original

Original request for help

Save

Abstract

En 中文

Graph construction plays a key role on learning algorithms based on graph Laplacian However the traditional graph construction approaches of epsilon-neighborhood and k-nearest-neighbor need to predefine the same neighbor parameter epsilon (or k) for all samples which usually suffers from the difficulty of parameter selection and generally fail to effectively fit intrinsic structures of data To mitigate these limitations to a certain extent in this paper we present a novel and sample dependent approach of graph construction and name the so-constructed graph as Sample-dependent Graph (SG) Specifically instead of predefining the same neighbor parameter for all sample, the SG depends on samples in question to determine neighbors of each sample and similarities between sample pairs As a result it not only avoids the intractability and high expense of neighbor parameter selection but also can more effectively fit the intrinsic structures of data Further in order to show the effectiveness of the SG we apply it to the dimensionality reduction based on graph embedding and incorporate it into the state-of-the-art off-the-shelf unsupervised locality preserving projection (LPP) to develop the sample-dependent LPP (SLPP) SLPP naturally inherits the merits of SG and maintains the attractive properties of the traditional LPP The experiments on the toy and benchmark (UCI face recognition object category and handwritten digits recognition) datasets show the effectiveness and feasibility of the SG and SLPP with promising results (C) 2010 Elsevier B V All rights reserved

Keywords:

Graph Laplacian

Graph construction

Dimensionality reduction (DR)

Graph embedding

Similarity neighborhood

Local neighbor

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.