Graph neural network: Difference between revisions

Revision as of 08:37, 6 April 2025

Revision as of 08:39, 6 April 2025

Line 23:

# <em>Global pooling</em>: 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.<ref name="lui2022" /> 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|Weisfeiler–Leman Graph Isomorphism Test]].<ref name="douglas2011" /><ref name="xu2019" /> In practice, this means that there exist different graph structures (e.g., [[molecules]] with the same [[atoms]] but different [[Chemical bond|bonds]]) that cannot be distinguished by GNNs. More powerful GNNs operating on higher-dimension geometries such as [[simplicial complex]]es can be designed <ref name=bronstein2021-2 /><ref name=grady2011discrete /><ref name=hajij2022></ref>, on sparse convolutions <ref name="Giraldo-SGNNs-1">{{cite journal|title=Higher-Order Sparse Convolutions In Graph Neural Networks|journal=IEEE International Conference on Acoustics, Speech and Signal Processing|date=2023|url=https://ieeexplore.ieee.org/document/10096494|last1=Giraldo|first1=H.|last2=Javed|first2=S.|last3=Mahmood|first3=A.|last4=Malliaros|first4=F.|last5=Bouwmans|first5=T.}}</ref> and on Sobolev norm

<ref name="Giraldo-SGNNs-2">{{cite journal|title=Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks|journal=IEEE Transactions on Signal and Information Processing Over Networks|date=2024|url=https://ieeexplore.ieee.org/document/10758782|last1=Giraldo|first1=H.|last2=Torovic|first2=A.|last3=Einizade|first3=A.|last4=Castro-Correa|first4=J.|last5=Badiey|first5=M.|last6=Malliaros|first6=F.|last7=Bouwmans|first7=T.}}</ref> can be designed <ref name=bronstein2021-2 /><ref name=grady2011discrete /><ref name=hajij2022></ref>. Thus, Graph Neural Networks (GNNs) show great promise in modeling relationships between nodes in a graph, but capturing higher-order relationships remains a challenge for large-scale networks. {{As of|2022}}, whether or not future architectures will overcome the message passing primitive is an open research question<ref name=velickovic2022 />.

[[File:GNN representational limits.png|thumb|[[Graph isomorphism|Non-isomorphic]] graphs that cannot be distinguished by a GNN due to the limitations of the Weisfeiler-Lehman Graph Isomorphism Test. Colors indicate node [[Feature (machine learning)|features]].]]