IM Engineer Study Notes
← Back to list
AI & Data
#GNN#메시지패싱#GCN#GraphSAGE#GAT
Last updated · 2026-10-01

Graph Neural Network (GNN)

1. Overview

A. Definition

A neural network that takes graph-structured data composed of nodes (vertices) and edges directly as input, and performs node-, edge-, and graph-level predictions by having each node repeatedly aggregate information from its neighbors to update its own representation (embedding).

Traditional neural networks rest on the implicit assumption that the input has a regular, fixed structure, like a grid (image) or a sequence (sentence). A CNN can slide a fixed-size filter because pixels are arranged on a 2D grid, and an RNN can read tokens in order because they are lined up in a row. Yet much real-world data lacks this regularity. In a social network each person has a different number of friends, in a molecular structure each atom forms a different number of bonds, and, as in a subway map, the connectivity itself carries the core meaning of the data. Such unstructured, non-Euclidean data has a different number of neighbors per node (variable degree) and no fixed ordering of nodes (permutation invariance), so existing models cannot be applied as-is.

Three converging trends explain the rapid rise of GNNs since the late 2010s. First, the explosion of social, e-commerce, and IoT activity caused an explosive increase in data that is inherently a graph; second, libraries such as PyTorch Geometric and DGL standardized complex message passing and greatly lowered the barrier to entry; third, advances in GPU/[[npu]] brought large-scale sparse matrix operations to practical speeds. As a result, graph problems that once relied on hand-crafted features moved to end-to-end learning.

Forcing data into a grid distorts information. Flattening a social graph into an adjacency matrix and feeding it to a CNN produces an entirely different input whenever the node order changes, violating the graph's essence that "order has no meaning." GNNs solve this with the idea that "instead of forcibly flattening structure into a grid, reflect the connectivity directly in the computation." The key insight is that "the meaning of a node is defined by its neighbors." That is, a user's tendencies are largely explained by whom they are connected to, and an atom's chemical role is revealed by which atoms it is bonded to. GNNs implement this intuition as the operation of repeatedly aggregating neighbor information, and as a result they have brought clear performance gains over prior methods on problems where the graph is essential — recommender systems (neighbor-based preference propagation), drug discovery (predicting toxicity/activity from molecular graphs), fraud detection (anomalous patterns in transaction networks), and traffic prediction (congestion propagation over road networks).

B. Characteristics

Three properties run through GNN design. First, permutation invariance/equivariance — the result must not change no matter how nodes are numbered, and a GNN's aggregation functions (sum, mean, max) are designed to be independent of input order. This is because, while an image's pixels have an implicit ordering of "top-left to bottom-right," a graph's neighbor set has no order. Second, local connectivity and weight sharing — just as a CNN uses the same filter at every position, a GNN applies the same aggregation/transformation parameters to every node, so a single model handles graphs of different sizes (inductive generalization). Thanks to this, a model trained on 10 nodes can be applied directly to a graph of a million nodes. Third, multi-level outputs — node classification (user tendencies), link prediction (edge level, friend recommendation), and graph classification (whole-graph level, molecular toxicity) can all be handled within the same message-passing framework.

These characteristics make GNNs a "general framework for learning structure." The essence is that the learning target is not the shape of the data (grid, sequence, graph) but the relationships themselves; indeed, CNNs and RNNs can be interpreted as special cases of GNNs by regarding them as graphs of grid or chain form. That said, this freedom of design means there are many elements to decide — aggregation method, number of layers, sampling strategy — as discussed later in the advanced and considerations sections.

Characteristic Content Practical meaning
Permutation invariance Result independent of node numbering Consistent application to arbitrary graphs
Weight sharing Same parameters for all nodes Generalization across graph sizes
Multi-level output Node/edge/graph prediction Diverse tasks in one framework
Attribute + structure fusion Learns node features and connectivity together No hand-crafted feature design

2. Core Principle — Message Passing

Almost all GNN variants are described by the common framework of message passing. At every layer, each node ① receives messages (Message) from its neighbors, ② combines them into one (Aggregate) in an order-independent way, and ③ merges the result with its own previous representation to update (Update). One such iteration corresponds to "absorbing information from 1-hop neighbors," so stacking K layers lets each node capture structural and attribute information from neighbors up to K hops away in its embedding. For example, in a 2-layer GNN a user's representation reflects friends (1 hop) and friends of friends (2 hops).

flowchart LR
  subgraph G["Input Graph"]
    A((A)) --- B((B))
    A --- C((C))
    B --- D((D))
    C --- D
  end
  G --> MP["Message Passing (K layers)"]
  MP --> EMB["Node embedding h_v"]
  EMB --> NODE["Node classification"]
  EMB --> LINK["Link prediction"]
  EMB --> GRAPH["Graph classification (Readout)"]

