Logic for Re-Labeling Nodes in a Directed Acyclic Graph

Question

We are currently working at the intersection of metaheuristics and machine learning.

As part of the scheduling problem that we are trying to solve, we have a project network (directed acylic graph) that captures the precedence relations between different activities that are to be scheduled.

Now we want to use this project network as a feature for a machine learning approach. One idea that came to mind is to use the adjacency matrix or reachability matrix as feature vectors for the machine learning model. Our intention is to capture the complete network structure as a feature and not just some "aggregating" measures such as density of transitive closure or ratio of nodes to arcs, etc.

The problem that we encounter is that depending on the labeling of the nodes, two identical project networks may have adjacency matrices that look very different. Ideally however, if the project networks are identical, the adjacency matrices should also be identical, independent of the labeling of the nodes.

We therefore propose to re-name the nodes according to some predefined logic. One could, for example, take into consideration the number of immediate or transitive successors.

Is anyone familiar with an approach like that or could guide us into the right direction with e.g. search terms to search for? The goal is to have a representation of the network that is invariant of the node labels.

Maybe research in the area of image processing would have to be something to look at? This may sound very "layman" but in the end it seems similar to the problem of having a single object but images of different perspectives. However, now we have the chance to "orient" the object in a predefined way (in this case by relabeling the nodes). Please excuse the clunky explanation.

For a visual help, I have drawn a quick sketch that illustrates the problem: Even though the networks are identical, the adjacency matrices are quite different:

Answer 1

I throw the following out as a possibility, but I am not at all sure that it is practical.

Let's say that you have a collection of adjacency matrices $\mathcal{A}$ known to be distinct, and you have a new adjacency matrix $\hat{A}$. You want to know whether it is "equivalent" to any of the matrices in $\mathcal{A}.$

Your dependency graphs are naturally layered (using the shortest number of links from the start node to each node $n$ to determine the layer containing $n$). As a first cut, you could label every matrix with the number of nodes, number of layers and maybe other information (number of nodes in each layer comes to mind). The labels would be designed so that equivalent matrices would have the same labels. Comparing the label of $\hat{A}$ to the label of each $A\in\mathcal{A}$ would let you quickly eliminate some (hopefully many) matrices $A$ from consideration because their labels did not match that of $\hat{A}.$

Now suppose that $A$ and $\hat{A}$ have the same label. $A$ and $\hat{A}$ are equivalent from your perspective if there is a permutation matrix $P$ of the same dimension as $A$ such that $\hat{A} = P^T A P.$ If you can find a labeling scheme such that two matrices have the same label if and only if such a permutation matrix exists, you are done. Otherwise, you would need to take each matrix $A\in\mathcal{A}$ whose label matched that of $\hat{A}$ and try to solve for $P.$ I cannot think of a direct way to do this using just matrix operations. Given $A$ and $\hat{A},$ you could solve for $P$ either using a binary linear program with a zero objective function (since all that matters is that the solution be feasible), or you could use a constraint solver. Either would be somewhat expensive computationally, hence the need for a quick filter (the label) to cut down on the number of problems to solve.