  We undertake a study of the notion of a quantum graph over arbitrary
finite-dimensional $C^*$-algebras $B$ equipped with arbitrary faithful states.
Quantum graphs are realised principally as either certain operators on
$L^2(B)$, the quantum adjacency matrices, or as certain operator bimodules over
$B'$. We present a simple, purely algebraic approach to proving equivalence
between these settings, thus recovering existing results in the tracial state
setting. For non-tracial states, our approach naturally suggests a
generalisation of the operator bimodule definition, which takes account of
(some aspect of) the modular automorphism group of the state. Furthermore, we
show that each such ``non-tracial'' quantum graphs corresponds to a ``tracial''
quantum graph which satisfies an extra symmetry condition. We study
homomorphisms (or CP-morphisms) of quantum graphs arising from UCP maps, and
the closely related examples of quantum graphs constructed from UCP maps. We
show that these constructions satisfy automatic bimodule properties. We study
quantum automorphisms of quantum graphs, give a definition of what it means for
a compact quantum group to act on an operator bimodule, and prove an
equivalence between this definition, and the usual notion defined using a
quantum adjacency matrix. We strive to give a relatively self-contained,
elementary, account, in the hope this will be of use to other researchers in
the field.
