Response to follow-up questions
Thank you for following up.
>Regarding (4), it would be better to rephrase as it sounds as if (4) was a way to construct \tilde{A}, which is not the intention I understand. Instead (1) is the definition of \tilde{A} when B and C are given.
Thank you for the suggestion. We agree that it would improve clarity to modify (4) by replacing $\mathbf{A} \approx \sigma( \mathbf{X} \mathbf{Y}^\top )$ with $\mathbf{A} \approx \tilde{\mathbf{A}} = \sigma( \mathbf{X} \mathbf{Y}^\top )$. We will make this change and modify the surrounding text appropriately.
>Looking more into Theorem 5.1, this is not actually the main result from Chanpuriya et al (2020); they prove it for the function \sigma(s) = max( 0, min (1,x)) instead of the Heaviside function H(x). So why does Theorem 5.1 hold?
This is a great, precise question. The proof of the theorem in Chanpuriya et al. (2020) is actually in terms of the Heaviside nonlinearity $H(z)$ (they call it ($s(z)$), and they just note how it implies the theorem in terms of the clipping nonlinearity $\sigma(z)$ (see the second paragraph of the proof). We lift the theorem from their work without the extra step of this implication because $H(z)$ is more suitable for this paper; we will note this clearly in the revision.
(The preceding answers the question of why Theorem 5.1 holds, but if you are curious, the implication is as follows: suppose you were given an adjacency matrix $\mathbf{A}$ and found $\mathbf{X},\mathbf{Y}$ such that $H( \mathbf{X} \mathbf{Y}^\top ) = \mathbf{A}$. Then you can scale up the factorization by replacing $\mathbf{X}$ with $\mathbf{X}' = c \cdot \mathbf{X}$ for a large enough positive constant $c$ such that $\sigma( \mathbf{X}' \mathbf{Y}^\top ) = H(\mathbf{X} \mathbf{Y}^\top ) = \mathbf{A}$. This is because, for each entry $z$ in $\mathbf{X} \mathbf{Y}^\top$, either 1) $z$ is negative, in which case $c \cdot z$ is still negative and hence $\sigma(c \cdot z)=H(z)=0$; or 2) $z$ is positive, in which case, for a large enough $c$, you have $c \cdot z \geq 1$ and hence $\sigma(c \cdot z)=H(z)=1$.)
>Thank you for expanding on your notion of a forest. What is the difference between a forest and a tree in your notion? Usually forests are collection of trees, and hence a partition into forests is ambiguous. Your example in the pdf seems to indicate that you equate forest and tree.
We use the standard notion of a forest, which is a union of *disjoint* trees. The example in the PDF shows a partition of the edges of a graph into two forests - call them $F_ \text{blue}$ and $F_ {\text{orange}}$. In this case, since we wanted a small example, $F_ \text{blue}$ and $F_ \text{orange}$ both happen to be trees. This does not mean that the union of $F_ \text{blue}$ and $F_ \text{orange}$ itself is a forest, because the union is exactly the original graph, which has a cycle and hence cannot be a forest. (Note that if the definition of forest was *any* union of trees, rather than a union of *disjoint* trees, then the union would be a forest. This is disallowed because the two trees are touching and not disjoint.) Perhaps this thought will help clarify: Suppose we took the example in the PDF and added two extra nodes which have an edge between them but are disconnected from the rest of the graph. These two extra nodes will definitely demand an extra tree to cover (which will just comprise the single edge between them), but they will not demand an extra forest, because this extra tree will be disjoint from both $F_ \text{blue}$ and $F_ {\text{orange}}$ and hence can be added to either forest.