Abstract
Graph data with uncertain connections between entities is commonly represented using uncertain graphs. This paper tackles the challenge of graph embedding within such uncertain attribute graphs. Current graph embedding techniques are typically oriented towards deterministic graphs, or uncertain graphs that lack attribute data. Furthermore, the majority of studies on uncertain graph learning simply adapt conventional algorithms for deterministic graphs to handle uncertainty, leading to compromised computational efficiency. To address these issues, we introduce an optimized embedding framework UAGE for uncertain attribute graphs. In UAGE, nodes are represented within a Gaussian distribution space to learn node attributes. We also propose a Probability Similarity Value (PSV) to manage relationship uncertainty and ensure that nodes with higher-order similar structures are located more closely in the latent space. Real-world dataset experiments confirm that UAGE surpasses contemporary methods in performance for downstream tasks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Banerjee, S.: A survey on mining and analysis of uncertain graphs. Knowl. Inf. Syst. 64, 1–37 (2022)
Bojchevski, A., Günnemann, S.: Deep gaussian embedding of graphs: unsupervised inductive learning via ranking. In: ICLR (2018)
Boldi, P., Bonchi, F., Gionis, A., Tassa, T.: Injecting uncertainty in graphs for identity obfuscation. arXiv preprint arXiv:1208.4145 (2012)
Dallachiesa, M., Aggarwal, C., Palpanas, T.: Node classification in uncertain graphs. In: SSDBM (2014)
Danesh, M., Dorrigiv, M., Yaghmaee, F.: DGCU: a new deep directed method based on gaussian embedding for clustering uncertain graphs. Comput. Electr. Eng. 101, 108066 (2022)
Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: SIGKDD, pp. 855–864 (2016)
Halim, Z., Waqas, M., Hussain, S.F.: Clustering large probabilistic graphs using multi-population evolutionary algorithm. Inf. Sci. 317, 78–95 (2015)
Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
Hettige, B., Li, Y.-F., Wang, W., Buntine, W.: Gaussian embedding of large-scale attributed graphs. In: Borovica-Gajic, R., Qi, J., Wang, W. (eds.) ADC 2020. LNCS, vol. 12008, pp. 134–146. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-39469-1_11
Hong, E.L., et al.: Gene ontology annotations at SGD: new data sources and annotation methods. Nucleic Acids Res. 36(suppl_1), D577–D581 (2007)
Hu, J., Cheng, R., Huang, Z., Fang, Y., Luo, S.: On embedding uncertain graphs. In: CIKM, pp. 157–166 (2017)
Hussain, S.F., Maab, I.: Clustering probabilistic graphs using neighbourhood paths. Inf. Sci. 568, 216–238 (2021)
Kipf, T.N., Welling, M.: Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016)
Kollios, G., Potamias, M., Terzi, E.: Clustering large probabilistic graphs. TKDE 25(2), 325–336 (2011)
Kumar, S., Mallik, A., Khetarpal, A., Panda, B.: Influence maximization in social networks using graph embedding and graph neural network. Inf. Sci. 607, 1617–1636 (2022)
Laurens, V.D.M., Hinton, G.: Visualizing data using t-SNE. J. Mach. Learn. Res. 9(2605), 2579–2605 (2008)
Liang, Y., Hu, T., Zhao, P.: Efficient structural clustering in large uncertain graphs. In: ICDE, pp. 1966–1969 (2020)
Liu, H., Zhang, X., Zhang, X., Li, Q., Wu, X.M.: RPC: representative possible world based consistent clustering algorithm for uncertain data. Comput. Commun. 176, 128–137 (2021)
Mikolov, T., Sutskever, I., Chen, K., Corrado, G., Dean, J.: Distributed representations of words and phrases and their compositionality. In: NIPS, pp. 3111–3119 (2013)
Nepusz, T., Yu, H., Paccanaro, A.: Detecting overlapping protein complexes in protein-protein interaction networks. Nat. Methods 9(5), 471–472 (2012)
Peng, H., et al.: Dynamic graph convolutional network for long-term traffic flow prediction with reinforcement learning. Inf. Sci. 578, 401–416 (2021)
Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: SIGKDD, pp. 701–710 (2014)
Potamias, M., Bonchi, F., Gionis, A., Kollios, G.: K-nearest neighbors in uncertain graphs. Proc. VLDB Endowment 3(1–2), 997–1008 (2010)
Qiu, Y.X., et al.: Efficient structural clustering on probabilistic graphs. TKDE 31(10), 1954–1968 (2019)
Sun, G., Zhang, X.: A novel framework for node/edge attributed graph embedding. In: Advances in Knowledge Discovery and Data Mining, pp. 169–182 (2019)
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: Line: large-scale information network embedding. In: WWW (2015)
Vilnis, L., McCallum, A.: Word representations via gaussian embedding. arXiv preprint arXiv:1412.6623 (2014)
Wang, D., Cui, P., Zhu, W.: Structural deep network embedding. In: SIGKDD, pp. 1225–1234 (2016)
Wang, X., Bo, D., Shi, C., Fan, S., Ye, Y., Yu, P.S.: A survey on heterogeneous graph embedding: methods, techniques, applications and sources. IEEE Trans. Big Data 1–1 (2022)
Xu, M.: Understanding graph embedding methods and their applications. SIAM Rev. 63(4), 825–853 (2021)
Yu, W., Lin, X., Zhang, W., Pei, J., McCann, J.: Simrank*: effective and scalable pairwise similarity search based on graph topology. VLDB J. 28, 401–426 (2019)
Zhu, D., Cui, P., Wang, D., Zhu, W.: Deep variational network embedding in Wasserstein space. In: SIGKDD, pp. 2827–2836 (2018)
Acknowledgement
The authors would like to thank the support from the National Natural Science Foundation of China under Grant (No. 62172372), the Natural Science Foundation of Zhejiang Province, China (No. LZ21F030001, No. LQ22F020033), and the Exploratory Research project of Zhejiang Lab (No. 2022KG0AN01).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Jiang, T., Yu, T., Qiao, X., Zhang, J. (2023). An Efficient Embedding Framework for Uncertain Attribute Graph. In: Strauss, C., Amagasa, T., Kotsis, G., Tjoa, A.M., Khalil, I. (eds) Database and Expert Systems Applications. DEXA 2023. Lecture Notes in Computer Science, vol 14147. Springer, Cham. https://doi.org/10.1007/978-3-031-39821-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-031-39821-6_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-39820-9
Online ISBN: 978-3-031-39821-6
eBook Packages: Computer ScienceComputer Science (R0)