The proliferation of online social networks has helped in generating large amounts of graph data which has immense value for data analytics. Network operators, like Facebook, often share this data with researchers or third party organizations, which helps both the entities generate revenues and improve their services.  As this data is shared with third party organizations, the concern of user privacy becomes pertinent.  Hence, it becomes essential to balance utility and privacy while releasing such data.  Advances in graph matching and the resulting recent attacks on graph datasets paints a grim picture.  We discuss the feasibility of privacy preserving data analytics in anonymized networks and provide an answer to the question, “Does there exist a regime where the network cannot be deanonymized, yet data analytics can be performed?”