Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Graph neural network
Class of artificial neural networks

Graph neural networks (GNNs) are a type of artificial neural network specialized for processing graphs, such as those used in molecular drug design where atoms are nodes and bonds are edges. GNNs use pairwise message passing to iteratively update node representations by exchanging information with neighbors. They extend to various domains including natural language processing, social networks, and molecular biology. Some neural networks like convolutional neural networks and transformers can be viewed as GNNs on specific graph structures. Popular open source libraries for GNNs include PyTorch Geometric (PyTorch), TensorFlow GNN, Deep Graph Library, and others.

We don't have any images related to Graph neural network yet.
We don't have any YouTube videos related to Graph neural network yet.
We don't have any PDF documents related to Graph neural network yet.
We don't have any Books related to Graph neural network yet.

Architecture

The architecture of a generic GNN implements the following fundamental layers:34

  1. Permutation equivariant: a permutation equivariant layer maps a representation of a graph into an updated representation of the same graph. In the literature, permutation equivariant layers are implemented via pairwise message passing between graph nodes.3536 Intuitively, in a message passing layer, nodes update their representations by aggregating the messages received from their immediate neighbours. As such, each message passing layer increases the receptive field of the GNN by one hop.
  2. Local pooling: a local pooling layer coarsens the graph via downsampling. Local pooling is used to increase the receptive field of a GNN, in a similar fashion to pooling layers in convolutional neural networks. Examples include k-nearest neighbours pooling, top-k pooling,37 and self-attention pooling.38
  3. Global pooling: a global pooling layer, also known as readout layer, provides fixed-size representation of the whole graph. The global pooling layer must be permutation invariant, such that permutations in the ordering of graph nodes and edges do not alter the final output.39 Examples include element-wise sum, mean or maximum.

It has been demonstrated that GNNs cannot be more expressive than the Weisfeiler–Leman Graph Isomorphism Test.4041 In practice, this means that there exist different graph structures (e.g., molecules with the same atoms but different bonds) that cannot be distinguished by GNNs. More powerful GNNs operating on higher-dimension geometries such as simplicial complexes can be designed.424344 As of 2022, whether or not future architectures will overcome the message passing primitive is an open research question.45

Message passing layers

Message passing layers are permutation-equivariant layers mapping a graph into an updated representation of the same graph. Formally, they can be expressed as message passing neural networks (MPNNs).46

Let G = ( V , E ) {\displaystyle G=(V,E)} be a graph, where V {\displaystyle V} is the node set and E {\displaystyle E} is the edge set. Let N u {\displaystyle N_{u}} be the neighbourhood of some node u ∈ V {\displaystyle u\in V} . Additionally, let x u {\displaystyle \mathbf {x} _{u}} be the features of node u ∈ V {\displaystyle u\in V} , and e u v {\displaystyle \mathbf {e} _{uv}} be the features of edge ( u , v ) ∈ E {\displaystyle (u,v)\in E} . An MPNN layer can be expressed as follows:47

h u = ϕ ( x u , ⨁ v ∈ N u ψ ( x u , x v , e u v ) ) {\displaystyle \mathbf {h} _{u}=\phi \left(\mathbf {x} _{u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)}

where ϕ {\displaystyle \phi } and ψ {\displaystyle \psi } are differentiable functions (e.g., artificial neural networks), and ⨁ {\displaystyle \bigoplus } is a permutation invariant aggregation operator that can accept an arbitrary number of inputs (e.g., element-wise sum, mean, or max). In particular, ϕ {\displaystyle \phi } and ψ {\displaystyle \psi } are referred to as update and message functions, respectively. Intuitively, in an MPNN computational block, graph nodes update their representations by aggregating the messages received from their neighbours.

The outputs of one or more MPNN layers are node representations h u {\displaystyle \mathbf {h} _{u}} for each node u ∈ V {\displaystyle u\in V} in the graph. Node representations can be employed for any downstream task, such as node/graph classification or edge prediction.

Graph nodes in an MPNN update their representation aggregating information from their immediate neighbours. As such, stacking n {\displaystyle n} MPNN layers means that one node will be able to communicate with nodes that are at most n {\displaystyle n} "hops" away. In principle, to ensure that every node receives information from every other node, one would need to stack a number of MPNN layers equal to the graph diameter. However, stacking many MPNN layers may cause issues such as oversmoothing48 and oversquashing.49 Oversmoothing refers to the issue of node representations becoming indistinguishable. Oversquashing refers to the bottleneck that is created by squeezing long-range dependencies into fixed-size representations. Countermeasures such as skip connections5051 (as in residual neural networks), gated update rules52 and jumping knowledge53 can mitigate oversmoothing. Modifying the final layer to be a fully-adjacent layer, i.e., by considering the graph as a complete graph, can mitigate oversquashing in problems where long-range dependencies are required.54

Other "flavours" of MPNN have been developed in the literature,55 such as graph convolutional networks56 and graph attention networks,57 whose definitions can be expressed in terms of the MPNN formalism.

Graph convolutional network

The graph convolutional network (GCN) was first introduced by Thomas Kipf and Max Welling in 2017.58

A GCN layer defines a first-order approximation of a localized spectral filter on graphs. GCNs can be understood as a generalization of convolutional neural networks to graph-structured data.

The formal expression of a GCN layer reads as follows:

H = σ ( D ~ − 1 2 A ~ D ~ − 1 2 X Θ ) {\displaystyle \mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)}

