I have two complete weighted graphs, with the same number of nodes and edges. Each node has a multi-dimensional vector, which represents its features. Edge weights are float numbers between 0 to 1. I'm trying to align these graphs.

I've started with (Hungarian) bipartite matching. I completely ignored the edges in both graphs and focused on the nodes. I created a bipartite graph. For each pair of nodes `(n1, n2)`

where `n1`

belongs to the first graph, and `n2`

belongs to the second graph, I've defined their edge to be the inner product of their vectors. This worked reasonably well, which shows that the nodes are semi-consistent between graphs.

But now I want to take into account the edge weights as well. I've looked at the graph alignment algorithms listed in this link which include algorithms like GWL, GRAMPA, and GRAAL. But they all seem to only work with the adjacency matrix (i.e. weights of edges) of the two graphs, while I want to consider both node and edge weights.

Another idea that I had was to add `N-1`

new dimensions to the node feature vectors. Where `N`

is the number of nodes, and each dimension contains an edge weight. i.e. for node `i`

, the newly added dimension `j`

contains the weight for edge `(i, j)`

. And then use the Hungarian bipartite matching again where cost is calculated using the inner product of node vectors. but this won't work, because the order of nodes is not consistent.

So my question is this, Are there any algorithms for this specific use case? any other tips or suggestions are also appreciated.

P.S. I originally posted this in Math Stackexchange, but as the graph alignment methods that I checked are new (S-GWL: NeurIPS 2019, Grampa: ICML 2020), I figured this site is more suitable.