REGAL: Representation Learning-based Graph Alignment

Abstract

Problems involving multiple networks are prevalent in many scientific and other domains. In particular, network alignment, or the task of identifying corresponding nodes in different networks, has applications across the social and natural sciences. Motivated by recent advancements in node representation learning for single-graph tasks, we propose REGAL (REpresentation learning-based Graph ALignment), a framework that leverages the power of automatically-learned node representations to match nodes across different graphs. Within REGAL we devise xNetMF, an elegant and principled node embedding formulation that uniquely generalizes to multi-network problems. Our results demonstrate the utility and promise of unsupervised representation learning-based network alignment in terms of both speed and accuracy. REGAL runs up to 30x faster in the representation learning stage than comparable methods, outperforms existing network alignment methods by 20 to 30% accuracy on average, and scales to networks with millions of nodes each.

In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM), 2018

References in corpus (5)

• LINE: Large-scale Information Network Embedding
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• Survey of Nearest Neighbor Techniques
• Graph analysis of functional brain networks: practical issues in translational neuroscience
• Learning Structural Node Embeddings Via Diffusion Wavelets

Cited by in corpus (18)

• A Benchmarking Study of Embedding-based Entity Alignment for Knowledge Graphs
• Network Together: Node Classification via Cross network Deep Network Embedding
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• MAUIL: Multi-level Attribute Embedding for Semi-supervised User Identity Linkage
• CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding
• Domain-adaptive Message Passing Graph Neural Network
• G-CREWE: Graph CompREssion With Embedding for Network Alignment
• Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs
• Network Alignment
• Data-driven network alignment
• Interactive Visual Pattern Search on Graph Data via Graph Representation Learning
• Meta Diagram based Active Social Networks Alignment
• Zoo Guide to Network Embedding
• Towards Improving Embedding Based Models of Social Network Alignment via Pseudo Anchors
• CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment
• ELRUNA: Elimination Rule-based Network Alignment
• The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
• A Hidden Challenge of Link Prediction: Which Pairs to Check?