arXiv (Cornell University) · 2019 · 37 citations · 23 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationMachine LearningGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryGraph-based LearningNeural NetworksBenchmark DatasetsGraph IsomorphismGraph MatchingGraph Neural NetworksGraph Property TestingGraph Representation LearningNetwork ApproximationSubgraph Isomorphism
Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.
23
A tutorial on spectral clustering
Ulrike von Luxburg · Statistics and Computing · 2007 · 10.3K citations · Full text
The Graph Neural Network Model
Franco Scarselli, M. Gori, Ah Chung Tsoi et al. · IEEE Transactions on Neural Networks · 2008 · 9.3K citations · Full text
Approximation capabilities of multilayer feedforward networks
Kurt Hornik · Neural Networks · 1991 · 6.1K citations