Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Improving node embedding by a compact neighborhood representation

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

Graph Embedding, a learning paradigm that represents graph vertices, edges, and other semantic information about a graph into low-dimensional vectors, has found wide applications in different machine learning tasks. In the past few years, we have had a plethora of methods centered on graph embedding using different techniques, such as spectral classification, matrix factorization and learning. In this context, choosing the appropriate dimension of the obtained embedding remains a fundamental issue. In this paper, we propose a compact representation of a node’s neighborhood, including attributes and structure, that can be used as an additional dimension to enrich node embedding, to ensure accuracy. This compact representation ensures that both semantic and structural properties of a node’s neighboring-hood are properly captured in a single dimension. Consequently, we improve the learned embedding from state-of-the-art models by introducing the neighborhood compact representation for each node as an additional layer of dimensionality. We leverage on this neighborhood encoding technique and compare with embedding from state-of-the-art models on two learning tasks: node classification and link prediction. The performance evaluation shows that our approach gives a better prediction and classification accuracy in both tasks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Narayanan A, Chandramohan M, Venkatesan R, Chen L, Liu YP, Jaiswal S (2017) graph2vec: Learning distributed representations of graphs. arXiv: abs/1707.05005

  2. Tu K, Cui P, Wang X, Wang F, Zhu W (2017) Structural deep embedding for hyper-networks. arXiv preprint arXiv:1711.10146

  3. Perozzi B, Al-Rfou R, Skiena S (2014) 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

  4. Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 855–864. ACM

  5. Cao S, Lu W, Xu Q (2015) Grarep: Learning graph representations with global structural information. In: Proceedings of the 24th ACM international on conference on information and knowledge management CIKM ’15, pp 891–900. ACM. https://doi.org/10.1145/2806416.2806512

  6. Perozzi B, Kulkarni V, Chen H, Skiena S (2017) Don’t walk, skip!: Online learning of multi-scale network embeddings. In: Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining ASONAM ’17, pp 258–265. ACM. https://doi.org/10.1145/3110025.3110086

  7. Luo G.-X, Li J, Peng H, Yang C, Sun L, Yu P.S, He L (2021) Graph entropy guided node embedding dimension selection for graph neural networks. In: IJCAI

  8. Adhikari B, Zhang Y, Ramakrishnan N, Prakash B.A (2018) Sub2vec: Feature learning for subgraphs. In: PAKDD

  9. Balalau O, Goyal S (2020) Subrank: Subgraph embeddings via a subgraph proximity measure. Adv Knowl Discovery Data Mining 12084:487–498

    Article  Google Scholar 

  10. Gu W, Tandon A, Ahn Y-Y, Radicchi F (2021) Principled approach to the selection of the embedding dimension of networks. Nature Commun. https://doi.org/10.1038/s41467-021-23795-5

    Article  Google Scholar 

  11. Yin Z, Shen Y (2018) On the dimensionality of word embedding. In: NeurIPS

  12. Hoff PD, Raftery AE, Handcock MS (2002) Latent space approaches to social network analysis. J Am Stat Assoc 97:1090–1098

    Article  MathSciNet  MATH  Google Scholar 

  13. Li A, Pan Y (2016) Structural information and dynamical complexity of networks. IEEE Trans Inf Theory 62:3290–3339

    Article  MathSciNet  MATH  Google Scholar 

  14. Zhu X, Lei C, Yu H, Li Y, Gan J, Zhang S (2018) Robust graph dimensionality reduction. In: Proceedings of the 27th international joint conference on artificial intelligence, pp 3257–3263. AAAI Press, ???

  15. Rudolf Fueter GP (1923) Rationale abzählung der gitterpunkte, vierteljschr. Naturforsch. Ges, Zürich 58, 280–386

  16. Nabti C, Seba H (2017) Compact neighborhood index for subgraph queries in massive graphs. arXiv: Databases

  17. Jian T, Meng Q, Mingzhe W, Ming Z, Jun Y, Qiaozhu M (2015) Line: Large-scale information network embedding. In: Proceedings of the 24th international conference on world wide web, pp 1067–1077

  18. Mikolov T, Chen K, Corrado G.S, Dean J (2013) Efficient estimation of word representations in vector space. Comput Res Repository (CoRR). arXiv:1301.3781

  19. Gao M, Chen L, He X, Zhou, A (2018) Bine: Bipartite network embedding. In: Proceedings of the 41st international ACM SIGIR conference on research and development in information retrieval SIGIR ’18, pp 715–724. ACM. https://doi.org/10.1145/3209978.3209987

  20. Ahmed N.K, Rossi R, Lee J.B, Willke T.L, Zhou R, Kong X, Eldardiry H (2018) Learning role-based graph embedding, pp 1–8 arXiv:1802.02896v2

  21. Sheikh N, Kefato ZT, Montresor A (2018) gat2vec: representation learning for attributed graphs. J Comput 101(3):187–209

    MathSciNet  MATH  Google Scholar 

  22. Donnat C, Zitnik M, Hallac D, Leskovec J (2018) Learning structural node embeddings via diffusion wavelets. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1320–1329. ACM

  23. Belkin M, Niyogi P (2002) Laplacian eigenmaps and spectral techniques for embedding and clustering. In: NIPS

  24. Makarov I, Kiselev D, Nikitinsky N, Subelj L (2021) Survey on graph embeddings and their applications to machine learning problems on graphs. PeerJ Comput Sci. 7

  25. Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining KDD ’16, pp 1225–1234. ACM. https://doi.org/10.1145/2939672.2939753

  26. Kipf T, Welling M (2016) Variational graph auto-encoders. In: NIPS workshop on Bayesian deep learning arXiv: 1611.07308

  27. Nathanson M (2015) Cantor polynomials and the Fueter–Pólya theorem. Am Math Monthly 123:1001–1012

    Article  MATH  Google Scholar 

  28. Lisi M (2007) Some remarks on the cantor pairing function. LE MATEMATICHE LXII-Fasc. I, pp 55–65

  29. Ryan R, Nesreen A (2015) The network data repository with interactive graph analytics and visualization. In: AAAI. http://networkrepository.com

  30. Diederik K, Jimmy B (2015) Adam: A method for stochastic optimization. CoRR arXiv: 1412.6980

  31. Gao F, Musial K, Cooper C, Tsoka S (2015) Link prediction methods and their accuracy for different social networks and network metrics. Sci Program 2015:172879–117287913

    Google Scholar 

  32. Yacouby R, Axman D (2020) Probabilistic extension of precision, recall, and f1 score for more thorough evaluation of classification models. In: EVAL4NLP

  33. Lan L, Wang P, Du X, Song K, Tao J, Guan X (2020) Node classification on graphs with few-shot novel labels via meta transformed network embedding. arXiv: abs/2007.02914

