Attributed Graphs are most commonly represented as an adjacency matrix or a list where nodes are considered first class citizens. There are many graph queries such as neighborhood, shortest path, page rank, connected component that operate on these matrix and list structures on nodes. The attributes of the node/edge can also be stored apart from the connections.
Another representation of the graph is an incidence matrix where the incident edges of a node are recorded in a matrix. I understand they represent exactly the same information as previous node-based methods.
My question is, are there any graph queries/workloads/algorithms that can benefit from the incidence matrix structure rather than using the node-based structures i.e. favoring an edge-based structure? When exactly are the incidence matrix used?
I can think of only one case where incidence matrix may prove faster:
Finding the degree of a node or finding adjacent nodes is an operation with complexity O(V) when using an adjacency matrix and O(E) when using an incidence matrix.
Usually E>V, but this may not be the case if the graph has many 0-degree nodes. Since finding adjacent nodes is a basic operation, many algorithms may prove to be faster on such graphs.