Network Comparison with Interpretable Contrastive Network Representation Learning

Takanori Fujiwara, Jian Zhao, Francine Chen, Yaoliang Yu, Kwan-Liu Ma

TL;DR

This paper introduces Contrastive Network Representation Learning (cNRL), a novel framework for comparing networks by identifying unique patterns in one network relative to another. Their proposed method, i-cNRL, leverages interpretable network representation learning and contrastive learning to provide insights into why these patterns are unique, enabling a deeper understanding of network differences.

What Problem Does This Paper Address?

Comparing networks is crucial for understanding differences between systems, such as biological networks from healthy versus diseased states, or social networks to identify unique collaboration patterns. Existing methods often rely on simple network statistics or provide only a high-level network-wide similarity, failing to pinpoint where or why these differences arise. Furthermore, many advanced machine learning techniques for network analysis lack interpretability, making it difficult to understand the learned representations. This paper addresses the need for a method that can not only identify unique patterns in networks but also explain the underlying reasons for these differences in a detailed, node-level manner.

Methods

The core of the proposed approach is Contrastive Network Representation Learning (cNRL). This framework integrates two key machine learning paradigms:

  • Network Representation Learning (NRL): This step transforms networks (Gr and GB) into low-dimensional feature matrices (XT and XB). The crucial aspect here is that the NRL method must produce features that are comparable across different networks. The authors specifically choose DeepGL for this task due to its ability to learn interpretable features.
  • Contrastive Learning: This step then uses the generated feature matrices to learn representations that highlight differences between the target network (Gr) and the background network (GB). The authors propose Contrastive PCA (cPCA) for this purpose, as it offers interpretability by providing contrastive principal component (cPC) loadings, which indicate the contribution of each learned feature to the unique patterns.

The combination of DeepGL and cPCA results in i-cNRL, which is designed to be:

  • General: Applicable to networks without requiring node correspondence or alignment.
  • Interpretable: Provides insights into which specific patterns are unique to a network.
  • Automatic: Includes automatic hyperparameter selection for contrastive learning.

Datasets

The paper evaluates i-cNRL on a variety of datasets:

  • Synthetic Networks:
    • Random networks (generated using Gilbert's model)
    • Scale-free networks (generated using Price's model)
    • An "Enhanced Price" model network, designed to mimic P2P networks with varying k-core numbers.
  • Real-World Networks:
    • Dolphin social network
    • Zachary's karate club network
    • P2P Gnutella08 network
    • Interactome networks: Combined-AP/MS and LC-multiple (yeast S. cerevisiae)
    • School contact networks (two days of data)

The paper provides links to original network datasets, processed datasets, and learned feature matrices for reproducibility.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between advanced network analysis techniques (NRL) and the need for interpretability in comparative studies, a common challenge in applying ML to complex network data.
  • Interpretability is Key: The choice of DeepGL for NRL and cPCA for contrastive learning is deliberate, aiming to provide not just a distinction between networks but also an explanation of why they differ. This is achieved through analyzing cPC loadings and relating them back to the learned features.
  • Visualizing Uniqueness: Visualizing both the target and background network representations (YT and YB) together in a 2D embedding allows for a direct assessment of whether contrastive learning has successfully identified unique patterns in the target network.
  • Iterative Refinement: The case study on refining network models demonstrates how i-cNRL can guide the improvement of generative models by identifying characteristics that are not well-captured by existing models.

Key Results

  • Effective Network Comparison: i-cNRL successfully identifies unique patterns in target networks across various synthetic and real-world datasets, as visualized in 2D embeddings.
  • Interpretable Explanations: The method provides interpretable insights, identifying features like "mean eigenvector centrality of neighbors" or "k-core numbers" as drivers of network uniqueness. For example, in the Dolphin vs. Karate network comparison, i-cNRL highlights differences in eigenvector centrality of neighbors, explaining community structures in the Dolphin network.
  • Quantitative Performance: Comparisons with other potential cNRL designs (e.g., using GraphSAGE or cVAE) show that DeepGL & cPCA (i-cNRL) generally provides competitive or superior results in terms of dispersion ratio, Bhattacharyya distance, and KL divergence, while crucially offering interpretability.
  • Model Refinement: The study demonstrates how i-cNRL can be used to refine network models, leading to better simulations of real-world network phenomena.

Limitations and Future Work

  • Scalability for Large Networks: The authors acknowledge that while i-cNRL is demonstrated on small to medium-sized networks, applying it to very large networks (millions of nodes) might be limited by the linearity of cPCA.
  • Nonlinear Contrastive Learning: For extremely large and complex networks, they plan to investigate incorporating nonlinear contrastive learning methods (like cVAE) while retaining interpretability.
  • Computational Cost: While efforts are made to optimize DeepGL (e.g., feature pruning), the computational cost can still be significant, especially for larger networks.
  • Feature Exclusion: The reliance on graph-tool for base feature computation means that if a feature produces 'NaN' values (e.g., in disconnected networks), it's excluded, potentially limiting the analysis if unique patterns are tied to these excluded features. The authors suggest precomputing alternative centrality measures to mitigate this.

Summary updated

Abstract

Identifying unique characteristics in a network through comparison with another network is an essential network analysis task. For example, with networks of protein interactions obtained from normal and cancer tissues, we can discover unique types of interactions in cancer tissues. This analysis task could be greatly assisted by contrastive learning, which is an emerging analysis approach to discover salient patterns in one dataset relative to another. However, existing contrastive learning methods cannot be directly applied to networks as they are designed only for high-dimensional data analysis. To address this problem, we introduce a new analysis approach called contrastive network representation learning (cNRL). By integrating two machine learning schemes, network representation learning and contrastive learning, cNRL enables embedding of network nodes into a low-dimensional representation that reveals the uniqueness of one network compared to another. Within this approach, we also design a method, named i-cNRL, which offers interpretability in the learned results, allowing for understanding which specific patterns are only found in one network. We demonstrate the effectiveness of i-cNRL for network comparison with multiple network models and real-world datasets. Furthermore, we compare i-cNRL and other potential cNRL algorithm designs through quantitative and qualitative evaluations.
BibTeX
@article{fujiwara2022network,
  author = {Takanori Fujiwara and Jian Zhao and Francine Chen and Yaoliang Yu and Kwan-Liu Ma},
  title = {{Network Comparison with Interpretable Contrastive Network Representation Learning}},
  journal = {J. Data Sci. Stat. Vis.},
  year = {2022},
  doi = {10.52933/jdssv.v2i5.56},
}
Figure