Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2021 Jan 26:3:608043.
doi: 10.3389/fdata.2020.608043. eCollection 2020.

Proximity-Based Compression for Network Embedding

Muhammad Ifte Islam  1 , Farhan Tanvir  1 , Ginger Johnson  2 , Esra Akbas  1 , Mehmet Emin Aktas  3
Affiliations

Proximity-Based Compression for Network Embedding

Muhammad Ifte Islam et al. Front Big Data. .

Abstract

Network embedding that encodes structural information of graphs into a low-dimensional vector space has been proven to be essential for network analysis applications, including node classification and community detection. Although recent methods show promising performance for various applications, graph embedding still has some challenges; either the huge size of graphs may hinder a direct application of the existing network embedding method to them, or they suffer compromises in accuracy from locality and noise. In this paper, we propose a novel Network Embedding method, NECL, to generate embedding more efficiently or effectively. Our goal is to answer the following two questions: 1) Does the network Compression significantly boost Learning? 2) Does network compression improve the quality of the representation? For these goals, first, we propose a novel graph compression method based on the neighborhood similarity that compresses the input graph to a smaller graph with incorporating local proximity of its vertices into super-nodes; second, we employ the compressed graph for network embedding instead of the original large graph to bring down the embedding cost and also to capture the global structure of the original graph; third, we refine the embeddings from the compressed graph to the original graph. NECL is a general meta-strategy that improves the efficiency and effectiveness of many state-of-the-art graph embedding algorithms based on node proximity, including DeepWalk, Node2vec, and LINE. Extensive experiments validate the efficiency and effectiveness of our method, which decreases embedding time and improves classification accuracy as evaluated on single and multi-label classification tasks with large real-world graphs.

Keywords: graph classification; graph compression; graph representation learning; network embedding; node similarity.

PubMed Disclaimer

Conflict of interest statement

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

Figures

FIGURE 1
FIGURE 1
Example of graph compressing on Les Miserables network (Original Network (A), Compressed Network (B), Embedding of Original Network (C) and Embedding of Compressed Network (D)).
FIGURE 2
FIGURE 2
Example of graph compressing. (a,b) are merged into super-node ab connected to the neighbors of both (a,b).
Algorithm 1
Algorithm 1
Graph Compressing (G, λ).
Algorithm 2
Algorithm 2
NECL: Network Embedding on Compressed Graph.
FIGURE 3
FIGURE 3
Detailed classification results on Citeseer.
FIGURE 4
FIGURE 4
Detailed classification results on Wiki.
FIGURE 5
FIGURE 5
Detailed classification results on DBLP.
FIGURE 6
FIGURE 6
Detailed classification results on BlogCatalog.
FIGURE 7
FIGURE 7
Run time analyses for different similarity threshold values λ (Citeseer (A), Wiki (B), DBLP (C) and BlogCatalog (D)).
FIGURE 8
FIGURE 8
The ratio of vertices/edges of the compressed graphs to that of the original graphs. (Citeseer (A), Wiki (B), DBLP (C) and BlogCatalog (D)).
FIGURE 9
FIGURE 9
Detailed comparisons of classification results on Citeseer
FIGURE 10
FIGURE 10
Detailed comparisons of classification results on Wiki.
FIGURE 11
FIGURE 11
Detailed comparisons of classification results on DBLP.
FIGURE 12
FIGURE 12
Detailed comparisons of classification results on BlogCatalog.
See this image and copyright information in PMC

References

    1. Adler M., Mitzenmacher M. (2001). “Towards compressing web graphs,” in Proceedings of data compression conference Snowbird, UT, USA, March 27-29, 2001 (DCC: IEEE; ), 203–212.
    1. Akbas E., Zhao P. (2017). “Attributed graph clustering: an attribute-aware graph embedding approach,” in Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining, Sydney, Australia, July, 2017, 305–308.
    1. Akbas E., Aktas M. E. (2019a). “Network embedding: on compression and learning,” in IEEE international conference on Big data (Big data), Los Angeles, CA, USA, December 9-12, 2019, 4763–4772.
    1. Akbas E., Aktas M. E. (2019b). Network embedding: on compression and learning. arXiv preprint arXiv:1907.02811 - PMC - PubMed
    1. Akbas E., Zhao P. (2019). “Graph clustering based on attribute-aware graph embedding,” in From security to community detection in social networking platforms (Springer International Publishing; ), 109–131.

LinkOut - more resources