The Polynomial Counting Capabilities of Message Passing Neural Networks
The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear arithmetic constraint. In this paper, we study the counting capabilities of MPNN beyond linear arithmetic, primarily utilising local and global mean aggregations. In particular, our goal is to tease out conditions required to express extensions of graded modal logic with polynomial counting constraints. We show that global polynomial counting constraints in node-labelled graphs can be checked using mean MPNN under mild assumptions. Checking local constraints is also possible, if we consider formulas with no nested modalities and additionally either (i) permit sum/max aggregations, or (ii) only restrict to regular graphs. We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures and similar assumptions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching
Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures in many applications. Some applications in heterogeneous graphs require explicit edge mod…
Node ClassificationRepresentation LearningMessage Passing on the Edge: Towards Scalable and Expressive GNNs
Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attention to GNNs that perform message passing …
Graph LearningCondPSE: A Polynomial-Filtered Structural Encoder with Conditional Modulation for Graphs
Message-passing graph neural networks are bounded by the 1-WL test and can miss topological structure that distinguishes non-isomorphic graphs. Positional and structural encodings (PSE) inject such topology-derived signa…
Molecular Property PredictionCIN++: Enhancing Topological Message Passing
Graph Neural Networks (GNNs) have demonstrated remarkable success in learning from graph-structured data. However, they face significant limitations in expressive power, struggling with long-range interactions and lackin…
Graph ClassificationGraph RegressionVariational message passing for online polynomial NARMAX identification
We propose a variational Bayesian inference procedure for online nonlinear system identification. For each output observation, a set of parameter posterior distributions is updated, which is then used to form a posterior…
Bayesian InferenceForm