Reproduce “REGAL: Representation Learning-based Graph Alignment” on OpenResearch

About this paper

Mark Heimann, Haoming Shen, Tara Safavi, Danai Koutra

REGAL provides an unsupervised, representation learning-based framework for aligning nodes across different graphs, leveraging a novel xNetMF method to generate cross-network comparable embeddings. The approach yielded 20-30% higher alignment accuracy and up to 30x faster embedding generation compared to existing methods, demonstrating scalability to millions of nodes.

Key insights

• Defining node identity through binned neighborhood degrees and attributes provides a robust and cross-network comparable representation, distinct from proximity-based definitions.
• The Nyström method can be adapted to implicitly factorize a large cross-network similarity matrix, allowing for efficient generation of low-variance node embeddings without explicit matrix construction.
• Employing efficient data structures like k-d trees during the alignment phase is critical for achieving scalability to millions of nodes, making the framework practical for large-scale graph analysis.

Summary by alphaXiv.