In formula form, the k-th layer representation of node v is written h_v^(k) = UPDATE(h_v^(k-1), AGGREGATE({h_u^(k-1) : u ∈ N(v)})), where N(v) is the neighbor set of v. The choice of aggregation function governs the character of the model: the mean stably captures a representative value of the neighbor distribution but blurs differences in neighbor count; the sum preserves degree (connection count) information but can grow large in scale; the max captures prominent neighbor features. For graph classification, where the whole graph must be summarized into a single vector, an additional Readout (pooling) step combines all node embeddings.

Message passing is powerful because it mixes structure and attributes simultaneously and automatically. For example, in fraud detection an account's risk depends not only on its own transaction patterns (attributes) but also on which accounts it is connected to and how (structure); message passing pulls in neighbors' attributes and blends them into a node's representation, naturally combining the two signals. Conversely, this can become a weakness: if a single wrongly connected edge spreads a contaminated message through neighbors, errors propagate and amplify, so the quality of the input graph directly determines performance.

A GNN's output is divided into three levels depending on the task, and every level starts from the same node embeddings. Node level feeds each node embedding to a classifier to predict user tendencies or paper topics; edge (link) level combines two node embeddings to predict the likelihood of a connection (friend recommendation, drug interaction); graph level uses Readout to summarize the whole and judge a molecule's overall toxicity or solubility. Being able to reuse a single learned representation across multiple tasks is a practical advantage of GNNs.

Step Operation Role
Message Transform and pass neighbor u's representation Generate information to pass
Aggregate Sum via sum/mean/max, etc. Permutation-invariant aggregation
Update Combine with prior representation (weights/activation) Update node representation
Readout Pool all node embeddings Graph-level representation (optional)

3. Major Architectures (GCN·GraphSAGE·GAT)

Representative architectures diverge according to how they concretize the three elements of message passing (especially how to aggregate). The figure below shows the process by which a node takes in neighbors and forms a representation, centered on each architecture's aggregation method.

flowchart TB
  N1["Neighbor node features"] --> AGG{"Aggregation method"}
  AGG -->|"Normalized weighted sum (degree-based)"| GCN["GCN"]
  AGG -->|"Sampling + mean/LSTM/pool"| SAGE["GraphSAGE"]
  AGG -->|"Attention weighted sum (learned importance)"| GAT["GAT"]
  GCN --> TRANS["Linear transform + activation"]
  SAGE --> TRANS
  GAT --> TRANS
  TRANS --> OUT["Next-layer node representation"]

A. GCN (Graph Convolutional Network). GCN is the most basic model, generalizing image convolution to graphs. The core idea is to gather neighbor representations not as a simple mean but as a degree-normalized weighted sum. Because highly connected (high-degree) neighbors tend to have their influence overestimated, their influence is adjusted by dividing by the square root of the degrees of the node and its neighbor (1/√(d_u·d_v)).

This normalization matters because a graph's degree distribution is extremely imbalanced. In a social network a celebrity has millions of followers while an ordinary user has dozens; without normalization, a simple sum lets high-degree nodes dominate the signal and destabilizes learning. GCN suppresses this cleanly in mathematical terms. However, GCN is a transductive method that uses the whole graph's adjacency matrix at once, so it is hard to apply directly to new nodes unseen during training, and it has the limitation of treating all neighbors equally (up to the normalization weight). It is therefore suited to fixed graphs whose node composition barely changes (e.g., topic classification in a paper citation network, community detection in a social graph), while services with frequent new nodes bear a heavy retraining burden.

B. GraphSAGE (SAmple and aggreGatE). Real-service graphs consist of hundreds of millions of nodes, making it unrealistic to aggregate all neighbors every time, and new users and items are constantly added. GraphSAGE solves this with neighbor sampling. For each node it randomly draws only a fixed number of neighbors (e.g., 25 at 1 hop, 10 at 2 hops) to aggregate, so computation stays constant even in graphs with widely varying degrees, enabling mini-batch training even on large graphs.

The more fundamental distinction is that GraphSAGE learns not per-node embeddings themselves but the function (mean/LSTM/pooling) for "how to aggregate neighbors" and the transformation weights. Once only the function is learned, even a new node unseen during training can have its representation computed immediately by gathering its neighbors, establishing inductive generalization. A representative case is Pinterest's recommender system PinSage, which applied this to a pin–board graph on the order of billions and processed newly added pins each day without retraining. Because of this property, it is effectively the standard in domains where content grows in real time, such as recommendation and advertising.

