Graph neural network: Difference between revisions

Revision as of 13:27, 6 April 2025

Revision as of 22:54, 9 May 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> {{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]].]]

Line 125:

:<math>\mathbf{A}' = \mathbf{A}_{\mathbf{i}, \mathbf{i}}</math>

where <math>\mathbf{i} = \text{top}_k(\mathbf{y})</math> is the subset of nodes with the top-k highest projection scores, <math>\odot</math> denotes [[Hadamard product (matrices) | 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.<ref name=":0">{{Citation |last1=Luan |first1=Sitao |title=The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges |date=2024-07-12 |url=https://arxiv.org/abs/2407.09618 |access-date=2025-02-02 |arxiv=2407.09618 |last2=Hua |first2=Chenqing |last3=Lu |first3=Qincheng |last4=Ma |first4=Liheng |last5=Wu |first5=Lirong |last6=Wang |first6=Xinyu |last7=Xu |first7=Minkai |last8=Chang |first8=Xiao-Wen |last9=Precup |first9=Doina}}</ref> However, recent work has identified a non-trivial set of datasets where GNN’s performance compared to the NN’s is not satisfactory.<ref>{{Cite journal |last1=Luan |first1=Sitao |last2=Hua |first2=Chenqing |last3=Lu |first3=Qincheng |last4=Zhu |first4=Jiaqi |last5=Chang |first5=Xiao-Wen |last6=Precup |first6=Doina |date=2024 |editor-last=Cherifi |editor-first=Hocine |editor2-last=Rocha |editor2-first=Luis M. |editor3-last=Cherifi |editor3-first=Chantal |editor4-last=Donduran |editor4-first=Murat |title=When Do We Need Graph Neural Networks for Node Classification? |url=https://link.springer.com/chapter/10.1007/978-3-031-53468-3_4 |journal=Complex Networks & Their Applications XII |series=Studies in Computational Intelligence |volume=1141 |language=en |___location=Cham |publisher=Springer Nature Switzerland |pages=37–48|doi=10.1007/978-3-031-53468-3_4 |isbn=978-3-031-53467-6 }}</ref> [[Heterophily]], i.e., low homophily, has been considered the main cause of this empirical observation.<ref name=":1">{{Cite journal |last1=Luan |first1=Sitao |last2=Hua |first2=Chenqing |last3=Lu |first3=Qincheng |last4=Zhu |first4=Jiaqi |last5=Zhao |first5=Mingde |last6=Zhang |first6=Shuyuan |last7=Chang |first7=Xiao-Wen |last8=Precup |first8=Doina |date=2022-12-06 |title=Revisiting Heterophily For Graph Neural Networks |url=https://proceedings.neurips.cc/paper_files/paper/2022/hash/092359ce5cf60a80e882378944bf1be4-Abstract-Conference.html |journal=Advances in Neural Information Processing Systems |language=en |volume=35 |pages=1362–1375|arxiv=2210.07606 }}</ref> People have begun to revisit and re-evaluate most existing graph models in the heterophily scenario across various kinds of graphs, e.g., [[Heterogeneous network|heterogeneous graphs]], [[Temporal network|temporal graphs]] and [[Hypergraph|hypergraphshypergraph]]s. Moreover, numerous graph-related applications are found to be closely related to the heterophily problem, e.g. [[Fraud detection|graph fraud/anomaly detection]], [[Adversarial attack|graph adversarial attacks and robustness]], privacy, [[federated learning]] and [[Point cloud|point cloud segmentation]], [[Clustering|graph clustering]], [[Recommenderrecommender system|recommender systems]]s, [[Generativegenerative model|generative models]]s, [[link prediction]], [[Graph isomorphism|graph classification]] and [[Graph coloring|coloring]], etc. In the past few years, considerable effort has been devoted to studying and addressing the heterophily issue in graph learning.<ref name=":0" /><ref name=":1" /><ref>{{Cite journal |last1=Luan |first1=Sitao |last2=Hua |first2=Chenqing |last3=Xu |first3=Minkai |last4=Lu |first4=Qincheng |last5=Zhu |first5=Jiaqi |last6=Chang |first6=Xiao-Wen |last7=Fu |first7=Jie |last8=Leskovec |first8=Jure |last9=Precup |first9=Doina |date=2023-12-15 |title=When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability |url=https://proceedings.neurips.cc/paper_files/paper/2023/hash/5ba11de4c74548071899cf41dec078bf-Abstract-Conference.html |journal=Advances in Neural Information Processing Systems |language=en |volume=36 |pages=28748–28760}}</ref>

== Applications ==

Line 149:

=== 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 nodes<ref>{{Cite journal |last1=Wang |first1=Su |last2=Wang |first2=Zhiliang |last3=Zhou |first3=Tao |last4=Sun |first4=Hongbin |last5=Yin |first5=Xia |last6=Han |first6=Dongqi |last7=Zhang |first7=Han |last8=Shi |first8=Xingang |last9=Yang |first9=Jiahai |date=2022 |title=Threatrace: Detecting and Tracing Host-Based Threats in Node Level Through Provenance Graph Learning |url=https://ieeexplore.ieee.org/document/9899459/;jsessionid=NzAXdLahhjEX-xmrFzOROk4qxoaz40aJFvKcZRgjck8-zCOucJi7!380715771 |journal=IEEE Transactions on Information Forensics and Security |volume=17 |pages=3972–3987 |doi=10.1109/TIFS.2022.3208815 |issn=1556-6021|arxiv=2111.04333 |s2cid=243847506 }}</ref> and within paths<ref>{{Cite journal |last1=Wang |first1=Qi |last2=Hassan |first2=Wajih Ul |last3=Li |first3=Ding |last4=Jee |first4=Kangkook |last5=Yu |first5=Xiao |date=2020 |title=You Are What You Do: Hunting Stealthy Malware via Data Provenance Analysis. |journal=Network and Distributed Systems Security (NDSS) Symposium|doi=10.14722/ndss.2020.24167 |isbn=978-1-891562-61-7 |s2cid=211267791 |doi-access=free }}</ref> to detect malicious processes, or on the edge level<ref>{{Cite journal |last1=King |first1=Isaiah J. |last2=Huang |first2=H. Howie |date=2022 |title=Euler: Detecting Network Lateral Movement via Scalable Temporal Link Prediction |url=https://www.ndss-symposium.org/wp-content/uploads/2022-107A-paper.pdf |journal=In Proceedings of the 29th Network and Distributed Systems Security Symposium (NDSS)|doi=10.14722/ndss.2022.24107 |s2cid=248221601 }}</ref> to detect [[Network Lateral Movement|lateral movement]].

=== Water distribution networks ===