  Summarizing a large graph by grouping the nodes into clusters is a standard
technique for studying the given network. Traditionally, the order of the
discovered groups does not matter. However, there are applications where, for
example, given a directed graph, we would like to find coherent groups while
minimizing the backward cross edges. More formally, in this paper, we study a
problem where we are given a directed network and are asked to partition the
graph into a sequence of coherent groups while attempting to conform to the
cross edges. We assume that nodes in the network have features, and we measure
the group coherence by comparing these features. Furthermore, we incorporate
the cross edges by penalizing the forward cross edges and backward cross edges
with different weights. If the weights are set to 0, then the problem is
equivalent to clustering. However, if we penalize the backward edges
significantly more, then the order of discovered groups matters, and we can
view our problem as a generalization of a classic segmentation problem. To
solve the algorithm we consider a common iterative approach where we solve the
groups given the centroids, and then find the centroids given the groups. We
show that - unlike in clustering - the first subproblem is NP-hard. However, we
show that if the underlying graph is a tree we can solve the subproblem with
dynamic programming. In addition, if the number of groups is 2, we can solve
the subproblem with a minimum cut. For the more general case, we propose a
heuristic where we optimize each pair of groups separately while keeping the
remaining groups intact. We also propose a greedy search where nodes are moved
between the groups while optimizing the overall loss. We demonstrate with our
experiments that the algorithms are practical and yield interpretable results.
