3
$\begingroup$

We are stuck with understanding the figure from the paper, shown below (link) Paper

  1. What is the idea of each of 8 graphs?

    • Is it smth like 1st eigenvector $v_1 = (a_1,a_2,…)$ where $a_i$ - negative values, ...etc and similarly last eigenvector (8th) $v_8 = ( b_1,b_2,…)$ where $b_i$ - either positive or negative values( if we look at picture)?
  2. Why assignment of values is less and less uniform?

My understanding so far is: The bigger the eigenvalue is, then the corresponding eigenvector accounts for the most non typical, big in value, ( maybe opposite values) of the vertexes, like in the very right graph. I.e. my feeling is that it is something like PCA, where the biggest eigenvalue is responsible for biggest variance of data. But my understanding is like a sieve.

$\endgroup$
  • $\begingroup$ I'd rather not download a post-script file to look at the picture, and ideally I'd like to be able to have your figure appear in the question. Could you possibly link to a jpg or png? $\endgroup$ – Omnomnomnom Nov 8 '16 at 15:52
  • $\begingroup$ Oh great, you took care of it. Thank you. $\endgroup$ – Omnomnomnom Nov 8 '16 at 15:55
  • $\begingroup$ Thank You! I know one more figure in other book, describing same intuition : i.stack.imgur.com/yRPvW.png $\endgroup$ – Ant Nov 8 '16 at 15:57
  • $\begingroup$ If you leverage intuition from physics and PDE's (noting that the gaph Laplacian is the discrete analog to the continuous Laplacian), the increasing eigenvalues correspond to increasing energy levels to the configuration of a system. The corresponding configuration is encoded by the eigenvector. Notably, $\lambda = 0$ corresponds to the constant function over the vertices. $\endgroup$ – Omnomnomnom Nov 8 '16 at 16:09
  • $\begingroup$ @Omnomnomnom , ok, seems good explanation, but I can not convince my fellows what these eigenvalues with eigenvectors are good intuition for graph. It is kind of some decomposition of the graph, that tells us which vertexes are important? $\endgroup$ – Ant Nov 8 '16 at 16:29
1
$\begingroup$

Let $M$ denote an oriented incidence matrix over a graph on $n$ vertices. In particular, let $e_1,\dots,e_m$ denote a list of directed edges, where $e_j$ connects the vertices $v_1(e_j)$ and $v_2(e_j)$. Note that if $f:V \to \Bbb R^n$ (which is to say that $f \in \Bbb R^n$), then we have $$ Mf = \left[f(v_1(e_j) - f(v_2(e_j))) \right]_{j=1}^m $$ If $L$ is the Laplacian, we compute $$ f^TLf = \|Mf\|^2 = \sum_{j=1}^m \left[f(v_1(e_j)) - f(v_2(e_j)) \right]^2 $$ which is to say that $\Phi(f) = f^TLf$ gives something akin to the "total variation of $f$ over the graph".

Now, the Rayleigh quotient gives us a useful recursive definition of eigenvalues and eigenvectors. In particular, let $\lambda_1,\lambda_2,\dots,\lambda_n$ denote the eigenvalues in increasing order, and let $f_1,f_2,\dots, f_n$ denote the associated eigenvectors. For the first eigevalue/eigenvector, we have $$ \lambda_1 = \lambda_{min}(L) = \min \left\{\Phi(f) : \|f\| = 1 \right\} $$ and $f_1$ is the vector for which this minimum is attained. We then have $$ \lambda_k = \min\left\{\Phi(f) : \|f\| = 1, \; f \perp f_j \text{ for } j = 1,\dots,k-1 \right\} $$ Predictably, the first few eigenvectors have very little variation since it is precisely the "total variation" which they minimize. However, as the vectors become more constrained (since they must be perpendicular to all previous eigenvectors), the amount of variation is forced to increase.

$\endgroup$
  • $\begingroup$ Omnomnomnom,I have few more questions. 1) By $f^TLf$ are trying to minimise the sum of values of functions for 2 connected vertexes?, why do we do so? 2) why do we require $||f||=1$, does it go from "Formulation using Lagrange multipliers"?, can you elaborate more? 3) I suppose there are 2 typos at $Mf$, $f^TLf$ - brackets for $v_1$ - do not close. And thank you very much, I think I started to get better the intuition of all that. $\endgroup$ – Ant Nov 8 '16 at 23:11
  • $\begingroup$ All of this comes from standard characterizations of eigenvalues of symmetric matrices. See the link in my answer and this link. $\endgroup$ – Omnomnomnom Nov 8 '16 at 23:18
  • $\begingroup$ And you're welcome $\endgroup$ – Omnomnomnom Nov 9 '16 at 0:11
  • $\begingroup$ I suppose that I didn't make one thing completely clear: $$ f^TLf = f^T(M^TM)f = (f^TM^T)(Mf) = (Mf)^T(Mf) = \|Mf\|^2 $$ $\endgroup$ – Omnomnomnom Nov 9 '16 at 17:52
  • $\begingroup$ This is clearer than other parts =) Thanks $\endgroup$ – Ant Nov 9 '16 at 21:18

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.