> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter18..md). # Chapter18. Limitations of Graph Neural Networks ## Limitations of Graph Neural Networks ### Today: Limitations of GNNs * Some Simple graph structures cannot be distinguished by conventional GNNs. * 노드 색깔이 같으면?? 문제가 생긴다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8TeBBGzRLtHBAJ8IU1%2F-M8TehkeWHK2k317LTMP%2Fimage.png?alt=media\&token=0f2ccdf6-1330-443b-83b0-6a91aa51173b) * GNNs are not robust to noise in graph data. * Noise에 대하여 로버스트하지 않다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8TeBBGzRLtHBAJ8IU1%2F-M8TgH2zt0J6yxid2Vo-%2Fimage.png?alt=media\&token=b3dfe732-9848-4b2f-84f6-9b90e0f4391f) ## 1. Limitations of conventional GNNs in a capturing graph structure ### Fundamental question * Given two different graphs, can GNNs map them into different graph representations? * 다른 그래프 표현에 대한 함수를 만들 수 있을까에 대한 문제. * Important condition for classification scenario. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8TgLxnYnQKBltT79lG%2F-M8Th3nGAqmSe4wrfXjp%2Fimage.png?alt=media\&token=d27d2e1b-e730-44e2-8ab2-ad145d7ed658) ### Graph Isomorphism * Essentially, graph isomorphism test problem * 그래프의 동형을 찾는 문제 * No polynomial algorithms exist for general case. * NPHARD 문제 * GNNs may not perfectly distinguish any graphs * 완벽히 이 문제를 풀 수는 없다. ### Rethinking GNNs * GNNs use different computational graphs to distinguish different graphs ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UrjVfokzAE5uQ181Y%2F-M8UtLF_eIrD99pWkWgQ%2Fimage.png?alt=media\&token=f06f635e-ea04-4479-895e-989e3cc82f1c) * Node representation captures rooted subtree structure. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UrjVfokzAE5uQ181Y%2F-M8UtchCSYMP3vwGSRYk%2Fimage.png?alt=media\&token=7dc01406-004c-4225-984f-a3221bcb9592) * Most discriminative GNNs map different subtrees into different node representations (denoted by different colors) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UrjVfokzAE5uQ181Y%2F-M8UtqXgwBLvJHiUhx1e%2Fimage.png?alt=media\&token=3bfdf4c8-4a4a-457a-9e38-de270e9d27a7) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UrjVfokzAE5uQ181Y%2F-M8UtzxEWfQgjfQ7xP8p%2Fimage.png?alt=media\&token=454a53c0-5004-4381-ae4c-0e464da33ded) ### Recall : Injectivity * Function is **injective** if it maps differenet elements into different outputs. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8Uu85FDYKdq-Q3K6k5%2F-M8UuPsWeikVVIwOQXHM%2Fimage.png?alt=media\&token=c95864d6-ffdd-41f1-8763-41c69001b9b7) ### Injective Neighbor Aggregation * Entire neighbor aggregation is injective if **every step** of neighbor aggregation is injective ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8Uu85FDYKdq-Q3K6k5%2F-M8UuiqExeAR-AY8VilG%2Fimage.png?alt=media\&token=acd2b80e-29c2-46a9-8df7-20516d6f8eed) ### Neighbor aggregation * Neighbor aggregation is essentially a function over multi-set (set with repeating elements) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8Uv4g6JFDX2TfU2PUt%2F-M8UvR9UnHYN7MwlPkeC%2Fimage.png?alt=media\&token=b1ef91e6-e574-4c11-ae02-b9aa4111a500) **Discriminative Power of CNNs can be characterized by that of multi-set functions** ### Case Study 1: GCN Recall : GCN uses mean pooling. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UvTYI1wDdypwZAPgk%2F-M8Uw4251UEmaw1i_wsV%2Fimage.png?alt=media\&token=4a561c12-77de-4df7-bdf7-6bd9b63bfe5e) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UvTYI1wDdypwZAPgk%2F-M8Uw8Il5AXcA0gAGkFm%2Fimage.png?alt=media\&token=00c7e332-0479-4c3f-89a1-20cdf229c51d) ![injective function](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M97oZOoBLNhnwqJkx_7%2F-M97owU0n3Y7Dxti_Y7u%2Fimage.png?alt=media\&token=dcd8f534-2d9f-42ca-a3dd-3378c6e3b99a) ### Case Study 2 : GraphSAGE-maxpool Recall : GraphSAGE uses max pooling. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UwBs2STr6FmBqEATp%2F-M8UwNilHt2d63VE7ERA%2Fimage.png?alt=media\&token=2b9fd376-684d-42aa-a586-74f08257fe16) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UwBs2STr6FmBqEATp%2F-M8UwSS8SwFhhBb5Fp58%2Fimage.png?alt=media\&token=6038c2a7-9f3f-461a-81bf-4a694dcea0b3) How can we design injective multi-set function using neural networks? ### Injective multi-set function * Theorem ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UwBs2STr6FmBqEATp%2F-M8Uwh_VuuJCI432X1Ui%2Fimage.png?alt=media\&token=d4149ead-8714-4e36-b140-ada7e68aefdd) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UwBs2STr6FmBqEATp%2F-M8Uwnf4QQp3XY9NiPBm%2Fimage.png?alt=media\&token=bf5843bd-ede5-4a5c-8571-e0a7e895fef9) ### Most discriminative GNN ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8UwrVwe5mwDXKI-BXL%2F-M8Ux7mQy4KPIIKVTS_A%2Fimage.png?alt=media\&token=1f7440e9-3282-4d3a-aa6e-f9fcaa080633) ### Graph pooling in GIN * Graph pooling is also function over multiset. Sum pooling can give **injective graph pooling**! ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8Ux9MrtfRg6FKoibX5%2F-M8UxXPN_HDLo2QiFZwe%2Fimage.png?alt=media\&token=6c5c7c5f-2838-4a79-9c32-174d2acb4608) ### Most discriminative GNN * So far : GIN achieves maximal discriminative power by using injective neighbor aggregation ### WL Graph Isomorphism Test * GIN is closely related to Wisfeiler-Lehman(WL) Graph Isomorphism Test * WL test is known to be capable of distinguishing most of real-world graphs. * Next : We will show GIN is as discriminative as the WL test. * WL first maps different rooted subtrees to different colors ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V0BFmUFu3JH6vkW91%2F-M8V5ZTT_J8Q3NoWCSws%2Fimage.png?alt=media\&token=606d0b86-8a5b-466c-8b03-162cb54acda6) * WL then counts different colors ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V0BFmUFu3JH6vkW91%2F-M8V5fbSBJ-obpd-L0rW%2Fimage.png?alt=media\&token=dd00d140-a703-4c92-8e34-5c4fa49ebf60) * Finally, WL compares the count ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V0BFmUFu3JH6vkW91%2F-M8V5nJTQc5QpKiVnMjy%2Fimage.png?alt=media\&token=e51be903-947e-43e1-aaa0-214f0c623031) WL test and GIN are opreationally equivalent. Graphs that WL test can distinguish <->Graphs that GIN can distinguish. ### Relation to Graph Isomorhpism test #### Observation * GINs have the same discriminative power as the WL graph isomorphism test. * WL test has been known to distinguish most of the graphs, except for some corner cases ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V5zufDP-0TGlkpkhK%2F-M8V6J_8G8T89mn55wUc%2Fimage.png?alt=media\&token=3e5ad7dc-b076-4840-a8a9-fa7788d9851e) ### Experiments : Training accuarcy * Graph classification : social and bio/chem graphs **Training accuracy** of different GNN architectures. GIN fits training data much better than GCN, GraphSAGE. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V5zufDP-0TGlkpkhK%2F-M8V6a7XICvVGdt-rvGS%2Fimage.png?alt=media\&token=41f11b70-9612-4c1b-8f97-998b464c7cb0) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V5zufDP-0TGlkpkhK%2F-M8V6fzgB7jccFhibElJ%2Fimage.png?alt=media\&token=cbec8598-f5ae-450e-919f-8a7f4af53d82) ### Experiments : Test accuracy * Graph classification : social and bio/chem graphs GIN outperforms existing GNNs also in terms of test accuracy because it can better capture graph structure. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V6kra_XSv0ZVwkHdw%2F-M8V7Y5QiYIlFtdlJjJs%2Fimage.png?alt=media\&token=aca20249-ddd6-4776-b8c7-cac02c7728fd) ### Summary of the first part * Existing GNNs use non-injective neighbor aggregation, thus have low discriminative power * GIN uses injective neighbor aggregationk, and is an discriminative as the WL graph isomorphism test. * GIN achieves state-of-the-art test performance in graph classification. ## 2. Vulnerability of GNNs to noise in graph data ### Adversarial Attacks in DNNs * Deep Neural Networks are **vulnerable to adversarial attacks** * Attacks are often implemented as **imperceptible noise** that changes the prediction ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8V7xvQ8MHl7zKYkiwI%2F-M8VC2c6oV2VD2CpV409%2Fimage.png?alt=media\&token=b588e5d0-9cca-4328-b3f4-8238d8fba6dc) ### Attacks on Graph Domains * **Adversaries** are **very common** in applications of graph neural networks, search engines, recommender systems, social networks, etc. * These adveraries **will exploit** any exposed vulnerabilites! ### Semi-Supervised Node Classification * Here we focus on **semi-supervised node classification** using **Graph Convolutional Neural Networks(GCN)** ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VCWyQ7VERFKHxvqt3%2Fimage.png?alt=media\&token=8b4e8381-3a5a-4ff1-820b-a7f0d7d3d7c5) ### GCN for Semi-Supervised Node Classification ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VCc5jj7_cvUPQ7hmi%2Fimage.png?alt=media\&token=a8c1db59-011b-4714-a2a9-5f9f53986517) ### Attack possibilities ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VCm5lf6KET8wrzhPC%2Fimage.png?alt=media\&token=b64dbc4d-b034-4d57-8d2d-ba891795f5b5) ### Nettack : High Level Idea * Zugner +, Adverarial Attacks on Neural Networks for Graph Data, KDD\`18 ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VCy7JMpecRenw76_c%2Fimage.png?alt=media\&token=4bfd76d6-b187-4b97-a95d-bb627b29a74f) ### Mathematical Formulation * Find a modified graph that maximized the change of predicted labels of target node Let's parse the objective function ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VDFR0zBNN48vFIfTa%2Fimage.png?alt=media\&token=7761bf6c-bae8-46ac-bb98-2ed2dd20ff57) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VDKIqkbmeldDl9Nk8%2Fimage.png?alt=media\&token=5b10a0c2-b85e-4c9d-bc67-56cb9475a4e5) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VDN7jCu_USEypTPkh%2Fimage.png?alt=media\&token=0a21fb38-330e-499a-8f67-1b60339c57d0) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VCKROIqNqBXOzXIgC%2F-M8VDQaw7hwXaMRRh2ZY%2Fimage.png?alt=media\&token=f5b749ec-18fe-4a62-8932-426c5c183073) ### Tractable Optimization * In practice, we cannot exactly solve the optimization problem because.. * Graph modification is discrete (cannot use simple gradient descent to optimize) * Inner loop involves expensive re-training of GCN ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VDXA1KAhWOogehPLz%2F-M8VDo71x1SmxC6LVqX-%2Fimage.png?alt=media\&token=69d7d8c8-632a-4c50-863c-d51012246919) * Some heuristics have been proposed to efficiently obtain an approximate solution * For example: * Greedily choosing the step-by-step graph modification * Simplifying GCN by removing ReLU activation (to work in closed form) * ETC ### Nettack Experiments * Semi-Supervised node classification with GCN * Class predictions for a single node, produced by 5 GCNs with different random initilizations ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VDXA1KAhWOogehPLz%2F-M8VEEuBi2AwbPUz0c-v%2Fimage.png?alt=media\&token=3f86617f-01d6-4380-8a01-c1fcf82562f5) ### Experiments * The GCN prediction is **easily manipulated** by only 5 modifications of graph structure (|V|=\~2K, |E=5k) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VDXA1KAhWOogehPLz%2F-M8VEWMLaSufy710uI0u%2Fimage.png?alt=media\&token=9cf8934f-3593-420f-ba8f-da039fb7db5d) ## 3. Open questions & Future directions ### GNNs for Science Domains * Chemistry : Molecular graphs * Molecular property prediction ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VDXA1KAhWOogehPLz%2F-M8VElW4vHY38DR7THPc%2Fimage.png?alt=media\&token=fe87955b-2fa2-4e60-909f-ca947239dfc5) * Biology : Protein-Protein Interaction Networks * Protein function prediction ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VDXA1KAhWOogehPLz%2F-M8VEtjT9TJVoj05gsIu%2Fimage.png?alt=media\&token=09298c49-b7a0-4240-8c83-c92466ea1cd4) ### Challenges of Applying GNNs * Scarcity of labeled data * Labels require expensive experiments * Models overfit to small training datasets * Out-of-distribution prediction * Test examples are very different from training in scientific discovery * Models typically perform poorly ### Pre-training for GNNs * Pre-training GNNs \[Hu+2019] ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M8VFDHZZ6wdO2xcD4-b%2F-M8VFLsp8JgYwQuHvoHG%2Fimage.png?alt=media\&token=2967b103-785d-44c5-a0ad-6ea43ea37777) ### Making GNNs Robust * We have seen how to attack GNNs * Open question: * How to defend against the attacks? Challenges * Tractable optimization on discrete graph data * Achieving good trade-off between Accuracy and Robustness ####