Representation Learning on Graphs: Methods and Applications

By William L. Hamilton, Rex Ying, Jure Leskovec. 2017

2,156 citations recorded by the source corpus.

Machine learning on graphs is an important and ubiquitous task with applications ranging from drug design to friendship recommendation in social networks. The primary challenge in this domain is finding a way to represent, or encode, graph structure so that it can be easily exploited by machine learning models. Traditionally, machine learning approaches relied on user-defined heuristics to extract features encoding structural information about a graph (e.g., degree statistics or kernel functions). However, recent years have seen a surge in approaches that automatically learn to encode graph structure into low-dimensional embeddings, using techniques based on deep learning and nonlinear dimensionality reduction. Here we provide a conceptual review of key advancements in this area of representation learning on graphs, including matrix factorization-based methods, random-walk based algorithms, and graph neural networks. We review methods to embed individual nodes as well as approaches to embed entire (sub)graphs. In doing so, we develop a unified framework to describe these recent approaches, and we highlight a number of important applications and directions for future work.

Subfields: Artificial Intelligence, Representation & Self-Supervised Learning, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Representation & Self-Supervised Learning

In Graph Learning

Citations in the corpus

Stochastic Training of Graph Convolutional Networks (2017, methodology): “To reduce the receptive field size, Hamilton et al. (2017a) propose a neighbor sampling (NS) algorithm.”
A Structural Probe for Finding Syntax in Word Representations (2019, background): “Under a reasonable deﬁnition, to embed a graph is to learn a vector representation of each node such that geometry in the vector space—distances and norms— approximates geometry in the graph (Hamilton et al., 2017).”
Strategies for Pre-training Graph Neural Networks (2019, methodology): “We also experimented with other popular architectures that are less expressive: GCN (Kipf & Welling, 2016), GAT (Veliˇckovi´c et al., 2019), and GraphSAGE (with mean neighborhood aggregation) (Hamilton et al., 2017b).”
Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018, methodology): “Hamilton et al. (2017b) [19] and Bronstein et al. (2017) [6] provide comprehensive surveys of recent advancements.”
Compositional Fairness Constraints for Graph Embeddings (2019, methodology): “In more recent years, the task of embedding graph-structured data has received increasing attention from the machine learning and data mining communities (Cai et al., 2018; Hamilton et al., 2017b).”
Position-aware Graph Neural Networks (2019, methodology): “Learning low-dimensional vector representations of nodes in graphs (Hamilton et al., 2017b) has led to advances on tasks such as node classiﬁcation (Kipf & Welling, 2017), link prediction (Grover & Leskovec, 2016), graph classiﬁcation (Ying et al., 2018b) and graph generation (You et al., 2018b),…”
Pre-training Graph Neural Networks with Kernels (2018, neutral): “Many approaches have addressed the problem of deﬁning neural networks for graphs [Hamilton et al. , 2017].”
How Powerful are Graph Neural Networks? (2018, methodology): “Recently, there has been a surge of interest in Graph Neural Network (GNN) approaches for representation learning of graphs (Li et al., 2016; Hamilton et al., 2017a; Kipf & Welling, 2017; Velickovic et al., 2018; Xu et al., 2018).”
Deep Graph Infomax (2018, methodology): “…ways to score a representation, but in the graph literature the most common techniques use classiﬁcation (Perozzi et al., 2014; Grover & Leskovec, 2016; Kipf & Welling, 2016b; Hamilton et al., 2017b), though other scoring functions are used (Duran & Niepert, 2017; Bojchevski & G¨unnemann, 2018).”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, background): “[17] provides a conceptual review of recent advancements in this area, and Bronstein et al.”
Modeling polypharmacy side effects with graph convolutional networks (2018, background): “Decagon develops a new graph auto-encoder approach (Hamilton et al. , 2017a), which allows us to develop an end-to-end trainable model for link prediction on a multimodal graph.”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “We include a brief discussion on the ﬁrst two kinds in the Appendix and refer the reader to [15] for a recent survey.”
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models (2018, background): “There have been recent successes in encoding a graph’s structural properties into node embeddings (Hamilton et al., 2017), and one approach to graph generation could be to deﬁne a generative model that decodes edge probabilities based on pairwise relationships between learned node embeddings (as in…”
Provably Powerful Graph Networks (2019, background): “…deep models that are able to learn new graph representations from raw features (e.g., Gori et al. (2005); Duvenaud et al. (2015); Niepert et al. (2016); Kipf and Welling (2016); Veliˇckovi´c et al. (2017); Monti et al. (2017); Hamilton et al. (2017a); Morris et al. (2018); Xu et al. (2019)).”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, methodology): “Notable instances of this model include Neural Fingerprints (Duvenaud et al. 2015), Gated Graph Neural Networks (Li et al. 2016), GraphSAGE (Hamilton, Ying, and Leskovec 2017a), SplineCNN (Fey et al. 2018), and the spectral approaches proposed in (Bruna et al. 2014; Defferrard, X., and Vandergheynst”
Towards Sparse Hierarchical Graph Classifiers (2018, background): “Therefore, it is natural to investigate and generalise CNN elements to graphs [3, 13, 2].”
Self-Supervised Learning: Generative or Contrastive (2020, background): “The central problem in machine learning on graphs is to find a way to represent graph structure so that it can be easily utilized by machine learning models [53].”
Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking (2017, methodology): “Most approaches cannot handle this issue at all, with a notable exception being SDNE and GraphSAGE (Wang et al., 2016; Hamilton et al., 2017).”
An Overview of Deep Semi-Supervised Learning (2020, methodology): “This is especially problematic for evolving graphs, massive graphs that cannot be fully stored in memory, or domains that require generalizing to new graphs after training [60].”