- What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?
Structural innovation is anything added that changes the topology of the network. So a structural innovation is any added connection or added node. I don't want to get too much into the implementation, but something similar to a dictionary global variable will work. When adding a connection (or node) between two nodes, we check if a connection (or node) has ever been placed between these two nodes before. If it has then we have stored an innovation number for what this connection (or node) is identical and we set its innovation number to that. We identify each node by its number.
- Is there a reason for storing the type of a node (input, hidden, output)?
Yes, there are many structural innovations that we do not want to happen. An innovation between two input node or an innovation between two output nodes are two examples of structural innovations we don't want.
- In the original paper, only connections have an innovation number, but in other sources, nodes do as well. Is this necessary for crossover? (This has already been asked here.)
Although I am unsure if it is explicitly stated, it is implied that nodes have an identifying number. You can see this in Figure 2 and 3 of the paper where each node is labeled with a number.
- How could I limit the mutation functions to not add backpropagation connections?
By backpropagation connections I assume you mean recurrent connections (correct me if I am wrong). You can prevent recurrent connections in many ways, but one way is to maintain a partially ordered set. When adding a connection between two nodes you check to see the order of those two nodes in the partially ordered set. The one that comes first will be the node from which the connection starts, while the second will be the node at which the connection ends.
As a note, we can prevent recurrent connections but often times allowing them provides opportunities to find a better solution (as @PaulG comments)