This article presents a new graph-learning technique to accurately infer the graph structure of COVID-19 data, helping to reveal the correlation of pandemic dynamics among different countries and identify influential countries for pandemic response analysis. The new technique estimates the graph Laplacian of the COVID-19 data by first deriving analytically its precise eigenvectors, also known as graph Fourier transform (GFT) basis. Given the eigenvectors, the eigenvalues of the graph Laplacian are readily estimated using convex optimization. With the graph Laplacian, we analyze the confirmed cases of different COVID-19 variants among European countries based on centrality measures and identify a different set of the most influential and representative countries from the current techniques. The accuracy of the new method is validated by repurposing part of COVID-19 data to be the test data and gauging the capability of the method to recover missing test data, showing 33.3% better in root mean squared error (RMSE) and 11.11% better in correlation of determination than existing techniques. The set of identified influential countries by the method is anticipated to be meaningful and contribute to the study of COVID-19 spread.