Using an autoencoder for anomaly detection on categorical data
In general an autoencoder should perform well, when it comes to detect fraud examples. Fraud examples should have in theory a much higher reconstruction error. 
When it comes to train the autoencoder on binary data, I agree with you that it can be quite challenging. I suggest to take a look at this blog:
https://blog.evjang.com/2016/11/tutorial-categorical-variational.html