Combine K-nearest neighbor with categorical embedding
If I understand well, you label encode categorical variables and fed them to a neural network. If this is the case, you can try the following:

add the numerical variables
create and train an autoencoder
use the encoder part to map input to a vector space and perform k-nearest neighbor to it.

You can read the second method described in https://towardsdatascience.com/detecting-credit-card-fraud-with-autoencoders-in-python-98391cace8a3 It uses a dataset with numerical variables only, but since you label encode categorical variables it applies in your case too.