A New Way to Train AI on Graph Data Without Supervision

Authors: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang Authors: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ABSTRACT The richness in the content of various information networks such as social networks and communication networks provides the unprecedented potential for learning high-quality expressive representations without external supervision. This paper investigates how to preserve and extract the abundant information from graph-structured data into embedding space in an unsupervised manner. To this end, we propose a novel concept, Graphical Mutual Information (GMI), to measure the correlation between input graphs and high-level hidden representations. GMI generalizes the idea of conventional mutual information computations from vector space to the graph domain where measuring mutual information from two aspects of node features and topological structure is indispensable. GMI exhibits several benefits: First, it is invariant to the isomorphic transformation of input graphs—an inevitable constraint in many existing graph representation learning algorithms; Besides, it can be efficiently estimated and maximized by current mutual information estimation methods such as MINE; Finally, our theoretical analysis confirms its correctness and rationality. With the aid of GMI, we develop an unsupervised learning model trained by maximizing GMI between the input and output of a graph neural encoder. Considerable experiments on transductive as well as inductive node classification and link prediction demonstrate that our method outperforms state-of-the-art unsupervised counterparts, and even sometimes exceeds the performance of supervised ones. 1 INTRODUCTION To achieve reliable quantitative analysis for diverse information networks, high-quality representation learning for graph-structured data has become one of the current fascinating topics. Recent meth-ods towards this goal, commonly categorized as Graph Neural Networks (GNNs), have made remarkable advancements in a great many learning tasks, such as node classification [35, 42, 50], link prediction [26, 27, 49], graph alignment [12, 19, 43], molecular gen-eration [4, 5, 46], to name a few. Albeit in fruitful progress, training GNNs in existing approaches usually requires a certain form of supervision. Undoubtedly, the labeling information is expensive to acquire—manual annotation or paying for permission, and is even impossible to attain because of the privacy policy. Not to mention that the reliability of given labels is sometimes questionable. Hence, how to achieve high-quality graph representation without supervision becomes necessitated for a great many practical cases, which motivates the study of this paper. 35 42 50 26 27 49 12 19 43 4 5 46 Through carefully examining our collected graph-structured data, we find that they generally come from various sources such as social networks, citation networks, and communication networks where a tremendous amount of both content and linkage informa-tion exist. For instance, data on many social platforms like Twitter, Flickr, and Facebook include features of users, e.g., basic personal details, texts, images, IP, and their relations, e.g., buying the same item, being friends. These rich content data are sufficient to sup-port subsequent mining tasks without additional guidance: if two entities exhibit the extreme similarity in features, there is a high probability of a link between them (link prediction), and they are likely to belong to the same category (classification); if two entities both link to the same entity, they probably have similar character-istics (recommendation). In this sense, preserving and extracting as much information as possible from information networks into embedding space facilitates learning high-quality expressive representations that exhibit desirable performance in mining tasks without any form of supervision. Unsupervised graph representation learning is a more favorable choice in many cases due to the freedom from labels, particularly when we intend to take benefit from a large scale unlabeled data in the wild. e.g. e.g. To fully inherit the rich information in graphs, in this paper, we execute graph embedding based upon Mutual Information (MI) maximization, inspired by the empirical success of the Deep Info-Max method [20] which operates on images. To discover useful representations, Deep InfoMax trains the encoder to maximize MI between its inputs (i.e., the images) and outputs (i.e., the hidden vectors). When considering Deep InfoMax in the graph domain, the first stone we need to step over is how to define MI between graphs and hidden vectors, whereas the topology of graphs is more complicated than images (see Figure 1). One of the challenges is to ensure the MI function between each node’s hidden representation and its neighborhood input features to obey the symmetric property, or equivalently, being invariant to permutations of the neighborhoods. As one recent work considering MI, Deep Graph Infomax (DGI) [41] first embeds a input graph and a corresponding corrupted graph, then summarizes the input graph as a vector via a readout function, finally maximizes MI between this summary vector and hidden representations by discriminating the input graph (positive sample) from the corrupted graph (negative sample). Figure 1 gives an easily understandable overview of DGI. Maximizing this kind of MI is proved to be equivalent to maximizing the one between the input node features and hidden vectors, but this equivalence holds under several preset conditions, e.g., the readout function should be injective, which yet seem to be over-restricted in real cases. Even we can guarantee the existence of injective readout function by certain design, e.g., the one used in DeepSets [47], the injective ability of readout function is also affected by how its parameters are trained. That is to say that an originally-injective function still has the risk of becoming non-injective if it is trained without any external supervision. And if the readout function is not injective, the input graph information contained in a summary vector will diminish as the size of the graph increases. Moreover, DGI stays in a coarse graph/patch-level MI maximization. Hence in DGI, there is no guarantee that the encoder can distill sufficient information from input data as it never elaborately correlates hidden representations with their original inputs. 20 i.e. i.e. 1). 41 1 e.g. e.g. 47 In this paper, we put forward a more straightforward way to consider MI in terms of graphical structures without using any readout function and corruption function. We directly derive MI by comparing the input (i.e., the sub-graph consisting of the input neighborhood) and the output (i.e., the hidden representation of each node) of the encoder. And interestingly, our theoretical derivations demonstrate that the directly-formulated MI can be decomposed into a weighted sum of local MIs between each neighborhood feature and the hidden vector. In this way, we have decomposed the input features and made the MI computation tractable. Moreover, this form of MI can easily satisfy the symmetric property if we adjust the values of weights. We defer more details to § 3.1. As the above MI is mainly measured at the level of node features, we term it as Feature Mutual Information (FMI). i.e. i.e. 3.1. Two remaining issues about FMI: 1. the combining weights are still unknown and 2. it does not take the topology (i.e., the edge features) into account. To further address these two issues, we define our Graphical Mutual Information (GMI) measurement based on FMI. In particular, GMI applies an intuitive value assignment by setting the weights in FMI equal to the proximity between each neighbor and the target node in the representation space. As to retain the topology information, GMI further correlates these weights with the input edge features via an additional mutual information term. The resulting GMI is topologically invariant and also calculable with Mutual Information Neural Estimation (MINE) [2]. The main contributions of our work are as follows: 1. 2. i.e. [2]. • Concepts: We generalize the conventional MI estimation to the graph domain and propose a new concept of Graphical Mutual Information (GMI) accordingly. GMI is free from the Concepts Concepts potential risk caused by the readout function since it considers MI between input graphs and high-level embeddings in a straightforward pattern. • Algorithms: Through our theoretical analysis, we give a tractable and calculable form of GMI which decomposes the Algorithms Algorithms entire GMI into a weighted sum of local MIs. With the help of the MINE method, GMI maximization can be easily achieved in a node-level. • Experimental Findings: We verify the effectiveness of GMI on several popular node classification and link prediction Experimental Findings Experimental Findings tasks including both transductive and inductive ones. The experiments demonstrate that our method delivers promising performance on a variety of benchmarks and it even sometimes outperforms the supervised counterparts. 2 RELATED WORK In line with the focus of our work, we briefly review the previous work in the two following areas: 1. mutual information estimation, and 2. neural networks for learning representation over graphs. 1. 2. Mutual information estimation. As InfoMax principle [3] advocates maximizing MI between the inputs and outputs of neural networks, many methods such as ICA algorithms [1, 21] attempt to employ the idea of MI in unsupervised feature learning. Nonetheless, these methods can not be generalized to deep neural networks easily due to the difficulty in calculating MI between high dimensional continuous variables. Fortunately, Mutual Information Neural Estimation (MINE) [2] makes the estimation of MI on deep neural networks feasible via training a statistics network as a classifier to distinguish samples coming from the joint distribution and the product of marginals of two random variables. Specifically, MINE uses the exact KL-based formulation of MI, while a non-KL alternative, the Jensen-Shannon divergence (JSD) [30], can be used without the concern about the precise value of MI. Mutual information estimation 3 1 21 2 30 Neural networks for graph representation learning. With the rapid development of graph neural networks (GNNs), a large number of graph representation learning algorithms based on GNNs are proposed in recent years, which exhibit stronger performance than traditional random walk-based and factorization-based embedding approaches [6, 15, 33, 34, 39]. Typically, these methods can be divided into supervised and unsupervised categories. Among them, there is a rich literature on supervised representation learning over graphs [7, 9, 25, 40, 48]. In spite of their variance in network architecture, they achieve empirical success with the help of labels that are often not accessible in realistic scenarios. In this case, unsupervised graph learning methods [11, 16, 41] have broader application potential. The well-known method is GraphSAGE [16], an inductive framework to train GNNs by a random-walk based objective in its unsupervised setting. And recently, DGI [41] applies the idea of MI maximization to the graph domain and obtains the strong performance in an unsupervised pattern. However, DGI implements a coarse-grained maximization (i.e ., maximizing MI at graph/patch-level) which makes it difficult to preserve the delicate information in the input graph. Besides, the condition imposed on the readout function used in DGI seems to be over-restricted in real cases. By contrast, we focus on removing out the restriction of readout function and arriving at graphical mutual information maximization in a node-level by directly maximizing MI between inputs and outputs of the encoder. Representations derived by our method are more sophisticated in keeping input graph information, which ensures its potential for downstream graph mining tasks, e.g., node classification, link prediction, and recommendation. Neural networks for graph representation learning 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 i e e.g. 3 GRAPHICAL MUTUAL INFORMATION: DEFINITION AND MAXIMIZATION Prior to going further, we first provide the preliminary concepts used in this paper. Let G = (V, E) denote a graph with N nodes vi ∈ V and edges eij = (vi , vj ) ∈ E. The node features, with assumed empirical probability distribution P, are given by X ∈ N vi eij vi vj X RN ×D = {x 1, · · · , x N } where xi ∈ RD denotes the feature for node vi . The adjacency matrix A ∈ RN ×N represent edge connections, where Aij associated to edge eij could be a real number or multi-dimensional vector1. N D x x N xi D vi A N N Aij eij The goal of graph representation learning is to learn an encoder f : RN ×D × RN ×N → RN ×D′ , such that the hidden vectors H = {h1, · · · , hN } = f (X , A) indicate high-level representations for all nodes. The encoding process can be rewritten in a node-wise form. f N D N N N D H h hN f X A To show this, we define Xi and Ai for node i as respectively the features of its neighbors and the corresponding adjacency matrix Xi Ai i conditional on the neighbors. Particularly, Xi consists of all k-hop neighbors of vi with k ≤ l when the encoder f is an l -layer GNN, and it contains the node i itself if we further add self-loops in the adjacency matrix. Here, we call the sub-graph expanded by Xi and Ai as a support graph for node i, denoted by Gi . With the definition of support graph, the encoding for each node becomes hi = f (Gi ) = f (Xi , Ai ). Xi vi k l f l i Xi Ai support graph i i hi f i f Xi Ai Difficulties in defining graphical mutual information. In Deep InfoMax [20], the training objective of the encoder is to maximize MI between its inputs and outputs. The MI is estimated by employing a statistics network as a discriminator to classify samples coming from the joint distribution and the ones drawn from the product of marginals. Naturally, when adapting the idea of Deep InfoMax to graphs, we should maximize MI between the representation hi and the support graph Gi for each node. We denote such graphical MI as I (hi ; Gi ). However, it is non-straightforward to define I (hi ; Gi ). The difficulties are: Difficulties in defining graphical mutual information. 20 hi i I hi i • The graphical MI should be invariant concerning the node index. In other words, we should have I (hi ; Gi ) = I (hi ; G′i ), if Gi and G′i are isomorphic to each other. I hi i I hi i i i • If we adopt MINE method for MI calculation, the discriminator in MINE only accepts inputs of a fixed size. This yet is infeasible for Gi as different Gi usually include different numbers of nodes and thus are of distinct sizes. i i To get around the issue of defining graphical mutual information, this section begins with introducing the concept of Feature Mutual Information (FMI) that only relies on node features. Upon the inspiration from the decomposition of FMI, we then define Graphical Mutual Information (GMI), which takes both the node features and 3.1 Feature Mutual Information We denote the empirical probability distribution of node features Xi as p(Xi ), the probability of hi as p(hi ), and the joint distribution by p(hi , Xi ). According to the information theory, the MI between hi and Xi is defined as Xi p Xi hi p hi p hi Xi hi Xi Interestingly, we have the following mutual information decomposition theorem for computing I (hi ; Xi ). I hi Xi Theorem 1 (Mutual Information Decomposition). If the conditional probability p(hi |Xi ) is multiplicative (see the definition of multiplicative in [36]), the global mutual information I (hi ; Xi ) defined in Eq. (1) can be decomposed as a weighted sum of local MIs, namely, If the conditional probability p hi Xi is multiplicative (see the definition of multiplicative in [36]), the global mutual information I 36 hi Xi defined in Eq. (1) can be decomposed as a weighted sum of local MIs, namely, where, xj is the j-th neighbor of node i, in is the number of all elements in Xi , and the weight wij satisfies 1 ≤ wij ≤ 1 for each j. where, xj is the j-th neighbor of node i, in is the number of all elements in Xi , and the weight wij satisfies 1 wij for each j. To prove the above theorem, we first introduce two lemmas and a definition. Lemma 1. For any random variables X, Y , and Z, we have For any random variables X, Y , and Z, we have With the decomposition in Theorem 1, we can calculate the right side of Eq. (2) via MINE as inputs of the discriminator now become the pairs of (hi , xj ) whose size always keep the same (i.e., D ′-by-D). Besides, we can adjust the weights to reflect the isomorphic transformation of input graphs. For instance, if Xi only contains one-hop neighbors of node i, setting all weights to be identical will lead to the same MI for the input nodes in different orders. 1, (2) hi xj i.e. D D Xi i Despite some benefits of the decomposition, it is hard to characterize the exact values of the weights since they are related to the values of I (hi ; xj ) and their underlying probability distributions. I hi xj A trivial way is setting all weights to be 1 , then maximizing the right side of Eq. (2) equivalents to maximizing the lower bound of I (hi ; Xi ), by which the true FMI is also maximized to some extent. Besides this method, we additionally provide a more enhanced solution by considering the weights as trainable attentions, which is the topic in the next subsection. 1 (2) I hi Xi 3.2 Topology-Aware Mutual Information Inspired from the decomposition in Theorem 1, we attempt to construct trainable weights from the other aspect of graphs (i.e., 3.2 Topology-Aware Mutual Information 1, i.e. topological view) so that the values of wij can be more flexible and capture the inherent property of graphs. Ultimately we derive the definition of Graphical Mutual Information (GMI). wij Definition 2 (Graphical Mutual Information). The MI between the hidden vector h and its support graph G = (X , A ) is defined as The MI between the hidden vector h and its support graph X A is defined as where the definitions of both xj and in are as same as Theorem 1, aij is the edge weight/feature in the adjacency matrix A, and σ (·) is a sigmoid function. Intuitively, weight wij in the first term of Eq. (10) measures the coped with in experiments are unweighted. Formally, we compute I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). (12) By maximizing I (hi ; Gi ) with the sum of Eq. (11) and Eq. (12) over all hidden vectors H , we arrive at our complete objective function for contribution of a local MI to the global one. We implement the contribution of I (hi ; xj ) by the similarity between representations hi and hj (i.e., wij = σ (hThj )). Meanwhile, the term I (wij ; aij ) maximizes MI between wij and the edge weight/feature of input graph (i.e., aij ) to enforce wij to conform to topological relations. In this sense, the degree of the contribution would be consistent with the proximity in topological structure, which is commonly accepted as a fact that wij could be larger if node j is “closer” to node i and smaller otherwise. This strategy compensates for the flaw that FMI only focuses on node features and makes local MIs contribute to the global one adaptively. To better understand the idea of attention in this strategy, you could refer to the attention-based GCN [40]. Note that the definition of Eq. (10) is applicable for general cases. For certain specific situations, we can slightly modify Eq. (10) for efficiency. For example, when dealing with unweighted graphs (namely the edge value is 1 if connected and 0 otherwise), we could replace the second MI term I (wij ; aij ) with a negative cross-entropy loss. Minimizing the cross-entropy also contributes to MI maximization, and it delivers a more efficient computation. We defer more details in the next section. Overall, there are several benefits by the definition of Eq. (10). First, this kind of MI is invariant to the isomorphic transformation of input graphs. Second, it is computationally feasible since each component on the right side can be estimated by MINE. More importantly, GMI is more powerful than DGI in capturing original input information due to its explicit correlation between hidden vectors and input features of both nodes and edges in a fine-grained node-level. 3.3 Maximization of GMI Now we directly maximize the right side of Eq. (10) with the help of MINE. Note that MINE estimates a lower-bound of MI with the Donsker-Varadhan (DV) [10] representation of the KL-divergence between the joint distribution and the product of the marginals. As we focus more on maximizing MI rather than obtaining its specific value, the other non-KL alternatives such as Jensen-Shannon MI estimator (JSD) [30] and Noise-Contrastive estimator (infoNCE) [31] could be employed to replace it. Based on the experimental findings and analysis in [20], we resort to JSD estimator in this paper for the sake of effectiveness and efficiency, since infoNCE estimator is sensitive to negative sampling strategies (the number of negative samples) thus may become a bottleneck for large-scale datasets with a fixed available memory. On the contrary, the insensitivity of JSD estimator to negative sampling strategies and its respectable performance on many tasks makes it more suitable for our task. In particular, we calculate I (hi ; xj ) in the first term of Eq. (10) by (10) [10] 30 31 20 I hi xj (10) where Dw : D × D ′ → R is a discriminator constructed by a neural network with parameter w. x j is an negative sampled from P = P, and sp(x ) = loд(1 + ex ) denotes the soft-plus function. w D D w x j sp x loд ex As mentioned in § 3.2, we maximize I (wij ; aij ) via calculating its cross-entropy instead of using JSD estimator since the graphs we coped with in experiments are unweighted. Formally, we compute 3.2, I wij aij By maximizing I (hi ; Gi ) with the sum of Eq. (11) and Eq. (12) over all hidden vectors H , we arrive at our complete objective function for GMI optimization. Besides, we can further add trade-off parameters to balance Eq. (11) and (12) for more flexibility. 4 EXPERIMENTS In this section, we empirically evaluate the performance of GMI on two common tasks: node classification (transductive and inductive) and link prediction. An additional relatively fair comparison between GMI and another two unsupervised algorithms (EP-B and DGI) further exhibits its effectiveness. Also we provide the visualization of t-SNE plots and analyze the influence of model depth. 4.1 Datasets To assess the quality of our approach in each task, we adopt 4 or 5 commonly used benchmark datasets in the previous work [16, 25, 41]. Detailed statistics are given in Table 1. 16 25 41]. 1. In the classification task, Cora, Citeseer, and PubMed [38]2 are citation networks where nodes correspond to documents and edges represent citations. Each document is associated with a bag-of-words representation vector and belongs to one of the predefined classes. Following the transductive setup in [25, 41], training is conducted on all nodes, and 1000 test nodes are used for evaluation. Reddit3 is a large social network consisting of numerous interconnected Reddit posts created during September 2014 [16]. Posts are treated as nodes and edges mean the same user comments. 38 25 41 16 ![ Table 1: Statistics of the datasets used in experiments. ](https://cdn.hackernoon.com/images/InxBRjRIs6M1kdhuWcyNHiiUrxm1-eph3eec.jpeg) The class label is the community and our objective is to predict which community different posts belong to. PPI3 is a protein-protein interaction dataset including multiple graphs related to different human tissues [52]. The positional gene sets, motif gene sets, and immuno-logical signatures are viewed as node features, and each node has a totally of 121 labels given by gene ontology sets. Classifying protein functions that may belong to multi genres across different PPI graphs is our goal. Following the inductive setup in [16], on Reddit, we feed posts made in the first 20 days into the model for training, while the remaining are used for testing (with 30% used for validation); on PPI, there are 20 graphs for training, 2 for validation and 2 for testing. It should be emphasized that, for Reddit and PPI, testing is carried out on unseen (untrained) nodes and graphs, while the first three datasets are used for transductive learning. 52 16 In the link prediction task, BlogCatalog4 is a social blogging website where bloggers follow each other and register their blogs under predefined 6 categories. The tags of blogs are taken as node features. Flickr4 is an image sharing website where users interact with others and form a social network. Users upload photos with 9 predefined classes and select attached tags to reflect their interests which provide attribute information. The description of Cora and PPI is omitted for brevity. Following the experimental settings and evaluation metrics in [15], given a graph with certain portions of edges removed, we aim to predict these missing links. For Cora, BlogCatalog, and Flickr, we randomly delete 20%, 50%, and 70% edges while ensuring that the rest of network obtained after the edge removal is connected and use the damaged network for training. About PPI, we directly treat part of the edges not seen during training as prediction targets instead of man-made edge deletion. 4.2 Experimental Settings Encoder design. We resort to a standard Graph Convolutional Network (GCN) model with the following layer-wise propagation rule as the encoder for both classification and link prediction tasks: Encoder design. Where Aˆ = D -1/2AD - 1/2A = A + In, Dii = Aij, H (1) and H (I + 1) are the input and output matrices of the l -th layer, W (l ) is a layer-specific trainable weight matrix. Here the nonlinear transformation σ we applied is the PReLU function (parametric ReLU) [17]. It should be recognized that for node i, the neighborhood Xi in its support graph Gi contains node i itself as self-loops are inserted through A¯ . l W l σ 17 i Xi To be more specific, the encoder we employed on Citeseer and PubMed is a one-layer GCN with the output dimension as D ′ = 512. And on Cora, Reddit, BlogCatalog, Flickr, and PPI, we utilize a two-layer GCN as our encoder. Here, we have hidden dimensions as D ′ = 512 in each GCN layer. Note that utilizing the similar GCN encoder for both transductive and inductive classification task makes our proposed method easier to follow and scale to large networks than DGI, since DGI has to design varying encoders to adapt to distinct learning tasks, especially the encoders used in inductive tasks are too intricate and complicated, which are not friendly to practical applications. D D Discriminator design. The discriminator in Eq. (11) scores the input-output feature pairs through a simple bilinear function, which is similar to the discriminator used in [31]: Discriminator design. (11) [31]: where Θ represents a trainable scoring matrix and the activation function σ we employed is the sigmoid aiming at converting scores into probabilities of (h , x ) being a positive example. σ h x Implementation details. Actually, for the weight wij of the first term in Eq. (10), we have two ways to get its value in experiments. The first is to keep wij = σ (hThj ), which makes local MIs contribute to the global one adaptively, and we term this variant GMI-adaptive. Implementation details. wij (10) wij σ h hj The other is to let wij = 1/in , i.e ., the left endpoint of the interval where wi j belongs (refer to Theorem 1), which means the contribution of each local MI is equal, and we term this variant GMI-mean. Here both GMI-mean and GMI-adaptive are included in the scope of comparison with baselines. wij 1/in i e wi j 1), All experiments are implemented in PyTorch [23] with Glorot initialization [13] and conducted on a single Tesla P40 GPU. In preprocessing, we perform row normalization on Cora, Citeseer, PubMed, BlogCatalog, and Flickr following [25], and apply the processing strategy in [16] on Reddit and PPI. During training, we use Adam Optimizer with an initial training of 0.001 on all seven datasets. Suggested by [41], we adopt an early stopping strategy with a window size of 20 on Cora, Citeseer, and PubMed, while training the model for a fixed number of epochs on the inductive datasets (20 on Reddit, 50 on PPI). The number of negative samples is set to 5. Due to the large scale of Reddit and PPI, we need to use the subsampling skill introduced in [16] to make them fit into GPU memory. In detail, a minibatch of 256 nodes is first selected, and then for each selected node, we uniformly sample 8 and 5 neighbors at its first and second-level neighborhoods, respectively. We adopt the one-hop neighborhood to construct the support graph in experiments and utilize XW (0) (i.e., a compressed input feature) to calculate FMI since using the original input feature X causes GPU memory overflow. The trade-off parameters are tuned in the range of [0,1] to balance Eq. (11) and Eq. (12). The Batch Normalization strategy [22] is employed to train our model on Reddit and PPI. 16 XW i.e. X (11) (12) [22] Evaluation metrics. For the classification task, we provide the learned embeddings across the training set to the logistic regression classifier and give the results on the test nodes [16, 25]. Specifically, in transductive learning, we adopt the mean classification accuracy after 50 runs to evaluate the performance, while the micro-averaged F1 score averaged after 50 runs is used in inductive learning. And for PPI, suggested by [41], we standardize the learned embeddings before feeding them into the logistic regression classifier. For the link prediction task, the criteria we adopted is AUC which is the area under the ROC curve. The negative samples involved in the calculation of AUC are generated by randomly selecting an equal number of node pairs with no connections in the original graph. The closer the AUC score approaches 1, the better the performance of the algorithm is. Similarly, we report the AUC score averaged after 10 runs. Evaluation metrics. 16 25 41 4.3 Classification Transductive learning. Table 2 reports the mean classification accuracy of our method and other baselines on transductive tasks. Here, results for EP-B [11], DGI [41], Planetoid-T [45], GAT [40], as well as GWNN [44] are taken from their original papers, and results for DeepWalk [33], LP (Label Propagation) [51], and GCN [25] are copied from Kipf & Welling [25]. As for raw features, we feed them into a logistic regression classifier for training and give the results on the test features5. Although we provide experimental results of both supervised and unsupervised methods, in this paper, we focus more on comparing against unsupervised ones which are consistent with our setup. Transductive learning. 2 11 41 45 40 44 33 51 25 25 As can be observed, our proposed GMI-mean and GMI-adaptive, compared with other unsupervised methods, achieve the best classification accuracy across all three datasets. We consider this strong performance benefits from the idea of attempting to directly maximize graphical MI between input and output pairs of the encoder E at a fine-grained node-level. Therefore, the encoded representation maximally preserves the information of node features and topology in G, which contributes to classification. By contrast, EP-B ignores the underlying information between input data and learned representations, and DGI stays in a graph/patch-level MI maximization, which restricts their capability of preserving and extracting the original input information into embedding space. Thus slightly weak performance on classification tasks. Besides, without the guidance of labels, our method exhibits comparable results to some supervised models like GCN and GAT, even better results than them on Citeseer and PubMed. We believe that representations learned via GMI maximization between inputs and outputs inherit the rich information in graph G which is enough for classification. More notable is that many available labels are given based on the information in G as well. So keeping as much information as possible from the input can compensate for the information provided by the label to some extent, which sustains the performance of GMI in downstream graph mining tasks. It could be claimed that learning from original inputs without labels promises the potential for higher quality representations than the supervised pattern as the extreme sparsity of the training labels may suffer from the threat of overfitting or the correctness of given labels might not be reliable. Inductive learning. Table 2 also summarizes the micro-averaged F1 scores of GMI and other baselines on Reddit and PPI. We cite the results of DGI, GAT, FastGCN [7], and GaAN [48] in their original papers, while results for the rest seven compared methods are extracted from Hamilton et al. [16] (here we reuse the unsupervised GraphSAGE results to match our setup). Similarly, the comparison with unsupervised algorithms is the emphasis of our work. Inductive learning. 2 7 48 16 GMI-mean and GMI-adaptive successfully outperform all other competing unsupervised algorithms on Reddit and PPI, which substantiates the effectiveness of GMI maximization in the inductive classification domain (generalization to unseen nodes). Interestingly, the result of our method on Reddit is competitive with some advanced supervised models, but the situation on PPI is quite different. After conducting further analysis, we note that 42% of nodes have zero feature values in PPI, which means the feature matrix X is very sparse [16]. In this case, directly and merely relying on input graph G = (X , A) limits the performance of unsupervised approaches including DGI and our method, whereas learning in a supervised fashion exhibits much better performance due to the auxiliary information brought by additional labels. 16 X A Evaluation on two variants of GMI. According to Table 2, the two variants of GMI (GMI-mean and GMI-adaptive), which use different strategies to measure the contribution of each local MI (details in § 4.2), achieve competitive results with each other, but GMI-adaptive exhibits slightly weaker performance than GMI-mean. Through further analysis, we assume that it might be due to the difficulties in training brought by the nature of adaptive learning. Maybe the performance of GMI-adaptive could be improved with the help of an advanced training strategy. In this sense, GMI-mean is more practical and feasible, thus it can be regarded as a representative in practice. Evaluation on two variants of GMI. 2, 4.2), 4.4 Effectiveness of Objective Function To further clarify the effectiveness of maximizing graphical MI in unsupervised graph representation learning and provide a relatively fair comparison with DGI and EP-B (two unsupervised algorithms), we replace our objective function with their loss functions, respectively, while keeping other experimental settings unchanged. Table 3 lists the results under the transductive and inductive setup. As can be observed, GMI (GMI-mean and GMI-adaptive) achieves stronger performance across all five datasets, which reflects DGI and EP-B lack some consideration in graph representation learning task. Specifically, EP-B loss only imposes constraints on each node and its neighbors at the output level (embedding space), it ignores the interaction between input and output pairs of the encoder, which results in its poor ability to retain the valid information in G. For DGI, although it correlates hidden representations with their original input features implicitly, it discusses MI at the graph/patch-level which is somewhat coarse. 3 Interestingly, compared with DGI, our FMI (without topology information) gains improvements more significantly with the increase of graph size. We attribute this discovery to the fact that the performance degradation of the readout function makes DGI lose certain useful information for node classification with the increase in graph size, although it exhibits good performance on small graphs such as Cora and Citeseer. When the topology of input graph is reflected, our GMI outperforms all other kinds of losses on all datasets. Furthermore, note that the whole training process of GMI is similar to the training of discriminatorys in generative models [14, 30], and GMI empirically exhibits a comparable training speed with EP-B and DGI on the largest dataset Reddit, which demonstrates its good scalability. 4.5 Link Prediction Based on the above experimental results, we find that DGI is a strong competitor to GMI in the scope of unsupervised algorithms. Therefore, in this section, we intend to further investigate the performance of DGI and GMI in another mining task—link prediction. Here we choose FMI and GMI-mean to compare with DGI. Table 4 reports their AUC scores on four different datasets. Under different edge removal rates, GMI and FMI both remarkably outperform DGI (except FMI in 70.0% BlogCatalog), showing that measuring graphical MI between input graph and output representations in a fine-grained pattern is capable of capturing rich information in inputs and delivering good generalization ability. About DGI, for one thing, its graph/patch-level MI maximization which is relatively coarse limits its performance in such a fine link prediction task; for another, the inappropriateness of corruption function weakens the ability of DGI to learn accurate representations to predict missing links. Recall that the negative sample for the discriminator in DGI is generated by corrupting the original input graph, and a well-designed corruption function is indispensable which needs some skillful strategies [41]. In this task, we still adopt feature shuffiing function which shows the best results in the classification task to build negative samples. But in the case where an input graph is incomplete in terms of topological links, the guidance provided by this corrupted graph as a negative label in the discriminator becomes unreliable due to the inaccuracy of input graph, leading to poor performance. Therefore, the necessity of task-oriented corruption function is a weakness of DGI. In contrast, our GMI is free from this issue by eliminating the corruption function and directly maximizing graphical MI between inputs and outputs of the encoder. Furthermore, it can be observed that FMI is competitive to GMI in most cases, even on Flickr FMI is superior to GMI. We assume it to the benefits brought by the direct and elaborate feature mutual information maximization at a node-level. Based on the Homophily hypothesis [29] (i.e., entities in the network with similar features are likely to interconnect), the input feature information preserved in learned embeddings makes FMI owns the good capability of inferring missing links. 4 41 29 i.e. 4.6 Visualization For an intuitive illustration, Table 5 displays t-SNE [28] plots of the learned embeddings on Cora and Citeseer. From a qualitative perspective, the distribution of plots learned by FMI and DGI seems to be similar, and the embeddings generated by GMI discernible clusters than raw features, FMI, and DGI. 5 28 Especially on Cora, the compactness and separability of clusters are extremely obvious, which represents the seven topic categories. As for quantitative analysis, we attempt to measure clustering quality by calculating the Silhouette Coefficient score [37]. Specifically, we employ silhouette_score function from the scikit-learn Python package [32] with all default settings and follow the user guide to perform the evaluation. The clustering of embeddings learned via GMI obtains a Silhouette Coefficient score of 0.425 on Cora, 0.402 on Citeseer, and 0.385 on PubMed, while DGI gets 0.417, 0.391, 0.373 and EP-B gains 0.384, 0.385, 0.379 on the three datasets, respectively. Both qualitatively and quantitatively, it demonstrates the great performance of GMI, which illustrates the rationality and effectiveness of graphical mutual information maximization in unsupervised graph representation learning. 37 silhouette_score 32 4.7 Influence of Model Depth In this part, we adjust the number of convolutional layers in the encoder to investigate the influence of model depth on classification accuracy. Considering the potential difficulty of training deep neural networks, suggested by [18], we also experiment with a counterpart residual version of the standard GMI model, which adds identity shortcut connections between every two hidden layers to improve the training of deep networks. Here, we continue to have D ′ = 512 features for each hidden layer and start applying identity shortcuts from the second layer as the input and output of the first layer are not the same dimension. 18 Moreover, compared to the standard GMI model that achieves GMI maximization between the final representation and original input graph, we consider another variant, called dense GMI, which maximizes GMI between each hidden layer and input graph. Figure 2 gives a detailed architecture illustration. The involved hyperparameters remain unchanged except that we train for fixed epochs (600 on Cora and Citeseer) without early stopping. Results are plotted in Figure 3. 2 3. For one thing, the increase of model depth significantly widens the performance gap between models with and without shortcut connections. The best result for Cora is obtained with a two-layer GCN encoder, while the best result for Citeseer is achieved with a one-layer GCN encoder. Except for the fact that the increase of model depth makes training with no adoption of shortcut con-nections difficult, we also assume that the farther neighborhood information brought by multiple convolutional layers may be noise for self-representation learning. Specifically, the different proximity between neighbors means distinct extents of similarity, if two arbitrary nodes are a certain distance apart, they are likely to be completely different. Therefore, in the standard GMI model, the information aggregated from the farther neighborhood might contain much noise that is dissimilar to the characteristic of node itself, which degrades the quality of learned embeddings and subsequent classification performance. In contrast, additional identity short-cuts enable the model to carry over the information of the previous layer’s input, which can be regarded as a complementary process to similar neighborhood information from shallower layers to deeper layers, thus the residual version is relatively less vulnerable to model depth. For another, we observe that the dense GMI variant can also alleviate the performance deterioration to some extent, although MI tends to decay with depth by data processing inequality [8]. This thanks to maximizing graphical MI between the output of each layer and input graph, which imposes a direct constraint on each hidden layer to preserve input information as intact as possible. Based on this observation, enforcing the constraint of maximizing MI on hidden layers to reduce the loss of information when training deep neural networks could be a good practice. 8 5 CONCLUSION To overcome the dilemma of lacking available supervision and evade the potential risk brought by unreliable labels, we introduce a novel concept of graphical mutual information (GMI) to carry out graph representation learning in an unsupervised pattern. Its core lies in directly maximizing the mutual information between the input and output of a graph neural encoder in terms of node features and topological structure. Through our theoretical analysis, we give a definition of GMI and decompose it into a form of a weighted sum which can be calculated by the current mutual information estimation method MINE easily. Accordingly, we develop an unsupervised model and conduct two common graph mining tasks. The results exhibit that GMI outperforms state-of-the-art unsupervised baselines across both classification tasks (transductive and inductive) and link prediction tasks, sometimes even be com-petitive with supervised algorithms. Future work will concentrate on task-oriented representation learning or adapting the idea of GMI maximization to other types of graphs such as heterogeneous graphs and hypergraphs. ACKNOWLEDGMENTS This work was supported by National Key Research and Develop-ment Program of China (No. 2018AAA0101400), National Nature Science Foundation of China (No. 61872287 and No. 61532015), Innovative Research Group of the National Natural Science Foun-dation of China (No. 61721002), Innovation Research Team of Min-istry of Education (IRT_17R86), and Project of China Knowledge Center for Engineering Science and Technology. Besides, this re-search was funded by National Science and Technology Major Project of the Ministry of Science and Technology of China (No. 2018AAA0102900). REFERENCES [1] Luís B Almeida. 2003. MISEP–Linear and Nonlinear ICA Based on Mutual Information. Journal of machine learning research 4, Dec (2003), 1297–1318. Journal of machine learning research [2] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. 2018. Mine: mutual information neural estimation. In ICML. ICML [3] Anthony J Bell and Terrence J Sejnowski. 1995. An information-maximization approach to blind separation and blind deconvolution. Neural computation 7, 6 (1995), 1129–1159. Neural computation [4] Esben Jannik Bjerrum and Richard Threlfall. 2017. Molecular generation with recurrent neural networks (RNNs). arXiv preprint arXiv:1705.04612 (2017). arXiv preprint arXiv:1705.04612 [5] Xavier Bresson and Thomas Laurent. 2019. A Two-Step Graph Convolutional Decoder for Molecule Generation. arXiv preprint arXiv:1906.03412 (2019). arXiv preprint arXiv:1906.03412 [6] Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015. Grarep: Learning graph repre-sentations with global structural information. In CIKM. CIKM [7] Jie Chen, Tengfei Ma, and Cao Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247 (2018). arXiv preprint arXiv:1801.10247 [8] Thomas M Cover and Joy A Thomas. 2012. Elements of information theory. John Wiley & Sons. Elements of information theory [9] Ming Ding, Jie Tang, and Jie Zhang. 2018. Semi-supervised learning on graphs with generative adversarial nets. In CIKM. CIKM [10] Monroe D Donsker and SR Srinivasa Varadhan. 1983. Asymptotic evaluation of certain Markov process expectations for large time. IV. Communications on pure and applied mathematics 36, 2 (1983), 183–212. Communications on pure and applied mathematics [11] Alberto Garcia Duran and Mathias Niepert. 2017. Learning graph representations with embedding propagation. In NeurIPS. NeurIPS [12] Evgeniy Faerman, Otto Voggenreiter, Felix Borutta, Tobias Emrich, Max Berrendorf, and Matthias Schubert. 2019. Graph Alignment Networks with Node Matching Scores. In NeurIPS. NeurIPS [13] Xavier Glorot and Yoshua Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In AISTATS. AISTATS [14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. In NeurIPS. NeurIPS [15] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In KDD. KDD [16] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS. NeurIPS [17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2015. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In ICCV. ICCV [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In CVPR. CVPR [19] Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. 2018. Regal: Representation learning-based graph alignment. In CIKM. CIKM [20] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. 2018. Learning deep represen-tations by mutual information estimation and maximization. arXiv preprint arXiv:1808.06670 (2018). arXiv preprint arXiv:1808.06670 [21] Aapo Hyvärinen and Petteri Pajunen. 1999. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks 12, 3 (1999), 429–439. Neural networks [22] Sergey Ioffe and Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167 (2015). arXiv preprint arXiv:1502.03167 [23] Nikhil Ketkar. 2017. Introduction to pytorch. In Deep learning with python. 195–208. Deep learning with python [24] Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic opti-mization. arXiv preprint arXiv:1412.6980 (2014). arXiv preprint arXiv:1412.6980 [25] Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016). arXiv preprint arXiv:1609.02907 [26] Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016). arXiv preprint arXiv:1611.07308 [27] David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. Journal of the American society for information science and technology 58, 7 (2007), 1019–1031. Journal of the American society for information science and technology [28] Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE. ournal of machine learning research 9, Nov (2008), 2579–2605. ournal of machine learning research [29] Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology 27, 1 (2001), 415–444. Annual review of sociology [30] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. 2016. f-gan: Training gen-erative neural samplers using variational divergence minimization. In NeurIPS. NeurIPS [31] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. 2018. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748 (2018). arXiv preprint arXiv:1807.03748 [32] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. 2011. Scikit-learn: Machine learning in Python. Journal of machine learning research 12, Oct (2011), 2825–2830. Journal of machine learning research [33] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In KDD. KDD [34] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM. WSDM [35] Meng Qu, Yoshua Bengio, and Jian Tang. 2019. GMNN: Graph Markov Neural Networks. In ICML. ICML [36] Renato Renner and Ueli Maurer. 2002. About the mutual (conditional) information. In ISIT. ISIT [37] Peter J Rousseeuw. 1987. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics 20 (1987), 53–65. Journal of computational and applied mathematics [38] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93–93. AI magazine [39] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. Line: Large-scale information network embedding. In WWW. WWW [40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017). arXiv preprint arXiv:1710.10903 [41] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2018. Deep graph infomax. arXiv preprint arXiv:1809.10341 (2018). arXiv preprint arXiv:1809.10341 [42] Jun Wu, Jingrui He, and Jiejun Xu. 2019. Net: Degree-specific Graph Neural Networks for Node and Graph Classification. arXiv preprint arXiv:1906.02319 (2019). arXiv preprint arXiv:1906.02319 [43] Yuting Wu, Xiao Liu, Yansong Feng, Zheng Wang, Rui Yan, and Dongyan Zhao. 2019. Relation-aware entity alignment for heterogeneous knowledge graphs. In IJCAI. IJCAI [44] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. 2019. Graph Wavelet Neural Network. arXiv preprint arXiv:1904.07785 (2019). arXiv preprint arXiv:1904.07785 [45] Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. arXiv preprint arXiv:1603.08861 (2016). arXiv preprint arXiv:1603.08861 [46] Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. 2018. Graph convolutional policy network for goal-directed molecular graph generation. In NeurIPS. NeurIPS [47] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. 2017. Deep sets. In NeurIPS. 3391–3401. NeurIPS [48] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung. 2018. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07294 (2018). arXiv preprint arXiv:1803.07294 [49] Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In NeurIPS. NeurIPS [50] Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. 2019. Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI. AAAI [51] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In ICML. ICML [52] Marinka Zitnik and Jure Leskovec. 2017. Predicting multicellular function through multi-layer tissue networks. Bioinformatics 33, 14 (2017), i190–i198. Bioinformatics This paper is available on ieee.org under CC by 4.0 Deed (Attribution 4.0 International) license. This paper is available on ieee.org under CC by 4.0 Deed (Attribution 4.0 International) license. available on ieee.org