where H {\displaystyle \mathbf {H} } is the matrix of node representations h u {\displaystyle \mathbf {h} _{u}} , X {\displaystyle \mathbf {X} } is the matrix of node features x u {\displaystyle \mathbf {x} _{u}} , σ ( ⋅ ) {\displaystyle \sigma (\cdot )} is an activation function (e.g., ReLU), A ~ {\displaystyle {\tilde {\mathbf {A} }}} is the graph adjacency matrix with the addition of self-loops, D ~ {\displaystyle {\tilde {\mathbf {D} }}} is the graph degree matrix with the addition of self-loops, and Θ {\displaystyle \mathbf {\Theta } } is a matrix of trainable parameters.

In particular, let A {\displaystyle \mathbf {A} } be the graph adjacency matrix: then, one can define A ~ = A + I {\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I} } and D ~ i i = ∑ j ∈ V A ~ i j {\displaystyle {\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}} , where I {\displaystyle \mathbf {I} } denotes the identity matrix. This normalization ensures that the eigenvalues of D ~ − 1 2 A ~ D ~ − 1 2 {\displaystyle {\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}} are bounded in the range [ 0 , 1 ] {\displaystyle [0,1]} , avoiding numerical instabilities and exploding/vanishing gradients.

A limitation of GCNs is that they do not allow multidimensional edge features e u v {\displaystyle \mathbf {e} _{uv}} .59 It is however possible to associate scalar weights w u v {\displaystyle w_{uv}} to each edge by imposing A u v = w u v {\displaystyle A_{uv}=w_{uv}} , i.e., by setting each nonzero entry in the adjacency matrix equal to the weight of the corresponding edge.

Graph attention network

The graph attention network (GAT) was introduced by Petar Veličković et al. in 2018.60

Graph attention network is a combination of a GNN and an attention layer. The implementation of attention layer in graphical neural networks helps provide attention or focus to the important information from the data instead of focusing on the whole data.

A multi-head GAT layer can be expressed as follows:

h u = ‖ k = 1 K σ ( ∑ v ∈ N u α u v W k x v ) {\displaystyle \mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}

where K {\displaystyle K} is the number of attention heads, ‖ {\displaystyle {\Big \Vert }} denotes vector concatenation, σ ( ⋅ ) {\displaystyle \sigma (\cdot )} is an activation function (e.g., ReLU), α i j {\displaystyle \alpha _{ij}} are attention coefficients, and W k {\displaystyle W^{k}} is a matrix of trainable parameters for the k {\displaystyle k} -th attention head.

For the final GAT layer, the outputs from each attention head are averaged before the application of the activation function. Formally, the final GAT layer can be written as:

h u = σ ( 1 K ∑ k = 1 K ∑ v ∈ N u α u v W k x v ) {\displaystyle \mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}

Attention in Machine Learning is a technique that mimics cognitive attention. In the context of learning on graphs, the attention coefficient α u v {\displaystyle \alpha _{uv}} measures how important is node u ∈ V {\displaystyle u\in V} to node v ∈ V {\displaystyle v\in V} .

Normalized attention coefficients are computed as follows:

α u v = exp ⁡ ( LeakyReLU ( a T [ W x u ‖ W x v ‖ e u v ] ) ) ∑ z ∈ N u exp ⁡ ( LeakyReLU ( a T [ W x u ‖ W x z ‖ e u z ] ) ) {\displaystyle \alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{z}\Vert \mathbf {e} _{uz}]\right))}}}

where a {\displaystyle \mathbf {a} } is a vector of learnable weights, ⋅ T {\displaystyle \cdot ^{T}} indicates transposition, e u v {\displaystyle \mathbf {e} _{uv}} are the edge features (if present), and LeakyReLU {\displaystyle {\text{LeakyReLU}}} is a modified ReLU activation function. Attention coefficients are normalized to make them easily comparable across different nodes.61

A GCN can be seen as a special case of a GAT where attention coefficients are not learnable, but fixed and equal to the edge weights w u v {\displaystyle w_{uv}} .

Gated graph sequence neural network

The gated graph sequence neural network (GGS-NN) was introduced by Yujia Li et al. in 2015.62 The GGS-NN extends the GNN formulation by Scarselli et al.63 to output sequences. The message passing framework is implemented as an update rule to a gated recurrent unit (GRU) cell.

A GGS-NN can be expressed as follows:

h u ( 0 ) = x u ‖ 0 {\displaystyle \mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0} } m u ( l + 1 ) = ∑ v ∈ N u Θ h v {\displaystyle \mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}} h u ( l + 1 ) = GRU ( m u ( l + 1 ) , h u ( l ) ) {\displaystyle \mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})}

where ‖ {\displaystyle \Vert } denotes vector concatenation, 0 {\displaystyle \mathbf {0} } is a vector of zeros, Θ {\displaystyle \mathbf {\Theta } } is a matrix of learnable parameters, GRU {\displaystyle {\text{GRU}}} is a GRU cell, and l {\displaystyle l} denotes the sequence index. In a GGS-NN, the node representations are regarded as the hidden states of a GRU cell. The initial node features x u ( 0 ) {\displaystyle \mathbf {x} _{u}^{(0)}} are zero-padded up to the hidden state dimension of the GRU cell. The same GRU cell is used for updating representations for each node.

