Question about the theorem proof in the paper about graphsage HOT 2 OPEN

We hope to refer to the theorem in our work but get confused about the proof

from graphsage.

Thanks for pointing this out! Indeed, I think there is a minor off-by-one confusion in Lemma 3 that needs to be fixed. In fact, to give all nodes in a 3-hop neighborhood unique colors that would require A^6, since these nodes might be separated by a path of length-6. That said, (unless I am further confused at the moment) what we actually need for the Theorem Proof (equation 10, and bottom of page 18) is just that all nodes in v's 2-hop neighborhood have unique colors, which requires the chromatic number of A^4.

I am in a bit of a rush at the moment, but I'll look over this carefully and make the revisions to the appendix on arxiv. I'll be sure to acknowledge you as well :)

from graphsage.