Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
arXiv:2107.01410
Abstract
In this paper, we propose a novel pooling layer for graph neural networks based on maximizing the mutual information between the pooled graph and the input graph. Since the maximum mutual information is difficult to compute, we employ the Shannon capacity of a graph as an inductive bias to our pooling method. More precisely, we show that the input graph to the pooling layer can be viewed as a representation of a noisy communication channel. For such a channel, sending the symbols belonging to an independent set of the graph yields a reliable and error-free transmission of information. We show that reaching the maximum mutual information is equivalent to finding a maximum weight independent set of the graph where the weights convey entropy contents. Through this communication theoretic standpoint, we provide a distinct perspective for posing the problem of graph pooling as maximizing the information transmission rate across a noisy communication channel, implemented by a graph neural network. We evaluate our method, referred to as Maximum Entropy Weighted Independent Set Pooling (MEWISPool), on graph classification tasks and the combinatorial optimization problem of the maximum independent set. Empirical results demonstrate that our method achieves the state-of-the-art and competitive results on graph classification tasks and the maximum independent set problem in several benchmark datasets.
arXiv comment21 pages, 12 figures, under review in 35th Conference on Neural Information Processing Systems (NeurIPS 2021)
References in corpus (18)
- Adam: A Method for Stochastic Optimization
- Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
- Semi-Supervised Classification with Graph Convolutional Networks
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Neural Message Passing for Quantum Chemistry
- Fast Graph Representation Learning with PyTorch Geometric
- Hierarchical Graph Representation Learning with Differentiable Pooling
- How Powerful are Graph Neural Networks?
- Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
- Exact Combinatorial Optimization with Graph Convolutional Neural Networks
- Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
- PairNorm: Tackling Oversmoothing in GNNs
- Benchmarking Graph Neural Networks
- Order Matters: Sequence to sequence for sets
- InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization
- Learning Symbolic Physics with Graph Networks
- Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
- Graph Cross Networks with Vertex Infomax Pooling