A quantum graph is a triple that consists of a finite-dimensional C*-algebra, a state, and a quantum adjacency matrix. Analogous to the Cuntz-Krieger algebra of a classical graph, the quantum Cuntz-Krieger (QCK) algebra of a quantum graph is generated by the operator coefficients of matrix partial isometries. In this talk, we discuss connections between a QCK algebra and a Cuntz-Pimsner algebra associated to a quantum graph correspondence, and in the complete quantum graph case, connections between the QCK algebra and a particular Exel crossed product. We end by discussing the challenges in defining the “infinite path space" for a quantum graph.