Exploiting Mutual Information for Substructure-aware Graph Representation Learning

1 Introduction

In this paper, we aim to design, implement, and evaluate a new substructure-aware Graph Representation Learning (GRL) approach. GRL aims to quantify graph by encoding structural information into low dimensional vectors. Due to the impressive effectiveness and robustness of GRL, GRL has drawn attentions in many application domains, such as biomedical sciences, human behavior modeling, social networks, computer vision, etc [Cai et al., 2018].

∗Contact Author

Unlike global or neighbor (local) connectivity structures, substructures are a set of subgraphs (e.g., sub-circles, highdegree sub-vertexes, etc.) that are represented by a subset of vertexes and edges. Substructures usually demonstrate unique patterns and semantics of graphs that can be used to significantly improve GRL. For example, a mobile user can be described by an activity graph, where nodes are Point of Interests (POIs) 1 and an edge is the transition frequency among two POIs, a sub-circle (a type of substructure) represents a periodical activity sequence of the user, indicating the job occupation and preference of the user. In this case, substructure information can be used to enhance the quality of mobile user profiling [Wang et al., 2019].

Extensive efforts have been made for preserving global and local structures in GRL. For example, Graph Convolutional Networks (GCNs) learn node representations by aggregating neighbors; random walk-based methods decomposed graph structures as a set of random walk paths sampled from a graph [Cai et al., 2018]. However, there is limited studies about preserving substructure information in GRL. In a recent study [Wang et al., 2019], Wang et al. propose an adversarial learning based framework to integrate substructures into GRL with a CNN approximated substructure detector. But the performances are significantly hindered by the low convergence of the adversarial learning and the precision uncertainty of the approximated detector.

Therefore, there is a compelling need to develop more effective method to model substructure awareness in GRL. Two unique challenges arise in achieving this goal.

First, how should we guarantee the accountability for the node-level representation? Despite a compressed and effective quantification of graph, the learned node representation should be coherent with the original representation in depicting graph. The coherence can be quantified by correlation that the learned representations should be highly correlated to the original ones. This motivates us to leverage Mutual Information (MI), a powerful correlation measurement, to investigate the correlation between the representations of the original and learned node representations. However, due to the untractable exact computation on continuous variables, MI is difficult to estimate and maximize, and cannot directly collaborate with well-studied Graph Convolutional Network (GCN) techniques for learning node representations. Fortunately, recent studies on neural MI estimation [Belghazi et al., 2018; Hjelm et al., 2018; Veliˇckovi´c et al., 2018] propose to effectively approximate MI by designing a neural estimator, which gives a great chance to elaborate MI estimation with learning graph representations. Therefore, besides to learn nodelevel representations through the encode-decode paradigm, we propose to guarantee the accountability of the learned node representations by maximizing the mutual information between the learned and original node representation.

1 In urban setting, Point of Interest (POI) is somewhere that users show interests.

Second, after we obtain the accountable graph-level representation, how should we preserve substructure information for the graph-level representation? As subsets of the graph structure, interested substructures are unique and representative for differentiating graphs. Thus, for the common goal of quantifying graph, the representation of substructures should be highly correlated to graph-level representation. In another word, maximizing the correlation between the graph-level and substructure representations would provide a direction to enforce the graph-level representation to preserve substructure information. To quantify such correlation, similarly, we also exploit to maximize MI between the representations of the graph-level and substructures. We first obtain the graphlevel representation and substructure representations by graph pooling operation over the entire graph and substructure respectively. We then maximize the MI between graph-level and substructure representations to enforce the graph-level representation preserve substructures.

Along these lines, in this paper, we develop a substructureaware graph representation learning framework. The proposed learning framework includes two stages, (1) node-level representation and (2) graph-level representation. The graphlevel representation is the final output that is expected to preserve substructure information of graph. Specifically, we propose to guarantee the accountability in the node-level representation by maximizing MI between the learned and original representations to guide the encoding step. And then, we propose to preserve the substructure information in the graphlevel representation by maximizing MI between the graphlevel and substructure representations. We apply the proposed framework to the application of next activity type prediction for mobile user profiling to evaluate the effectiveness with real-world mobile checkin data.

