# Network alignment and matching

[TOC]

## People

- **Will Payne ([e-mail])**
- **Eleanor Foster ([e-mail])**
- Ambrose Yim ([e-mail])
- Matthew Aldridge ([e-mail], @mpaldridge)
- Ruaridh Clark ([e-mail])
- Beate Ehrhardt ([e-mail])
- James Martin ([e-mail])
- Joseph Field ([e-mail])
- Jelena Grbic ([e-mail])
- David Allwright
- Xuan Vinh Doan ([e-mail])

## Problem

### Problem statement

:::info
Given two directed graphs with node and edge attributes -- which are probably pretty similar:
1. Assess the quality of a given "alignment" between the two graphs.
2. Find the best possible "alignment" between the graphs.
:::

### Mathematicization

A graph $G = (V, E, a, b)$ consists of:
- a finite set of nodes $V$
- We should expect this to be large -- perhaps in the hundreds-of-thousands or even millions.
- a set $E \subset V^2$ of directed edges
- Edges are directed, no loops, no multi-edges, and we never have both the edges $ij$ and $ji$.
- The graph is mostly sparse, although there may be a small number of high-degree nodes.
- a labelling $a \colon V \to \mathcal A$ of the nodes (so $a(i)$ is the attribute of node $i$)
- a labelling $b \colon E \to \mathcal B$ of the edges (so $b(ij)$ is the attribute of edge $ij$)
- I think we are supposed to be thinking of the node attributes as "categorical" rather than having numerical meanings, but the edge attributes should perhaps be considered as "weights" with numerical meaning (??)
- Perhaps nodes might have multiple attributes?

An *alignment* between two graphs $G_1 = (V_1, E_1, a_1, b_1)$, $G_2 = (V_2, E_2, a_2, b_2)$ is a function $\phi \colon V_1 \to V_2$. (The aligned nodes $\phi(i)$ must be distinct, but we would allow occasionally not matching some node $i \in V_1$ to a partner in $V_2$ and vice versa.)

We can think of this as a "matching" between $V_1$ and $V_2$, where there is a "matching edge" between $i \in V_1$ and $j \in V_2$ if $\phi(i) = j$, together with some lonely unmatched nodes. (But these "matching edges" are not the same as the actual edges in the graphs $G_1$ or $G_2$.)

An alignment is good (in rough most-important-first order) if:
1. Most nodes are actually aligned with another node.
1. The edge structure is mostly the same.
- if $ij \in E_1$, then usually $\phi(i)\phi(j) \in E_2$, and if $ij \not\in E_1$ then usually $\phi(i)\phi(j) \not\in E_2$
- Are there "global structure" things (eg connectivity) that aren't captured by treating all edges the same?
- Is aligning the edge but in the wrong direction better (or worse!) than not aligning it at all?
1. Most nodes are matched up with a node of the same attribute.
- $a_1(i) = a_2(\phi(i))$ for most nodes $i$
1. The edge attributes mostly match up.
- if $ij \in E_1$ and $\phi(i)\phi(j) \in E_2$, then usually $b_1(ij) = b_2(\phi(i)\phi(j))$
- or perhaps $b_1(ij) \approx b_2(\phi(i)\phi(j))$?

<!--
### Ingredients for the problem

#### Technical Expertise

| | Similarity measure | Iterative Optimisation |
| --------------- | ------------------ | ------------- |
| Optimisation | | |
| Network Science | | |
| ML | | |

#### Additional Problem Features from DSTL
-->

## Ideas: scoring functions

Fix two graphs $G_1$, $G_2$. Let $\phi$ be an alignment. How should we define the score $S_{G_1,G_2}(\phi)$ of this alignment?

### A "toy" score

- For each $i \in V_1$:
- score $\lambda$ if the node attributes match; that is, if $a_1(i) = a_2(\phi(i))$
- For each $ij \in V_1^2$:
- score $\mu$ if they are both edges; that is, if $ij \in E_1$ and $\phi(i)\phi(j) \in E_2$
- score $\nu$ if the are both non-edges; that is, if $ij \not\in E_1$ and $\phi(i)\phi(j) \not\in E_2$
- (Is having both of these redundant?)

This "toy score" doesn't pay any attention to the edge attributes.

So:
\begin{align}
S_{G_1,G_2}(\phi) &= \lambda \sum_i \mathbb I\big[a_1(i) = a_2(\phi(i))\big] \\
&\qquad {}+ \mu \sum_{i,j} \mathbb I\big[ij \in E_1 \big]\mathbb I\big[ \phi(i)\phi(j) \in E_2\big] \\
&\qquad {}+ \nu \sum_{i,j} \mathbb I\big[ij \not\in E_1 \big]\mathbb I\big[ \phi(i)\phi(j) \not\in E_2\big]
\end{align}

Can we pick values of $\lambda, \mu, \nu$ that help line this toy score up somewhat with the priorities we have?

Setting $\lambda = 0, \mu = \nu = 1$ gives the "add up the difference of the two adjacency matrices" that someone mentioned on Wednesday.

## Ideas: algorithms for alignment

### Iterative Optimisation

#### Improvement heuristic with 'Guided' search

- We try to match $G_1$, $G_2$ by an iterative optimisation.

#### Genetic algorithm

