  We generalize a previous framework for designing utility-optimal
differentially private (DP) mechanisms via graphs, where datasets are vertices
in the graph and edges represent dataset neighborhood. The boundary set
contains datasets where an individual's response changes the binary-valued
query compared to its neighbors. Previous work was limited to the homogeneous
case where the privacy parameter $\varepsilon$ across all datasets was the same
and the mechanism at boundary datasets was identical. In our work, the
mechanism can take different distributions at the boundary and the privacy
parameter $\varepsilon$ is a function of neighboring datasets, which recovers
an earlier definition of personalized DP as special case. The problem is how to
extend the mechanism, which is only defined at the boundary set, to other
datasets in the graph in a computationally efficient and utility optimal
manner. Using the concept of strongest induced DP condition we solve this
problem efficiently in polynomial time (in the size of the graph).
