A walkthrough of representation learning on graphs.

In the path of building machines to understand the real world we live in, it becomes evident that the ability to just identify individual items or recognise a pattern out of the given set of samples is merely a small part of the puzzle.
For instance, take the common application of machine learning to train a model to identify classes of objects in a set of given images. We know that state-of-the-art models are able to identify the different objects to almost the level of humans in those images.
But do they really understand what it sees? Or can they reason about the objects they detect? Do they really understand? No.
Towards the goal of building intelligence, it is clear that the systems should have the ability to formulate far more complex models of the world from the individual items they detect/sense.
How do we know that this is what should happen? Well, because that’s what we do. Humans. The best evidence of intelligence that we know of in the world.
A model can be interpreted as a representation of a thing or a set of things. Narrowing down to our area of focus, a model can be seen as a graph.
Taking the same example of detecting objects in an image, imagine we detect an instance of a dog and a person in a given image. Now a trained model will easily detect the dog and the person individually. But if it was us, after seeing the dog and the person in the image we naturally go further to see that, oh, that must be the pet of that person. And normally people and dogs have a good relationship.
Now what we did there was, we made sense. We reasoned. This phenomenon of ‘making sense’ can be interpreted as an act of knowledge. Knowledge about the interactions between the detected object and past experience that we have seen these objects together before.
This infers that we need to integrate knowledge into our systems if we want them to build models of the world.
As we know, recent advancements in technology have gathered a huge magnitude of data about us and the world we live in. And the more data we collect, people have thought of ways to organise and manage this data, specifically in methods of graphs. It turns out that many points of data can be represented symbolically in ways defined by logic.
With the surge in the success of machine learning, integration of knowledge is clearly identified as a path to improvement. Hence more research interest has been gathered around the areas of using graphs in the pipelines of machine learning, that turns out to be quite promising.
But one challenge in this quest is that the machine learning approaches and the graph building approaches, don’t specifically speak the same language. In other terms, machine learning prevails in the numeric space, whereas graphs prevail in the symbolic space.
In the field of machine learning, several recent research attempts have taken strides towards trying to encode the graph structures in machine-readable forms.
Even though traditional methods have taken more statistical approaches towards this goal, it is seen that more and more approaches of automatically learning these embeddings have emerged more triumphant.
The following few posts aim to synthesise these concepts and present an overview of the different approaches of representation learning on graphs. The ideas will be discussed as a walk-through of the paper by Hamilton et al. called ‘Representation Learning on Graphs: Methods and Applications’.
The discussion is divided into two main sections, namely, Embedding of Nodes and Embedding of Subgraphs.
The notions throughout the explanations are as follows;
Input is an undirected graph G = (V, E), associated binary adjacency matrix A
Node attribute matrix X ∈ R m×|V|
Output vector z ∈ Rd , where d << |V|
The goal is to use A and X to map a node/subgraph to a vector z.
You can avoid the paywall and read the rest that follows this post using the links below :)
See the second post that follows this — Embedding of Nodes
And the third post in this series — Embedding of Subgraphs
Thanks for reading.