Graphs are ubiquitous for modeling relational data, appearing across social networks, biology, and chemistry. Measuring the similarity between graphs is central to tasks like graph classification and clustering, yet it poses significant computational challenges on large datasets. We introduce a matrix factorization framework for graph comparison. Viewing adjacency matrices as kernel matrices, we first define a pseudo-metric called MMFD that admits a simple closed-form solution without iterative optimization. We then generalize it to MFD, which more effectively exploits the factor structure of adjacency matrices. To handle large-scale clustering, we further develop a variant with linear time and space complexity in the number of graphs. Experiments on real-world datasets show that our methods substantially improve clustering performance and efficiency over existing approaches.