  In a Private Information Retrieval (PIR) protocol, a user can download a file
from a database without revealing the identity of the file to each individual
server. A PIR protocol is called $t$-private if the identity of the file
remains concealed even if $t$ of the servers collude. Graph based replication
is a simple technique, which is prevalent in both theory and practice, for
achieving erasure robustness in storage systems. In this technique each file is
replicated on two or more storage servers, giving rise to a (hyper-)graph
structure. In this paper we study private information retrieval protocols in
graph based replication systems. The main interest of this work is maximizing
the parameter $t$, and in particular, understanding the structure of the
colluding sets which emerge in a given graph. Our main contribution is a
$2$-replication scheme which guarantees perfect privacy from acyclic sets in
the graph, and guarantees partial-privacy in the presence of cycles.
Furthermore, by providing an upper bound, it is shown that the PIR rate of this
scheme is at most a factor of two from its optimal value for an important
family of graphs. Lastly, we extend our results to larger replication factors
and to graph-based coding, which is a similar technique with smaller storage
overhead and larger PIR rate.
