  It is very common to face classification problems where the number of
available labeled samples is small compared to their dimension. These
conditions are likely to cause underdetermined settings, with high risk of
overfitting. To improve the generalization ability of trained classifiers,
common solutions include using priors about the data distribution. Among many
options, data structure priors, often represented through graphs, are
increasingly popular in the field. In this paper, we introduce a generic model
where observed class signals are supposed to be deteriorated with two sources
of noise, one independent of the underlying graph structure and isotropic, and
the other colored by a known graph operator. Under this model, we derive an
optimal methodology to classify such signals. Interestingly, this methodology
includes a single parameter, making it particularly suitable for cases where
available data is scarce. Using various real datasets, we showcase the ability
of the proposed model to be implemented in real world scenarios, resulting in
increased generalization accuracy compared to popular alternatives.
