Battery life estimation is critical for optimizing battery performance and guaranteeing minimal degradation for better efficiency and reliability of battery-powered systems. The existing methods to predict the Remaining Useful Life(RUL) of Lithium-ion Batteries (LiBs) neglect the relational dependencies of the battery parameters to model the nonlinear degradation trajectories. We present the Battery GraphNets framework that jointly learns to incorporate a discrete dependency graph structure between battery parameters to capture the complex interactions and the graph-learning algorithm to model the intrinsic battery degradation for RUL prognosis. The proposed method outperforms several popular methods by a significant margin on publicly available battery datasets and achieves SOTA performance. We report the ablation studies to support the efficacy of our approach.