Local pooling layers

Local pooling layers coarsen the graph via downsampling. We present here several learnable local pooling strategies that have been proposed.64 For each case, the input is the initial graph is represented by a matrix X {\displaystyle \mathbf {X} } of node features, and the graph adjacency matrix A {\displaystyle \mathbf {A} } . The output is the new matrix X ′ {\displaystyle \mathbf {X} '} of node features, and the new graph adjacency matrix A ′ {\displaystyle \mathbf {A} '} .

Top-k pooling

We first set

y = X p ‖ p ‖ {\displaystyle \mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}}

where p {\displaystyle \mathbf {p} } is a learnable projection vector. The projection vector p {\displaystyle \mathbf {p} } computes a scalar projection value for each graph node.

The top-k pooling layer 65 can then be formalised as follows:

X ′ = ( X ⊙ sigmoid ( y ) ) i {\displaystyle \mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }} A ′ = A i , i {\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}

where i = top k ( y ) {\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )} is the subset of nodes with the top-k highest projection scores, ⊙ {\displaystyle \odot } denotes element-wise matrix multiplication, and sigmoid ( ⋅ ) {\displaystyle {\text{sigmoid}}(\cdot )} is the sigmoid function. In other words, the nodes with the top-k highest projection scores are retained in the new adjacency matrix A ′ {\displaystyle \mathbf {A} '} . The sigmoid ( ⋅ ) {\displaystyle {\text{sigmoid}}(\cdot )} operation makes the projection vector p {\displaystyle \mathbf {p} } trainable by backpropagation, which otherwise would produce discrete outputs.66

Self-attention pooling

We first set

y = GNN ( X , A ) {\displaystyle \mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )}

where GNN {\displaystyle {\text{GNN}}} is a generic permutation equivariant GNN layer (e.g., GCN, GAT, MPNN).

The Self-attention pooling layer67 can then be formalised as follows:

X ′ = ( X ⊙ y ) i {\displaystyle \mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }} A ′ = A i , i {\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}

where i = top k ( y ) {\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )} is the subset of nodes with the top-k highest projection scores, ⊙ {\displaystyle \odot } denotes element-wise matrix multiplication.

The self-attention pooling layer can be seen as an extension of the top-k pooling layer. Differently from top-k pooling, the self-attention scores computed in self-attention pooling account both for the graph features and the graph topology.

Heterophilic Graph Learning

Homophily principle, i.e., nodes with the same labels or similar attributes are more likely to be connected, has been commonly believed to be the main reason for the superiority of Graph Neural Networks (GNNs) over traditional Neural Networks (NNs) on graph-structured data, especially on node-level tasks.68 However, recent work has identified a non-trivial set of datasets where GNN’s performance compared to the NN’s is not satisfactory.69 Heterophily, i.e., low homophily, has been considered the main cause of this empirical observation.70 People have begun to revisit and re-evaluate most existing graph models in the heterophily scenario across various kinds of graphs, e.g., heterogeneous graphs, temporal graphs and hypergraphs. Moreover, numerous graph-related applications are found to be closely related to the heterophily problem, e.g. graph fraud/anomaly detection, graph adversarial attacks and robustness, privacy, federated learning and point cloud segmentation, graph clustering, recommender systems, generative models, link prediction, graph classification and coloring, etc. In the past few years, considerable effort has been devoted to studying and addressing the heterophily issue in graph learning.717273

Applications

Protein folding

See also: AlphaFold

Graph neural networks are one of the main building blocks of AlphaFold, an artificial intelligence program developed by Google's DeepMind for solving the protein folding problem in biology. AlphaFold achieved first place in several CASP competitions.747576

Social networks

See also: Recommender system

Social networks are a major application domain for GNNs due to their natural representation as social graphs. GNNs are used to develop recommender systems based on both social relations and item relations.7778

Combinatorial optimization

See also: Combinatorial optimization

GNNs are used as fundamental building blocks for several combinatorial optimization algorithms.79 Examples include computing shortest paths or Eulerian circuits for a given graph,80 deriving chip placements superior or competitive to handcrafted human solutions,81 and improving expert-designed branching rules in branch and bound.82

Cyber security

See also: Intrusion detection system

When viewed as a graph, a network of computers can be analyzed with GNNs for anomaly detection. Anomalies within provenance graphs often correlate to malicious activity within the network. GNNs have been used to identify these anomalies on individual nodes83 and within paths84 to detect malicious processes, or on the edge level85 to detect lateral movement.

Water distribution networks

See also: Water distribution system

Water distribution systems can be modelled as graphs, being then a straightforward application of GNN. This kind of algorithm has been applied to water demand forecasting,86 interconnecting District Measuring Areas to improve the forecasting capacity. Other application of this algorithm on water distribution modelling is the development of metamodels.87

Computer Vision

See also: Computer vision

To represent an image as a graph structure, the image is first divided into multiple patches, each of which is treated as a node in the graph. Edges are then formed by connecting each node to its nearest neighbors based on spatial or feature similarity. This graph-based representation enables the application of graph learning models to visual tasks. The relational structure helps to enhance feature extraction and improve performance on image understanding.88

