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.
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 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:
- Stability of MI: Unlike adversarial training, MI maximization offers a direct and stable objective, leading to better convergence.
- 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.
- 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