Leonardo F.R. Ribeiro
Daniel R. Figueiredo
ABSTRACT
Structural identity is a concept of symmetry in which network nodes are identified according to the network structure and their relationship to other nodes. Structural identity has been studied in theory and practice over the past decades, but only recently has it been addressed with representational learning techniques. This work presents struc2vec, a novel and flexible framework for learning latent representations for the structural identity of nodes. struc2vec uses a hierarchy to measure node similarity at different scales, and constructs a multilayer graph to encode structural similarities and generate structural context for nodes. Numerical experiments indicate that state-of-the-art techniques for learning node representations fail in capturing stronger notions of structural identity, while struc2vec exhibits much superior performance in this task, as it overcomes limitations of prior approaches. As a consequence, numerical experiments indicate that struc2vec improves performance on classification tasks that depend more on structural identity.
Supplemental Material
- Nir Atias and Roded Sharan. 2012. Comparative analysis of protein networks: hard problems, practical solutions. Commun. ACM 55 (2012). Google Scholar
Digital Library
- Yoshua Bengio, Rejean Ducharme, Pascal Vincent, and Christian Jauvin. 2003. A Neural Probabilistic Language Model. JMLR (2003).Google ScholarDigital Library
- V Blondel, A Gajardo, M Heymans, P Senellart, and P Van Dooren. 2004. A measure of similarity between graph vertices: Applications to synonym extraction and web searching. SIAM review (2004).Google Scholar
- Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2016. Deep Neural Networks for Learning Graph Representations. In AAAI.Google Scholar
- F Fouss, A Pirotte, J Renders, and M Saerens. 2007. Random-Walk Computation of Similarities Between Nodes of a Graph with Application to Collaborative Recommendation. IEEE Trans. on Knowl. and Data Eng. (2007).Google ScholarDigital Library
- Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In ACM SIGKDD.Google Scholar
- K Henderson, B Gallagher, T Eliassi-Rad, H Tong, S Basu, L Akoglu, D Koutra, C Faloutsos, and L Li. 2012. Rolx: structural role extraction & mining in large graphs. In ACM SIGKDD. Google ScholarDigital Library
- Jon M Kleinberg. 1999. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM)(1999).Google Scholar
- Elizabeth A Leicht, Petter Holme, and Mark EJ Newman. 2006. Vertex similarity in networks. Physical Review E 73 (2006).Google Scholar
- Jure Leskovec and Julian J Mcauley. 2012. Learning to discover social circles in ego networks. In NIPS.Google Scholar
- Francois Lorrain and Harrison C White. 1971. Structural equivalence of individuals in social networks. The Journal of mathematical sociology 1 (1971).Google Scholar
- Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient Estimation of Word Representations in Vector Space. In ICLR Workshop.Google Scholar
- T Mikolov, I Sutskever, K Chen, G Corrado, and J Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality. In NIPS.Google Scholar
- A Narayanan, M Chandramohan, L Chen, Y Liu, and S Saminathan. 2016. subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs. In Workshop on Mining and Learning with Graphs.Google Scholar
- Pedram Pedarsani and Matthias Grossglauser. 2011. On the privacy of anonymized networks. In ACM SIGKDD.Google Scholar
- Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. In ACM SIGKDD.Google Scholar
- Narciso Pizarro. 2007. Structural Identity and Equivalence of Individuals in Social Networks Beyond Duality. International Sociology 22 (2007).Google Scholar
- T Rakthanmanon, B Campana, A Mueen, G Batista, B Westover, Q Zhu, J Zakaria, and E Keogh. 2013. Addressing big data time series: Mining trillions of time series subsequences under dynamic time warping. ACM TKDD (2013).Google Scholar
- Lee Douglas Sailer. 1978. Structural equivalence: Meaning and definition, computation and application. Social Networks (1978).Google Scholar
- S Salvador and P Chan. 2004. FastDTW: Toward accurate dynamic time warping in linear time and space. In Workshop on Min. Temp. and Seq. Data, ACM SIGKDD.Google Scholar
- N Shervashidze, P Schweitzer, E van Leeuwen, K Mehlhorn, and K Borgwardt. 2011. Weisfeiler-Lehman Graph Kernels. JMLR (2011).Google Scholar
- R Singh, J Xu, and B Berger. 2008. Global alignment of multiple protein interaction networks with application to functional orthology detection. PNAS(2008).Google Scholar
- Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In WWW.Google ScholarDigital Library
- Daixin Wang, Peng Cui, and Wenwu Zhu. 2016. Structural Deep Network Embedding. In ACM SIGKDD. Google ScholarDigital Library
- Wayne W Zachary. 1977. An information flow model for conflict and fission in small groups. Journal of anthropological research (1977).Google Scholar
- Laura A Zager and George C Verghese. 2008. Graph similarity scoring and matching. Applied mathematics letters (2008).Google Scholar
Index Terms
- struc2vec: Learning Node Representations from Structural Identity
Recommendations
A network representation learning method based on topology
AbstractIn the network, nodes with similar neighborhood topology often have similar functions and play similar roles. Accurately identifying the role of nodes is the key to our understanding of the network and then facilitates the completion ...
node2vec: Scalable Feature Learning for Networks
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data MiningPrediction tasks over nodes and edges in networks require careful effort in engineering features used by learning algorithms. Recent research in the broader field of representation learning has led to significant progress in automating prediction by ...
Embedding Node Structural Role Identity Using Stress Majorization
CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge ManagementNodes in networks may have one or more functions that determine their role in the system. As opposed to local proximity, which captures the local context of nodes, the role identity captures the functional "role" that nodes play in a network, such as ...
Comments