Identifying startups with the highest potential for success is a complex task, necessitating the examination of various information sources, including firm demographics, management team composition, and financial performance. The effectiveness of existing methodologies, such as feature-based and network-topological approaches, is limited for predicting highpotential startups. In response, we propose a novel Venture Graph Neural Network (VenGNN) model, leveraging Heterogeneous Information Networks (HIN) and Graph Neural Networks (GNN) techniques to address the prediction problem. Specifically, we construct a Heterogeneous Venture Information Network (HVIN) using raw business data and deem the prediction as a node classification task. Our model integrates theory-guided semantic meta-paths, firm demographics, sampling-based self-attention, and centrality encoding to overcome certain constraints of existing GNNs. Our experimental analysis reveals that VenGNN outperforms state-of-the-art models by 15-20% across a wide range of performance metrics. Our study also includes a comprehensive interpretation analysis to provide investors with an essential understanding for better decision-making.