I think the computation graph is not broken, but the model architecture creates small gradients.
This dummy code produces valid gradients, which have a very small magnitude:
model = SentimentNet(10, 10, 10, 10, 10, 10, 'cpu')
x = torch.randint(0, 10, (10, 10))
hidden = model.init_hidden(10)
out = model(x, hidden)
out[0].mean().backward()
for name, param in model.named_parameters():
    print(name, param.grad)

print(model.embedding.weight.grad)

Also, note that nn.CrossEntropyLoss expects raw logits as the model output, not probabilities, so you should remove the softmax from your model (which might also increase the gradient magnitudes).