Each shot should roll crit independently, with each shot also being a random AD value between a minimum % and maximum % of his total AD. You aren't aiming shotgun pellets, you spray a shit-load with each blast and hope it hurts. Another significant % damage reduction is applied based on distance, falling off drastically as distance is closed.
This would make him drastically weaker at a range, while keeping some of his up-close damage, incentivizing more risk to get that reward.
In addition, make it so his auto attacks function normally (1 projectile) with the same properties described above. **The additional pellets should be an on-attack effect so they do not benefit from lifesteal. **
Boom, Graves is fixed, and even gets to keep his hilariously broken E.