Download references

Acknowledgements

This work was supported by the Agence National de la Recherche (ANR) under Grant Agreement No ANR-20-CE23-0002, and Petroleum Technology Development Fund, Nigeria with grant number PTDF/GFC/035.

Funding

For the research leading to these results, Hamida Seba and Mohammed Haddad received funding from Agence National de la Recherche (ANR) under Grant Agreement No ANR-20-CE23-0002, Ikenna Oluigbo was supported by Petroleum Technology Development Fund, Nigeria with grant number PTDF/GFC/035,

Author information

Authors and Affiliations

  1. Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, UMR5205, 69622, Villeurbanne, France

    Ikenna Victor Oluigbo, Hamida Seba & Mohammed Haddad

Authors
  1. Ikenna Victor Oluigbo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hamida Seba
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohammed Haddad
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

The study conception and design was performed by HS. Implementation and analyses were performed by IO and HH. The first draft of the manuscript was written by IO and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Hamida Seba.

Ethics declarations

Conflict of interest

All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.

Ethics approval

All authors declare that they adhere to the ethical principles of the journal

Code availability

The source code of the algorithms and the related data are available in https://gitlab.liris.cnrs.fr/hseba/cnr.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Oluigbo, I.V., Seba, H. & Haddad, M. Improving node embedding by a compact neighborhood representation. Neural Comput & Applic 35, 7035–7048 (2023). https://doi.org/10.1007/s00521-022-08076-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-022-08076-6

Keywords

Search

Navigation