C. GAT (Graph Attention Network). Whereas GCN weights neighbors by degree alone, GAT learns from data "which neighbor is more important to me." It computes an attention coefficient for each neighbor pair and uses it as the aggregation weight, so even with the same number of neighbors it focuses more on connections that carry greater meaning.

For example, in a paper citation network it can distinguish core citations that deeply engage the same topic from conventional, formal citations and give the former greater weight, and in a molecular graph it can focus on bonds decisive for reactivity. If GCN's fixed weights "treat all neighbors by their structural importance," GAT is one step more flexible in that it "also learns and reflects their semantic importance." Multi-head attention learns multiple perspectives in parallel to mitigate the bias of any one perspective and improve stability, but because coefficients are computed for every edge, computation and memory grow, so it must be combined with sampling on very large graphs.

D. GIN (Graph Isomorphism Network) and expressive power. How one chooses the aggregation function is not merely a performance matter but touches the fundamental limit of whether the model can distinguish structurally different graphs. Mean/max aggregation sees the "distribution" of neighbors but blurs the "count," so it may mistake different structures for the same representation. For instance, mean aggregation cannot distinguish a node with one neighbor from a node with two identical neighbors. GIN is designed to preserve such multiplicity information by using a sum and an injective function in aggregation, and its expressive power has been theoretically proven equivalent to the Weisfeiler-Lehman test, a classic technique for graph isomorphism discrimination. This gives the important lesson in GNN design that "the choice of aggregation function sets the model's theoretical upper bound," and it is especially important for graph classification where subtle structural differences, as in molecules, determine properties.

Category GCN GraphSAGE GAT
Aggregation core Degree-normalized weighted sum Neighbor sampling + aggregator Attention weighted sum
Training mode Transductive Inductive Both inductive/transductive
Large-scale scaling Weak (full adjacency matrix) Strong (sampling·mini-batch) Medium (per-edge computation)
Neighbor importance Fixed (degree-based) Uniform/aggregator Learned variable weights
Representative case Community classification PinSage recommendation Citation networks·molecular analysis

4. Comparison — Why GNN Instead of Existing Models

The same data can be handled with traditional methods too. For instance, one can discard the graph's structural information and feed only node attributes into an ordinary MLP, or hand-design graph features such as "number of neighbors, number of triangles" and feed them to a classifier. However, the former discards the core signal of connectivity wholesale, greatly lowering performance, while the latter requires expertise and trial-and-error in feature design and must be redone for each new problem. GNNs are fundamentally advantageous in that they learn structure and attributes together, automatically from data.

The difference from graph embedding methods such as Node2Vec·DeepWalk is also clear. These pre-learn per-node vectors via random walks, but they cannot use node attributes and have the transductive limitation of not handling new nodes unseen in training. GNNs, by contrast, blend node attributes into aggregation and allow inductive generalization. Indeed, on benchmarks for predicting the toxicity of drug candidates (e.g., MoleculeNet), GNNs that represent molecules as graphs have been reported in many cases to surpass traditional molecular fingerprint-based models, and the fundamental cause of this difference lies in "whether a human designs the representation or the data learns it structure and all."

Comparison target Structural info Node attributes New-node handling Feature design
MLP (attributes only) Not used Used Possible Automatic
Hand-crafted graph features Partial (human-summarized) Used Possible Manual
Graph embedding (Node2Vec) Used Not used Impossible (transductive) Automatic
GNN Used (message passing) Used Possible (inductive) Automatic

As the table shows, GNNs are the only approach that satisfies all four axes, which is why they are an option for problems with rich connectivity and meaningful attributes per node. They are not, however, "always superior"; on sparse or meaningless connectivity they may instead pull in noise and degrade performance, as discussed in the considerations section below.

5. Advanced — The Over-smoothing Problem and Recent Trends

A. Over-smoothing and its practical implications. GNNs have the advantage of seeing more distant neighbors as more layers are stacked, but paradoxically, as depth increases, all node representations become similar and indistinguishable — over-smoothing. This is because repeated aggregation eventually converges to the average over the whole graph.

Intuitively, aggregation is an operation that "mixes" representations with neighbors at every layer, and repeating it infinitely homogenizes all nodes to the same color, like a drop of ink spreading in water. The denser the connectivity, the faster this happens; in a social graph with the small-world property — where any two people are connected within just 6 hops — representations blur after stacking only 5–6 layers. Thus practical GNNs are often used shallowly, around 2–3 layers, and to overcome this they combine techniques such as residual connections, re-injection of initial representations (JKNet), and edge dropout (DropEdge). This is a GNN-specific design constraint, in contrast to CNNs where "depth is performance," and from a professional engineer's perspective how to secure long-range dependencies with a shallow model becomes a core design challenge.

