Skip to content
Back to search results

Graph Neural Network — GCN / GAT / GraphSAGE

Year
2017–2018 (major variants)
Type
Deep learning on graph-structured data
Font size

What does it do?

A Graph Neural Network (GNN) is a deep learning architecture that operates directly on graph-structured data by combining node features with structural information through iterative neighborhood message passing.

The three canonical variants — the Graph Convolutional Network (GCN) introduced by Kipf and Welling in 2017, the Graph Attention Network (GAT) introduced by Veličković et al. in 2018, and GraphSAGE — differ in how they aggregate neighbor information: GCN applies a spectral convolution over the full adjacency, GAT weights neighbors by learned attention scores, and GraphSAGE samples and aggregates local neighborhoods inductively, enabling generalization to unseen nodes.

The intuition behind the method

Think of every node in a graph as a person in a social network. That person has their own profile (features), but who they know also says a lot about them. A GNN lets each node repeatedly collect messages from its neighbors, mix those messages with its own information, and update its representation — layer by layer. After a few rounds of this gossip-style exchange, each node's embedding reflects not just itself but the local subgraph around it. GCN does this with a fixed symmetric average of neighbors; GAT decides which neighbors to trust more by learning attention weights; GraphSAGE samples a fixed subset of neighbors and learns an aggregation function that can be applied to nodes it has never seen before.

History

The foundations of applying neural networks to graphs were laid by Scarselli et al. (2009), but the modern GNN era began with Kipf and Welling's Graph Convolutional Network (2017), which simplified spectral graph convolution into an efficient first-order approximation using symmetric normalized adjacency multiplication. A year later, Veličković et al. (2018) introduced Graph Attention Networks, replacing the fixed averaging of GCN with learnable attention coefficients on each edge — allowing the model to selectively weight neighbors. Concurrently, Hamilton et al. (2017) proposed GraphSAGE, an inductive framework that samples fixed-size neighborhoods and learns aggregation functions transferable to unseen nodes, making GNNs practical for large and dynamic graphs. These three papers established the message-passing paradigm that now underpins the majority of GNN research.

When to use it

Use a GNN when your data is naturally graph-structured — social networks, citation networks, molecular graphs, knowledge graphs, or any setting where relationships between entities carry predictive signal. You need a node feature matrix and an edge list. A minimum of around 50 nodes is required for meaningful training. GNNs are applicable to node classification (predicting a label for each node), link prediction (inferring missing edges), and graph classification (assigning a label to a whole graph). The homophily assumption — connected nodes tend to share the same label — is implicitly exploited by GCN and standard GAT; if your graph is heterophilic, consider architectures designed for that setting. For large graphs, full-batch training is memory-prohibitive and mini-batch neighborhood sampling (GraphSAGE-style) is needed. If your graph has fewer than 20 nodes, traditional centrality metrics are a more appropriate choice.

Limitations and considerations

  • Over-smoothing: stacking many GNN layers pushes all node embeddings toward a common value, limiting effective depth to around 2–4 layers in practice.
  • Scalability: full-batch GCN and GAT require holding the entire adjacency matrix and feature matrix in memory, which is infeasible for very large graphs without sampling or partitioning.
  • The homophily assumption baked into standard aggregation degrades performance on heterophilic graphs where neighbors tend to have different labels.
  • Minimum sample size of ~50 nodes is required; fewer nodes leave the model without enough signal to learn meaningful representations.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Jointly leverages both node features and graph topology, outperforming methods that use either alone.
  • GAT's attention mechanism provides per-edge importance scores, adding interpretability to the aggregation.
  • GraphSAGE is inductive and can generalize to nodes and graphs not seen during training, enabling deployment on growing networks.
  • A unified message-passing framework covers node classification, link prediction, and graph classification with the same architectural backbone.

Applications

  • Node classification in citation networks — predicting the topic of a paper based on its content and citation links.
  • Drug discovery — predicting molecular properties by treating atoms as nodes and chemical bonds as edges.
  • Recommender systems — modeling users and items as a bipartite graph and predicting user-item interactions via link prediction.
  • Fraud detection in financial transaction networks — identifying anomalous nodes based on their features and neighborhood structure.
  • Knowledge graph completion — inferring missing relations between entities in large-scale knowledge bases.

