Large-scale graph-oriented computations are becoming central to our modern life, ranging from social networks, through disease outbreak paths, to transportation routes. For instance, in prosperous cities where economy and population are continuously accelerating (e.g., Doha), infrastructures typically struggle to keep pace with logistics, traffic jam, and supply chain management, among others. Graph-based algorithms for road, bus and train networks can be effectively crafted and greatly serve in mitigating these and similar problems. While it is usually simple to devise algorithms to solve such real-world problems, it is much harder to engineer efficient deployments of them, especially at large scale. To fill this critical gap, academia and industry developed various graph analytics engines such as GraphLab and Google’s Pregel, which execute graph algorithms as vertex-programs on clusters of machines (e.g., the cloud). Nonetheless, efficient processing of Big Graphs is still quite challenging due to the incessant increase in the scale of the problem (e.g., currently billions of vertices and trillions of edges), poor locality, and high communication and storage (i.e., I/O) overhead, to mention a few. In this proposal, we address some of these major challenges and suggest two main directions to effectively tackle them. Specifically, we first show that no current Distributed File System (DFS) utilized by graph analytics engines is graph-aware in nature. This results in high I/O overhead and degraded performance. To overcome that, we propose a novel graph-oriented DFS that suits all current graph analytics engines and expedite their performance. Second, we demonstrate that the I/O overhead imposed by some common graph analytics engines is dependent on the number of cluster machines and the application message sizes. Consequently, this incurs incompetent scalability as cluster and messages sizes are expanded. We promote a highly-scalable solution that is independent of the cluster and message sizes. We plan to test our suggested schemes on private and public clouds, using various real-world applications.