2 Preliminaries

2.1 Mutual Information and Estimation

Mutual Information (MI) is a measurement to evaluate the dependency between two random variables. Due to the promising capability of capturing non-linear dependencies, MI has been applied in various disciplines, such as cosmology, biomedical sciences, computer vision, feature selection, and information bottleneck [Belghazi et al., 2018].

However, untractable exact computation and limited known distribution families hinder the further adaption of MI for continuous variables [Belghazi et al., 2018]. To estimate MI, non-parametric methods and approximate gaussianity of data distribution are proposed, which perform poor in expanding data scales (i.e., sample size or dimensions) [Belghazi et al., 2018]. A neural estimator MINE is then proposed to exploit gradient descent over neural networks to estimate MI, which is linearly scalable in dimensionality and sample size [Belghazi et al., 2018]. Moreover, DIM [Hjelm et al., 2018] combine the MI with deep representation learning for learning better global and local representations for images. Following DIM, DGI [Veliˇckovi´c et al., 2018] further extends MI neural estimation on learning graph representations. In this paper, we follow the methodology of MINE, DIM and DGI to exploit MI for learning graph representations with incorporating substructures.

2.2 Problem Statement

In this paper, we study the problem of learning graph representations with preserving interested substructures. Formally, given a list of graph G = {G (1) , G (2) , · · · , G (K) }, where G (k) = {V (k) ,E(k) }, we aim to learn a mapping function f : G → hg that takes the graph G as input, and outputs the vectorized graph-level representation hg = {h(1) g , h(2) g , · · · , h(K) g } for each graph in G, while subject to the special attention on preserving interested substructures.

3 Methodology

3.1 Model Intuition

We learn the substructure-aware graph representations on the following intuitions.

Intuition 1: Accountability of Representations. For the node-level representation, the learned representation should be a summarized vector that is highly correlated to the original representation. Therefore, we need to guarantee the accountability of the learned representation.

Intuition 2: Substructure Preservation. For the graphlevel representation, substructures demonstrates specific patterns of graphs, which would enrich the semantics of graph representations. Therefore, we need to preserve substructures in the graph-level representation.

3.2 Framework Overview

Figure 1 shows the overview of the proposed two-stage framework. In the first stage, we first propose to learn nodelevel representation with exploiting GCN through the encodedecode paradigm by minimizing the reconstruction loss that follows a contrastive learning-style convention. Then, we maximize MI between the learned and original node-level representation for guaranteeing the accountability. In the second stage, we obtain the graph-level representation and substructure representation with the graph pooling operation over the node-level representation of the entire graph and interested subgraph respectively. Then, we propose to preserve the substructure information by maximizing MI between the graph-level and substructure representations. Details will be introduced in the following.

Figure 1 shows an overview of the proposed framework. The proposed framework includes three key component. First, the graph is fed into an encode-decode paradigm to learn the node representations by minimizing the contrastive loss between positive and negative samples. Second, to guarantee the accountability of the learned representation, we aim to maximize the mutual information between the original and the learned node representations. Third, we obtain the graphlevel representation and substructured graph representation by the pooling operation. We maximize the mutual information between them to preserve the substructures in the graphlevel graph representation. Details will be introduced in rest of the section.

3.3 Learning Node-Level Representation

For better generality, we learn node-level representation with Graph Convolutional Network (GCN) in the unsupervised fashion. We follow the idea of GAE [Kipf and Welling, 2016b] to learn representation in a encode-decode paradigm. Specifically, the encoder is a o-layer GCN. At the l-th layer, the node representation can be denoted as

where ˆA = A+I, A is the adjacency matrix. I is the identity matrix, ˆDii = ∑i ˆAij, and Wl-1 is the weight. Then, the

