Laplacianoid

Introduction

After experimenting with using a graph's Laplacian on its own adjacency matrix in a straightforward way, I found that it was doing the blurring operation I want on the tail end of each graph edge, but not on the head ends. I designed a new operation that works on both ends of each edge.

I call this double operation "Laplacianoid" because it's made of two Laplacian operations, not one:

$ℒ\left(\mathbf{x}\right)\mathbf{y}={\mathbf{L}}_{\mathbf{o}}\left(\mathbf{x}\right)\mathbf{y}+{\mathbf{yL}}_{\mathbf{i}}\left(\mathbf{x}\right)$,

that is,

${\left(-ℒ\left(\mathbf{x}\right)\mathbf{y}\right)}_{ij}=\sum _k\left[x_{ik}\left(y_{kj}-y_{ij}\right)+\left(y_{ik}-y_{ij}\right)x_{kj}\right]$.

Note $ℒ\left(\mathbf{x}\right)\mathbf{y}$ is not a product of two matrices; it's the operation of linear operator $ℒ\left(\mathbf{x}\right)$ on matrix $\mathbf{y}$. Given an $n\times n$ matrix $\mathbf{x}$, $ℒ\left(\mathbf{x}\right)$ is a linear operator on the space of $n\times n$ matrices. If both $\mathbf{x}$ and $\mathbf{y}$ are symmetric, then $ℒ\left(\mathbf{x}\right)\mathbf{y}$ is also symmetric.

Laplacianoid ODE

Note: I am also studying a stochastic process based on the Laplacianoid operation: see Laplacian Experiments/Stochastic for the analysis of that process.

The ODE

$\dot{\mathbf{e}}=-ℒ\left(\mathbf{e}\right)\mathbf{e}$,

i.e.,

${\dot{e}}_{ij}=\sum _k\left[e_{ik}\left(e_{kj}-e_{ij}\right)+\left(e_{ik}-e_{ij}\right)e_{kj}\right]$

$=\sum _k\left[2e_{ik}{e}_{kj}-\left(e_{ik}+e_{kj}\right)e_{ij}\right]$

does what I want much better than the one-sided operations like $\mathbf{L}\left(\mathbf{e}\right)\mathbf{e}$.

Simulation indicates that this tends to equilibrium at a multiple of the complete graph, that is at

$e_{ij}=k$ for all $i,j$.

Other equilibria include disconnected complete subgraphs, i.e. let the set of vertices $V$ be the union of disjoint $V_s$, and

$e_{ij}=k_s$ for $\left\{i,j\right\}\subseteq V_s$, $0$ otherwise.

In either of these cases $e_{ik}\left(e_{kj}-e_{ij}\right)$ and $e_{kj}\left(e_{ik}-e_{ij}\right)$ are both zero for all $i,j,k$.

Q: Are there other equilibria? Which are stable?

Linear algebra of ℒ

Let's assume that $\mathbf{e}$ is symmetric here (or equivalently, that the graph is undirected), so that ${\mathbf{L}}_{\mathbf{o}}\left(\mathbf{e}\right)={\mathbf{L}}_{\mathbf{i}}\left(\mathbf{e}\right)=\mathbf{L}\left(\mathbf{e}\right)$. Since $ℒ\left(\mathbf{e}\right)$ is a linear operator on the $n^2$-dimensional space of $n\times n$ matrices, it has $n^2$ eigenvalues, and an eigenmatrix (rather than eigenvector) for each. If ${\mathbf{v}}_i$ are the eigenvectors of $\mathbf{L}\left(\mathbf{e}\right)$ with eigenvalues ${\lambda }_i$, the eigenmatrices of $ℒ\left(\mathbf{e}\right)$ are ${\mathbf{x}}_{ij}={\mathbf{v}}_i{\mathbf{v}}_j^{\mathrm{T}}$ with eigenvalues ${\lambda }_{ij}={\lambda }_i+{\lambda }_j$:

$ℒ\left(\mathbf{e}\right){\mathbf{x}}_{ij}=\mathbf{L}\left(\mathbf{e}\right){\mathbf{x}}_{ij}+{\mathbf{x}}_{ij}\mathbf{L}\left(\mathbf{e}\right)$

$=\left({\lambda }_i+{\lambda }_j\right){\mathbf{x}}_{ij}$.

