Discovering Discrete Structures using SDP Relaxation: Hidden Integrality, Statistical Optimality and Semirandom Robustness