research-article

Open access

Semi-Supervised Embedding of Attributed Multiplex Networks

Authors:

Claudia PlantAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 578 - 587

https://doi.org/10.1145/3543507.3583485

Published: 30 April 2023 Publication History

All formats PDF

Abstract

Complex information can be represented as networks (graphs) characterized by a large number of nodes, multiple types of nodes, and multiple types of relationships between them, i.e. multiplex networks. Additionally, these networks are enriched with different types of node features.

We propose a Semi-supervised Embedding approach for Attributed Multiplex Networks (SSAMN), to jointly embed nodes, node attributes, and node labels of multiplex networks in a low dimensional space. Network embedding techniques have garnered research attention for real-world applications. However, most existing techniques solely focus on learning the node embeddings, and only a few learn class label embeddings. Our method assumes that we have different classes of nodes and that we know the class label of some, very few nodes for every class. Guided by this type of supervision, SSAMN learns a low-dimensional representation incorporating all information in a large labeled multiplex network. SSAMN integrates techniques from Spectral Embedding and Homogeneity Analysis to improve the embedding of nodes, node attributes, and node labels. Our experiments demonstrate that we only need very few labels per class in order to have a final embedding that preservers the information of the graph. To evaluate the performance of SSAMN, we run experiments on four real-world datasets. The results show that our approach outperforms state-of-the-art methods for downstream tasks such as semi-supervised node classification and node clustering.

Supplemental Material

PDF File

Appendix

Download
448.60 KB

References

[1]

Saïd Amghibech. 2003. Eigenvalues of the Discrete p-Laplacian for Graphs. Ars Comb. 67 (2003).

[2]

Yunsheng Bai, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. 2019. Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (Macao, China) (IJCAI’19). AAAI Press, 1988–1994.

[3]

Mikhail Belkin and Partha Niyogi. 2001. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In NIPS. MIT Press, 585–591.

[4]

Ginestra Bianconi. 2018. Multilayer Networks: Structure and Function. Oxford University Press. https://doi.org/10.1093/oso/9780198753919.001.0001

[5]

Thomas Bühler and Matthias Hein. 2009. Spectral Clustering Based on the Graph P-Laplacian. In Proceedings of the 26th Annual International Conference on Machine Learning (Montreal, Quebec, Canada) (ICML ’09). Association for Computing Machinery, New York, NY, USA, 81–88. https://doi.org/10.1145/1553374.1553385

[6]

Leonid A. Bunimovich, Chi-Jen Wang, Seokjoo Chae, and Benjamin Z. Webb. 2018. Uncovering Hierarchical Structure in Social Networks Using Isospectral Reductions. In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). 1199–1206. https://doi.org/10.1109/ASONAM.2018.8508506

[7]

Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. 2019. Representation Learning for Attributed Multiplex Heterogeneous Network(KDD ’19). 1358–1368.

[8]

Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. 2019. A Survey on Network Embedding. IEEE Transactions on Knowledge and Data Engineering 31, 5 (2019), 833–852. https://doi.org/10.1109/TKDE.2018.2849727

[9]

Jan de Leeuw and Patrick Mair. 2009. Gifi Methods for Optimal Scaling in R: The Package homals. Journal of Statistical Software, Articles 31, 4 (2009), 1–21.

[10]

Francisco Aparecido Rodrigues Yamir Moreno Emanuele Cozzo, Guilherme Ferraz de Arruda. 2018. Multiplex Networks. Springer Cham. https://doi.org/10.1007/978-3-319-92255-3

[11]

Guoji Fu, Peilin Zhao, and Yatao Bian. 2022. p-Laplacian Based Graph Neural Networks. In Proceedings of the 39th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (Eds.). PMLR, 6878–6917. https://proceedings.mlr.press/v162/fu22e.html

[12]

Aditya Grover and Jure Leskovec. 2016. Node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (San Francisco, California, USA) (KDD ’16). Association for Computing Machinery, New York, NY, USA, 855–864. https://doi.org/10.1145/2939672.2939754

[13]

Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. 2020. Implicit Graph Neural Networks. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.). Vol. 33. Curran Associates, Inc., 11984–11995.

[14]

Lawrence Hubert and Phipps Arabie. 1985. Comparing partitions. Journal of Classification 2 (12 1985), 193–218. Issue 1. https://doi.org/10.1007/BF01908075

[15]

Baoyu Jing, Chanyoung Park, and Hanghang Tong. 2021. HDMI: High-order Deep Multiplex Infomax. Proceedings of the Web Conference 2021 (Apr 2021). https://doi.org/10.1145/3442381.3449971

[16]

I. T. Jolliffe. 1986. Principal Components in Regression Analysis. Springer New York, New York, NY, 129–155.

[17]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR).