B. Recent trends. First, Spatio-Temporal GNNs combine a time axis with graph structure and are used for traffic congestion prediction and power demand forecasting — by jointly modeling the road network (space) and time slots (time), they estimate how congestion at one intersection spreads to adjacent segments via both spatial propagation and time-series patterns. Second, the combination of GNNs and LLMs is active. The GraphRAG family, which embeds knowledge graphs with a GNN and uses them as evidence for retrieval-augmented generation ([[rag]]), is strong at multi-hop reasoning that follows relationships between entities, more so than conventional RAG that retrieves only document fragments. For example, in a query that chains multiple relationships, such as "the CEO of a startup invested in by a subsidiary of company A," plain similarity search brings back evidence fragments scattered, whereas graph traversal narrows precisely by following the path. Third, attempts continue to extend attention graph-wide, as in graph transformers, to mitigate over-smoothing and long-range dependency problems. These trends are still at a stage where standards are being established, so specific figures or superiority are hard to assert.

C. Industrial application cases. In finance, viewing accounts and transactions as a graph, GNNs are applied to money-laundering and anomalous-transaction detection, catching transaction rings that look normal individually but are suspicious in network structure (circular remittances, multi-stage distributed transfers). The core value is catching structural anomalies that rule-based detection misses. In logistics and delivery they are used for road-network-graph-based route and demand prediction, and in telecom for fault-propagation analysis based on network topology. In e-commerce they strengthen collaborative filtering with a user–item bipartite graph to raise the accuracy of [[recommendation-system]], which is the area where the GraphSAGE family is most widely used.

Industry Graph definition (node–edge) Task level Expected effect
Recommendation·Ads User–item, purchase·click Link prediction Complement sparse data·accuracy↑
Finance Account·transaction, remittance relation Node/subgraph Structural anomalous-transaction detection
Drug·Materials Atom–bond (molecule) Graph classification Pre-screening toxicity·activity
Transport·Energy Point–link (road·power grid) Spatio-temporal prediction Proactive response to congestion·demand
Knowledge·Search Entity–relation (knowledge graph) Multi-hop reasoning Strengthening GraphRAG evidence

What these cases share is that "the relationship is the signal." A single transaction, one atom, or one road segment looks ordinary in isolation, but the more the key information is hidden in how they are connected, the greater the GNN's advantage. Conversely, for a problem where relationships contribute little to prediction, a GNN's complexity only adds cost, so before adoption it is practically useful to check "does performance hold even if connections are severed" with a simple experiment (comparison after edge removal).

6. Considerations and Implications

Adopting a GNN requires not a mere model swap but the capability to model data as a graph and an operational framework. From a professional engineer's perspective, the following should be considered comprehensively.

  • Judging applicability: A GNN is not advantageous for every problem. First verify whether connectivity gives a substantive signal to prediction (e.g., recommendation, fraud detection, molecules); if structure is sparse or meaningless, a model for tabular data (GBM, etc.) is better. "Is it worth representing as a graph?" is the starting point.
  • Scalability·operations trade-off: Graphs with hundreds of millions of nodes cannot be fully aggregated, so sampling (GraphSAGE), distributed graph storage, and approximate aggregation are essential. In real-time inference, neighbor-lookup latency becomes a bottleneck, so one must design a balance between pre-computing embeddings and online updates.
  • Depth vs. expressive-power conflict: Because over-smoothing makes deep stacking hard, problems where long-range dependencies matter should be complemented with residual connections, graph transformers, and multi-scale designs, and the number of layers should be determined experimentally alongside performance and cost.
  • Data quality·bias·explainability: A graph's missing edges or wrong connections propagate and amplify errors through message passing. Also, in sensitive domains such as finance and hiring, bias embedded in the connection structure can lead to discrimination, so [[explainable-ai]] techniques (explaining important edges/subgraphs) and fairness checks should go hand in hand.
  • Adversarial attacks·security: Graphs are vulnerable to structural adversarial attacks that overturn predictions merely by cunningly adding/removing one or two edges. In domains where adversaries exist, such as fraud detection and content moderation, one must jointly design robustness against edge tampering and detection of anomalous connections.
  • Related technologies·outlook: Challenges include GraphRAG combined with knowledge graphs·[[vector-database]]·LLMs, operating graph features via a feature store ([[feature-store]]), and integration into MLOps pipelines. In the medium-to-long term, GNNs are expected to settle as the standard representation-learning means for relational and connected data, developing in convergence and competition with the transformer family.

References

In one line: A GNN is a neural network in which nodes repeatedly aggregate neighbor information (message passing) to learn representations; it has evolved through differences in aggregation such as GCN·GraphSAGE·GAT and excels at problems where the graph is essential, such as recommendation, drug discovery, and fraud detection.