A link-analysis-based discriminant analysis for exploring partially labeled graphs

This letter investigates a link-analysis variant of discriminant analysis for projecting nodes of a (partially) labeled graph in a low-dimensional subspace and extracting discriminant node features. Basically, it corresponds to a kernel discriminant analysis computed from a kernel on a graph together with a class betweenness measure. As for standard discriminant analysis, the projected nodes are maximally separated with respect to the ratio of between-class inertia on total inertia – the distances being computed according to the kernel. The visualization of various graphs shows that the resulting display conveys useful information. Moreover, semi-supervised classification experiments indicate that the discriminant analysis indeed extracts relevant node features that are able to classify unlabeled nodes with competing performance.

► A link-analysis variant of the discriminant analysis is investigated.
► Nodes of a partially labeled graph are projected in a low-dimensional subspace.
► These nodes are maximally separated according to the between-class inertia ratio.
► The new low-dimensional subspace preserves local consistency for classification.
► A low-dimensional visualization of graph nodes is developed.