Exploiting Mutual Information for Substructure-aware Graph Representation Learning

Pengyang Wang, Yanjie Fu, Yuanchun Zhou, Kunpeng Liu, Xiaolin Li, Kien A. Hua

Abstract

Graph Representation Learning (GRL) is pivotal for transforming complex graph data into actionable low-dimensional vectors. However, existing methods often fail to capture semantic substructures or suffer from "representation drift" where embeddings lose fidelity to original features. We propose MI-StrutRL, a framework that utilizes Mutual Information (MI) to bridge local node features and global graph substructures. By enforcing node-level accountability and substructure preservation through MI maximization, our model achieves superior performance in complex tasks like mobile user profiling, outperforming state-of-the-art baselines by significant margins.

Introduction

The primary goal of Graph Representation Learning (GRL) is to encode graph structures into low-dimensional embeddings. While current techniques effectively capture local neighborhoods or global graph properties, they frequently overlook substructures—recurring patterns like "circles" or "hubs" that carry critical semantic information.

Traditional approaches to capturing these patterns often rely on Generative Adversarial Networks (GANs), which are notoriously difficult to train and prone to non-convergence. Moreover, embeddings may become so specialized to the graph topology that they lose their connection to the original node attributes. MI-StrutRL addresses these issues by providing a stable, mathematically grounded objective to ensure embeddings are both "accountable" to input data and aware of meaningful subgraphs.

Methods: The MI-StrutRL Framework

The authors introduce a two-stage framework designed to balance feature fidelity with structural awareness.

Overview of the MI-StrutRL framework showing node-level and graph-level MI maximization.

Stage 1: Node-Level Accountability

In the first stage, a Graph Convolutional Network (GCN) acts as an encoder to produce node embeddings ($h_v$). To prevent the loss of essential node characteristics, the model maximizes the Mutual Information (MI) between the original input features ($x$) and the learned embeddings ($h_v$). This "accountability" constraint ensures the compressed vectors remain faithful to the source data. The implementation utilizes a Jensen-Shannon MI estimator to capture non-linear correlations that standard metrics might miss.

Stage 2: Graph-Level Substructure Preservation

The second stage focuses on preserving specific substructures, such as "circles" representing periodic human activity. The model generates two summary vectors via pooling: one for the entire graph ($h_g$) and one for the extracted substructure ($h_s$). By maximizing the MI between $h_g$ and $h_s$, the framework forces the final graph-level representation to prioritize the patterns found within these key subgraphs.

Experimental Evaluation

The model was evaluated on two large-scale human mobility datasets:

  • New York Check-ins: 227,428 check-ins across 400 Point of Interest (POI) categories.
  • Tokyo Check-ins: 573,703 check-ins across 385 POI categories.

In these graphs, nodes represent activity types (e.g., "Office," "Cafe"), and edges denote transition frequencies. The downstream task was to predict a user's next activity type.

Key Results and Insights

MI-StrutRL consistently outperformed competitive baselines, including DeepWalk, GAE, DGI, and StructRL.

Performance analysis of MI-StrutRL variants across different accuracy metrics for the New York dataset.

Performance Gains

  • New York Dataset: At Accuracy@3, MI-StrutRL reached a score of 0.1200, a 116% improvement over DGI (0.0554) and an 85.8% improvement over the previous state-of-the-art, StructRL (0.0646).
  • Tokyo Dataset: At Accuracy@2, the model outperformed StructRL by 39.9% and DeepWalk by a staggering 289%.

Discussion

The success of MI-StrutRL highlights several key principles:

  1. Stability of MI: Unlike adversarial training, MI maximization offers a direct and stable objective, leading to better convergence.
  2. Importance of "Circles": In mobility data, periodic substructures (e.g., Home → Work → Home) are highly indicative of user identity. Prioritizing these motifs significantly enhances profiling accuracy.
  3. Dynamic Feature Importance: Ablation studies revealed that substructure awareness is most critical for short-range predictions (Accuracy@2), whereas node accountability becomes increasingly vital for broader prediction windows (Accuracy@5).

Conclusion and Future Work

MI-StrutRL demonstrates that Mutual Information is a powerful tool for creating accountable and pattern-aware graph embeddings. While the current implementation requires pre-defined substructures, future research could focus on automated substructure discovery. Additionally, extending this approach to other domains, such as molecular biology or social network analysis, could reveal further benefits of MI-induced representation learning.

Summary updated

Abstract

In this paper, we design and evaluate a new substructure-aware Graph Representation Learning (GRL) approach. GRL aims to map graph structure information into low-dimensional representations. While extensive efforts have been made for modeling global and/or local structure information, GRL can be improved by substructure information. Some recent studies exploit adversarial learning to incorporate substructure awareness, but hindered by unstable convergence. This study will address the major research question: is there a better way to integrate substructure awareness into GRL? As subsets of the graph structure, interested substructures (i.e., subgraph) are unique and representative for differentiating graphs, leading to the high correlation between the representation of the graph-level structure and substructures. Since mutual information (MI) is to evaluate the mutual dependence between two variables, we develop a MI inducted substructure-aware GRL method. We decompose the GRL pipeline into two stages: (1) node-level, where we introduce to maximize MI between the original and learned representation by the intuition that the original and learned representation should be highly correlated; (2) graph-level, where we preserve substructures by maximizing MI between the graph-level structure and substructure representation. Finally, we present extensive experimental results to demonstrate the improved performances of our method with real-world data.
BibTeX
@inproceedings{wang2020exploiting,
  author = {Pengyang Wang and Yanjie Fu and Yuanchun Zhou and Kunpeng Liu and Xiaolin Li and Kien A. Hua},
  title = {{Exploiting Mutual Information for Substructure-aware Graph Representation Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/472},
}
Figure