Yonnou nouvo fason pou antrene AI sou done grafe san sipèvizyon

Authors: 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 [ , , ], link prediction [ , , ], graph alignment [ , , ], molecular gen-eration [ , , ], 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, , basic personal details, texts, images, IP, and their relations, , 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 [ ] which operates on images. To discover useful representations, Deep InfoMax trains the encoder to maximize MI between its inputs ( , the images) and outputs ( , 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 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) [ ] 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 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, , 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, , the one used in DeepSets [ ], 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 ( , the sub-graph consisting of the input neighborhood) and the output ( , 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 § 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: the combining weights are still unknown and it does not take the topology ( , 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) The main contributions of our work are as follows: 1. 2. i.e. . • : 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 potential risk caused by the readout function since it considers MI between input graphs and high-level embeddings in a straightforward pattern. • : Through our theoretical analysis, we give a tractable and calculable form of GMI which decomposes the 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. • : We verify the effectiveness of GMI on several popular node classification and link prediction 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: mutual information estimation, and neural networks for learning representation over graphs. 1. 2. . As InfoMax principle [ ] advocates maximizing MI between the inputs and outputs of neural networks, many methods such as ICA algorithms [ , ] 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) [ ] 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) [ ], can be used without the concern about the precise value of MI. Mutual information estimation 3 1 21 2 30 . 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 [ , , , , ]. Typically, these methods can be divided into supervised and unsupervised categories. Among them, there is a rich literature on supervised representation learning over graphs [ , , , , ]. 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 [ , , ] have broader application potential. The well-known method is GraphSAGE [ ], an inductive framework to train GNNs by a random-walk based objective in its unsupervised setting. And recently, DGI [ ] 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 ( . ., 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, , 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 nodes ∈ V and edges = ( , ) ∈ E. The node features, with assumed empirical probability distribution P, are given by ∈ N vi eij vi vj X R × = { 1, · · · , } where ∈ R denotes the feature for node . The adjacency matrix ∈ R × represent edge connections, where associated to edge 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 : R × × R × → R × ′ , such that the hidden vectors = { 1, · · · , } = ( , ) 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 and for node as respectively the features of its neighbors and the corresponding adjacency matrix Xi Ai i conditional on the neighbors. Particularly, consists of all k-hop neighbors of with ≤ when the encoder is an -layer GNN, and it contains the node itself if we further add self-loops in the adjacency matrix. Here, we call the sub-graph expanded by and as a for node , denoted by G . With the definition of support graph, the encoding for each node becomes = (G ) = ( , ). Xi vi k l f l i Xi Ai support graph i i hi f i f Xi Ai In Deep InfoMax [ ], 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 and the support graph G for each node. We denote such graphical MI as ( ; G ). 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 ( ; G ) = ( ; G′ ), if G and G′ 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 G as different G 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 as ( ), the probability of as ( ), and the joint distribution by ( . According to the information theory, the MI between and is defined as Xi p Xi hi p hi p hi hi Xi Interestingly, we have the following mutual information decomposition theorem for computing ( ; ). I hi Xi Theorem 1 (Mutual Information Decomposition). ( | ) ( ; ) If the conditional probability p hi Xi is multiplicative (see the definition of multiplicative in [ ]), the global mutual information I 36 hi Xi defined in Eq. (1) can be decomposed as a weighted sum of local MIs, namely, ≤ ≤ 1 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 With the decomposition in Theorem we can calculate the right side of Eq. via MINE as inputs of the discriminator now become the pairs of ( , ) whose size always keep the same ( , ′-by- ). Besides, we can adjust the weights to reflect the isomorphic transformation of input graphs. For instance, if only contains one-hop neighbors of node , 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 ( ; ) and their underlying probability distributions. I hi xj A trivial way is setting all weights to be , then maximizing the right side of Eq. equivalents to maximizing the lower bound of ( ; ), 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 Inspired from the decomposition in Theorem we attempt to construct trainable weights from the other aspect of graphs ( , 3.2 Topology-Aware Mutual Information 1, i.e. topological view) so that the values of 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). G = ( , ) 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. 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. with the help of MINE. Note that MINE estimates a lower-bound of MI with the Donsker-Varadhan (DV) 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) [ ] and Noise-Contrastive estimator (infoNCE) [ ] could be employed to replace it. Based on the experimental findings and analysis in [ ], 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 ( ; ) in the first term of Eq. by (10) 30 31 20 I hi xj (10) where D : × ′ → R is a discriminator constructed by a neural network with parameter . is an negative sampled from P = P, and ( ) = (1 + ) denotes the soft-plus function. w D D w x j sp x loд ex As mentioned in § we maximize ( ; ) 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 [ , , Detailed statistics are given in Table 16 25 41]. 1. In the classification task, Cora, Citeseer, and PubMed [ ]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 [ , ], 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 [ ]. 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 [ ]. 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 [ ], 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, 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 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 -th layer, ( ) is a layer-specific trainable weight matrix. Here the nonlinear transformation we applied is the PReLU function (parametric ReLU) [ ]. It should be recognized that for node , the neighborhood 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 ′ = 512. And on Cora, Reddit, BlogCatalog, Flickr, and PPI, we utilize a two-layer GCN as our encoder. Here, we have hidden dimensions as ′ = 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 The discriminator in Eq. scores the input-output feature pairs through a simple bilinear function, which is similar to the discriminator used in Discriminator design. (11) : where Θ represents a trainable scoring matrix and the activation function we employed is the sigmoid aiming at converting scores into probabilities of ( , ) being a positive example. σ h x Actually, for the weight of the first term in Eq. , we have two ways to get its value in experiments. The first is to keep = ( T ), 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 = , . ., the left endpoint of the interval where belongs ( wij 1/in i e wi j