In this paper, we present TeethGNN, a novel 3D tooth segmentation method based on graph neural networks (GNNs). Given a mesh-represented 3D dental model in non-euclidean domain, our method outputs accurate and fine-grained separation of each individual tooth robust to scanning noise, foreign matters (e.g., bubbles, dental accessories, etc.), and even severe malocclusion. Unlike previous CNN-based methods that bypass handling non-euclidean mesh data by reshaping hand-crafted geometric features into regular grids, we explore the non-uniform and irregular structure of mesh itself in its dual space and exploit graph neural networks for effective geometric feature learning. To address the crowded teeth issues and incomplete segmentation that commonly exist in previous methods, we design a two-branch network, one of which predicts a segmentation label for each facet while the other regresses each facet an offset away from its tooth centroid. Clustering are later conducted on offset-shifted locations, enabling both the separation of adjoining teeth and the adjustment of incompletely segmented teeth. Exploiting GNN for directly processing mesh data frees us from extracting hand-crafted feature, and largely speeds up the inference procedure. Extensive experiments have shown that our method achieves the new state-of-the-art results for teeth segmentation and outperforms previous methods both quantitatively and qualitatively.