Graph alignment by considering node and edge weights

Question

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.

Answer 1

This is a very interesting problem, although I'm not sure if it's a mathematical problem exactly (as opposed to one of algorithmic modeling). That said, here are some two suggestions.

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$.

Suggestion #2: We can also tweak the OP's second suggestion to address their concern. In this approach, we take the vector associated with each node and extend it with information from the neighboring edges. The OP rightly points out that there's no natural order to the edges (since we don't know the node permutation), so it's not obvious in which order to list them. There are several approaches; we share three:

• The classic approach in, e.g., graph neural nets would be to take the set of edge weights and compute some permutation-invariant statistics, like the mean and variance, and append those values.
• 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.
• Finally, in practice, the easiest version is to take all the neighboring edges, sort them by magnitude, and append that sorted list. (We need to give missing edges a weight of zero so the resulting vectors are all the same length.)