  Graph neural networks (GNNs) play a key role in learning representations from
graph-structured data and are demonstrated to be useful in many applications.
However, the GNN training pipeline has been shown to be vulnerable to node
feature leakage and edge extraction attacks. This paper investigates a scenario
where an attacker aims to recover private edge information from a trained GNN
model. Previous studies have employed differential privacy (DP) to add noise
directly to the adjacency matrix or a compact graph representation. The added
perturbations cause the graph structure to be substantially morphed, reducing
the model utility. We propose a new privacy-preserving GNN training algorithm,
Eclipse, that maintains good model utility while providing strong privacy
protection on edges. Eclipse is based on two key observations. First, adjacency
matrices in graph structures exhibit low-rank behavior. Thus, Eclipse trains
GNNs with a low-rank format of the graph via singular values decomposition
(SVD), rather than the original graph. Using the low-rank format, Eclipse
preserves the primary graph topology and removes the remaining residual edges.
Eclipse adds noise to the low-rank singular values instead of the entire graph,
thereby preserving the graph privacy while still maintaining enough of the
graph structure to maintain model utility. We theoretically show Eclipse
provide formal DP guarantee on edges. Experiments on benchmark graph datasets
show that Eclipse achieves significantly better privacy-utility tradeoff
compared to existing privacy-preserving GNN training methods. In particular,
under strong privacy constraints ($\epsilon$ < 4), Eclipse shows significant
gains in the model utility by up to 46%. We further demonstrate that Eclipse
also has better resilience against common edge attacks (e.g., LPA), lowering
the attack AUC by up to 5% compared to other state-of-the-art baselines.
