Graph Neural Networks (GNNs) are powerful frameworks for learning graph representations. They use neighborhood aggregation to compute node representations by recursively aggregating and transforming neighboring node features. Despite their success in node and graph classification tasks, there is limited understanding of their theoretical properties and limitations. This paper presents a theoretical framework to analyze the expressive power of GNNs, showing that they cannot distinguish certain simple graph structures. A simple architecture, the Graph Isomorphism Network (GIN), is developed, which is provably as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test. The GIN achieves state-of-the-art performance on graph classification benchmarks. Theoretical analysis shows that GNNs are at most as powerful as the WL test in distinguishing graph structures. The paper also identifies graph structures that cannot be distinguished by popular GNN variants like GCN and GraphSAGE. Empirical results validate the theoretical findings, showing that GIN outperforms other GNNs in terms of test accuracy and generalization. The study highlights the importance of expressive aggregation functions in capturing graph structures and the limitations of less powerful GNN variants.Graph Neural Networks (GNNs) are powerful frameworks for learning graph representations. They use neighborhood aggregation to compute node representations by recursively aggregating and transforming neighboring node features. Despite their success in node and graph classification tasks, there is limited understanding of their theoretical properties and limitations. This paper presents a theoretical framework to analyze the expressive power of GNNs, showing that they cannot distinguish certain simple graph structures. A simple architecture, the Graph Isomorphism Network (GIN), is developed, which is provably as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test. The GIN achieves state-of-the-art performance on graph classification benchmarks. Theoretical analysis shows that GNNs are at most as powerful as the WL test in distinguishing graph structures. The paper also identifies graph structures that cannot be distinguished by popular GNN variants like GCN and GraphSAGE. Empirical results validate the theoretical findings, showing that GIN outperforms other GNNs in terms of test accuracy and generalization. The study highlights the importance of expressive aggregation functions in capturing graph structures and the limitations of less powerful GNN variants.