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.