Graph node representation learning is a central problem in social network analysis, aiming to learn the vector representation for each node in a graph. The key problem is how to model the dependence of each node to its neighbor nodes since the neighborhood can uniquely characterize a graph. Most existing approaches rely on defining the specific neighborhood dependence as the computation mechanism of representations, which may exclude important subtle structures within the graph and dependence among neighbors. Instead, we propose a novel graph node embedding method (namely P 2 IR) via developing a novel notion, namely partial permutation invariant set function to learn those subtle structures. Our method can 1) learn an arbitrary form of the representation function from the neighborhood, without losing any potential dependence structures, 2) automatically decide the significance of neighbors at different distances, and 3) be applicable to both homogeneous and heterogeneous graph embedding, which may contain multiple types of nodes. Theoretical guarantee for the representation capability of our method has been proved for general homogeneous and heterogeneous graphs. Evaluation results on benchmark data sets show that the proposed P 2 IR outperforms the state-of-the-art approaches on producing node vectors for classification tasks.
The authors introduce the idea of a partial permutation invariant set function and use this to learn node embeddings. The paper is well-written and the discussion is quite easy to follow along. The paper also introduces some interesting concepts like a partial permutation invariant set function. However, I find that some of the paper's main claims can be further backed up by more experiments.
The paper is well-written. The authors evaluate their approach on a large number of real-world homogeneous and heterogeneous graphs. Furthermore, they show the stability of their method by showing consistently good results even when training set size is varied. Defined the notion of a partial permutation invariant set function and provided theoretical guarantees pertaining to this.
One of the strengths of the proposed method is its ability to "automatically decide the significance of nodes at different distances." The authors devote a good portion of their paper to talk about this. However, a recent paper published in NIPS '18 [1] with a pre-print available much earlier solves this problem by applying attention over powers of a transition matrix. The authors should talk about [1] and ideally compare against them.
I feel that a lot of the authors main claims can be strengthened further if more experiments were shown to back these up. What I mean to say is, it would be nice to see some other experiments apart from just classification performance. To compare with [1], for instance, they show link prediction/classification results but on top of these they also show that their method may choose very different "neighborhoods" to attend to.
The authors gave a fairly comprehensive review of related literature (which was good!) and they mentioned that "most existing methods either explicitly or implicitly restrict the dependence form of each node to its neighbors and also the depth of neighbors." I feel another approach they should compare against which does not seem to have this problem is [2] since the method learns "role-based" embeddings which are more dependent on structure rather than proximity.
The paper in its current form is fairly good. If comparison can be made against [1] & [2] and some additional experiments can be added, the quality of the paper can be improved further.
[1] Watch Your Step: Learning Node Embeddings via Graph Attention. Abu-El-Haija et al. In Proc. of NIPS 2018.
[2] Higher-Order Network Representation Learning. Rossi et al. In Proc. of WWW 2018.
There are some minor errors in the paper:
Table 1 in page 7 seems to be an error. It's an empty table and it is not referred to anywhere in the paper.
The format of some references needs double-checking. For example,
"Jian Tang, Meng Qu, and Qiaozhu Mei. Pte: Predictive text embedding through large-scale heterogeneous text networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1165–1174. ACM, 2015a."
(1) "21th" should be "21st".
"Shiyu Chang, Wei Han, Jiliang Tang, Guo-Jun Qi, Charu C Aggarwal, and Thomas S Huang. Heterogeneous network embedding via deep architectures. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 119–128. ACM, 2015."
(2) "21th" should be "21st".
"Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pp. 1105–1114, 2016."
(3) "22Nd" should be "22nd"
"Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’16, pp. 1225–1234, 2016."
(4) "22Nd" should be "22nd"
"Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701–710. ACM, 2014"
(5) "international conference on Knowledge discovery and data mining" should be "International Conference on Knowledge Discovery and Data Mining"
"Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pp. 3111–3119, 2013."
(6) "Advances in neural information processing systems" should be "Advances in Neural Information Processing Systems"
"Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067–1077. International World Wide Web Conferences Steering Committee, 2015b."
(7) "International World Wide Web Conferences Steering Committee" should be removed.
The 3rd sentence in the abstract is a little bit too long. It would be better if the authors could break the sentence into shorter ones. Here is the sentence: "While most existing approaches rely on defining the specific neighborhood dependence as the computation mechanism of representations, which may exclude important subtle structures within the graph and dependence among neighbors, we propose a novel graph node embedding method (namely P2IR) via developing a novel notion, namely partial permutation invariant set function."