Preliminaries

Graph

What is Graph?

• A data structure consisting of two components: nodes(vertices) and edges
• G = (V,E)

  • V: the set of nodes, E: the edges between them

    https://lh3.googleusercontent.com/fh3CK1NzTTh--qjgDiDDqhI_ISV1qADhFb7NKzyJOKPxxAGJhj5VHPWwC1hVMS5tisTFxUK0FQc2Rro6dvvQqKHKNlgHsbwffewzwG_UeKHyARSIzdsOHLkJSjO7Ci5UVioWAfQX

Why Graph?

• A graph can represent things like social media networks, or molecules(nodes → users // edges → connections)

How to represent Graph?

• A graph is often represented by A, an adjacency matrix
  • A graph that has n nodes ⇒ A has a dimension of (n x n)
  • When the nodes have a set of features (e.g., a user profile), in this case, f number of features ⇒ The node feature matrix X has a dimension of (n x f)

Graph Neural Network (GNN)

What is GNN?

• Graph Neural Networks
• A class of deep learning methods designed to perform inference on data described by graphs

Why GNN? (Why CNNs fail on graphs?)

• To handle complex graph data with conventional machine learning and deep learning tools
• Conventional ML and DL tools are specialized in simple data types

  • E.g., images with the same structure and size ⇒ We can think of as fixed-size grid graphs

  • E.g., text and speech ⇒ We can think of them as line graphs(reference)

    https://lh4.googleusercontent.com/S1Jpu7J4OdDfcxihhLKyzxNtMJukxu3ZawcQrx5WKcOPCgvTVBl9E22JAczq-tWqDO2XKFD_XdoqretJiDnI4FAl11xNJnvxmOfxy19T-4sAUMz50YnFS08KzmRWOWzgXtzhzuy8

With GNN we can do

• Node classification
• Graph classification
• Graph visualization