Outlier detection plays a significant role in various real world applications\nsuch as intrusion, malfunction, and fraud detection. Traditionally, outlier\ndetection techniques are applied to find outliers in the context of the whole\ndataset. However, this practice neglects contextual outliers, that are not\noutliers in the whole dataset but in some specific neighborhoods. Contextual\noutliers are particularly important in data exploration and targeted anomaly\nexplanation and diagnosis. In these scenarios, the data owner computes the\nfollowing information: i) The attributes that contribute to the abnormality of\nan outlier (metric), ii) Contextual description of the outlier's neighborhoods\n(context), and iii) The utility score of the context, e.g. its strength in\nshowing the outlier's significance, or in relation to a particular explanation\nfor the outlier. However, revealing the outlier's context leaks information\nabout the other individuals in the population as well, violating their privacy.\nWe address the issue of population privacy violations in this paper, and\npropose a solution for the two main challenges. In this setting, the data owner\nis required to release a valid context for the queried record, i.e. a context\nin which the record is an outlier. Hence, the first major challenge is that the\nprivacy technique must preserve the validity of the context for each record. We\npropose techniques to protect the privacy of individuals through a relaxed\nnotion of differential privacy to satisfy this requirement. The second major\nchallenge is applying the proposed techniques efficiently, as they impose\nintensive computation to the base algorithm. To overcome this challenge, we\npropose a graph structure to map the contexts to, and introduce differentially\nprivate graph search algorithms as efficient solutions for the computation\nproblem caused by differential privacy techniques.\n