Graph Neural Networks (GNNs) have emerged as the primary tool for learning on graph-structured data. Yet, many GNNs are primarily suited for toy academic benchmarks, often limiting their efficacy in real-world scenarios. This thesis proposes novel approaches to enable the use of GNNs in real-world applications, including but not limited to social networks and recommender systems.

Our contributions are as follows:

Scalability: We introduce Scalable Inception Graph Neural Networks (SIGN). By decoupling graph propagation from model learning, SIGN obtains comparable accuracy to previous models but with up to 30x faster inference, enabling efficient GNNs on web-scale graphs.

Temporality: We propose Temporal Graph Networks (TGN), a comprehensive framework for learning on evolving graphs. Representing a temporal graph as a series of events, TGN dynamically updates node representations through event-driven messages prior to their aggregation across the graph. TGN outperforms previous methods on both temporal node-classification and link-prediction tasks.

Edge Directionality: Our research shows the importance of leveraging edge directionality, especially in heterophilic tasks. We introduce Directed Graph Neural Networks (Dir-GNN), a general framework to extend any spatial GNN to directed graphs. Incorporating edge directionality with Dir-GNN leads to large accuracy gains in heterophilic scenarios, while leaving performance unchanged on homophilic graphs.

Missing Data: Addressing data incompleteness, Feature Propagation (FP) imputes missing node attributes by propagating existing ones through the graph. Paired with a downstream GNN, FP mitigates accuracy degradation to about 4% even when 99% of the features are absent, vastly outperforming previous methods.

Structural Inference: We propose NuGget, a method to reconstruct unknown graphs in a game-theoretic setup. NuGget recovers the network structure of a game from players' equilibrium actions, outperforming previous models without relying on explicit utility functions.