Figure calculation - figure introduction

chart

Most data structures can be seen as graph data structures , Including the list , Trees, etc . If you study it in depth, you can look at graph theory

chart (Graph) It's a node (Vertices/Nodes) And the side (Edge)

$$G=(V,E)$$

notes ： In general , We think that figure (graph) And the Internet (network) The two terms can be used interchangeably . Usually we call it graph .

Classification of graphs

• Undirected and directed graphs ： Whether there is direction between nodes , If there is no direction, it means that both sides can visit directly , If there is a direction , It can only be accessed in a unilateral direction

• Unauthorized graph and authorized graph ： Whether the connecting edge has weight , If there is no weight, the weight of each edge is the same , If there is weight, judge the importance of connection according to the weight

• Isomorphic diagrams and isomers ： Whether nodes and edges belong to the same type , If it is a unified type, it is isomorphic graph , If it's a different type , Is a heterogeneous graph

Degree and neighbor of graph

• Use V Representation node ,E edge , Then the graph can be used G=(V, E) Express
• For digraphs and undirected graphs , Different sides , An undirected graph is equivalent to a bilateral digraph

• degree ： The number of nodes associated with it
  • The degree of ： The number of nodes reaching this node
  • The degree of ： The number of nodes from this node to other nodes

For the node 4： There are three neighbors , The degree is 3, The degree of 2, The degree of 1

The representation of the figure

• Adjacency matrix ：n Nodes ,$nxn$ Matrix , Indicate the relationship between nodes , If node i And nodes j There's a side between , be $A_{ij}=1$, Or the weight value of the edge , If there is no edge $A_{ij}=0$, Adjacency matrix of undirected graph is symmetric matrix .

• Adjacency list ： Similar to hash table , Each node acts as key, The following value is a list , Indicates the connected nodes .

  

• Side set ： Be similar to pair Pair style , Give the start and end points of each edge

• structure characteristics , Node characteristics , Edge feature

Practical example

Graph is a unified language to describe complex things . Like social networks , Internet , Recommendation system , Chemical molecules, etc .

Social networks

• node ： people

• edge ： All kinds of connections between people , Such as parental relationship 、 Friendship 、 Colleague relations, etc .

Internet

• node ： Webpage
• edge ： Hyperlinks between web pages

Recommendation system

• node ： Users and products
• edge ： user 、 Purchase between goods 、 Click and so on

Chemical molecules

• node ： atom
• edge ： The interaction between atoms , Also known as chemical bonds

Picture learning

The data object is graph

Like voice 、 Images 、 Text has a neat and regular data structure ：

In reality, the graph is irregular , Difficult to model directly ：

Figure the advantages of learning

• General deep learning ： Most of them deal with rule data , Difficult to handle irregular data .

• Picture learning ： It can easily handle irregular data ( chart ), Make full use of graph structure information .

Application of graph learning

• Node level tasks
• Side level tasks
• Graph level tasks

Node level tasks

• Financial fraud detection

Node classification task , Features and associations based on nodes , Judge the node （ People or incoming items ） Is it a fraud category or a non fraud category

Reference article ：《A semi-supervised Graph Attentive Network for Financial Fraud Detection》

• object detection

Different from general target detection image data , It's usually 3D Point cloud data , Discrete data obtained by means of lidar .

Reference article ： 《Point-GNN: Graph Neural Network for 3D object Detection in a Point Cloud》

Side level tasks

• Recommendation system

The recommendation system is classic Link Prediction Mission

Graph level tasks

• Smell recognition

Reference article ：《Learning to Smell: Using Deep Learning to Predict the Olfactory Properties of Molecules》

Figure learning application

Reference resources

• https://www.jiqizhixin.com/articles/2019-07-30-10?from=synced&keyword=%E5%9B%BE%E8%AE%BA%E4%B8%8E%E5%9B%BE%E5%AD%A6%E4%B9%A0

• Stanford CS224W Course ： http://cs224w.stanford.edu

• Figure Learning Library PGL：https://github.com/PaddlePaddle/PGL