When $\mathbf{e}$ is symmetric, $\mathbf{L}\left(\mathbf{e}\right)$ has nonnegative eigenvalues, so the only zero eigenvalues of $ℒ\left(\mathbf{e}\right)$ come from zero eigenvalues of $\mathbf{L}\left(\mathbf{e}\right)$. If $\mathbf{e}$ is connected, the only zero eigenvector of the Laplacian is the vector of all ones, $\mathbf{1}$, so the only zero eigenmatrix of $ℒ\left(\mathbf{e}\right)$ is $\mathbf{1}{\mathbf{1}}^{\mathrm{T}}$.

If the graph is not connected, it's a union of disjoint subgraphs $G_1,\mathrm{\dots },G_k$ with adjacency matrices ${\mathbf{e}}_1,\mathrm{\dots },{\mathbf{e}}_k$ with $\mathbf{e}={\mathbf{e}}_1+\mathrm{\cdots }+{\mathbf{e}}_k$. The null space of $\mathbf{L}\left(\mathbf{e}\right)$ contains $k$ orthogonal eigenvectors ${\mathbf{v}}_i$ with ${\left({\mathbf{v}}_i\right)}_j=1\text{ if vertex }j\text{ is part of subgraph }i\text{, }0\text{ otherwise}$. It follows that the nullspace of $ℒ\left(\mathbf{e}\right)$ is $k^2$-dimensional and the corresponding eigenmatrices are constructed from pairs of these ${\mathbf{v}}_i$ as above.

We know already that $\sum _{i,j}{\left({\mathbf{L}}_{\mathbf{o}}\left(\mathbf{e}\right)\mathbf{e}\right)}_{ij}=0$ because it's zero for each $j$ provided $\mathbf{e}$ is symmetric, and $\sum _{i,j}{\left({\mathbf{eL}}_{\mathbf{i}}\left(\mathbf{e}\right)\right)}_{ij}=0$ by the same process on each $i$, so in the $ℒ$ ODE the sum of all edge weights is conserved. If the equilibrium matrix $\mathbf{e}\left(\mathrm{\infty }\right)$ is connected, then, it must be that $\mathbf{e}\left(\mathrm{\infty }\right)=\frac{{\sum }_{i,j}{e}_{ij}\left(0\right)}{n^2}\mathbf{1}{\mathbf{1}}^{\mathrm{T}}$.

It seems like it ought to be straightforward to show that if $\mathbf{e}$ is connected at time 0, it stays connected.

It's sometimes helpful to write the regular Laplacian of a graph $\mathbf{e}$ in the form

$-\mathbf{L}{\left(\mathbf{e}\right)}_{ij}=e_{ij}-\sum _k{e}_{ik}{\delta }_{ij}$

where ${\delta }_{ij}$ is $1$ when $i=j$ and $0$ otherwise. The corresponding expression for the Laplacianoid is

$-ℒ{\left(\mathbf{e}\right)}_{ij,k\mathrm{\ell }}=e_{ik}{\delta }_{\mathrm{\ell }j}+e_{\mathrm{\ell }j}{\delta }_{ik}-\sum _p\left(e_{ip}+e_{pj}\right){\delta }_{ik}{\delta }_{\mathrm{\ell }j}$.

This can be plugged in to give us the Laplacianoid operation we know:

$\begin{aligned}\displaystyle(-\mathscr{L}(\mathbf{e})\mathbf{x})_{{ij}}&\displaystyle=\sum _{{k\ell}}-\mathscr{L}(\mathbf{e})_{{ij,k\ell}}x_{{k\ell}}\\&\displaystyle=\sum _{k}e_{{ik}}x_{{kj}}+\sum _{{\ell}}e_{{\ell j}}x_{{i\ell}}-\sum _{p}(e_{{ip}}+e_{{pj}})x_{{ij}}\end{aligned}$

In this way we can think of the Laplacianoid as a sort of hypermatrix - an object with four indices that operates on matrices the way a matrix operates on vectors.

The Jacobian of the dynamics

To assess the stability of the ODE's equilibria, we need to look at its Jacobian. Since

${\dot{e}}_{ij}=\sum _k\left[2e_{ik}{e}_{kj}-\left(e_{ik}+e_{kj}\right)e_{ij}\right]$,

we have

$\frac{\partial {\dot{e}}_{ij}}{\partial e_{ij}}=2e_{ii}+2e_{jj}-2e_{ij}-\sum _k\left(e_{ik}+e_{kj}\right)$,

and for $k\ne i$ and $\mathrm{\ell }\ne j$,

$\frac{\partial {\dot{e}}_{ij}}{\partial e_{i\mathrm{\ell }}}=2e_{\mathrm{\ell }j}-e_{ij}$,

