2
$\begingroup$

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:

Adjacency matrices of two identical networks

$\endgroup$
4
  • $\begingroup$ Just to be clear, you are concerned only with the precedence relationships and not with the task times, correct? In your Network 1, swapping the labels on nodes 4 and 5 would produce an identical adjacency matrix, but the times to go 3 -> 4 -> 6 and 3 -> 5 -> 6 would not necessarily be the same after interchanging nodes 4 and 5. $\endgroup$
    – prubin
    Apr 27, 2022 at 20:34
  • $\begingroup$ No suggestions on how to handle this with a clever encoding/transformation. But, for the ML side - as you probably know, yet for reference - you are broadly looking for Geometric Deep Learning and Graph Neural Networks, which study symmetries and invariances of objects in learning representations including permutation invariance on graphs. Some prominent researchers in this area are: Bronstein, Veličković, Cohen, Welling. A collection of great resources twitter.com/omarsar0/status/1490276912601653248 and on the intersection of OR and ML doi.org/10.48550/arXiv.2102.09544 $\endgroup$
    – ktnr
    Apr 27, 2022 at 21:35
  • $\begingroup$ Search for graph isomorphism problem and canonical representative. $\endgroup$
    – RobPratt
    Apr 27, 2022 at 21:43
  • $\begingroup$ Yes @prubin that is correct: For now we are simply concerned with the precedence relations, but you are indeed right: Task times (and other characteristics such as resource requirements) are neglected for now. Great insights also regarding the search terms and references, thanks to all commenters! $\endgroup$
    – derhendrik
    Apr 28, 2022 at 9:14

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.