[18]

Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. 2021. Rethinking Graph Transformers with Spectral Attention. In Advances in Neural Information Processing Systems, A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (Eds.). https://openreview.net/forum¿id=huAdB-Tj4yG

[19]

Weiyi Liu, Pin-yu Chen, Sailung Yeung, Toyotaro Suzumura, and Lingli Chen. 2017. Principled Multilayer Network Embedding. In 2017 IEEE International Conference on Data Mining Workshops (ICDMW). 134–141. https://doi.org/10.1109/ICDMW.2017.23

[20]

Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. 2022. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022. 1392–1403.

[21]

Zhijun Liu, Chao Huang, Yanwei Yu, Baode Fan, and Junyu Dong. 2020. Fast Attributed Multiplex Heterogeneous Network Embedding. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management (Virtual Event, Ireland) (CIKM ’20). Association for Computing Machinery, New York, NY, USA, 995–1004. https://doi.org/10.1145/3340531.3411944

[22]

Dijun Luo, Heng Huang, Chris Ding, and Feiping Nie. 2010. On the eigenvectors of p-Laplacian. Machine Learning 81 (2010). https://doi.org/10.1007/s10994-010-5201-z

[23]

Dongsheng Luo, Jingchao Ni, Suhang Wang, Yuchen Bian, Xiong Yu, and Xiang Zhang. 2020. Deep Multi-Graph Clustering via Attentive Cross-Graph Association. In Proceedings of the 13th International Conference on Web Search and Data Mining (Houston, TX, USA) (WSDM ’20). Association for Computing Machinery, New York, NY, USA, 393–401. https://doi.org/10.1145/3336191.3371806

[24]

Dongsheng Luo, Jingchao Ni, Suhang Wang, Yuchen Bian, Xiong Yu, and Xiang Zhang. 2020. Deep Multi-Graph Clustering via Attentive Cross-Graph Association(WSDM ’20). Association for Computing Machinery, 393–401.

[25]

Dominik Mautz, Wei Ye, Claudia Plant, and Christian Böhm. 2020. Non-Redundant Subspace Clusterings with Nr-Kmeans and Nr-DipMeans. ACM Trans. Knowl. Discov. Data 14, 5, Article 55 (jun 2020), 24 pages. https://doi.org/10.1145/3385652

[26]

Anasua Mitra, Priyesh Vijayan, Ranbir Sanasam, Diganta Goswami, Srinivasan Parthasarathy, and Balaraman Ravindran. 2021. Semi-Supervised Deep Learning for Multiplex Networks. Association for Computing Machinery, 1234–1244.

[27]

Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. 2022. Simple Unsupervised Graph Representation Learning. Proceedings of the AAAI Conference on Artificial Intelligence 36, 7 (Jun. 2022), 7797–7805. https://doi.org/10.1609/aaai.v36i7.20748

[28]

Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. 2001. On Spectral Clustering: Analysis and an algorithm. In NIPS’01. 849–856.

[29]

Jingchao Ni, Shiyu Chang, Xiao Liu, Wei Cheng, Haifeng Chen, Dongkuan Xu, and Xiang Zhang. 2018. Co-Regularized Deep Multi-Network Embedding. In Proceedings of the 2018 World Wide Web Conference (Lyon, France) (WWW ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 469–478. https://doi.org/10.1145/3178876.3186113

[30]

Chanyoung Park, D. Kim, Jiawei Han, and Hwanjo Yu. 2020. Unsupervised Attributed Multiplex Network Embedding. In AAAI.

[31]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, New York, USA) (KDD ’14). ACM, New York, NY, USA, 701–710. https://doi.org/10.1145/2623330.2623732

[32]

Sudeep Pushpakom, Francesco Iorio, Patrick A. Eyers, K. Jane Escott, Shirley Hopper, Andrew Wells, Andrew Doig, Tim Guilliams, Joanna Latimer, Christine McNamee, Alan Norris, Philippe Sanseau, David Cavalla, and Munir Pirmohamed. 2019. Drug repurposing: progress, challenges and recommendations. Nature Reviews Drug Discovery 18 (2019). https://doi.org/10.1038/nrd.2018.168

[33]

David Hilbert (auth.) Richard Courant. 1968. Methoden der Mathematischen Physik I. Springer Berlin Heidelberg.

[34]

Camilo Ruiz, Marinka Zitnik, and Jure Leskovec. 2021. Identification of disease treatment mechanisms through the multiscale interactome. Nature Communications 12 (2021). https://doi.org/10.1038/s41467-021-21770-8

[35]

Ylli Sadikaj, Yllka Velaj, Sahar Behzadi, and Claudia Plant. 2021. Spectral Clustering of Attributed Multi-Relational Graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (Virtual Event, Singapore) (KDD ’21). Association for Computing Machinery, New York, NY, USA, 1431–1440. https://doi.org/10.1145/3447548.3467381