- We try to converge to a match between $G_{1}, G_{2}$ using a sequence of graph 'populations' $F_{k} := \{\tilde{G}^{k}_{1},\ldots,\tilde{G}^{k}_{n}\}$ at iteration $k$.

At each iteration $k$ we:
1. Determine fitness of each member of the population
1. Until convergence repeat at iteration $k+1$:
a. Select a subset of 'parents' $\Omega_{k}\subset F_{k}$
b. Crossover and generate new 'child' population using paired parents $\omega_{i},\omega_{j} \in \Omega_{k}$
c. Perform mutation on new population
d. Determine fitness for new population $F_{k+1}$

#### Simulated annealing

It can be good to ocassionally accept a worse alignment, if it allows one to avoid getting stuck in a "locally optimal" alignment.

#### From Xuan Vinh Doan

**Note from Xuan Vinh Doan (University of Warwick):**

> Perhaps others will continue discussing the heuristic approach.
>
> I’ve had a quick search for network alignment problem and come up with the following review paper: https://dl.acm.org/doi/pdf/10.1145/3340531.3412168. The optimisation approach I believe is discussed in [1] and as mentioned [on Wednesday], we will be able to develop similar formulations once the dissimilarity function is established. The solution approach can be a first-order method for the relaxed problem or the community-based approach (as discussed today when one constructs communities graphs first and apply the alignment algorithm before aligning nodes in each pair of matched communities).

### Similarity heuristics

- Optimal Transport + Laplacian covariance approach: [Wasserstein-based Graph Alignment](https://arxiv.org/pdf/2003.06048.pdf)
- Isorank
- Graph edit distance (need to tailor relative 'cost' of edit operations (e.g. vertex/edge insertion/deletion, flipping edge direction... ))

### Clustering

(To do)

### Graph isomorphism algorithms

How do `nauty`, `trace` etc work if you give them only "nearly-isomorphic" graphs.

Graph isomorphism algorithms (as I understand it...) work by producing a "canonical labelling" of the vertices of a graph. Once we have two graphs canonically labelled, it's trivial to check if they are the same graph. Does a canonical labelling of our "almost-isomorphic" graphs help at all?

#### Weisfeiler-Lehman/Graph Neural Network (GNN) 🤖 frameworks

GNNs and WL procedures Using local label message passing scheme to generate additional vertex features $\varphi(v)$ that take native vertex/edge attributes into account to summarise local graph structure near the vertex.

If $\varphi(v) \approx \varphi(u)$ for $u \in G_1$ and $v\in G_2$, then $u$ and $v$ may be likely to be matched.

In WL tests, if the set of vertex wise features generated by two graphs using these procedures are identical, then they may isomorphic


* **Pros:** Algorithms naturally incorporate vertex and edge labels into account
* **Cons:** Potentially unstable w.r.t. edge direction/label 'errors'

**References:**
- Explicit architectures for undirected graph: [Graph Alignment Kernels using Weisfeiler and Leman Hierarchies](https://www.lix.polytechnique.fr/Labo/Ioannis.Nikolentzos/files/gawl_aistats23.pdf)
- Graph alignment using GNNs in a semi-supervised framework [GANN: Graph Alignment Neural Network for Semi-Supervised Learning](https://arxiv.org/pdf/2303.07778.pdf).
- Article linking WL with GNN [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://arxiv.org/pdf/1810.02244.pdf)
- An example research article on comparing the expressiveness of WL methods to spectral methods [Weisfeiler–Leman and Graph Spectra](https://arxiv.org/pdf/2103.02972.pdf)
- Links between other alignment methods, such as Isorank, with GNN approaches [Deep graph alignment network](https://www.sciencedirect.com/science/article/pii/S0925231221013461?ref=cra_js_challenge&fr=RR-1)
- Training free approach [TRAINING FREE GRAPH NEURAL NETWORKS FOR GRAPH MATCHING](https://arxiv.org/pdf/2201.05349.pdf)

### Spectral things 👻

Can use one or two eigenvectors to embed a graph in 1D or 2D space

The directedness of the graph is a problem here. Potential solution: [a Hermitian Laplacian for directed graphs](https://link.springer.com/article/10.1007/s00026-005-0237-z).

Also problematic: spectral decomposition for large networks very expensive $O(n^3)$ if all eigenvalues, eigenvectors needed for method. (Is it $O(n^2)$ for sparse graphs?)

Hard to incorporate labels on vertices/edges.

If the directed graph is strongly connected, there is a unique largest eigenvalue with a real positive eigenvector -- but we don't expect our graph to be strongly connected. (But the PageRank trick -- adding a very low weight complete graph -- could work.)

### Expressing as a binary integer program

Introduce binary variables $x_{ij}$, for $i \in V_1, j \in V_2$. The idea is that $x_{ij} = 1$ denotes "$i \in V_1$ is aligned with $j \in V_2$" and $x_{ij} = 0$ denotes they are not aligned.

The constraints
$$\sum_i x_{ij} \leq 1 \qquad \sum_j x_{ij} \leq 1 $$
ensure no node in one graph is matched with multiple nodes in the other graph. The less-than-or-equal allows us to not match up a node, if that node doesn't have a good sibling in the other graph.

## Notes from 22 March meeting