Graph Classification with GNNs: Optimisation, Representation and Inductive Bias
Theoretical studies on the representation power of GNNs have been centered around understanding the equivalence of GNNs, using WL-Tests for detecting graph isomorphism. In this paper, we argue that such equivalence ignores the accompanying optimization issues and does not provide a holistic view of the GNN learning process. We illustrate these gaps between representation and optimization with examples and experiments. We also explore the existence of an implicit inductive bias (e.g. fully connected networks prefer to learn low frequency functions in their input space) in GNNs, in the context of graph classification tasks. We further prove theoretically that the message-passing layers in the graph, have a tendency to search for either discriminative subgraphs, or a collection of discriminative nodes dispersed across the graph, depending on the different global pooling layers used. We empirically verify this bias through experiments over real-world and synthetic datasets. Finally, we show how our work can help in incorporating domain knowledge via attention based architectures, and can evince their capability to discriminate coherent subgraphs.
Code (1)
Tasks
Graph ClassificationInductive BiasMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Collective Learning Framework to Boost GNN Expressiveness
Graph Neural Networks (GNNs) have recently been used for node and graph classification tasks with great success, but GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among…
ClassificationGeneral ClassificationGraph ClassificationInductive Learning+2Robustness of Graph Classification: failure modes, causes, and noise-resistant loss in Graph Neural Networks
Graph Neural Networks (GNNs) are powerful at solving graph classification tasks, yet applied problems often contain noisy labels. In this work, we study GNN robustness to label noise, demonstrate GNN failure modes when m…
Graph ClassificationInductive BiasConTextING: Granting Document-Wise Contextual Embeddings to Graph Neural Networks for Inductive Text Classification
Graph neural networks (GNNs) have been recently applied in natural language processing. Various GNN research studies are proposed to learn node interactions within the local graph of each document that contains words, se…
text-classificationText ClassificationWord EmbeddingsInductive Lottery Ticket Learning for Graph Neural Networks
Deep graph neural networks (GNNs) have gained increasing popularity, while usually suffer from unaffordable computations for real-world large-scale applications. Hence, pruning GNNs is of great need but largely unexplore…
Graph ClassificationNode ClassificationTransductive LearningEgo-GNNs: Exploiting Ego Structures in Graph Neural Networks
Graph neural networks (GNNs) have achieved remarkable success as a framework for deep learning on graph-structured data. However, GNNs are fundamentally limited by their tree-structured inductive bias: the WL-subtree ker…
Inductive BiasNode Classification