$\frac{\partial {\dot{e}}_{ij}}{\partial e_{kj}}=2e_{ik}-e_{ij}$,

$\frac{\partial {\dot{e}}_{ij}}{\partial e_{k\mathrm{\ell }}}=0$.

We can encapsulate this by writing (for all $k,\mathrm{\ell }$)

$\frac{\partial {\dot{e}}_{ij}}{\partial e_{k\mathrm{\ell }}}=\left(2e_{\mathrm{\ell }j}-e_{ij}\right){\delta }_{ik}+\left(2e_{ik}-e_{ij}\right){\delta }_{\mathrm{\ell }j}-\sum _p\left(e_{ip}+e_{pj}\right){\delta }_{ik}{\delta }_{\mathrm{\ell }j}.$

As with a regular vector dynamical system, if ${\mathbf{e}}^{*}$ is an equilibrium, a point near the equilibrium $\mathbf{e}={\mathbf{e}}^{*}+\mathbf{x}$ has derivative ${\dot{e}}_{ij}={\dot{x}}_{ij}\approx \sum _{k,\mathrm{\ell }}\frac{\partial {\dot{e}}_{ij}}{\partial e_{k\mathrm{\ell }}}{x}_{k\mathrm{\ell }}$, and we want to know if there is any such $\mathbf{x}$ that grows rather than shrinking. This really is a regular vector dynamical system, notwithstanding the fact that the state variables are written in a square rather than a column, so all the linear theory applies, including the fact that ${\mathbf{e}}^{*}$ is hyperbolically stable if and only if all the eigenvalues of the Jacobian are negative.

So let's look at the quadratic form associated with the Jacobian, because if we can show that the quadratic form is never positive (that is, if it's a negative definite or negative semidefinite form) we can conclude that the eigenvalues of the Jacobian are all negative or non-positive. Because the ODE is restricted to symmetric matrices as long as the initial value is symmetric, we can restrict ourselves to the action of the Jacobian on symmetric perturbations $\mathbf{x}$. The quadratic form is

$Q\left(\mathbf{x}\right)=\sum _{i,j,k,\mathrm{\ell }}{x}_{ij}\frac{\partial {\dot{e}}_{ij}}{\partial e_{k\mathrm{\ell }}}{x}_{k\mathrm{\ell }}$

and for symmetric $\mathbf{x}$,

$Q\left(\mathbf{x}\right)=\sum _{a,b,c}{e}_{ab}\left(4x_{ac}{x}_{bc}-x_{ab}{x}_{ac}-x_{ab}{x}_{bc}-x_{ac}^2-x_{bc}^2\right)$

This does not seem to be negative semidefinite necessarily, and it seems like it might have positive values at at least some equilibrium values of ${\mathbf{e}}^{*}$.

Let's investigate the complete-graph equilibrium, since I think it ought to be stable. In this case

$Q\left(\mathbf{x}\right)=\sum _{a,b,c}k\left(-{\left(x_{ac}-x_{bc}\right)}^2-x_{ac}\left(x_{ab}-x_{bc}\right)-x_{bc}\left(x_{ab}-x_{ac}\right)\right)$

but since we are considering only symmetric $\mathbf{x}$, we can write

$\sum _{a,b,c}{x}_{ac}\left(x_{ab}-x_{bc}\right)=\sum _{a,b,c}{x}_{ac}{x}_{ab}-\sum _{a,b,c}{x}_{ac}{x}_{bc}$

this works for the third term of the above expression as well as for the second, so we conclude that

$Q\left(\mathbf{x}\right)=-k\sum _{a,b,c}{\left(x_{ac}-x_{bc}\right)}^2,$

and so it is negative semidefinite. $Q\left(\mathbf{x}\right)$ is zero when $x_{ac}=x_{bc}$ for all $a,b,c$; for symmetric $\mathbf{x}$ this condition implies that all entries of $\mathbf{x}$ are equal: $x_{ij}=x_{\mathrm{\ell } j}=x_{j\mathrm{\ell }}=x_{k\mathrm{\ell }}$. These are the zero eigenmatrices of the Jacobian, and all other eigenvalues are negative.

Consequently this ${\mathbf{e}}^{*}$ is a hyperbolically stable fixed point, except that it's neutral to the addition of a constant to all entries of the matrix. The dynamics conserves the sum of all matrix entries, so in fact it's entirely stable.

Now when ${\mathbf{e}}^{*}$ is made of disjoint cliques, it's different:

