1
$\begingroup$

I have a graph and I'm interested in adding node to my graph such that it preserve the harmonic solution (page 2). Concretely, given a graph $G = (V,E)$ with $|V| = n$ and the labels (real values) for some vertices $V_l$, the harmonic solution gives the labels for the rest of the graph:

\begin{equation} \text{min} \ \frac{1}{2}\sum_{(x,y) \in E} \omega_{x,y} (f(x) - f(y))^2 \end{equation}

Now in the paper mentioned above, they have proved that the star-mesh transform can preserve the harmonic solution. In the star-mesh transform, the number of nodes decreases.

My question is: Is there a transform to add a new node to an existing graph, which preserves the harmonic solution? I tried the $\Delta$ - Y transform but triangles do not always exist in a graph.

$\endgroup$
  • 1
    $\begingroup$ Without having actually done the math, I suspect you can add vertices by subdividing an edge and adjusting the weights on the new edges appropriately. $\endgroup$ – Misha Lavrov Mar 9 at 16:14
  • $\begingroup$ Do you have any suggestion in more detail? I googled a lot and couldn't find a solution. $\endgroup$ – lenhhoxung Mar 20 at 1:01
1
$\begingroup$

If we think of the graph $G$ as an electric network with weights as conductances and the given labels as voltage sources, then the remaining labels correspond to potentials in the electric network at the unlabeled vertices. So we expect that the harmonic solution will not change if we change $G$ in a way that produces an equivalent electric network.

Here are two simple changes that should do this. For the first one, I have an electric network-free proof; the second one ought to also be true by analogy, but I'm too lazy to confirm it.

Another (boring) change is to add a vertex that's only connected to vertices with fixed labels. The $f$-values on two vertices only interact, in the minimization problem, if there's a path connecting them using only unlabeled vertices. So when there's no such path from vertices you're adding to existing vertices, the harmonic solution on existing vertices will not change.

Adding a copy of a vertex

Replace any unlabeled vertex $x$ by two vertices $x', x''$ with the same neighbors as $x$, and with edge weights $w_{x', y} = w_{x'', y} = \frac12 w_{x,y}$. (This corresponds to two parallel circuits in the electric network.)

First of all, the harmonic solution for the new graph should have $f(x') = f(x'')$. This is because, keeping all values on nodes other than $x'$ and $x''$ fixed, the values $f(x')$ and $f(x'')$ show up in similar terms, so the quantity we're minimizing is equal to $P(f(x')) + P(f(x'')) + Q$ for some fixed quadratic polynomial $P$ and constant $Q$. If we have $P(f(x')) \ne P(f(x''))$, then we should replace one by the other to make the objective function smaller, and if we have $P(f(x')) = P(f(x''))$, then we can set $f(x') = f(x'')$ without changing the objective function.

Now the optimization problem for the new graph becomes equivalent to the optimization problem for the old graph, because (given that $f(x') = f(x'')$), we have a $$ w_{x,y} (f(x) - f(y))^2 = \frac12 w_{x,y}(f(x) - f(y))^2 + \frac12 w_{x,y}(f(x) - f(y))^2 $$ term in the old graph corresponding to every $$ w_{x',y} (f(x') - f(y))^2 + w_{x'',y} (f(x'') - f(y))^2 $$ term in the new graph. For every value of one objective function, we get the same value in the other objective function when $f(x) = f(x') = f(x'')$ and all other labels are kept the same.

So the harmonic solution is the same for both graphs.

Subdividing an edge

We should expect by the electric network analogy that if we replace edge $(x,y)$ with two edges $(x,z)$ and $(z,y)$, where $z$ is a new node, then the harmonic solution should stay the same provided that we choose $w_{x,z}$ and $w_{z,y}$ to satisfy $$\frac1{w_{x,y}} = \frac1{w_{x,z}} + \frac1{w_{z,y}}.$$ After all, the new electric network is equivalent to the previous one, since resistances add when connecting resistors in parallel.

This feels painful to check using the minimization problem, though.

$\endgroup$
  • $\begingroup$ It is very interesting. I'm going to check ti carefully $\endgroup$ – lenhhoxung Mar 20 at 8:30
  • $\begingroup$ Probably, this is the most comprehensive answer I've received up to now. The intuition for 2nd solution (subdividing edges) is clear. Thanks $\endgroup$ – lenhhoxung Mar 20 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.