Graph neural network: Difference between revisions

Revision as of 06:08, 6 April 2025

Revision as of 06:11, 6 April 2025

Line 24:

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=HHigherHigher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks|journal=IEEE Transactions on Signal and Information Processing Over Networks|date=20232024|url=https://ieeexplore.ieee.org/document/1009649410758782|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>. 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]].]]