$Q\left(\mathbf{x}\right)=\sum _s\sum _{a,b\in V_s,c\in V}{k}_s\left(-{\left(x_{ac}-x_{bc}\right)}^2-x_{ac}\left(x_{ab}-x_{bc}\right)-x_{bc}\left(x_{ab}-x_{ac}\right)\right)$

If $\mathbf{x}$ has an edge $x_{ij}>0$ from one clique to another, we can have a positive term at $\left(a,b,c\right)=\left(i,i,j\right)$.

The linearized system is

${\dot{x}}_{ij}=\sum _{k,\mathrm{\ell }}\frac{\partial {\dot{e}}_{ij}}{\partial e_{k\mathrm{\ell }}}{x}_{k\mathrm{\ell }}$

and for this ${\mathbf{e}}^{*}$ this has two cases: if $i$ and $j$ are in the same $V_s$, i.e. if $e_{ij}>0$,

${\dot{x}}_{ij}=\sum _{\mathrm{\ell }\in V_s}{k}_s{x}_{i\mathrm{\ell }}-\sum _{\mathrm{\ell }\notin V_s}{k}_s{x}_{i\mathrm{\ell }}+\sum _{k\in V_s}{k}_s{x}_{kj}-\sum _{k\notin V_s}{k}_s{x}_{kj}-\sum _{p\in V_s}2k_s{x}_{ij}$

and if $i\in V_s$ and $j\in V_t$ ($s\ne t$),

${\dot{x}}_{ij}=\sum _{\mathrm{\ell }\in V_t}2k_t{x}_{i\mathrm{\ell }}+\sum _{k\in V_s}2k_s{x}_{kj}-\sum _{p\in V_s}{k}_s{x}_{ij}-\sum _{p\in V_t}{k}_t{x}_{ij}$

I wish to construct an eigenmatrix with a positive eigenvalue, that is $\dot{\mathbf{x}}=\lambda \mathbf{x}$ with $\lambda >0$. This will demonstrate that the union of multiple disjoint cliques is not a stable equilibrium.

A positive eigenmatrix

Given an equilibrium matrix ${\mathbf{e}}^{*}$ made of multiple disjoint cliques, let us choose two distinct cliques $V_s$ and $V_t$, and let $x_{ij}=0$ except that $x_{ij}$ is $z$ for every edge connecting $V_s$ and $V_t$, $u$ for every edge within $V_s$ and $v$ for every edge within $V_t$.

Then for an edge from $V_s$ to $V_t$

${\dot{x}}_{ij}=\left(\left|V_s\right|k_s+\left|V_t\right|k_t\right)z,$

and from $V_t$ to $V_s$

${\dot{x}}_{ij}=\left(\left|V_t\right|k_t+\left|V_s\right|k_s\right)z,$

while for an edge within $V_s$

${\dot{x}}_{ij}=-\left|V_t\right|k_{s}z$

and within $V_t$

${\dot{x}}_{ij}=-\left|V_s\right|k_{t}z.$

For all other edges ${\dot{x}}_{ij}=0$.

So if this is going to be an eigenmatrix we must have

$\lambda =\left|V_s\right|k_s+\left|V_t\right|k_t$;

and given this we require

$-\left|V_t\right|k_{s}z=\lambda u$

and

$-\left|V_s\right|k_{t}z=\lambda v$,

so we simply set $u=-\left|V_t\right|k_{s}z/\lambda$ and $v=-\left|V_s\right|k_{t}z/\lambda$, and there it is!

(Note that $\mathbf{x}$ is not a graph's adjacency matrix itself, it's a perturbation to ${\mathbf{e}}^{*}$, so it's fine for it to have negative entries. It adds weight to edges that are zero, and subtracts from edges that are positive.)

A corrected Laplacianoid

Here's a variation on the Laplacianoid, with a correction term so that it does the same thing but doesn't create loops, i.e. nonzero $e_{ii}$. The Laplacanoid equation does, because of lots of terms like ${\dot{e}}_{11}=\mathrm{\cdots }+e_{12}{e}_{21}+\mathrm{\cdots }$. So to remove those:

This should be a lot like the uncorrected Laplacianoid, preserving symmetry of $\mathbf{y}$, and

$\dot{\mathbf{e}}=-{ℒ}_c\left(\mathbf{e}\right)\mathbf{e}$

should conserve the sum of edge weights, and hopefully will go to all edges equal, but with no loops.

This is also a linear operator. I haven't done any simulations or analysis on it yet...