Graph data is a kind of data composed of nodes and edges, which models the entities as the nodes, nodes may be connected by edges, and edge indicates a relationship between entities. By analyzing and mining these data, a lot of valuable information can be revealed. Meanwhile, it also brings risks of privacy information disclosure for every entity in the graph. To address this issue, a graph data publishing method is proposed based on the negative database (NDB). This method transforms the structural characteristics of the graph data into the encoding format of a negative database. Based on this, a generation method for perturbed graphs (NDB-Graph) is designed. Since NDB is a privacy-preserving technique that does not explicitly store the original data and is difficult to reverse, the published graph data ensures the security of the original graph data. Besides, due to the high efficiency of graph neural network in relation feature processing in graph data, it is widely used in various task processing modeling on graph data, such as recommendation system. a graph neural network recommendation system is also proposed based on NDB technology to protect the privacy of graph data for each user. Compared with publishing method PBCN, the proposed method outperforms it in most cases in experiments on the Karate and Facebook datasets. For example, on Facebook datasets, the smallest L1-error of degree distribution is only 6, which is about 2.6% lower than the PBCN method under the same privacy level, the worst case is about 1 400, which is about 46.5% lower than the PBCN method under the same privacy level. The experiment of collaborative filtering based on LightGCN also demonstrates that the proposed privacy protection method has high precision.