learned the representation is hv = hl . The decoder is a inner product of the learned representation to recover the adjacency matrix

The objective is to minimize the reconstruction loss between the original adjacency matrix ˆA and reconstructed adjacency matrix ˆA′ .

We follow the convention of contrastive learning approach to minimize the reconstruction loss. We first sample positive nodes from neighbors, and negative nodes randomly from non-neighbors. Then, we minimize the cross-entropy loss of positive and negative node pairs

where ˆA′pos and ˆA′neg are derived from positive nodes pairs and negative node pairs respevtively, based on Equation 3.

3.4 Representation Accountability Guarantee

Intuitively, the learned low dimensional representation should be highly correlated to the original representations. To guarantee such accountability, we exploit mutual information to investigate the correlation between the learned representations hv and the original representation x.

Following the idea from DIM [Hjelm et al., 2018] and DGI [Veliˇckovi´c et al., 2018], we define a Jensen Shannon MI estimator to estimate and maximize the MI between x and hv as

where sp is the softplus function that sp(c) = log(1 + ec ), X is the positive samples and ˜X is the negative sample. We will present how we generate positive and negative samples later.

Since the noise-contrastive type objective with a standard binary cross-entropy (BCE) can effectively maximize mutual information [Veliˇckovi´c et al., 2018], we define the loss function as:

where D denotes a discriminator to provide probability scores for sampled pairs. For the k-th graph, we regard the positive samples as the pairs of (x(k) i , hvi ), and the negative samples as the pairs of (x ˜ (k) i , hvi ), where x ˜ (k) i is a randomly picked node from another graph. The objective is to minimize Lj, which is equivalent to maximize the mutual information.

3.5 Preserving Substructures in the Graph-Level Representation

Substructures, which are pivotal for learning complete representations for graphs [Cai et al., 2018; Wang et al., 2019], are subset of global structures. In another word, the representations of substructures should be highly correlated to the graph-level representations for a given graph. Therefore, this motivates us to exploit to maximize MI between the graphlevel and substructure representations to provide a direction to enforce the graph-level representation to preserve substructure information.

First, we obtain the graph-level representation and substructure information from node representations generated by the base model. Specifically, as shown in Figure 1, for the k-th graph, on one hand, we exploit the pooling operator over all the nodes representations to obtain the graph-level representation h(k) g ; on the other hand, the pooling operator is also applied over the nodes associated with substructures to generate the representation of substructures h(k) s .

Then, we exploit to use neural network for estimating and maximizing mutual information MI(hg; hs) between the graph-level representations h(k) g and the representation of substructures h(k) s to guarantee the highly correlated relationship. We have the similar noise-contrastive type loss function:

where D denotes a discriminator to provide probability scores for sampled pairs, h(˜k) s is the graph-level representations that are not of k-th graph. We design the positive samples as the pairs of (h(k) s , h(k) g ), and the negative samples as the pairs of (h(˜k) s , h(k) g ). The objective is to minimize Ls, which is equivalent to maximizeMI(hg; hs). In this way, the optimal graph-level representation hg would preserve substructures.

3.6 Optimization

The loss of the model includes: (i) the contrastive learning loss for graph reconstruction (Equation 3); (ii) the representation accountability learning loss (Equation 5), and (iii) the substructure preservation loss (Equation 6). The objective is to minimize the overall loss L as follows:

where λr, λj, and λs are the weights of Lr, Lj, and Ls respectively. We employ gradient descent to minimize L.

3.7 Comparison with RelatedWork

