G-CREWE: Graph CompREssion With Embedding for Network Alignment

Publication Year: 2020 Publication Type : JournalArticle

Abstract:


Network alignment is useful for multiple applications that require increasingly large graphs to be processed. Existing research approaches this as an optimization problem or computes the similarity based on node representations. However, the process of aligning every pair of nodes between relatively large networks is time-consuming and resource-intensive. In this paper, we propose a framework, called G-CREWE (Graph CompREssionWith Embedding) to solve the network alignment problem. G-CREWE uses node embeddings to align the networks on two levels of resolution, a fine resolution given by the original network and a coarse resolution given by a compressed version, to achieve an efficient and effective network alignment. The framework first extracts node features and learns the node embedding via a Graph Convolutional Network (GCN). Then, node embedding helps to guide the process of graph compression and finally improve the alignment performance. As part of G-CREWE, we also propose a new compression mechanism called MERGE (Minimum DEgRee NeiGhbors ComprEssion) to reduce the size of the input networks while preserving the consistency in their topological structure. Experiments on all real networks show that our method is more than twice as fast as the most competitive existing methods while maintaining high accuracy.


BibTex:

@article{DBLP:journals/corr/abs-2007-16208, archiveprefix = {arXiv},
   
    author = {Kyle Kai Qin and Flora D. Salim and Yongli Ren and Wei Shao and Mark Heimann and Danai Koutra},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    biburl = {https://dblp.org/rec/journals/corr/abs-2007-16208.bib},
    eprint = {2007.16208},
    journal = {CoRR},
    timestamp = {Mon, 03 Aug 2020 01:00:00 +0200},
    title = {G-CREWE: Graph CompREssion With Embedding for Network Alignment},
    url = {https://arxiv.org/abs/2007.16208},
    volume = {abs/2007.16208},
    year = {2020}
}

Cite:

Related Publications

RUP: Large Room Utilisation Prediction with carbon dioxide sensor
Type : JournalArticle
Show More
A Scalable Room Occupancy Prediction with Transferable Time Series Decomposition of CO 2 Sensor Data
Type : JournalArticle
Show More
Topical Event Detection on Twitter
Type : ConferenceProceeding
Show More

© 2021 Flora Salim - CRUISE Research Group.