We study the variable selection problem in survival analysis to identify the most important factors affecting survival time. Our method incorporates prior knowledge of mutual correlations among variables, represented through a graph. We utilize the Cox proportional hazard model with a graph-based regularizer for variable selection. We present a computationally efficient algorithm developed to solve the graph regularized maximum likelihood problem by establishing connections with the group lasso, and provide theoretical guarantees about the recovery error and asymptotic distribution of the proposed estimators. The improved performance of the proposed approach compared with existing methods are demonstrated in both synthetic and real organ transplantation datasets.