Graph Embedding via Graph Summarization

被引:5
作者
Yang, Jingyanning [1 ]
You, Jinguo [1 ,2 ]
Wan, Xiaorong [1 ]
机构
[1] Kunming Univ Sci & Technol, Fac Informat Engn & Automat, Kunming 650500, Yunnan, Peoples R China
[2] Kunming Univ Sci & Technol, Yunnan Key Lab Artificial Intelligence, Kunming 650500, Yunnan, Peoples R China
关键词
Graph embedding; graph summarization; graph coarsening; random walks;
D O I
10.1109/ACCESS.2021.3067901
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Graph representation learning aims to represent the structural and semantic information of graph objects as dense real value vectors in low dimensional space by machine learning. It is widely used in node classification, link prediction, and recommendation systems. However, directly computing the embeddings for original graphs is prohibitively inefficient, especially for large-scale graphs. To address this issue, we present the GSE (Graph Summarization Embedding) model, a more efficient model that computes the nodes' embeddings based on graph summarization. Specifically, the model first searches for the minimum information entropy of k groups to transform the original graph into a hypergraph with higher-order structural features. Next, the summarization graph's connection probabilities are used to determine the biased random walks on the hypergraph, which then generates the sequences of the super-nodes. Finally, the node sequences are fed into the skip-gram to generate the vectors of these nodes. Our proposed model improves the efficiency of graph embedding on big data graphs and effectively alleviates the local optimal problem caused by the random walks. Experimental results demonstrate that GSE outperforms main existing clustering baselines, such as K_Means Clustering, Affinity Propagation Clustering, Canopy Clustering, and ACP Clustering. Moreover, our model can be coupled with the main graph embedding methods and improves the Macro-F1 scores and Micro-F1 scores for classification tasks on a variety of real-world graph data.
引用
收藏
页码:45163 / 45174
页数:12
相关论文
共 50 条
[31]   Persistent graph stream summarization for real-time graph analytics [J].
Jia, Yan ;
Gu, Zhaoquan ;
Jiang, Zhihao ;
Gao, Cuiyun ;
Yang, Jianye .
WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS, 2023, 26 (05) :2647-2667
[32]   Low-Rank Projection Learning via Graph Embedding [J].
Liang, Yingyi ;
You, Lei ;
Lu, Xiaohuan ;
He, Zhenyu ;
Wang, Hongpeng .
NEUROCOMPUTING, 2019, 348 :97-106
[33]   Graph Summarization Methods and Applications: A Survey [J].
Liu, Yike ;
Safavi, Tara ;
Dighe, Abhilash ;
Koutra, Danai .
ACM COMPUTING SURVEYS, 2018, 51 (03)
[34]   Graph Summarization for Entity Relatedness Visualization [J].
Miao, Yukai ;
Qin, Jianbin ;
Wang, Wei .
SIGIR'17: PROCEEDINGS OF THE 40TH INTERNATIONAL ACM SIGIR CONFERENCE ON RESEARCH AND DEVELOPMENT IN INFORMATION RETRIEVAL, 2017, :1161-1164
[35]   Multi-relation Graph Summarization [J].
Ke, Xiangyu ;
Khan, Arijit ;
Bonchi, Francesco .
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, 2022, 16 (05)
[36]   Graph Summarization for Preserving Spectral Characteristics [J].
Zhou, Houquan ;
Liu, Shenghua ;
Shen, Huawei ;
Cheng, Xueqi .
PROCEEDINGS OF THE 2024 SIAM INTERNATIONAL CONFERENCE ON DATA MINING, SDM, 2024, :271-279
[37]   Graph Summarization with Controlled Utility Loss [J].
Hajiabadi, Mandi ;
Singh, Jasbir ;
Srinivasan, Venkatesh ;
Thomo, Alex .
KDD '21: PROCEEDINGS OF THE 27TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY & DATA MINING, 2021, :536-546
[38]   StrucGCN: Structural enhanced graph convolutional networks for graph embedding [J].
Zhang, Jie ;
Li, Mingxuan ;
Xu, Yitai ;
He, Hua ;
Li, Qun ;
Wang, Tao .
INFORMATION FUSION, 2025, 117
[39]   Graph Embedding Using Constant Shift Embedding [J].
Jouili, Salim ;
Tabbone, Salvatore .
RECOGNIZING PATTERNS IN SIGNALS, SPEECH, IMAGES, AND VIDEOS, 2010, 6388 :83-92
[40]   Embedding torus on the star graph [J].
Saikia, DK ;
Badrinath, R ;
Sen, RK .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1998, 9 (07) :650-663