When I think of graphs, I usually think of ones used for representing the alignment of biological sequences. Nodes have two sides, left and right, and both sides have their own neighbors. A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left.
Sometimes the graphs are path-centric. There is a fixed set of paths (or walks, if you prefer), and the graph is induced by them. The typical query is path extension: if you have already traversed >A<B>C>D, what are the possible left/right extensions according to the underlying paths matching the context. In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths.
Matrices don't feel like a good abstraction for graphs like this.
There are a number of representations for graphs like this, mostly differing by whether they are mutable or immutable, faster or more space-efficient, and graph-centric or path-centric. Generic algorithms use either node identifiers, which are consistent across graph representations, or opaque handles, which are representation-specific and often more efficient to use. Sometimes you select the representation according to the algorithm you want to use. Sometimes you select the algorithm according to the graph you already have (because conversions can be expensive). And sometimes you adjust the problem definition to reach something that can be computed efficiently with the available tools.