[36]

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-Scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web (Florence, Italy) (WWW ’15). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1067–1077. https://doi.org/10.1145/2736277.2741093

[37]

L.J.P. van der Maaten and G.E. Hinton. 2008. Visualizing High-Dimensional Data Using t-SNE. Journal of Machine Learning Research 9 (2008), 2579–2605.

[38]

Barch DM Behrens TE Yacoub E Ugurbil K Van Essen DC, Smith SM. 2013. The WU-Minn Human Connectome Project: an overview. Neuroimage (2013). https://doi.org/10.1016/j.neuroimage.2013.05.041

[39]

Petar Veličković, Wiliam Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2019. Deep Graph Infomax.

[40]

Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, and Philip S. Yu. 2022. A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources. IEEE Transactions on Big Data (2022), 1–1. https://doi.org/10.1109/TBDATA.2022.3177455

[41]

Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019. Heterogeneous Graph Attention Network(WWW ’19). 2022–2032.

[42]

Wei Ye, Sebastian Goebl, Claudia Plant, and Christian Böhm. 2016. FUSE: Full Spectral Clustering. In KDD. ACM, 1985–1994.

[43]

Wei Ye, Linfei Zhou, Xin Sun, Claudia Plant, and Christian Böhm. 2017. Attributed Graph Clustering with Unimodal Normalized Cut. In ECML/PKDD.

[44]

Lorenzo Zangari, Roberto Interdonato, Antonio Calió, and Andrea Tagarelli. 2021. Graph convolutional and attention models for entity classification in multilayer networks. Applied Network Science 6 (2021). https://doi.org/10.1007/s41109-021-00420-4

[45]

Hongming Zhang, Liwei Qiu, Lingling Yi, and Yangqiu Song. 2018. Scalable Multiplex Network Embedding. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18. International Joint Conferences on Artificial Intelligence Organization, 3082–3088. https://doi.org/10.24963/ijcai.2018/428

[46]

Zhen Zhang, Hongxia Yang, Jiajun Bu, Sheng Zhou, Pinggang Yu, Jianwei Zhang, Martin Ester, and Can Wang. 2018. ANRL: Attributed Network Representation Learning via Deep Neural Networks. In Proc. of IJCAI’18. ijcai.org, 3155–3161.

[47]

Jianan Zhao, Xiao Wang, Chuan Shi, Zekuan Liu, and Yanfang Ye. 2020. Network Schema Preserving Heterogeneous Information Network Embedding. In IJCAI’20, Christian Bessiere (Ed.). 1366–1372. https://doi.org/10.24963/ijcai.2020/190 Main track.

[48]

Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020. Graph neural networks: A review of methods and applications. AI Open 1 (2020), 57–81. https://doi.org/10.1016/j.aiopen.2021.01.001

[49]

Marinka Zitnik, Monica Agrawal, and Jure Leskovec. 2018. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics 34, 13 (06 2018), i457–i466.

Cited By

Shen ZHe HKang ZCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Balanced Multi-Relational Graph ClusteringProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681325(4120-4128)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681325
Abdous KMrabah NBouguessa MSerra ESpezzano F(2024)A Geometric Perspective for High-Dimensional Multiplex GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679541(4-13)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679541

Index Terms

Semi-Supervised Embedding of Attributed Multiplex Networks
1. Computing methodologies
  1. Machine learning
    1. Machine learning algorithms
2. Networks
  1. Network properties

Recommendations

Label Informed Attributed Network Embedding
WSDM '17: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining

Attributed network embedding aims to seek low-dimensional vector representations for nodes in a network, such that original network topological structure and node attribute proximity can be preserved in the vectors. These learned representations have ...
Semi-Supervised Deep Learning for Multiplex Networks
KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Multiplex networks are complex graph structures in which a set of entities are connected to each other via multiple types of relations, each relation representing a distinct layer. Such graphs are used to investigate many complex biological, social, and ...
Attributed network embedding via subspace discovery
Abstract
Network embedding aims to learn a latent, low-dimensional vector representations of network nodes, effective in supporting various network analytic tasks. While prior arts on network embedding focus primarily on preserving network topology ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Data Availability

Appendix https://dl.acm.org/doi/10.1145/3543507.3583485#SSAMN_CameraReady_WWW23_Appendix.pdf

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
600
Total Downloads

Downloads (Last 12 months)332
Downloads (Last 6 weeks)43

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shen ZHe HKang ZCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Balanced Multi-Relational Graph ClusteringProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681325(4120-4128)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681325
Abdous KMrabah NBouguessa MSerra ESpezzano F(2024)A Geometric Perspective for High-Dimensional Multiplex GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679541(4-13)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679541

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents