Compressed Sensing (CS) and Total Variation (TV)- based iterative image reconstruction algorithms have received increased attention recently. This is due to the ability of such methods to reconstruct from limited and noisy data. Local TV methods fail to preserve texture details and fine structures, which are tedious for the method to distinguish from noise. In many cases local methods also create additional artifacts due to over smoothing. Non-Local Total Variation (NLTV) has been increasingly used for medical imaging applications. However, it is not updated in every iteration of the algorithm, has a high computational complexity and depends on the scale of pairwise parameters. In this work we propose using Adaptive Graph- based TV in combination with CS (ACSGT). Similar to NLTV our proposed method goes beyond spatial similarity between different regions of an image being reconstructed by establishing a connection between similar regions in the image regardless of spatial distance. However, it is computationally much more efficient and scalable when compared to NLTV due to the use of approximate nearest neighbor search algorithm. Moreover, our method is adaptive, i.e, it involves updating the graph prior every iteration making the connection between similar regions stronger. Since TV is a special case of graph TV the proposed method can be seen as a generalization of CS and TV methods. We test our proposed algorithm by reconstructing a variety of different phantoms from limited and corrupted data and observe that we achieve a better result with ACSGT in every case.