Probing New Physics with Multi-Messenger Astronomy