Introduction to Graph Machine Learning

In this blog post, we cover the basics of graph machine learning.

We first study what graphs are, why they are used, and how best to represent them. We then cover briefly how people learn on graphs, from pre-neural methods (exploring graph features at the same time) to what are commonly called Graph Neural Networks. Lastly, we peek into the world of Transformers for graphs.

Graphs

What is a graph?

In its essence, a graph is a description of items linked by relations.

Examples of graphs include social networks (Twitter, Mastodon, any citation networks linking papers and authors), molecules, knowledge graphs (such as UML diagrams, encyclopedias, and any website with hyperlinks between its pages), sentences expressed as their syntactic trees, any 3D mesh, and more! It is, therefore, not hyperbolic to say that graphs are everywhere.

The items of a graph (or network) are called its nodes (or vertices), and their connections its edges (or links). For example, in a social network, nodes are users and edges their connections; in a molecule, nodes are atoms and edges their molecular bond.

• A graph with either typed nodes or typed edges is called heterogeneous (example: citation networks with items that can be either papers or authors have typed nodes, and XML diagram where relations are typed have typed edges). It cannot be represented solely through its topology, it needs additional information. This post focuses on homogeneous graphs.
• A graph can also be directed (like a follower network, where A follows B does not imply B follows A) or undirected (like a molecule, where the relation between atoms goes both ways). Edges can connect different nodes or one node to itself (self-edges), but not all nodes need to be connected.

If you want to use your data, you must first consider its best characterisation (homogeneous/heterogeneous, directed/undirected, and so on).

What are graphs used for?

Let's look at a panel of possible tasks we can do on graphs.

How do we represent graphs?

It should: