A fundamental problem of graph databases is subgraph isomorphism query (a.k.a subgraph query): given a query graph $Q$ and a graph database, it retrieves the graphs $G$ s from the database that contain $Q$ . Due to the cost of managing massive data coupled with the computational hardness of subgraph isomorphism testing, outsourcing the computations to a third-party provider is an appealing alternative. However, confidentiality has been a critical attribute of quality of service ( QoS ) in query services. To the best of our knowledge, subgraph query services with tunable preservation of privacy of structural information have never been addressed. In this paper, we present the first work on structure-preserving $\mathsf {subIso}$ ( $\mathsf {SPsubIso}$ ). A crucial step of our work is to transform $\mathsf {subIso}$ —the seminal subgraph isomorphism algorithm (the Ullmann’s algorithm)—into a series of matrix operations. We propose a novel cyclic group based encryption ( $\mathsf {CGBE}$ ) method for private matrix operations. We propose a protocol that involves the query client and static indexes to optimize $\mathsf {SPsubIso}$ . We prove that the structural information of both $Q$ and $G$ are preserved under $\mathsf {CGBE}$ and analyze the privacy preservation in the presence of the optimizations. Our extensive experiments on both real and synthetic datasets verify that $\mathsf {SPsubIso}$ is efficient and the optimizations are effective.