Counting graphs and trees with modal logic for neural networks
On Counting Graphs for Modal Logic with Counting
Artificial IntelligenceLogic in Computer Science
Summary
The paper looks at how hard it is to count certain types of trees and graphs that satisfy special rules used by some neural networks called graph neural networks. These rules are expressed in a kind of logical language called modal logic with counting. The researchers also examine how these counting processes behave when repeated or approximated many times. Understanding this complexity helps show what kinds of graph properties can be efficiently analyzed or verified using these logical formulas and networks.
What this means in practice
- •For graph algorithm engineers: Analyze the limits of efficient counting methods for graphs that meet logical constraints from modal logic with counting.
- •For network security teams: Assess which graph properties can be precisely counted or verified to improve automated detection in network topologies.
A theory result. No direct application yet.
Authors
Avijeet Ghosh, François Schwarzentruber
Abstract
In this paper, we study the theoretical computational complexity of counting trees and graphs that are classified positively by a graph neural networks, or said equivalently that satisfy a given formula of modal logic with counting. We also study convergence.