How it works

How it works

1

The graph is defined by a node feature matrix X (one row per node, one column per attribute) and an edge list (or adjacency matrix) A. Undirected edges are standard for GCN and GAT; GraphSAGE also supports directed graphs. Self-loops are typically added to A so each node is included in its own aggregation.

2

Raw node attributes are normalized and, if necessary, embedded into a continuous vector space. Edge attributes, if present, can be incorporated as additional signals. The result is a dense feature matrix that each GNN layer will transform.

3

Each GNN layer computes a new node representation by aggregating the features of a node's neighbors and combining them with the node's own features through a learnable weight matrix and a non-linear activation. GCN applies a normalized adjacency multiplication (spectral convolution); GAT computes softmax attention coefficients for each edge so influential neighbors contribute more; GraphSAGE randomly samples a fixed-size neighborhood and applies a differentiable aggregator (mean, LSTM, or pooling). Stacking L layers lets information flow L hops away, but stacking too many layers causes over-smoothing, where all node embeddings converge to the same value.

4

The final node embeddings are fed into a task-specific head. For node classification a softmax layer assigns class probabilities to each node. For link prediction an inner product or MLP scores the likelihood of an edge between two node embeddings. For graph classification a global pooling (sum, mean, or hierarchical) aggregates all node embeddings into a single graph-level vector before the classification layer.

5

Model performance is measured on a held-out test set using metrics appropriate to the task: accuracy or F1 for node and graph classification, AUC-ROC for link prediction. Because graph datasets often have limited size, transductive evaluation (train/val/test masks on the same graph) or inductive splits (disjoint subgraphs) should match the deployment scenario.

Common pitfalls

  • Adding too many GNN layers causes over-smoothing: all node embeddings converge and the model loses discriminative power. Keep the number of layers at 2–4 and monitor embedding variance.
  • Training on the full graph without mini-batching is memory-prohibitive for large networks; use GraphSAGE-style neighbor sampling or graph partitioning for graphs with more than a few thousand nodes.
  • Applying a transductively trained GCN directly to new, unseen nodes at inference time is incorrect; use an inductive method like GraphSAGE if your deployment requires generalization to new nodes.
  • Ignoring the homophily assumption on heterophilic graphs produces poor results; inspect the graph's assortativity coefficient before choosing a standard GNN variant.
  • With fewer than 20 nodes GNN training yields unreliable representations; prefer conventional network centrality analysis in that regime.

Frequently asked questions

Which GNN variant should I start with — GCN, GAT, or GraphSAGE?

GCN is the simplest baseline and works well on small-to-medium homophilic graphs where all nodes are known at training time. GAT is preferable when neighbor importance varies and you want interpretable attention weights. GraphSAGE is the right choice when you need to generalize to nodes unseen during training or when the graph is too large for full-batch processing.

What is over-smoothing and how do I avoid it?

Over-smoothing occurs when many GNN layers cause all node embeddings to converge to the same value, eliminating discriminative information. In practice, 2–4 layers is usually optimal. Techniques such as residual connections, jumping knowledge networks, and DropEdge can help if deeper architectures are necessary.

Do GNNs require labeled data for all nodes?

No. GCN and GAT are commonly used in semi-supervised settings where only a small fraction of nodes carry labels; the graph structure propagates information from labeled to unlabeled nodes. GraphSAGE can also be trained in a fully supervised or unsupervised manner depending on the task.

How large does the graph need to be?

A minimum of around 50 nodes is needed for meaningful GNN training. With fewer than 20 nodes the model cannot learn reliable representations and traditional centrality-based analysis is more appropriate. For graphs with millions of nodes, mini-batch neighbor sampling (as in GraphSAGE) or graph partitioning methods are required to keep memory usage tractable.

Related methods

Sources

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    Open DOI reference
    Copied.
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    Open DOI reference
    Copied.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    Open DOI reference
    Copied.