Text and NLP

See also: Natural language processing

Graph-based representation of text helps to capture deeper semantic relationships between words. Many studies have used graph networks to enhance performance in various text processing tasks such as text classification, question answering, Neural Machine Translation (NMT), event extraction, fact verification, etc.89

References

  1. Wu, Lingfei; Cui, Peng; Pei, Jian; Zhao, Liang (2022). "Graph Neural Networks: Foundations, Frontiers, and Applications". Springer Singapore: 725. https://graph-neural-networks.github.io/ ↩

  2. Scarselli, Franco; Gori, Marco; Tsoi, Ah Chung; Hagenbuchner, Markus; Monfardini, Gabriele (2009). "The Graph Neural Network Model". IEEE Transactions on Neural Networks. 20 (1): 61–80. doi:10.1109/TNN.2008.2005605. ISSN 1941-0093. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  3. Micheli, Alessio (2009). "Neural Network for Graphs: A Contextual Constructive Approach". IEEE Transactions on Neural Networks. 20 (3): 498–511. doi:10.1109/TNN.2008.2010350. ISSN 1045-9227. PMID 19193509. S2CID 17486263. https://ieeexplore.ieee.org/document/4700287 ↩

  4. Sanchez-Lengeling, Benjamin; Reif, Emily; Pearce, Adam; Wiltschko, Alex (2021-09-02). "A Gentle Introduction to Graph Neural Networks". Distill. 6 (9): e33. doi:10.23915/distill.00033. ISSN 2476-0757. https://distill.pub/2021/gnn-intro ↩

  5. Daigavane, Ameya; Ravindran, Balaraman; Aggarwal, Gaurav (2021-09-02). "Understanding Convolutions on Graphs". Distill. 6 (9): e32. doi:10.23915/distill.00032. ISSN 2476-0757. S2CID 239678898. https://distill.pub/2021/understanding-gnns ↩

  6. Stokes, Jonathan M.; Yang, Kevin; Swanson, Kyle; Jin, Wengong; Cubillos-Ruiz, Andres; Donghia, Nina M.; MacNair, Craig R.; French, Shawn; Carfrae, Lindsey A.; Bloom-Ackermann, Zohar; Tran, Victoria M.; Chiappino-Pepe, Anush; Badran, Ahmed H.; Andrews, Ian W.; Chory, Emma J. (2020-02-20). "A Deep Learning Approach to Antibiotic Discovery". Cell. 180 (4): 688–702.e13. doi:10.1016/j.cell.2020.01.021. ISSN 1097-4172. PMC 8349178. PMID 32084340. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8349178 ↩

  7. Yang, Kevin; Swanson, Kyle; Jin, Wengong; Coley, Connor; Eiden, Philipp; Gao, Hua; Guzman-Perez, Angel; Hopper, Timothy; Kelley, Brian (2019-11-20), Analyzing Learned Molecular Representations for Property Prediction, arXiv:1904.01561 /wiki/ArXiv_(identifier) ↩

  8. Marchant, Jo (2020-02-20). "Powerful antibiotics discovered using AI". Nature. doi:10.1038/d41586-020-00018-3. PMID 33603175. https://www.nature.com/articles/d41586-020-00018-3 ↩

  9. Scarselli, Franco; Gori, Marco; Tsoi, Ah Chung; Hagenbuchner, Markus; Monfardini, Gabriele (2009). "The Graph Neural Network Model". IEEE Transactions on Neural Networks. 20 (1): 61–80. doi:10.1109/TNN.2008.2005605. ISSN 1941-0093. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  10. Micheli, Alessio (2009). "Neural Network for Graphs: A Contextual Constructive Approach". IEEE Transactions on Neural Networks. 20 (3): 498–511. doi:10.1109/TNN.2008.2010350. ISSN 1045-9227. PMID 19193509. S2CID 17486263. https://ieeexplore.ieee.org/document/4700287 ↩

  11. Kipf, Thomas N; Welling, Max (2016). "Semi-supervised classification with graph convolutional networks". IEEE Transactions on Neural Networks. 5 (1): 61–80. arXiv:1609.02907. doi:10.1109/TNN.2008.2005605. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  12. Hamilton, William; Ying, Rex; Leskovec, Jure (2017). "Inductive Representation Learning on Large Graphs" (PDF). Neural Information Processing Systems. 31. arXiv:1706.02216 – via Stanford. https://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf ↩

  13. Veličković, Petar; Cucurull, Guillem; Casanova, Arantxa; Romero, Adriana; Liò, Pietro; Bengio, Yoshua (2018-02-04). "Graph Attention Networks". arXiv:1710.10903 [stat.ML]. /wiki/ArXiv_(identifier) ↩

  14. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  15. Hajij, M.; Zamzmi, G.; Papamarkou, T.; Miolane, N.; Guzmán-Sáenz, A.; Ramamurthy, K. N.; Schaub, M. T. (2022). "Topological deep learning: Going beyond graph data". arXiv:2206.00606 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  16. Scarselli, Franco; Gori, Marco; Tsoi, Ah Chung; Hagenbuchner, Markus; Monfardini, Gabriele (2009). "The Graph Neural Network Model". IEEE Transactions on Neural Networks. 20 (1): 61–80. doi:10.1109/TNN.2008.2005605. ISSN 1941-0093. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  17. Micheli, Alessio (2009). "Neural Network for Graphs: A Contextual Constructive Approach". IEEE Transactions on Neural Networks. 20 (3): 498–511. doi:10.1109/TNN.2008.2010350. ISSN 1045-9227. PMID 19193509. S2CID 17486263. https://ieeexplore.ieee.org/document/4700287 ↩

  18. Veličković, Petar (2022). "Message passing all the way up". arXiv:2202.11097 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  19. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  20. Wu, Lingfei; Chen, Yu; Shen, Kai; Guo, Xiaojie; Gao, Hanning; Li, Shucheng; Pei, Jian; Long, Bo (2023). "Graph Neural Networks for Natural Language Processing: A Survey". Foundations and Trends in Machine Learning. 16 (2): 119–328. arXiv:2106.06090. doi:10.1561/2200000096. ISSN 1941-0093. PMID 19068426. S2CID 206756462. https://www.nowpublishers.com/article/Details/MAL-096 ↩

  21. Ying, Rex; He, Ruining; Chen, Kaifeng; Eksombatchai, Pong; Hamilton, William L.; Leskovec, Jure (2018). Graph Convolutional Neural Networks for Web-Scale Recommender Systems. pp. 974–983. arXiv:1806.01973. doi:10.1145/3219819.3219890. ISBN 9781450355520. S2CID 46949657. 9781450355520 ↩

  22. "Stanford Large Network Dataset Collection". snap.stanford.edu. Retrieved 2021-07-05. https://snap.stanford.edu/data/ ↩

  23. Zhang, Weihang; Cui, Yang; Liu, Bowen; Loza, Martin; Park, Sung-Joon; Nakai, Kenta (5 April 2024). "HyGAnno: Hybrid graph neural network-based cell type annotation for single-cell ATAC sequencing data". Briefings in Bioinformatics. 25 (3): bbae152. doi:10.1093/bib/bbae152. PMC 10998639. PMID 38581422. https://academic.oup.com/bib/article/25/3/bbae152/7641197 ↩

  24. Gilmer, Justin; Schoenholz, Samuel S.; Riley, Patrick F.; Vinyals, Oriol; Dahl, George E. (2017-07-17). "Neural Message Passing for Quantum Chemistry". Proceedings of Machine Learning Research: 1263–1272. arXiv:1704.01212. http://proceedings.mlr.press/v70/gilmer17a.html ↩

  25. Coley, Connor W.; Jin, Wengong; Rogers, Luke; Jamison, Timothy F.; Jaakkola, Tommi S.; Green, William H.; Barzilay, Regina; Jensen, Klavs F. (2019-01-02). "A graph-convolutional neural network model for the prediction of chemical reactivity". Chemical Science. 10 (2): 370–377. doi:10.1039/C8SC04228D. ISSN 2041-6539. PMC 6335848. PMID 30746086. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6335848 ↩

  26. Qasim, Shah Rukh; Kieseler, Jan; Iiyama, Yutaro; Pierini, Maurizio Pierini (2019). "Learning representations of irregular particle-detector geometry with distance-weighted graph networks". The European Physical Journal C. 79 (7): 608. arXiv:1902.07987. Bibcode:2019EPJC...79..608Q. doi:10.1140/epjc/s10052-019-7113-9. S2CID 88518244. https://doi.org/10.1140%2Fepjc%2Fs10052-019-7113-9 ↩

  27. Li, Zhuwen; Chen, Qifeng; Koltun, Vladlen (2018). "Combinatorial optimization with graph convolutional networks and guided tree search". Neural Information Processing Systems. 31: 537–546. arXiv:1810.10659. doi:10.1007/978-3-030-04221-9_48. /wiki/ArXiv_(identifier) ↩

  28. Matthias, Fey; Lenssen, Jan E. (2019). "Fast Graph Representation Learning with PyTorch Geometric". arXiv:1903.02428 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  29. "Tensorflow GNN". GitHub. Retrieved 30 June 2022. https://github.com/tensorflow/gnn ↩

  30. "Deep Graph Library (DGL)". Retrieved 2024-09-12. https://www.dgl.ai/ ↩

  31. "jraph". GitHub. Retrieved 30 June 2022. https://github.com/deepmind/jraph ↩

  32. Lucibello, Carlo (2021). "GraphNeuralNetworks.jl". GitHub. Retrieved 2023-09-21. https://github.com/CarloLucibello/GraphNeuralNetworks.jl ↩

  33. FluxML/GeometricFlux.jl, FluxML, 2024-01-31, retrieved 2024-02-03 https://github.com/FluxML/GeometricFlux.jl ↩

  34. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  35. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  36. Veličković, Petar (2022). "Message passing all the way up". arXiv:2202.11097 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  37. Gao, Hongyang; Ji, Shuiwang Ji (2019). "Graph U-Nets". arXiv:1905.05178 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  38. Lee, Junhyun; Lee, Inyeop; Kang, Jaewoo (2019). "Self-Attention Graph Pooling". arXiv:1904.08082 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  39. Liu, Chuang; Zhan, Yibing; Li, Chang; Du, Bo; Wu, Jia; Hu, Wenbin; Liu, Tongliang; Tao, Dacheng (2022). "Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities". arXiv:2204.07321 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  40. Douglas, B. L. (2011-01-27). "The Weisfeiler–Lehman Method and Graph Isomorphism Testing". arXiv:1101.5211 [math.CO]. /wiki/ArXiv_(identifier) ↩

  41. Xu, Keyulu; Hu, Weihua; Leskovec, Jure; Jegelka, Stefanie (2019-02-22). "How Powerful are Graph Neural Networks?". arXiv:1810.00826 [cs.LG]. /wiki/Stefanie_Jegelka ↩

  42. Bodnar, Christian; Frasca, Fabrizio; Guang Wang, Yu; Otter, Nina; Montúfar, Guido; Liò, Pietro; Bronstein, Michael (2021). "Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks". arXiv:2103.03212 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  43. Grady, Leo; Polimeni, Jonathan (2011). Discrete Calculus: Applied Analysis on Graphs for Computational Science (PDF). Springer. http://leogrady.net/wp-content/uploads/2017/01/grady2010discrete.pdf ↩

  44. Hajij, M.; Zamzmi, G.; Papamarkou, T.; Miolane, N.; Guzmán-Sáenz, A.; Ramamurthy, K. N.; Schaub, M. T. (2022). "Topological deep learning: Going beyond graph data". arXiv:2206.00606 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  45. Veličković, Petar (2022). "Message passing all the way up". arXiv:2202.11097 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  46. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  47. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  48. Chen, Deli; Lin, Yankai; Li, Wei; Li, Peng; Zhou, Jie; Sun, Xu (2020). "Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (4): 3438–3445. arXiv:1909.03211. doi:10.1609/aaai.v34i04.5747. S2CID 202539008. /wiki/ArXiv_(identifier) ↩

  49. Alon, Uri; Yahav, Eran (2021). "On the Bottleneck of Graph Neural Networks and its Practical Implications". arXiv:2006.05205 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  50. Hamilton, William; Ying, Rex; Leskovec, Jure (2017). "Inductive Representation Learning on Large Graphs" (PDF). Neural Information Processing Systems. 31. arXiv:1706.02216 – via Stanford. https://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf ↩

  51. Xu, Keyulu; Zhang, Mozhi; Jegelka, Stephanie; Kawaguchi, Kenji (2021). "Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth". arXiv:2105.04550 [cs.LG]. /wiki/Stefanie_Jegelka ↩

  52. Li, Yujia; Tarlow, Daniel; Brockschmidt, Mark; Zemel, Richard (2016). "Gated Graph Sequence Neural Networks". arXiv:1511.05493 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  53. Xu, Keyulu; Li, Chengtao; Tian, Yonglong; Sonobe, Tomohiro; Kawarabayashi, Ken-ichi; Jegelka, Stefanie (2018). "Representation Learning on Graphs with Jumping Knowledge Networks". arXiv:1806.03536 [cs.LG]. /wiki/Stefanie_Jegelka ↩

  54. Alon, Uri; Yahav, Eran (2021). "On the Bottleneck of Graph Neural Networks and its Practical Implications". arXiv:2006.05205 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  55. Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (May 4, 2021). "Geometric Deep Learning: Grids, Groups, Graphs Geodesics and Gauges". arXiv:2104.13478 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  56. Kipf, Thomas N; Welling, Max (2016). "Semi-supervised classification with graph convolutional networks". IEEE Transactions on Neural Networks. 5 (1): 61–80. arXiv:1609.02907. doi:10.1109/TNN.2008.2005605. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  57. Veličković, Petar; Cucurull, Guillem; Casanova, Arantxa; Romero, Adriana; Liò, Pietro; Bengio, Yoshua (2018-02-04). "Graph Attention Networks". arXiv:1710.10903 [stat.ML]. /wiki/ArXiv_(identifier) ↩

  58. Kipf, Thomas N; Welling, Max (2016). "Semi-supervised classification with graph convolutional networks". IEEE Transactions on Neural Networks. 5 (1): 61–80. arXiv:1609.02907. doi:10.1109/TNN.2008.2005605. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  59. Kipf, Thomas N; Welling, Max (2016). "Semi-supervised classification with graph convolutional networks". IEEE Transactions on Neural Networks. 5 (1): 61–80. arXiv:1609.02907. doi:10.1109/TNN.2008.2005605. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  60. Veličković, Petar; Cucurull, Guillem; Casanova, Arantxa; Romero, Adriana; Liò, Pietro; Bengio, Yoshua (2018-02-04). "Graph Attention Networks". arXiv:1710.10903 [stat.ML]. /wiki/ArXiv_(identifier) ↩

  61. Veličković, Petar; Cucurull, Guillem; Casanova, Arantxa; Romero, Adriana; Liò, Pietro; Bengio, Yoshua (2018-02-04). "Graph Attention Networks". arXiv:1710.10903 [stat.ML]. /wiki/ArXiv_(identifier) ↩

  62. Li, Yujia; Tarlow, Daniel; Brockschmidt, Mark; Zemel, Richard (2016). "Gated Graph Sequence Neural Networks". arXiv:1511.05493 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  63. Scarselli, Franco; Gori, Marco; Tsoi, Ah Chung; Hagenbuchner, Markus; Monfardini, Gabriele (2009). "The Graph Neural Network Model". IEEE Transactions on Neural Networks. 20 (1): 61–80. doi:10.1109/TNN.2008.2005605. ISSN 1941-0093. PMID 19068426. S2CID 206756462. https://ieeexplore.ieee.org/document/4700287 ↩

  64. Liu, Chuang; Zhan, Yibing; Li, Chang; Du, Bo; Wu, Jia; Hu, Wenbin; Liu, Tongliang; Tao, Dacheng (2022). "Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities". arXiv:2204.07321 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  65. Gao, Hongyang; Ji, Shuiwang Ji (2019). "Graph U-Nets". arXiv:1905.05178 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  66. Gao, Hongyang; Ji, Shuiwang Ji (2019). "Graph U-Nets". arXiv:1905.05178 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  67. Lee, Junhyun; Lee, Inyeop; Kang, Jaewoo (2019). "Self-Attention Graph Pooling". arXiv:1904.08082 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  68. Luan, Sitao; Hua, Chenqing; Lu, Qincheng; Ma, Liheng; Wu, Lirong; Wang, Xinyu; Xu, Minkai; Chang, Xiao-Wen; Precup, Doina (2024-07-12), The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges, arXiv:2407.09618, retrieved 2025-02-02 https://arxiv.org/abs/2407.09618 ↩

  69. Luan, Sitao; Hua, Chenqing; Lu, Qincheng; Zhu, Jiaqi; Chang, Xiao-Wen; Precup, Doina (2024). Cherifi, Hocine; Rocha, Luis M.; Cherifi, Chantal; Donduran, Murat (eds.). "When Do We Need Graph Neural Networks for Node Classification?". Complex Networks & Their Applications XII. Studies in Computational Intelligence. 1141. Cham: Springer Nature Switzerland: 37–48. doi:10.1007/978-3-031-53468-3_4. ISBN 978-3-031-53467-6. 978-3-031-53467-6 ↩

  70. Luan, Sitao; Hua, Chenqing; Lu, Qincheng; Zhu, Jiaqi; Zhao, Mingde; Zhang, Shuyuan; Chang, Xiao-Wen; Precup, Doina (2022-12-06). "Revisiting Heterophily For Graph Neural Networks". Advances in Neural Information Processing Systems. 35: 1362–1375. arXiv:2210.07606. https://proceedings.neurips.cc/paper_files/paper/2022/hash/092359ce5cf60a80e882378944bf1be4-Abstract-Conference.html ↩

  71. Luan, Sitao; Hua, Chenqing; Lu, Qincheng; Ma, Liheng; Wu, Lirong; Wang, Xinyu; Xu, Minkai; Chang, Xiao-Wen; Precup, Doina (2024-07-12), The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges, arXiv:2407.09618, retrieved 2025-02-02 https://arxiv.org/abs/2407.09618 ↩

  72. Luan, Sitao; Hua, Chenqing; Lu, Qincheng; Zhu, Jiaqi; Zhao, Mingde; Zhang, Shuyuan; Chang, Xiao-Wen; Precup, Doina (2022-12-06). "Revisiting Heterophily For Graph Neural Networks". Advances in Neural Information Processing Systems. 35: 1362–1375. arXiv:2210.07606. https://proceedings.neurips.cc/paper_files/paper/2022/hash/092359ce5cf60a80e882378944bf1be4-Abstract-Conference.html ↩

  73. Luan, Sitao; Hua, Chenqing; Xu, Minkai; Lu, Qincheng; Zhu, Jiaqi; Chang, Xiao-Wen; Fu, Jie; Leskovec, Jure; Precup, Doina (2023-12-15). "When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability". Advances in Neural Information Processing Systems. 36: 28748–28760. https://proceedings.neurips.cc/paper_files/paper/2023/hash/5ba11de4c74548071899cf41dec078bf-Abstract-Conference.html ↩

  74. Sample, Ian (2 December 2018). "Google's DeepMind predicts 3D shapes of proteins". The Guardian. Retrieved 30 November 2020. https://www.theguardian.com/science/2018/dec/02/google-deepminds-ai-program-alphafold-predicts-3d-shapes-of-proteins ↩

  75. "DeepMind's protein-folding AI has solved a 50-year-old grand challenge of biology". MIT Technology Review. Retrieved 30 November 2020. https://www.technologyreview.com/2020/11/30/1012712/deepmind-protein-folding-ai-solved-biology-science-drugs-disease/ ↩

  76. Xu, Keyulu; Li, Chengtao; Tian, Yonglong; Sonobe, Tomohiro; Kawarabayashi, Ken-ichi; Jegelka, Stefanie (2018). "Representation Learning on Graphs with Jumping Knowledge Networks". arXiv:1806.03536 [cs.LG]. /wiki/Stefanie_Jegelka ↩

  77. Fan, Wenqi; Ma, Yao; Li, Qing; He, Yuan; Zhao, Eric; Tang, Jiliang; Yin, Dawei (2019). Graph Neural Networks for Social Recommendation. pp. 417–426. arXiv:1902.07243. doi:10.1145/3308558.3313488. hdl:10397/81232. ISBN 9781450366748. S2CID 67769538. 9781450366748 ↩

  78. Ying, Rex; He, Ruining; Chen, Kaifeng; Eksombatchai, Pong; Hamilton, William L.; Leskovec, Jure (2018). Graph Convolutional Neural Networks for Web-Scale Recommender Systems. pp. 974–983. arXiv:1806.01973. doi:10.1145/3219819.3219890. ISBN 9781450355520. S2CID 46949657. 9781450355520 ↩

  79. Cappart, Quentin; Chételat, Didier; Khalil, Elias; Lodi, Andrea; Morris, Christopher; Veličković, Petar (2021). "Combinatorial optimization and reasoning with graph neural networks". arXiv:2102.09544 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  80. Li, Yujia; Tarlow, Daniel; Brockschmidt, Mark; Zemel, Richard (2016). "Gated Graph Sequence Neural Networks". arXiv:1511.05493 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  81. Mirhoseini, Azalia; Goldie, Anna; Yazgan, Mustafa; Jiang, Joe Wenjie; Songhori, Ebrahim; Wang, Shen; Lee, Young-Joon; Johnson, Eric; Pathak, Omkar; Nazi, Azade; Pak, Jiwoo; Tong, Andy; Srinivasa, Kavya; Hang, William; Tuncer, Emre; Le, Quoc V.; Laudon, James; Ho, Richard; Carpenter, Roger; Dean, Jeff (2021). "A graph placement methodology for fast chip design". Nature. 594 (7862): 207–212. Bibcode:2021Natur.594..207M. doi:10.1038/s41586-021-03544-w. PMID 34108699. S2CID 235395490. /wiki/Bibcode_(identifier) ↩

  82. Gasse, Maxime; Chételat, Didier; Ferroni, Nicola; Charlin, Laurent; Lodi, Andrea (2019). "Exact Combinatorial Optimization with Graph Convolutional Neural Networks". arXiv:1906.01629 [cs.LG]. /wiki/ArXiv_(identifier) ↩

  83. Wang, Su; Wang, Zhiliang; Zhou, Tao; Sun, Hongbin; Yin, Xia; Han, Dongqi; Zhang, Han; Shi, Xingang; Yang, Jiahai (2022). "Threatrace: Detecting and Tracing Host-Based Threats in Node Level Through Provenance Graph Learning". IEEE Transactions on Information Forensics and Security. 17: 3972–3987. arXiv:2111.04333. doi:10.1109/TIFS.2022.3208815. ISSN 1556-6021. S2CID 243847506. https://ieeexplore.ieee.org/document/9899459/;jsessionid=NzAXdLahhjEX-xmrFzOROk4qxoaz40aJFvKcZRgjck8-zCOucJi7!380715771 ↩

  84. Wang, Qi; Hassan, Wajih Ul; Li, Ding; Jee, Kangkook; Yu, Xiao (2020). "You Are What You Do: Hunting Stealthy Malware via Data Provenance Analysis". Network and Distributed Systems Security Symposium. doi:10.14722/ndss.2020.24167. ISBN 978-1-891562-61-7. S2CID 211267791. 978-1-891562-61-7 ↩

  85. King, Isaiah J.; Huang, H. Howie (2022). "Euler: Detecting Network Lateral Movement via Scalable Temporal Link Prediction" (PDF). In Proceedings of the 29th Network and Distributed Systems Security Symposium. doi:10.14722/ndss.2022.24107. S2CID 248221601. https://www.ndss-symposium.org/wp-content/uploads/2022-107A-paper.pdf ↩

  86. Zanfei, Ariele; et al. (2022). "Graph Convolutional Recurrent Neural Networks for Water Demand Forecasting". Water Resources Research. 58 (7). AGU. Bibcode:2022WRR....5832299Z. doi:10.1029/2022WR032299. Retrieved June 11, 2024. https://agupubs.onlinelibrary.wiley.com/doi/10.1029/2022WR032299 ↩

  87. Zanfei, Ariele; et al. (2023). "Shall we always use hydraulic models? A graph neural network metamodel for water system calibration and uncertainty assessment". Water Research. 242. Bibcode:2023WatRe.24220264Z. doi:10.1016/j.watres.2023.120264. PMID 37393807. Retrieved June 11, 2024. https://www.sciencedirect.com/science/article/abs/pii/S0043135423007005 ↩

  88. Han, Kai; Wang, Yunhe; Guo, Jianyuan; Tang, Yehui; Wu, Enhua (2022-11-04), Vision GNN: An Image is Worth Graph of Nodes, arXiv, doi:10.48550/arXiv.2206.00272, arXiv:2206.00272, retrieved 2025-06-03 http://arxiv.org/abs/2206.00272 ↩

  89. Zhou, Jie; Cui, Ganqu; Hu, Shengding; Zhang, Zhengyan; Yang, Cheng; Liu, Zhiyuan; Wang, Lifeng; Li, Changcheng; Sun, Maosong (2020-01-01). "Graph neural networks: A review of methods and applications". AI Open. 1: 57–81. doi:10.1016/j.aiopen.2021.01.001. ISSN 2666-6510. https://www.sciencedirect.com/science/article/pii/S2666651021000012 ↩