Graph Representation Learning - McGill University School ...

1 Graph Representation LearningWilliam L. HamiltonMcGill University2020 Pre-publication draft of a book to be published byMorgan & Claypool version released with relevant copyrights held by the author andpublisher extend to this pre-publication : William L. Hamilton. (2020). Graph Representation Lectures on Artificial Intelligence and Machine Learning , Vol. 14,No. 3 , Pages data is ubiquitous throughout the natural and social sciences,from telecommunication networks to quantum chemistry. Building relational inductivebiases into deep Learning architectures is crucial if we want systems that can learn,reason, and generalize from this kind of data.

2 Recent years have seen a surge in researchon Graph Representation Learning , including techniques for deep Graph embeddings,generalizations of convolutional neural networks to Graph -structured data, and neuralmessage-passing approaches inspired by belief propagation. These advances in graphrepresentation Learning have led to new state-of-the-art results in numerous domains,including chemical synthesis, 3D-vision, recommender systems, question answering,and social network goal of this book is to provide a synthesis and overview of Graph representationlearning.

3 We begin with a discussion of the goals of Graph Representation Learning , aswell as key methodological foundations in Graph theory and network analysis. Follow-ing this, we introduce and review methods for Learning node embeddings, includingrandom-walk based methods and applications to knowledge graphs. We then providea technical synthesis and introduction to the highly successful Graph neural network (GNN) formalism, which has become a dominant and fast-growing paradigm for deeplearning with Graph data. The book concludes with a synthesis of recent advancementsin deep generative models for graphs a nascent, but quickly growing subset of graphrepresentation What is a Graph ?

4 Graphs .. Information .. Machine Learning on graphs .. classification .. prediction .. and community detection .. classification, regression, and clustering ..72 Background and Traditional Graph Statistics and Kernel Methods .. statistics and features .. features and Graph kernels .. Neighborhood Overlap Detection .. overlap measures .. overlap measures .. Graph Laplacians and Spectral Methods .. Laplacians .. Cuts and Clustering .. spectral clustering.

5 Towards Learned Representations .. 27I Node Embeddings283 Neighborhood Reconstruction An Encoder-Decoder Perspective .. Encoder .. Decoder .. an Encoder-Decoder Model .. of the Encoder-Decoder Approach .. Factorization-based approaches .. Random walk embeddings .. walk methods and matrix factorization .. Limitations of Shallow Embeddings .. 364 Multi-relational Data and Knowledge Reconstructing multi-relational data .. Loss functions.

6 Multi-relational decoders .. abilities .. 44II Graph neural Networks465 The Graph neural network neural Message Passing .. of the Message Passing Framework .. and Intuitions .. Basic GNN .. Passing with Self-loops .. Generalized Neighborhood Aggregation .. Normalization .. Aggregators .. Attention .. Generalized Update Methods .. and Skip-Connections .. Updates .. Knowledge Connections .. Edge Features and Multi-relational GNNs.

7 Graph neural Networks .. and Feature Concatenation .. Graph Pooling .. Generalized Message Passing .. 666 Graph neural Networks in Applications and Loss Functions .. for Node Classification .. for Graph Classification .. for Relation Prediction .. GNNs .. Efficiency Concerns and Node Sampling .. Implementations .. and Mini-Batching .. Parameter Sharing and Regularization .. 73ivv7 Theoretical GNNs and Graph Convolutions.

8 And the Fourier Transform .. Time Signals to Graph Signals .. Graph Convolutions .. GNNs .. GNNs and Probabilistic Graphical Models .. Space Embeddings of Distributions .. as Graphical Models .. mean-field inference .. and PGMs More Generally .. GNNs and Graph Isomorphism .. Isomorphism .. Isomorphism and Representational Capacity .. Weisfieler-Lehman Algorithm .. and the WL Algorithm .. the WL Algorithm .. 97 III Generative Graph Models1028 Traditional Graph Generation Overview of Traditional Approaches.

9 Erd os-R enyi Model .. Stochastic Block Models .. Preferential Attachment .. Traditional Applications .. 1079 Deep Generative Variational Autoencoder Approaches .. Latents .. Latents .. Adversarial Approaches .. Autoregressive Methods .. Edge Dependencies .. Models for Graph Generation .. Evaluating Graph Generation .. Molecule Generation .. 121 Conclusion123 Bibliography125 PrefaceThe field of Graph Representation Learning has grown at an incredible and some-times unwieldy pace over the past seven years.

10 I first encountered this area asa graduate student in 2013, during the time when many researchers began in-vestigating deep Learning methods for embedding Graph -structured data. Inthe years since 2013, the field of Graph Representation Learning has witnesseda truly impressive rise and expansion from the development of the standardgraph neural network paradigm to the nascent work on deep generative mod-els of Graph -structured data. The field has transformed from a small subsetof researchers working on a relatively niche topic to one of the fastest growingsub-areas of deep , as the field as grown, our understanding of the methods and the-ories underlying Graph Representation Learning has also stretched backwardsthrough time.