Diving into Graphs/GNN/GCN

Koshy
2 min readMar 6, 2023

--

Graphs
Photo by DeepMind on Unsplash

Most entity relationships can be modelled with a graph data structure. Entity in our context could be people (as applied in most social networks), topics (search solutions), destination lookup (maps), delivery networks (parcel/courier services) and more.

Defining relationship between entities using a graph today relies on explicit attribute/property mapping on the edges of the graph or as a property of the node itself. The graph model heavily depends on the use-cases/scenarios in hand. You could model the edge of the graph to represent the distance between nodes (as in maps) or the relation itself (father-of, friend-of) etc or more. Graph modelling in itself needs a thorough understanding of the domain, the problem statement and definitely require refinements with the architects.

Kicking off

If you have been away from applied graphs, the fundamentals and basic graph algorithms are quite well covered in here: Introduction to Graph Theory | Graphs in Python (analyticsvidhya.com)

CNN’s and GCN’s

Once you have designed couple of graph models, you realize its a challenge to smartly aggregate/summarize relationships across the nodes/edges. You could write typical graph traversal algorithms, visit nodes/edges one by one while internally aggregating the relations. Alternatively, you could review feasibility to use Graph Convolution Networks (GCN). Yes, but before you dive into GCN, you would need a refresher on — adjacency matrix, matrix multiplication and then get a fundamental understanding of the Convolution Neural Network (CNN) too. Would recommend dummies read here.

Diving further into GNN

A required area to dive into next is the Graph Neural Network (GNN). A Gentle Introduction to Graph Neural Networks (distill.pub) is a great start, followed with this detailed one. The detailed one is part of a larger course and has interesting set of videos.

If you have successfully reached here and have tried couple of stunts with GCN’s and GNN’s, you would be keen to know where the research/ academia is headed. This is where Recent Advances in Deep Learning for Routing Problems | Chaitanya K. Joshi (chaitjo.com helps.

Further ahead, do review the best graph neural network resources to learn from (indiaai.gov.in too, especially the open-source libraries mentioned.

--

--

Koshy

A versatile software engineer, he has a range of interests beyond coding. Earlier posts are here : https://devwaves.blogspot.com/