# Evaluation metric and Class Imbalance in Label Propagation

I'm using the MAD Label Propagation algorithm as described in the following paper "New Regularized Algorithms for Transductive Learning" by Partha Pratim Talukdar and Koby Crammer http://talukdar.net/papers/adsorption_ecml09.pdf

I have two labels, say A and B. Around 300k vertices and 1.4 million edges. I'm using it in the classification setting. However, I have a doubt regarding evaluation:
The labels A and B are mostly complimentary. Presence of one indicated absence of the other.

I'm holding back around 20% of the labels for evaluation But how should I evaluate the performance? If score(A) > score(B) for a node does it imply label A has a stronger association with the node? In the paper, it looks like the scores for each label are calculated independently of the scores for the other labels. There doesn't seem to be a notion of 'discrimination' between nodes, as is the case in traditional classifiers like Logistic Regression, Booted trees etc.
In that case does it even make sense to compare the scores for 2 labels for a given node?

Or should I instead take the top-K scored nodes (from the test set) for a each label and see what fraction of them are actually correct?

Moreover, my labels are imbalanced. Around 87% A and 13% B. How does this affect the scores? From the paper it seems the algorithm is heavily susceptible to class imbalance. Is there any way to overcome this?

PS: This is one of my first questions on this site. Please call out any mistakes or bad practices I may have used in farming/presenting the question

• By minimum keep the ratio of $A$ and $B$ labels the same in the training and test data (Stratified split). Some kind of resampling might be a good idea but I let others (who are more experienced) comment on that. – mmh Sep 26 '15 at 17:09

In 2-class label propagation methods, you can use the approach of class mass normalization to make the final prediction instead of maximum score. Please refer to section Incorporating Class Prior Knowledge Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions

• That seems to be a highly complex solution to a simple problem. If class imbalance matters you are using the wrong metrics. Use continuous information-preserving metrics. See for example this and this. – Frank Harrell Jun 16 at 12:48