Network Alignment: Recent Advances and Future Trends

In the era of big data, networks are often from multiple sources such as the social networks of diverse platforms (e.g., Facebook, Twitter), protein-protein interaction (PPI) networks of different tissues, transaction networks at multiple financial institutes and knowledge graphs derived from a variety of knowledge bases (e.g., DBpedia, Freebase, etc.). The very first step before exploring insights from these multi-sourced networks is to integrate and unify different networks. In general, network alignment is such a task that aims to uncover the correspondences among nodes across different graphs. The challenges of network alignment include: (1) the heterogeneity of the multi-sourced networks, e.g., different structural patterns, (2) the variety of the real-world networks, e.g., how to leverage the rich contextual information, and (3) the computational complexity. The goal of this tutorial is to (1) provide a comprehensive overview of the recent advances in network alignment, and (2) identify the open challenges and future trends. We believe this can be beneficial to numerous application problems, and attract both researchers and practitioners from both data mining area and other interdisciplinary areas. In particular, we start with introducing the backgrounds, problem definition and key challenges of network alignment. Next, our emphases will be on (1) the recent techniques on addressing network alignment problem and other related problems with a careful balance between the algorithms and applications, and (2) the open challenges and future trends.

Detailed descriptions of this tutorial can be found here.

Slides: [pdf]

• Introduction (20 minutes)

  • Motivations

  • Problem definitions and related settings

  • Key challenges

  • Traditional solutions and limitations

• Part I: Network Alignment Algorithms: Recent Advances (90 minutes)

  • Pairwise network alignment

  • Collective network alignment

  • High-order network alignment

  • Hierarchical network alignment

  • Knowledge graph alignment

  • Cross-layer dependency inference

• Part II: Network Alignment Applications (40 minutes)

  • Applications in social analysis

  • Applications in bioinformatics

  • Applications in knowledge completion

  • Applications in security

• Part III: Future Research Directions (30 minutes)

  • Big network alignment

  • Adversarial network alignment

  • Active network alignment

  • Integrated network alignment

• Chen, Chen, et al. "FASCINATE: fast cross-layer dependency inference on multi-layered networks." Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016.

• Heimann, Mark, et al. "Regal: Representation learning-based graph alignment." Proceedings of the 27th ACM International Conference on Information and Knowledge Management. ACM, 2018.

• Koutra, Danai, Hanghang Tong, and David Lubensky. "Big-align: Fast bipartite graph alignment." 2013 IEEE 13th International Conference on Data Mining. IEEE, 2013.

• Liu, Li, et al. "Aligning Users across Social Networks Using Network Embedding." IJCAI. 2016.

• Mohammadi, Shahin, et al. "Triangular Alignment TAME: A Tensor-Based Approach for Higher-Order Network Alignment." IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 14.6 (2017): 1446-1458.

• Xu, Hongteng, et al. "Gromov-wasserstein learning for graph matching and node embedding." arXiv preprint arXiv:1901.06003 (2019).

• Xu, Kun, et al. "Cross-lingual knowledge graph alignment via graph matching neural network." arXiv preprint arXiv:1905.11605 (2019).

• Zafarani, Reza, and Huan Liu. "Connecting users across social media sites: a behavioral-modeling approach." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.

• Zhang, Jiawei, and S. Yu Philip. "Multiple anonymized social networks alignment." 2015 IEEE International Conference on Data Mining. IEEE, 2015.

• Zhang, Si, and Hanghang Tong. "Final: Fast attributed network alignment." Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016.

• Zhang, Si, et al. "Multilevel Network Alignment." The World Wide Web Conference. ACM, 2019.