Android malware constantly evolves so as to evade detection. The entire malware population to be non-stationary. Contrary to this fact, most of the prior works on machine learning based android malware detection have assumed that the distribution of the observed malware characteristics (i.e., features) does not change over time. The problem of malware population drift and propose a novel online learning based framework to detect malware, named CASANDRA (Context-aware, Adaptive and Scalable Android malware detector). In order to perform accurate detection, a novel graph kernel that facilitates capturing apps security-sensitive behaviors along with their context information from dependence graphs is proposed. Besides being accurate and scalable, CASANDRA has specific advantages: first, being adaptive to the evolution in malware features over time; second, explaining the significant features that led to an apps classification as being malicious or benign.