In this paper, we present a graph representation that is based on the assumption that data live on a union of manifolds. Such a representation is based on sample proximities in reproducing kernel Hilbert spaces and is thus linear in the feature space and nonlinear in the original space. Moreover, it also expresses sample relationships under sparse and low-rank constraints,meaning that the resulting graph will have limited connectivity (sparseness) and that samples belonging to the same group will be likely to be connected together and not with those from other groups (low rankness). We present this graph representation as a general representation that can be then applied to any graph-based method. In the experiments, we consider the clustering of hyperspectral images and semi-supervised classification (one class and multiclass).