Graph Neural Nets
Some data is not a table or a sequence but a graph, and the question is how a network can learn from the structure and properties of that graph. The page starts with what GNNs actually do and where they fall short, then the courses, then graph convolutional networks, and then the node-embedding methods one after another: DeepWalk, Node2vec, GraphSAGE, SDNE, Diff2vec, and Splitter with its relatives.
The same notes are in Graph Theory.
The first thing to read is the skeptical one. (amazing) Why i am luke warm about GNN’s - really good insight to what they do (compressing data, vs adjacy graphs, vs graphs, high dim relations, etc.). With that caution in mind, the (amazing) Graphical intro to GNNs is Distill's gentle introduction to graph neural networks, built around the question of which components are needed for learning algorithms that leverage the structure and properties of graphs. For a talk instead of an article, Learning on graphs youtube - uriel singer is Uriel Singer's lecture on learning on graphs.
Once the idea is clear, the next question is how to compare models fairly. Benchmarking GNN’s, methodology, git, the works. is the NTU Graph Deep Learning Lab post by Chaitanya Joshi on the Benchmarking Graph Neural Networks paper, written because GNNs are now used across social sciences, knowledge graphs, chemistry, physics, and neuroscience. The papers themselves are gathered in Awesome graph classification on github, a collection of important graph embedding, classification, and representation learning papers with implementations.
Octavian in medium on graphs wrote A really good intro to graph networks, too long too summarize; it touches clever, mcgraph, regression, classification, embedding on graphs. The author's list then moved to the application of graph networks, and to recommender systems using GNN, w2v, pytorch w2v, networkx, sparse matrices, matrix factorization, and dictionary optimization, part 1 here (how to find product relations, important: creating negative samples); those sources are kept at the end of the page.
The graph view also reaches text. Transformers are GNN, original: Transformers are graphs, not the typical embedding on a graph, but a more holistic approach to understanding text as a graph. is The Gradient's piece "Transformers are Graph Neural Networks". The author's next notes were CNN for graphs and, for a practical start, Staring with gnn, David Mack's guide for research teams that have graph data and want to perform machine learning on it but are not sure where to start. The notes that followed are really good - Basics deep walk and graphsage, application of gnn, Michael Bronstein’s Central page for Graph deep learning articles on Medium (worth reading), and Medium on Intro, basics, deep walk, graph sage; their sources are at the end of the page.
Attention also has a graph form. GAT graphi attention networks is the paper page with examples. The graph attentional layer utilised throughout these networks is computationally efficient (does not require costly matrix operations, and is parallelizable across all nodes in the graph), allows for (implicitly) assigning different importances to different nodes within a neighborhood while dealing with different sized neighborhoods, and does not depend on knowing the entire graph structure upfront—thus addressing many of the theoretical issues with approaches.
Structure can matter more than neighborhood. Struc2vec and its KDD 2017 youtube talk are about Learning Node Representations from Structural Identity: the struc2vec algorithm learns continuous representations for nodes in any graph. struc2vec captures structural equivalence between nodes.
GNN courses
After the overview, the courses give the same material in order, with lectures to follow.
The same notes are in Graph/GNN courses.
The machine learning with graphs by Stanford course is CS224W. The Graph deep learning course is the geometric deep learning course on Grids, Groups, Graphs, Geodesics, and Gauges. Its short version is on youtube: the ICLR 2021 keynote by Michael Bronstein, "Geometric Deep Learning: The Erlangen Programme of ML", covering graphs, sets, groups, GNNs.
Graph Convolutional Networks
The courses lead to the most common GNN layer, the graph convolution. The Explaination here, with some examples is the post "How powerful are Graph Convolutional Networks?", which starts from the fact that many real-world datasets come as graphs or networks (social networks, knowledge graphs, protein-interaction networks, the World Wide Web) while little attention had gone into generalizing neural networks to them.
Deep walk
Before convolutions on graphs, the simpler route was to turn a graph into walks and embed them like words.
The same notes are in Graph Theory.
The code is the Git repo, DeepWalk - Deep Learning for Graphs, and the Paper is the arXiv paper "DeepWalk: Online Learning of Social Representations". For the intuition, Medium is the illustrated explanation of using skipgram to encode graph structure, and medium on W2v, deep walk, graph2vec, n2v goes wider.
Node2vec
Node2vec keeps the walk idea from DeepWalk and changes how the walks are drawn.
The same notes are in Graph Topics.
The Git repo is an implementation of the node2vec algorithm, and Stanford is the node2vec project page. Elior on medium also gave the talk on youtube, the PyData Tel Aviv Meetup session on Node2vec by Elior Cohen. The Paper starts from the problem that prediction tasks over nodes and edges need carefully engineered features, and that representation learning can automate that by learning the features themselves.
Graphsage
After walk-based embeddings, GraphSAGE is the next method on the list. Its only note is a medium post, kept at the end of the page.
SDNE - structural deep network embedding
SDNE follows GraphSAGE as another way to embed nodes, here with a deep structural model. Its only note is a medium post, kept at the end of the page.
Diff2vec
Diff2vec replaces random walks with diffusion. The Git repo is the reference implementation of Diffusion2Vec (Complenet 2018) built on Gensim and NetworkX, and the figure below shows the method.
Splitter
Every method so far gives each node one vector. Splitter asks whether that is enough. The git repo is a PyTorch implementation of the WWW 2019 work, and the paper is “Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts”. Its abstract states the problem and the result:
Recent interest in graph embedding methods has focused on learning a single representation for each node in the graph. But can nodes really be best described by a single vector representation? In this work, we propose a method for learning multiple representations of the nodes in a graph (e.g., the users of a social network). Based on a principled decomposition of the ego-network, each representation encodes the role of the node in a different local community in which the nodes participate. These representations allow for improved reconstruction of the nuanced relationships that occur in the graph a phenomenon that we illustrate through state-of-the-art results on link prediction tasks on a variety of graphs, reducing the error by up to 90%. In addition, we show that these embeddings allow for effective visual analysis of the learned community structure.
The two figures below show the Splitter idea.
Communities can also be learned together with the embedding. Self clustering graph embeddings is the TensorFlow reference implementation of 'GEMSEC: Graph Embedding with Self Clustering' (ASONAM 2019), shown in the next figure.
Back on the walk side, Walklets is similar to deep walk with node skips - lots of improvements, works in scale due to lower size representations, improves results, etc.
When speed is the constraint, Nodevectors is the library: its Git repo calls it The fastest network node embeddings in the west.
To close the loop back to the basics, the Towards Data Science gentle introduction to graph neural network basics, DeepWalk and GraphSAGE is at https://towardsdatascience.com/a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3.
Deprecated links
These links and images no longer work. The original wording is kept here. A same-resource copy, when one was checked, is used above.
- Towards Data Science: home. This address no longer opens: https://towardsdatascience.com/graph-deep-learning/home - Towards Data Science: graph-embeddings-the-summary-cc6075aba007. This address no longer opens: https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007 - Towards Data Science: how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-62acf5b143d0. This address no longer opens: https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-62acf5b143d0 - Towards Data Science: https-medium-com-aishwaryajadhav-applications-of-graph-neural-networks-1420576be574. This address no longer opens: https://towardsdatascience.com/https-medium-com-aishwaryajadhav-applications-of-graph-neural-networks-1420576be574 - Towards Data Science: node2vec-embeddings-for-graph-data-32a866340fef. This address no longer opens: https://towardsdatascience.com/node2vec-embeddings-for-graph-data-32a866340fef - Towards Data Science: recommender-systems-applying-graph-and-nlp-techniques-619dbedd9ecc. This address no longer opens: https://towardsdatascience.com/recommender-systems-applying-graph-and-nlp-techniques-619dbedd9ecc - Towards Data Science: transformers-are-graph-neural-networks-bca9f75412aa. This address no longer opens: https://towardsdatascience.com/transformers-are-graph-neural-networks-bca9f75412aa
Last updated
Was this helpful?