Resistive-switching memories are alternative to Si-based ones, which face scaling and high power consumption issues. Tetrahedral amorphous carbon (ta-C) shows reversible, non-volatile resistive switching. Here we report polarity independent ta-C resistive memory devices with graphene-based electrodes. Our devices show ON/OFF resistance ratios$\sim$4x$105$, ten times higher than with metal electrodes, with no increase in switching power, and low power density$\sim$14$\mu$W/$\mu$m$^2$. We attribute this to a suppressed tunneling current due to the low density of states of graphene near the Dirac point, consistent with the current-voltage characteristics derived from a quantum point contact model. Our devices also have multiple resistive states. This allows storing more than one bit per cell. This can be exploited in a range of signal processing/computing-type operations, such as implementing logic, providing synaptic and neuron-like mimics, and performing analogue signal processing in non-von-Neumann architectures