Network representation learning

Between 2016 and 2019, thanks to the efforts of two PhD stu­den­ts under my super­vi­sion, Zekarias Kefato and Nasrullah Sheikh, I began explo­ring pro­blems com­ple­te­ly outsi­de the distri­bu­ted systems field—namely, machi­ne lear­ning, with a par­ti­cu­lar focus on net­work repre­sen­ta­tion lear­ning. Perhaps it is my aca­de­mic age, but when I say “I began explo­ring,” what I real­ly mean is that Zekarias and Nasrullah did 95% of the work, whi­le my role was main­ly to ensu­re that the papers were easy to read.

Network Representation Learning (NRL) is a method for lear­ning a low-dimen­sio­nal embed­ding of a gra­ph in such a way that its geo­me­tric pro­per­ties are pre­ser­ved. The lear­ned embed­dings can then be applied to various down­stream machi­ne lear­ning tasks, such as clas­si­fi­ca­tion and link prediction.

NRL can leve­ra­ge dif­fe­rent sour­ces of infor­ma­tion in a gra­ph, such as net­work struc­tu­re, attri­bu­tes, and casca­des. These sour­ces may be used inde­pen­den­tly or in com­bi­na­tion, depen­ding on their avai­la­bi­li­ty. Early research relied pri­ma­ri­ly on struc­tu­ral infor­ma­tion becau­se it is always avai­la­ble by default. More recent work sug­gests that incor­po­ra­ting addi­tio­nal infor­ma­tion can lead to bet­ter repre­sen­ta­tions. The main chal­len­ge lies in how to effec­ti­ve­ly inte­gra­te dif­fe­rent sour­ces of infor­ma­tion into the lear­ning process.

Towards this end, we wor­ked on two directions: 

  1. Network repre­sen­ta­tion lear­ning on attri­bu­ted gra­phs and hete­ro­ge­neous gra­phs. GAT2VEC [Computing19] learns a repre­sen­ta­tion of nodes from struc­tu­ral con­text and attri­bu­te con­text obtai­ned from struc­tu­ral and attri­bu­te infor­ma­tion respec­ti­ve­ly. The HETNET2VEC [SNAMS18b] model is for hete­ro­ge­nous net­work repre­sen­ta­tion lear­ning. The model pre­ser­ves the various seman­tic rela­tion­ship among nodes to learn a representation. 
  2. Using casca­de infor­ma­tion for net­work repre­sen­ta­tion lear­ning [MLG17] [MLG17][LOD18] and vira­li­ty pre­dic­tion [SNAMS18a]. In the case of social net­works, the under­ly­ing net­work infor­ma­tion may not be avai­la­ble due to pro­vi­der restric­tions, but we can obser­ve the dif­fu­sion even­ts which are signals of the under­ly­ing net­works. Using casca­des we can use reco­ver the under­ly­ing net­work throu­gh net­work repre­sen­ta­tion learning.

Additional resul­ts have been obtai­ned in the  field of influen­cer detec­tion [MAISON17], net­work inference/link pre­dic­tion  [MOD17]

[MAISON17]   Zekarias T. Kefato and Alberto Montresor. Personalized influen­cer detec­tion: Topic and expo­su­re-con­for­mi­ty aware. In Proc. of the International Workshop on Mining Actionable Insights from Social Networks, MAISoN’17. ACM, February 2017. [PDF], [Bibtex].

[MLG17]   Zekarias T. Kefato, Nasrullah Sheikh, and Alberto Montresor. Deepinfer: Diffusion net­work infe­ren­ce throu­gh repre­sen­ta­tion lear­ning. In Proc. of the 13th International Workshop on Mining and Learning With Graphs, MLG’17. ACM, August 2017. [PDF], [Bibtex].

[MOD17]   Zekarias T. Kefato, Nasrullah Sheikh, and Alberto Montresor. Mineral: Multi-modal net­work repre­sen­ta­tion lear­ning. In Proc. of the 3rd International Conference on Machine Learning, Optimization and Big Data, MOD’17. ACM, September 2017. [PDF], [Bibtex].

[LOD18]   Zekarias T. Kefato, Nasrullah Sheikh, and Alberto Montresor. REFINE: Representation lear­ning from dif­fu­sion even­ts. In Proc. of the 4th Conference on Machine Learning, Optimization and Data scien­ce, LOD’18. Springer, September 2018. [PDF], [Bibtex].

[SNAMS18a]   Zekarias T. Kefato, Nasrullah Sheikh, Leila Bahri, Amira Soliman, Alberto Montresor, and Sarunas Girdzijauskas. CAS2VEC: net­work-agno­stic casca­de pre­dic­tion in onli­ne social net­works. In Proc. of the 5th International Conferenceon Social Networks Analysis, Management and Security (SNAMS 2018), pages 72–79. IEEE, October 2018. [PDF], [Bibtex].

[SNAMS18b]   Nasrullah Sheikh, Zekarias T. Kefato, and Alberto Montresor. Semi-super­vi­sed hete­ro­ge­neous infor­ma­tion net­work embed­ding for node clas­si­fi­ca­tion using 1D-CNN. In Proc. of the 5th International Conference on Social Networks Analysis, Management and Security (SNAMS 2018), pages 177–181. IEEE, October 2018. [PDF], [Bibtex].

[Computing19]   Nasrullah Sheikh, Zekarias Kefato, and Alberto Montresor. GAT2VEC: Representation lear­ning for attri­bu­ted gra­phs. Computing, 101(3):187–209, 2019. [PDF], [Bibtex].

[CN19]   Nasrullah Sheikh, Zekarias T. Kefato, and Alberto Montresor. A sim­ple approach to attri­bu­ted gra­ph embed­ding via enhan­ced autoen­co­der. In Proceedings of the Eighth Int. Conference on Complex Networks and Their Applications (COMPLEX NETWORKS 2019), volu­me 881 of Studies in Computational Intelligence, pages 797–809. Springer, December 2019.  [PDF], [Bibtex]

[WWW21]   Zekarias T. Kefato, Sarunas Girdzijauskas, Nasrullah Sheikh, and Alberto Montresor. Dynamic embed­dings for inte­rac­tion pre­dic­tion. In Jure Leskovec, Marko Grobelnik, Marc Najork, Jie Tang, and Leila Zia, edi­tors, The Web Conference 2021, WWW’21, pages 1609–1618. ACM / IW3C2, April 2021. [PDF], [Bibtex].

Scroll to top