We present network embedding algorithms that capture information about a node from the local distribution over node attributes around it, as observed over random walks following an approach similar to Skip-gram. Observations from neighborhoods of different sizes are either pooled (AE) or encoded distinctly in a multiscale approach (MUSAE). Capturing attribute-neighborhood relationships over multiple scales is useful for a diverse range of applications, including latent feature identification across disconnected networks with similar attributes. We prove theoretically that matrices of node-feature pointwise mutual information are implicitly factorized by the embeddings. Experiments show that our algorithms are robust, computationally efficient and outperform comparable models on social, web and citation network datasets.
Figure 1: Phenomena affecting and inspiring the design of the multi-scale attributed network embedding procedure. In Figure 1a attributed nodes D and G have the same feature set and their nearest neighbours also exhibit equivalent sets of features, whereas features at higher order neighbourhoods differ. Figure 1b shows that as the order of neighbourhoods considered (r) increases, the product of the adjacency matrix power and the feature matrix becomes less sparse. This suggests that an implicit decomposition method would be computationally beneficial.
Our key contributions are:
1. to introduce the first Skip-gram style embedding algorithms that consider attribute distributions over local neighborhoods, both pooled (AE) and multi-scale (MUSAE), and their counterparts that attribute distinct features to each node (AE-EGO and MUSAE-EGO);
2. to theoretically prove that their embeddings approximately factorize PMI matrices based on the product of an adjacency matrix power and node-feature matrix;
3. to show that popular network embedding methods DeepWalk (Perozzi et al., 2014) and Walklets (Perozzi et al., 2017) are special cases of our AE and MUSAE;
4. we show empirically that AE and MUSAE embeddings enable strong performance at regression, classification, and link prediction tasks for real-world networks (e.g. Wikipedia and Facebook), are computationally scalable and enable transfer learning between networks.
We provide reference implementations of AE and MUSAE, together with the datasets used for evaluation at https://github.com/iclr2020/MUSAE.
This paper introduces Skip-gram style embedding algorithms that consider attribute distributions over local neighborhoods. Algorithm 1 and 2 shows that in fact they propagate randomly selected node features to neighbors. The reviewer doesn’t think this random-walk way for selecting node feature is appropriate.  Node features describe node content. The features of neighboring nodes may complement each other. However, there is no benefit to select random features and then propagate, given that there already many approaches smartly combining node content in neighborhood. 
The proof part follows Qiu et al (2018). But it is unclear, why c^{−1}A is the stationary joint distribution over consecutive nodes p(wj , wj+1).  and c^{−1}DF describes the stationary joint distribution p(f,wj) over nodes and features. There needs more explanation. 
The Remark 1 and 2 discuss the case AE with F=I_|V|,  which is in fact the case when there is no node attributes. In this case, the AE process naturally goes back to plain network embedding, where DeepWalk and WalkLets are proposed for. Therefore, these remarks are done by Qiu et al (2018) already, not make no much new contribution here. 
Figure 2 shows that the presented two approaches just slightly better or equivalent, or sometimes worse than baseline methods. As mentioned earlier, it is not beneficial to randomly select features to propagate. 
The experiments presented in Section 5.2 evaluate whether the learned embedding can be used for label inference in a different graph. But it is unknown how success the transferring is. There is no F1-score of a solution that does embedding of the target network itself independently, and then classify the target network nodes.