  Counting the number of homomorphisms of a pattern graph H in a large input
graph G is a fundamental problem in computer science. There are myriad
applications of this problem in databases, graph algorithms, and network
science. Often, we need more than just the total count. Especially in large
network analysis, we wish to compute, for each vertex v of G, the number of
H-homomorphisms that v participates in. This problem is referred to as
homomorphism orbit counting, as it relates to the orbits of vertices of H under
its automorphisms.
  Given the need for fast algorithms for this problem, we study when
near-linear time algorithms are possible. A natural restriction is to assume
that the input graph G has bounded degeneracy, a commonly observed property in
modern massive networks. Can we characterize the patterns H for which
homomorphism orbit counting can be done in linear time?
  We discover a dichotomy theorem that resolves this problem. For pattern H,
let l be the length of the longest induced path between any two vertices of the
same orbit (under the automorphisms of H). If l <= 5, then H-homomorphism orbit
counting can be done in linear time for bounded degeneracy graphs. If l > 5,
then (assuming fine-grained complexity conjectures) there is no near-linear
time algorithm for this problem. We build on existing work on dichotomy
theorems for counting the total H-homomorphism count. Somewhat surprisingly,
there exist (and we characterize) patterns H for which the total homomorphism
count can be computed in linear time, but the corresponding orbit counting
problem cannot be done in near-linear time.