We discuss the differences between our proposed method and recent studies from two perspectives: (1) structure preserving and (2) representation accountability. On one hand, GCN variants (e.g., GCN [Kipf and Welling, 2016a], GAE [Kipf and Welling, 2016b], DGI [Veliˇckovi´c et al., 2018]), and random walk-based approaches (e.g., DeepWalk [Perozzi et al., 2014]) are two main streams for graph representation learning that focus on preserving global and/or local structures of graph, but substructures are not considered in these approaches, while StructRL [Wang et al., 2019] models the substructures through adversarial learning that is limited by the bad convergence and accuracy of the pre-trained approximated detector. On the other hand, DGI first exploits mutual information to guarantee the correlation between learned output and original input to endow the accountability for representations, while others ignores such important property. Different to the literature, in this paper, we simultaneously model substructures and provide the accountability-guarantee to enhance the graph representation. The experiment later will show the superior performance of our proposed framework.

4 Application: Mobile User Profiling For Next Activity Type Prediction

As mentioned in Introduction, preserving substructures of user activity graph can benefit mobile user profiling. Therefore, to validate the effectiveness of preserving substructures, we apply the proposed method to conduct mobile user profiling with the task of predicting next activity type.

First, for each user, we follow the formulation from the work [Wang et al., 2019] to construct a user activity graph, where the nodes are POI categories and edges are the normalized visiting frequencies among POI categories. POI categories are regarded as activity types. User activity graph demonstrates the preference and patterns of participating different activities. For simplicity, we only consider the "circle" substructure [Wang et al., 2019] in this paper.

Then, we exploit the proposed method over the constructed user activity graph to learn user representations as the features, which is further fed into a classifier to predict the next activity type. The more accurate the prediction, the better the user profiling, and then, the better the proposed method preserves substructures of user activity graph.

5 Experiment

5.1 Data Description

We evaluate the performance over two real-world check-in datasets [Yang et al., 2014] of New York and Tokyo. Table 1 shows the statistics of the dataset. The format of each dataset is <User ID, Venue ID, Venue Category ID, Venue Category Name, Latitude, Logitudem, Time>.

In the experiment, we chronologically extract POI category visit sequence for each user. We reserve the last visit POI category as the prediction target, and use all of the previous ones to construct user activity graph.

5.2 EvaluationMetrics

We use the prediction accuracy to evaluate the performance. The evaluation metric Accuracy@N is defined as: let Ti denote the target POI category that the user actually visited, P N i denote the topN predicted POI category list ranked in a descending order based on the predicted visit probabilities for user i, we consider the prediction is a success once the Ti ∈ P N i . Then where |U| denote the user numbers. We report Accuracy@2, Accuracy@3, Accuracy@4. Accuracy@5 in this paper.

5.3 Baseline Algorithms

1. GAE. The Graph Autoencoder [Kipf and Welling, 2016b] learned node representations in the encode-decode paradigm with GCN as the encoder and inner production to recover adjancacy matrix as the decoder. In the experiment, we set the number of GCN layer = 2, the input feature size=100, the output feature size = 40, learning rate = 0.001.
2. DeepWalk. The DeepWalk model [Perozzi et al., 2014] extends the word2vec model [Mikolov et al., 2013] to the scenario of network embedding by truncated random walks. We set the number of walks = 50, the size of representation = 40, the walk length = 40, and the window size = 10.
3. DGI. Deep Graph Infomax [Veliˇckovi´c et al., 2018] extends learning representations with MI maximation to graph embedding by modeling global and local structures. We set the input feature size=100, the output feature size = 40, learning rate = 0.001.
4. StructRL. StructRL [Wang et al., 2019] learns graph representations with attention on substructures without considering the accountability of learned representations. We set the input feature size=100, the output feature size is 40, learning rate = 0.001.

All the baseline algorithms and our proposed method are unsupervised learning approach. In the experiment, we first exploit each algorithm to learn graph features for each user. Then, we train a fully connected neural network to predict the visiting probability for each POI category. We conduct 10-fold cross validation and report the average Accuracy@N.

5.4 Overall Performance

We compare our method with the baseline methods in terms of Accuracy@N. In general, Figure 2 and 3 show our model outperforms other baseline methods for both the New York and Tokyo dataset. One interesting observation is that with N increasing, the improvement of our proposed model is less significant.

