On the choice of indicator function in graph clustering problem In section 5.1 from A tutorial on spectral clustering by von Luxburg (p. 10), the author reformulates RatioCut using the graph Laplacian. To do so, he defines a partitioning vector f, such that
$$
f_i= \begin{cases}\sqrt{\frac{|\overline{\mathcal{A}}|}{|\mathcal{A}|}} & \text { if } v_i \in \mathcal{A} \\ -\sqrt{\frac{|\mathcal{A}|}{|\overline{\mathcal{A}}|}} & \text { if } v_i \in \overline{\mathcal{A}}\end{cases}
$$
This choice of partitioning vector seems too arbitrary to me. In fact, author defines another vector
$$h_{i, j}= \begin{cases}1 / \sqrt{\left|A_{j}\right|} & \text { if } v_{i} \in A_{j} \\ 0 & \text { otherwise }\end{cases}$$
when deriving a spectral formulation for the case of arbitrary k. Is there a reason for these choices?
 A: This choice of function is far from arbitrary, it is carefully chosen so that $$
f'Lf = |V|\,\mathrm{RatioCut}(A, \bar A).
$$
The reasoning for defining $h_{i, j}$ in that manner is for a more generalized conic optimization problem, engineered similarly to the definition of $f$ so that $\mathrm{tr}(H^T L H) = \mathrm{RatioCut}(A_1, \ldots, A_k)$.
If you try to work in reverse and define a function $f: V \to \mathbb R$ such that $f' L f$ is a multiple of $\mathrm{RatioCut}(A, \bar A)$, you'll derive a similar function. Now, $\mathbf 1$ always spans the $0$-eigenspace of $L$, so we'll want to exclude $\mathrm{span}(\mathbf 1)$ from our optimization problem or our partition will always be degenerate. The orthogonal complement of $\mathbf 1$ is the collection of vectors with $f^T \mathbf 1 = \sum_{u \in V} f(u) = 0$, so our entries need to sum to $0$. We wish to count edge crossings with the bilinear form of the Laplacian $f' L f = \sum_{u \sim v} (f(u) - f(v))^2$, so $f(u) - f(v) \neq 0$ for edge crossings and $f(u)
- f(v) = 0$ otherwise.
Combining these conditions, we have a function that is constant on $A$ and $\bar A$ that sums to $0$. An easy first guess is
$$
    f(u) = \begin{cases}
        1 &\text{if } u \in A \\
       -1 &\text{if } u \in \bar A.
    \end{cases}
$$
The function is constant on $A$ and $\bar A$ and $f(u) - f(v)$ is nonzero if and only if $u, v$ are in different clusters. However, the function does not sum to zero if $|A| \neq |\bar A|$, so we need to normalize the entries so that
$$\begin{align*}
    \sum_{u \in V} f(u) &= 0 \\
    \sum_{u \in A} f(u) + \sum_{u \in \bar A} f(u) &= 0 \\
    c |A| + d |\bar A| &= 0,
\end{align*}$$
where $c, d \in \mathbb R$ are the entries of $f$ over $A$ and $\bar A$, respectively. Setting $c = -1/d$ and solving, $c = \sqrt{|\bar A|/|A|}$ and
$d = -1/c = -\sqrt{|A| / |\bar A|}$. Any function $f$ for which $f' L f =
k\, \mathrm{RatioCut}(A, \bar A)$ is a constant multiple of this function.
Similar considerations are necessary for the more general setting as well. If you try to define an $n \times k$ matrix $H$ such that $\mathrm{tr}(H' L H) = \mathrm{RatioCut}(A_1, \ldots, A_k)$ you'll end up with the exact same function as Luxburg.
