Graph alignment by considering node and edge weights

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.

Suggestion #1: Currently, each edge $$e$$ has two weights associated with it: the intrinsic edge weight $$a_e$$ (i.e., the one in the range $$[0,1]$$), and the inner product of the nodes defining the edge $$b_e$$ (i.e., the one used in the Hungarian method). The simplest approach would be to choose a fixed $$\lambda >0$$ and define a new edge weight $$c_e=a_e + \lambda b_e$$, then use either the Hungarian method or one of the other edge algorithms mentioned above. If the OP has some ultimate measure of quality for their solution, they could use that to tune $$\lambda$$ on a validation set. One might also consider using cosine similarity instead of inner product to normalize the scale of $$b_e$$.
• This approach is, of course, a special case of the more general approach of evaluating symmetric functions of the data. If we have $$N$$ nodes in our graph, we could choose our favorite basis for symmetric polynomials and evaluate the first $$N$$ polynomials. This produces a permutation-invariant fingerprint of the neighboring edges and avoids the information loss of the previous approach.