Comparing to DeepWalk, which is the representative of random walk-based methods, graph convolution-based methods (GAE, DGI, our proposed method) and autoencoderbased methods (GAE, StructRL) perform better in modeling structure information of user activity graph. Comparing to GAE, which is the base model of our proposed framework, our proposed framework additionally considers substructures and the accountability of the learned representation, thus, enhance the quality of learned representations. Comparing to DGI, which only models global and local structures, the incorporation of substructures improving the graph representation is validated by the better performance of our proposed method. Comparing to StructRL, which only incorporates substructures, accountability-guarantee provided by our proposed method further elevates the reasonability of the learned representations; and also, mutual information quantifies the non-linear relationship among structures, while only linear relations between countersamples are considered in StructRL.

In summary, the results validate that incorporating substructures and accountability can improve the quality of graph representations.

5.5 Analysis of Lj, Ls

To analyze the contribution of representation accountability and substructures preserving, we define two variants of our proposed model: (1) MI-StructRL-J, which only adds Lj to the base model for incorporating accountability of the learned representations; (2) MI-StructRL-S, which only adds Ls to the base model for incorporating substructures. We compare the base model, MI-StructRL-J, MI-StructRL-S, and MIStructRL in the experiment.

As shown in Figure 2 and 3, when N is relatively small, the improvement by incorporating substructures is more significant than the representation accountability. When N is getting larger, the improvement by the representation accountability is more significant than incorporating substructures. The results indicate that incorporating substructures is more important for top short range prediction.

6 RelatedWork

Graph Representation Learning. Graph representation learning aims to learn representations of graph structures, which can be categorized into matrix factorization based, deep learning based , edge reconstruction based, graph kernel based and generative models [Cai et al., 2018]. Specifically, matrix factorization based methods mainly exploit graph laplacian eigenmaps [Cai et al., 2007] and node proximity matrix factorization [Cao et al., 2015] to learn graph representations; deep learning based methods are a huge group in which many works on random walk [Perozzi et al., 2014] Edge reconstruction based methods carry the insight that the edge connectivity constructed based on embedding and original features should be as similar as possible [Zhang and Wang, 2016]; graph kernel based method aim to model graph structures from the perspectives of graphlet [Yanardag and Vishwanathan, 2015] and substree patterns [Shervashidze et al., 2011]; generative models aim to learn representations by maximizing the joint distribution of the input features and the target labels [Bernardo et al., 2007].

Human mobility modeling. Our work has connection with human mobility modeling. Human mobility modeling aims to learn human patterns from the human mobility data, which has been applied into various applications. For example, Wang et al. propose to learn the representation of urban residential communities by modeling human mobility patterns [Wang et al., 2018b; Fu et al., 2019; Zhang et al., 2019]. Wang et al. propose to analyze the driving behavior by modeling the human mobility from the perspectives of peer and temporal dependencies [Wang et al., 2018a]. Liu et al. propose to predict the travel destination by modeling the patterns of Mobike users with coupling among multi-view spatio-temporal contexts[Liu et al., 2018].

7 Conclusion

Substructures are pivotal for improving graph representations. While recent studies on graph representation learning mainly focus on modeling global and/or local structures of graph, fewer efforts have been made on preserving substructures. Therefore, in this paper, we decompose the GRL pipeline into two stages, (1) node-level and (2) graph-level. In the node-level stage, to further guarantee the accountability of representation, we propose to maximize the mutual information between the learned and original node representations. In the graph-level stage, motivated by the intuition that the representation of substructures should be highly correlated to the graph-level representation, we preserve the substructures by maximizing the mutual information between the substructures and the graph-level structures. We simultaneously optimize the learning procedure of node representations, accountability and substructures. The experimental results show that preserving substructures via maximizing mutual information between substructures and graph-level structures effectively enhance the performance of graph representations.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (NSFC) under Grant 61836013.