1/6/2022: Flexible HNC: A graph-based learning method that relies on pairwise similarities and its capability to handle label noise, Tor Nitayanont, University of California, Berkeley

The Hochbaum’s Normalized Cut method, or HNC, is a graph-based approach to the binary classification problem. In HNC, we define a graph of which vertices represent samples and arc weights represent pairwise similarities between samples. There are also additional arcs that connect the samples to the source node of the graph with parametric weights. The classification result can be obtained by solving for a minimum cut on this graph. In this work, we introduce a variant of the HNC method called Flexible HNC. This proposed method takes into account the possibility that the given labels of the labeled samples are inaccurate by introducing the concept of label confidence. The results of the experiments in our work show that the Flexible HNC method improves the classification performance, both when noisy labels are introduced to the datasets and when there is no added noise. In terms of noise detection, the method delivers promising results in comparison with other existing methods that handle noisy labels.

The presentation slides can be found here: Flexible_HNC