Is it possible to implement a Neural Network using a graph data structure?
Many implementations you can find out in the web are done on matrices (MATLAB for instance) since it provides a compact notation. Haykin's textbook on neural networks takes this approach. Matrices also provide a simple translation to hardware design (FPGA, ASIC, etc.). They are also more often implemented on the FPU.

If you implement a neural network in an object oriented manner, you are effectively doing what your question asks: implementing a neural network on a graph. Your neurons are then objects that have relations with each others. There are a few books that take that approach. One I can think of is an undergrad level book by Renard called Réseaux de neurones (sorry, only in French).