Graph neural network: Difference between revisions

Revision as of 20:53, 28 June 2021

Revision as of 21:41, 28 June 2021

Line 1:

{{AfC submission|t||ts=20210628052201|u=Sheng-Yu PJ Huang|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

[[File:Line graph construction (original).png|thumb|Graph with 5 nodes.]]

In [[deep learning]], a '''graph neural network (GNN)''' is a subarea of [[neural network]], which is designed to process [[Graph theory|graph]] structured data or data that is able to be formulated as a graph potentially<ref name=":0">{{Cite journal|date=2020-01-01|title=Graph neural networks: A review of methods and applications|url=https://www.sciencedirect.com/science/article/pii/S2666651021000012|journal=AI Open|language=en|volume=1|pages=57–81|doi=10.1016/j.aiopen.2021.01.001|issn=2666-6510}}</ref><ref>{{Cite journal|last=Zhang|first=Si|last2=Tong|first2=Hanghang|last3=Xu|first3=Jiejun|last4=Maciejewski|first4=Ross|date=2019-11-10|title=Graph convolutional networks: a comprehensive review|url=https://doi.org/10.1186/s40649-019-0069-y|journal=Computational Social Networks|volume=6|issue=1|pages=11|doi=10.1186/s40649-019-0069-y|issn=2197-4314}}</ref> (e.g. [[social network]], [[polygon mesh]], [[point cloud]]). Since graph data is [[Non-Euclidean geometry|non-Euclidean]], relations between data points cannot be easily represented by their ordering when recording them, and hence [[Convolutional neural network|standard CNN]] is not able to be directly applied to graph data. On the other hand, GNN not only be able to applied to non-Euclidean data but also Euclidean data such as sentences, images or videos since such data can be represented as graph data if organized properly.

== Pipeline of a GNN model<ref name=":0" /> ==

The design pipeline for a GNN model can be generally derived as four steps: find graph structure, specify graph, builddesign modelloss functions, and designbuild lossmodel functions.

[[File:Pipe-line of GNN.png|thumb|558x558px|The general design pipeline for a GNN model.]]

=== Find graph structure ===

In [[graph theory]], a graph is denoted byas <math>G=(V,E)</math>, where:

* <math>V</math>, a [[Set (mathematics)|set]] of ''vertices'' (also called ''nodes'' or ''points'');

Line 17:

=== Specify graph ===

[[File:Scene graph example.png|thumb|529x529px|An example of scene graph.]]

After a graph structure is found in the given data, the type of this graph should also be specified. A graph can be simply categorize as [[Directed graph|directed]]/[[Undirected graph|undirected]] or [[Homogeneous graph|homogeneous]]/[[Heterogeneous graph|heterogeneous]]. Note that for heterogeneous graphs, each edge may differ to the others by its property. For example, each edge in a [[scene graph]]<ref>{{Cite journal|last=Johnson|first=Justin|last2=Krishna|first2=Ranjay|last3=Stark|first3=Michael|last4=Li|first4=Li-Jia|last5=Shamma|first5=David A.|last6=Bernstein|first6=Michael S.|last7=Fei-Fei|first7=Li|title=Image retrieval using scene graphs|url=https://ieeexplore.ieee.org/document/7298990|journal=2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)|pages=3668–3678|doi=10.1109/CVPR.2015.7298990}}</ref> has different meaning to represent the relation between nodes. Sometimes the data's nodes can be merged to obtain graphs of different resolutions, and hence the graph structure may dynamically changed during the learning process. For example, when regarding [[point cloud]] as a graph, it is mostly a dynamic graph<ref>{{Cite journal|last=Wang|first=Yue|last2=Sun|first2=Yongbin|last3=Liu|first3=Z.|last4=Sarma|first4=Sanjay E.|last5=Bronstein|first5=M.|last6=Solomon|first6=J.|date=2019|title=Dynamic Graph CNN for Learning on Point Clouds|url=https://www.semanticscholar.org/paper/Dynamic-Graph-CNN-for-Learning-on-Point-Clouds-Wang-Sun/e1799aaf23c12af6932dc0ef3dfb1638f01413d1|journal=ACM Trans. Graph.|doi=10.1145/3326362}}</ref><ref>{{Cite journal|last=Thomas|first=Hugues|last2=Qi|first2=Charles R.|last3=Deschaud|first3=Jean-Emmanuel|last4=Marcotegui|first4=Beatriz|last5=Goulette|first5=François|last6=Guibas|first6=Leonidas|title=KPConv: Flexible and Deformable Convolution for Point Clouds|url=https://ieeexplore.ieee.org/document/9010002|journal=2019 IEEE/CVF International Conference on Computer Vision (ICCV)|pages=6410–6419|doi=10.1109/ICCV.2019.00651}}</ref><ref>{{Cite journal|last=Lin|first=Zhi-Hao|last2=Huang|first2=Sheng-Yu|last3=Wang|first3=Yu-Chiang Frank|title=Convolution in the Cloud: Learning Deformable Kernels in 3D Graph Convolution Networks for Point Cloud Analysis|url=https://ieeexplore.ieee.org/document/9156514|journal=2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)|pages=1797–1806|doi=10.1109/CVPR42600.2020.00187}}</ref><ref>{{Cite journal|last=Lin|first=Zhi-Hao|last2=Huang|first2=Sheng Yu|last3=Wang|first3=Yu-Chiang Frank|date=2021|title=Learning of 3D Graph Convolution Networks for Point Cloud Analysis|url=https://ieeexplore.ieee.org/abstract/document/9355025|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|pages=1–1|doi=10.1109/TPAMI.2021.3059758|issn=1939-3539}}</ref>.

=== Design loss function ===

Base on the task you are dealing with, [[Loss function|loss functions]] have to be chosen wisely. For example, for a [[Supervised learning|supervised]] node-level classification task, [[Cross entropy|cross-entropy]] might be a reasonable choice.

=== Build model ===

* Propagation module: updating information carried by nodes and/or edges by some aggregation methods.

* Sampling module: when a graph is too large, sampling modules are needed for computation preservation.

* Pooling module: when higher level information (sub-graph-level, graph-level) is needed for the task, pooling modules are needed to aggregate low-level information and provide hierarchical propagation.

== References ==