Graph Representation Learning with Individualization and Refinement
Graph Neural Networks (GNNs) have emerged as prominent models for representation learning on graph structured data. GNNs follow an approach of message passing analogous to 1-dimensional Weisfeiler Lehman (1-WL) test for graph isomorphism and consequently are limited by the distinguishing power of 1-WL. More expressive higher-order GNNs which operate on k-tuples of nodes need increased computational resources in order to process higher-order tensors. Instead of the WL approach, in this work, we follow the classical approach of Individualization and Refinement (IR), a technique followed by most practical isomorphism solvers. Individualization refers to artificially distinguishing a node in the graph and refinement is the propagation of this information to other nodes through message passing. We learn to adaptively select nodes to individualize and to aggregate the resulting graphs after refinement to help handle the complexity. Our technique lets us learn richer node embeddings while keeping the computational complexity manageable. Theoretically, we show that our procedure is more expressive than the 1-WL test. Experiments show that our method outperforms prominent 1-WL GNN models as well as competitive higher-order baselines on several benchmark synthetic and real datasets. Furthermore, our method opens new doors for exploring the paradigm of learning on graph structures with individualization and refinement.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Representation LearningRepresentation LearningSimilar Papers 제목 키워드 기반
Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
We propose and study Hierarchical Ego Graph Neural Networks (HEGNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradig…
Isomorphism TestingPF-GNN: Differentiable particle filtering based approximation of universal graph representations
Message passing Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. Other more expressive models either are computationally expensive or need …
State EstimationEvaluation of Deep Learning Topcoders Method for Neuron Individualization in Histological Macaque Brain Section
Cell individualization has a vital role in digital pathology image analysis. Deep Learning is considered as an efficient tool for instance segmentation tasks, including cell individualization. However, the precision of t…
Deep LearningInstance SegmentationSemantic SegmentationCan machine learning solve the challenge of adaptive learning and the individualization of learning paths? A field experiment in an online learning platform
The individualization of learning contents based on digital technologies promises large individual and social benefits. However, it remains an open question how this individualization can be implemented. To tackle this q…
Self-LearningConvolutional Knowledge Tracing: Modeling Individualization in Student Learning Process
With the development of online education systems, a growing number of research works are focusing on Knowledge Tracing (KT), which aims to assess students' changing knowledge state and help them learn knowledge concepts …
Knowledge Tracing