Node Classification on a Knowledge Graph: Analyzing NELL with a GCN

1. Project Overview

Background and Goals

As an assignment for a graph neural networks course, I implemented a GCN (Graph Convolutional Network) node classification model on the NELL (Never-Ending Language Learning) knowledge graph dataset and analyzed its performance. The goal went beyond calling a library: I wanted to analyze the structural properties of the dataset in depth and understand how graph neural networks work.

In particular, I set out to answer three questions:

• Can a GNN effectively learn the semantic categories of nodes in a large knowledge graph?
• What performance is achievable with 186 classes and severe class imbalance?
• How much does graph structure contribute to node classification?

I trained and evaluated the model on the NELL dataset and reached a final test accuracy of 97.86%. Along the way, I gained a deep understanding of the structural properties of knowledge graphs, the message passing mechanism of GCNs, and training strategies for large sparse graphs.

What Is a Graph Neural Network (GNN)?

Properties of Graph Data

Traditional machine learning and deep learning mostly deal with data in Euclidean space. Images are represented as 2D grids and text as 1D sequences, and architectures like CNNs and RNNs are specialized for such structured data. But much real-world data has a non-Euclidean structure:

• Social networks: Users (nodes) and friendships (edges)
• Molecular structures: Atoms (nodes) and chemical bonds (edges)
• Knowledge graphs: Entities (nodes) and relations (edges)
• Recommender systems: User-item interaction graphs

Graph data like this has a variable number of nodes, irregular connection patterns, and no fixed ordering. That is why traditional neural networks are hard to apply directly.

The Message Passing Paradigm

GNNs use the message passing paradigm to process graph-structured data. Each node gathers information from its neighbors (Aggregate) and updates its own representation (Update). Repeating this over several layers lets each node's representation capture information from an increasingly wide neighborhood.

The general form of message passing is:

Where:

• $h_v^{(k)}$: The representation of node v at layer k
• $\mathcal{N}(v)$: The set of neighbors of node v
• AGGREGATE: A function that gathers information from neighbors (e.g. mean, sum, max)
• UPDATE: A function that combines the aggregated information with the node's own information

Expressive Power of GNNs

GNNs are closely related to the Weisfeiler-Leman (WL) graph isomorphism test. The WL test is an algorithm that decides whether two graphs are structurally identical by repeatedly updating node labels with neighbor information. It has been proven theoretically that the expressive power of standard GNNs (GCN, GraphSAGE, etc.) is equivalent to the 1-WL test.

This means there are limits to the graph structures a GNN can distinguish, but in practice it provides enough expressive power in most cases.

Graph Convolutional Network (GCN)

The Core Idea of GCN

The GCN, proposed by Kipf and Welling in 2017, is based on spectral graph theory. It transforms graph signals into the frequency domain through the eigendecomposition of the graph Laplacian, applies a filter, and transforms them back to the node domain. Approximating this with Chebyshev polynomials and keeping only the first-order term yields the following simple form:

Where:

• $\tilde{A} = A + I$: The adjacency matrix with self-loops added
• $\tilde{D}$: The degree matrix of $\tilde{A}$
• $H^{(l)}$: The node representation matrix at layer l
• $W^{(l)}$: A learnable weight matrix
• $\sigma$: A nonlinear activation function

What the Normalization Means

The $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ term performs symmetric normalization. This normalization matters because of:

1. Scale invariance: It balances how much information propagates between high-degree and low-degree nodes
2. Numerical stability: Feature values stay within [-1, 1], keeping training stable
3. Both directions considered: It accounts for the degrees of both the sender and the receiver

Intuitively, it keeps very high-degree hub nodes from having outsized influence and lets low-degree nodes pass along meaningful information too.

GCN vs Other GNN Variants

Besides the GCN, there are many GNN variants:

I chose the GCN for this project. It is effective for node classification on knowledge graphs, intuitive to implement, and computationally efficient.

What Is a Knowledge Graph?

Definition and Structure

A knowledge graph represents real-world knowledge as a graph. Nodes represent entities, and edges represent relations between entities. Knowledge is typically expressed as triples of the form (head, relation, tail).

Examples:

• (Seoul, capital of, South Korea)
• (Einstein, place of birth, Ulm)
• (Python, programming language, software)

Applications of Knowledge Graphs

Knowledge graphs are used in many fields:

• Search engines: Google Knowledge Graph, Bing Satori
• Recommender systems: Recommendations based on relations between items
• Question answering: Generating answers from structured knowledge
• Natural language processing: Entity linking, relation extraction

The NELL Project

NELL (Never-Ending Language Learning) is a research project that Carnegie Mellon University has run since 2010. Its goal is to build a knowledge base by continuously reading text on the web and extracting knowledge.

Characteristics of NELL:

• Automatic knowledge extraction: Extracts knowledge from web documents using patterns
• Continuous learning: Runs 24/7, steadily expanding its knowledge
• Self-supervision: Uses what it already knows to verify new knowledge
• Multiple data sources: Draws on text, tables, images, and other sources

The NELL dataset is the knowledge graph extracted by this project, processed for graph learning. Entities are represented as nodes and relations as edges, and each entity's semantic category (e.g. city, athlete, drug) is provided as the node label.

Development Environment

• Frameworks: PyTorch 2.0, PyTorch Geometric
• Graph analysis: NetworkX
• Visualization: Matplotlib, Seaborn
• Hardware: NVIDIA GPU (CUDA)
• Key library versions:
  • torch_geometric: latest version
  • networkx: 3.x
  • numpy, scipy: for scientific computing

2. Dataset Analysis (Task 1)

Loading the NELL Dataset

I used the NELL dataset provided by PyTorch Geometric. The loading code is as follows:

from torch_geometric.datasets import NELL

dataset = NELL(root='./data/NELL')
data = dataset[0]

print(f"Nodes: {data.num_nodes:,}, Edges: {data.num_edges:,}")
print(f"Features: {data.num_node_features}, Classes: {dataset.num_classes}")

After loading, the basic statistics of the NELL dataset are:

65,755 entities are connected by 251,550 relations, and each entity belongs to one of 186 semantic categories. The feature vectors are very high-dimensional at 61,278, because NELL's knowledge extraction encodes a wide range of text patterns and contextual information.

Exploring the Data Structure

Sparse Feature Matrix

The node features of the NELL dataset are stored as a sparse matrix. Storing a 61,278-dimensional dense vector for every node would take about 16GB of memory.

# Convert the sparse matrix to a dense matrix
x_dense = data.x.to_dense() if hasattr(data.x, 'to_dense') else data.x
print(f"Feature matrix shape: {x_dense.shape}")

Feature matrix analysis:

• Shape: (65,755, 61,278)
• Sparsity: 99.87% (most values are 0)
• Average non-zero features per node: About 80
• Value range: 0.0 ~ 1.0 (normalized)

This extremely sparse feature representation stems from how NELL extracts knowledge. Each entity is represented by the presence or absence of patterns in which it appeared in specific contexts in web text, and most entities appear in only a tiny fraction of all patterns.

Label Distribution

I analyzed the distribution of the 186 classes:

from collections import Counter

label_counts = Counter(data.y.numpy())
print("Top 10 Classes:")
for label, count in label_counts.most_common(10):
    print(f"  Class {label}: {count:,} ({count/len(data.y)*100:.1f}%)")

Distribution of the top 10 classes:

Severe class imbalance is evident. Class 0 accounts for 85.7% of all nodes, and the remaining 185 classes share 14.3%. This imbalance comes from the nature of NELL. Class 0 is a "general concept" or "unknown" category that holds entities without a clear category assigned.

With imbalance this extreme, simply predicting Class 0 for every node yields 85.7% accuracy. So evaluating the model properly requires per-class accuracy or confusion matrix analysis.

Converting to a NetworkX Graph

To analyze the graph structure in detail, I converted the PyTorch Geometric format into a NetworkX graph:

import networkx as nx
import numpy as np

# Convert the edge index to a NetworkX graph
edge_list = data.edge_index.numpy().T
G_full = nx.Graph()
G_full.add_edges_from([tuple(edge) for edge in edge_list])

print(f"NetworkX graph: {G_full.number_of_nodes():,} nodes, {G_full.number_of_edges():,} edges")

Conversion results:

• Nodes: 65,755 (same as the original)
• Edges: 125,775 (half of the original - converted to an undirected graph)

PyTorch Geometric's edge_index stores the graph in directed form, keeping both directions of every edge. Converting to an undirected NetworkX graph halves the edge count.

Connected Component Analysis

components = list(nx.connected_components(G_full))
component_sizes = [len(comp) for comp in components]

print(f"Connected: {nx.is_connected(G_full)}")
print(f"Number of components: {len(components)}")
print(f"Largest component: {max(component_sizes):,} nodes")
print(f"Smallest component: {min(component_sizes)} nodes")

Results:

• Connectivity: Disconnected graph (Not Connected)
• Number of connected components: 78
• Largest component size: 62,028 nodes (94.3% of all nodes)
• Smallest component size: 1 node (isolated node)
• Average component size: 843.3 nodes

The graph is not fully connected and splits into 78 connected components. But the largest connected component contains 94.3% of all nodes, so most entities belong to one giant connected structure. The other 77 components are relatively small clusters or isolated nodes.

Visualizing the Whole Graph

To get a picture of the overall structure, I made a visualization with four subplots:

Degree Distribution (Top Left)

A degree distribution histogram on a log scale. The x-axis is node degree (number of connected edges), and the y-axis is the frequency of nodes with that degree.

Observations:

• Power-law distribution: The degree distribution follows a power law; most nodes have low degree and a few have very high degree
• Degree range: From 1 to about 4,500
• Mode: Most nodes are concentrated in the degree 1~10 range

This distribution is characteristic of a scale-free network, reflecting that some important concepts (hub nodes) in a knowledge graph have many relations.

Connected Component Size Distribution (Top Right)

The size distribution of connected components on a log scale. It is polarized: one giant component with more than 60,000 nodes and many very small components.

Top 20 Class Distribution (Bottom Left)

Class 0 has overwhelmingly more nodes, and the other classes have comparatively very few. This visualization confirms the class imbalance analyzed above.

Graph Structure (Bottom Right)

I sampled 5,000 nodes from the largest connected component and visualized them in a circular layout. Node color indicates degree, with bright colors (yellow) for high-degree nodes. A dense connection structure in the center and low-degree nodes spread around the outside are visible.

3. Graph Analysis (Task 2)

Graph Structure Analysis

Basic Statistics

def analyze_graph_structure(G_full):
    num_nodes = G_full.number_of_nodes()
    num_edges = G_full.number_of_edges()
    density = nx.density(G_full)
    avg_degree = 2 * num_edges / num_nodes

    return {
        'nodes': num_nodes,
        'edges': num_edges,
        'density': density,
        'avg_degree': avg_degree
    }

What Graph Density Means

Density is the fraction of all possible edges that actually exist:

The density of the NELL graph is very low at 0.000058. This means it is an extremely sparse graph. If every pair of nodes were connected, about 2.16 billion edges would be needed, but only 126,000 actually exist.

This sparsity reflects the nature of knowledge graphs. Not every entity is related to every other entity; relations form only among entities in a particular domain or that are semantically related.

Checking for Special Structures

num_selfloops = nx.number_of_selfloops(G_full)
isolated_nodes = len(list(nx.isolates(G_full)))

print(f"Self loops: {num_selfloops}")
print(f"Isolated nodes: {isolated_nodes}")

• Self-loops: 0 (no entity is related to itself)
• Isolated nodes: 0 (every node has at least one edge)

Degree Distribution Analysis

The degree distribution is a key indicator for understanding the structural properties of a network.

degrees = [d for n, d in G_full.degree()]
avg_degree = np.mean(degrees)
median_degree = np.median(degrees)
max_degree = max(degrees)
min_degree = min(degrees)

print(f"Average degree: {avg_degree:.2f}")
print(f"Median degree: {median_degree:.1f}")
print(f"Max degree: {max_degree}")
print(f"Min degree: {min_degree}")

Degree statistics:

The large gap between the mean (3.83) and the median (1.0) indicates very high skewness. Most nodes have degree 1~3, but a few hub nodes with thousands of connections pull the mean up.

Hub Node Analysis

sorted_degrees = sorted(G_full.degree(), key=lambda x: x[1], reverse=True)
print("Top 10 hub nodes:")
for i, (node, degree) in enumerate(sorted_degrees[:10]):
    print(f"  {i+1}. Node {node}: {degree} connections")

Top 10 hub nodes:

The top hub node (Node 3) has 4,684 connections, meaning it is directly connected to about 7% of all nodes. Hub nodes like these usually correspond to widely used concepts (e.g. "person", "organization", "location").

Detailed Degree Distribution Visualization

Linear histogram (top left)

Most nodes are concentrated in the degree 1~10 range, so the bars bunch up near the origin. The red dashed line marks the mean (3.83), and the green dashed line marks the median (1.0).

Log-scale histogram (top right)

With the y-axis on a log scale, the long-tail distribution becomes clearer. A fair number of nodes have degree above 100, and there are extreme hub nodes above 4,000.

Cumulative distribution function CCDF (bottom left)

The complementary cumulative distribution function on a log-log scale. A nearly straight line is the typical pattern of a power-law distribution. This confirms that the NELL knowledge graph is a scale-free network.

Property of a power-law distribution:

Here γ is the exponent of the distribution, typically in the range 2 < γ < 3. From the slope of the NELL graph's CCDF, γ ≈ 2.5 is estimated.

Top 20 nodes (bottom right)

A bar chart of the top 20 nodes by degree. The top 3 nodes have especially high degrees, followed by a gradual decline, a pattern similar to a Zipf distribution.

Network Topology Analysis

A complete topology analysis of a large graph is computationally expensive. So I sampled 1,000 nodes for the analysis.

import random

sample_size = 1000
sampled_nodes = random.sample(list(G_full.nodes()), sample_size)
G_sample = G_full.subgraph(sampled_nodes).copy()

Clustering Coefficient

The clustering coefficient measures how connected a node's neighbors are to each other. It quantifies the question "is a friend of my friend also my friend?"

Here $e_i$ is the number of edges among the neighbors of node i, and $k_i$ is the degree of node i.

clustering_coeffs = list(nx.clustering(G_sample).values())
avg_clustering = np.mean(clustering_coeffs)
print(f"Average clustering coefficient: {avg_clustering:.4f}")

Average clustering coefficient: 0.1847

This value is higher than expected for a completely random graph (Erdős–Rényi model). A random graph's clustering coefficient is expected to equal its density, 0.000058, but the actual value is much higher. This means the NELL graph has local clustering structure.

Such high clustering is natural in a knowledge graph. For example, if "Einstein," "theory of relativity," and "Nobel Prize in Physics" are connected to each other, they form a triangle.

Path Length Analysis

I analyzed the average path length and diameter in the largest connected component.

# Extract the largest connected component
largest_cc = max(nx.connected_components(G_sample), key=len)
G_largest = G_sample.subgraph(largest_cc)

avg_path = nx.average_shortest_path_length(G_largest)
diameter = nx.diameter(G_largest)
radius = nx.radius(G_largest)

An average path length of 4.23 means any two nodes can reach each other through about 4 intermediate nodes on average. This shows the small-world property: concepts in a knowledge graph are linked by short chains of relations.

Centrality Analysis

I analyzed three centrality measures:

1. Degree Centrality

The normalized number of connections of a node, measuring direct influence.

degree_cent = nx.degree_centrality(G_sample)
top_degree = sorted(degree_cent.items(), key=lambda x: x[1], reverse=True)[:5]

2. Closeness Centrality

The reciprocal of the average distance to all other nodes, measuring how fast information spreads.

3. Betweenness Centrality

Measures how often a node appears on the shortest paths between other pairs of nodes. It identifies nodes that act as brokers.

Centrality results (top 5 nodes):

The top nodes largely agree across the three centrality measures, showing that key concepts in a knowledge graph play important roles in several respects.

Domain-Specific Interpretation

Summarizing the analysis of the NELL knowledge graph:

1. Large sparse graph: 65,755 entities, 125,775 relations, density 0.000058
2. Scale-free: Power-law degree distribution; a few hub nodes carry many connections
3. Modular structure: 78 connected components, high clustering coefficient
4. Small-world: Short average path length (about 4 hops)

These properties have important implications for GNN design:

• Sparsity → efficient message passing is possible
• Hub nodes → normalization matters (the GCN's symmetric normalization is effective)
• Clustering → local aggregation can learn meaningful patterns
• Short paths → even a 2-3 layer GNN can propagate information widely

Graph Structure Visualization

I made a detailed visualization of a sampled subgraph.

Main graph (left)

A subgraph of 300 nodes visualized with a spring layout. Node color indicates degree using the viridis colormap (purple: low degree, yellow: high degree). Red labels mark the top 10% of nodes by degree.

High-degree hub nodes sit in the center, with low-degree nodes radiating out from them in a star-like structure.

Degree distribution (top right)

A degree distribution histogram of the sampled graph. Like the full graph, it is concentrated at low degrees.

Class distribution (bottom right)

The class label distribution of the sampled nodes. The dominance of Class 0 reflects the full graph.

Network Topology Visualization

I visualized the graph structure from four perspectives.

By degree (top left)

Node color indicates degree. High-degree nodes (bright) sit at the center of the graph, and low-degree nodes (dark) sit on the outside.

By clustering coefficient (top right)

Node color indicates the local clustering coefficient. Nodes with a high clustering coefficient (bright) belong to local communities whose members are tightly connected to each other.

Hub nodes highlighted (bottom left)

The top 10% of nodes by degree are shown in red and the rest in light blue. You can see that the hub nodes form the structural center of the graph.

By class label (bottom right)

Node color indicates the class label. Nodes of the same class tend to cluster together spatially. This structure favors a GNN that classifies nodes by aggregating neighbor information.

4. Model Design and Implementation (Task 3)

GCN Model Architecture

Taking the properties of the NELL dataset into account, I designed a 3-layer GCN model.

Model Structure

from torch.nn import Linear, Dropout, BatchNorm1d
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, in_dim, hidden_dim, out_dim):
        super().__init__()
        # GCN layers
        self.gcn1 = GCNConv(in_dim, hidden_dim)
        self.bn1 = BatchNorm1d(hidden_dim)

        self.gcn2 = GCNConv(hidden_dim, hidden_dim)
        self.bn2 = BatchNorm1d(hidden_dim)

        self.gcn3 = GCNConv(hidden_dim, hidden_dim)
        self.bn3 = BatchNorm1d(hidden_dim)

        self.dropout = Dropout(p=0.4)
        self.out = Linear(hidden_dim, out_dim)

    def forward(self, x, edge_index):
        # Layer 1
        h = self.gcn1(x, edge_index)
        h = self.bn1(h)
        h = h.relu()
        h = self.dropout(h)

        # Layer 2
        h = self.gcn2(h, edge_index)
        h = self.bn2(h)
        h = h.relu()
        h = self.dropout(h)

        # Layer 3
        h = self.gcn3(h, edge_index)
        h = self.bn3(h)
        h = h.relu()
        h = self.dropout(h)

        # Output
        z = self.out(h)
        return h, z

Model Summary

GCN(
  (gcn1): GCNConv(61278, 128)
  (bn1): BatchNorm1d(128)
  (gcn2): GCNConv(128, 128)
  (bn2): BatchNorm1d(128)
  (gcn3): GCNConv(128, 128)
  (bn3): BatchNorm1d(128)
  (dropout): Dropout(p=0.4)
  (out): Linear(in_features=128, out_features=186)
)

Total parameters: 7,901,498

Per-layer structure:

Design Decisions

Number of Layers: 3

In a GNN, the number of layers equals the number of hops information propagates. A k-layer GNN aggregates information from k-hop neighbors.

Why 3 layers:

1. Adequate receptive field: In the NELL graph, with an average path length of about 4, 3 layers can gather information from most relevant nodes
2. Avoiding over-smoothing: When a GNN is too deep, all node representations become similar
3. Computational efficiency: On a large graph, many layers sharply increase memory and compute costs

Hidden Dimension: 128

hidden_dim = 128

Rationale:

• Compression: Compressing from 61,278 dimensions to 128, about 479x, to learn meaningful representations
• Expressive power: Enough capacity to distinguish 186 classes
• Efficiency: A balance between GPU memory and compute cost

I tested 64, 128, and 256 dimensions experimentally, and 128 was the sweet spot between performance and efficiency.

Using BatchNorm

self.bn1 = BatchNorm1d(hidden_dim)

Why BatchNorm is applied after each GCN layer:

1. Stable training: Normalizing the distribution of activations prevents vanishing/exploding gradients
2. Faster convergence: Allows a higher learning rate
3. Regularization: Implicit regularization helps prevent overfitting

BatchNorm works in GNNs much as it does in ordinary neural networks, but it matters even more because the irregular graph structure makes feature distributions vary widely across nodes.

Dropout: 0.4

self.dropout = Dropout(p=0.4)

I applied 40% dropout to prevent overfitting. Rationale:

• NELL's sparse features: Highly sparse inputs carry a risk of overfitting
• Class imbalance: Prevents overfitting to minority classes
• Prior work: Within the range (0.3-0.5) recommended in the GCN paper

Activation Function: ReLU

h = h.relu()

Why ReLU:

• Computational efficiency: A simple max(0, x) operation
• Mitigates vanishing gradients: The gradient is 1 in the positive region
• Sparse activation: Setting negative inputs to 0 encourages sparse representations

Data Split

Split Ratio

train_ratio, val_ratio, test_ratio = 0.6, 0.2, 0.2

Split Implementation

# Fix the seed for reproducibility
shuffled_indices = torch.randperm(num_nodes, generator=torch.Generator().manual_seed(42))

num_train = int(num_nodes * train_ratio)
num_val = int(num_nodes * val_ratio)

# Create masks
train_mask = torch.zeros(num_nodes, dtype=torch.bool)
val_mask = torch.zeros(num_nodes, dtype=torch.bool)
test_mask = torch.zeros(num_nodes, dtype=torch.bool)

train_mask[shuffled_indices[:num_train]] = True
val_mask[shuffled_indices[num_train:num_train + num_val]] = True
test_mask[shuffled_indices[num_train + num_val:]] = True

Transductive learning: When training a GNN, the features of all nodes and the graph structure are used, but labels are used only for training nodes. This is the typical semi-supervised learning setting, where unlabeled nodes still receive information through the graph structure.

PyTorch Geometric Data Object

from torch_geometric.data import Data

data = Data(
    x=x_dense,              # node features (65755, 61278)
    edge_index=edge_index,  # edge index (2, 251550)
    y=y,                    # node labels (65755,)
    train_mask=train_mask,
    val_mask=val_mask,
    test_mask=test_mask
).to(device)

PyTorch Geometric's Data object is a format that stores graph data efficiently and can be moved to the GPU. edge_index stores edges in COO (Coordinate) format, which is optimized for sparse matrix operations.

5. Training and Results

Training Setup

Loss Function

criterion = torch.nn.CrossEntropyLoss()

Since this is a multi-class classification problem, I used cross-entropy loss. Over 186 classes:

Here $\mathcal{V}_L$ is the set of labeled nodes, $y_{ic}$ is the one-hot encoding of the true label, and $\hat{y}_{ic}$ is the predicted probability.

Optimizer

optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

• Learning rate 0.01: Fairly high for the Adam optimizer, but stable when combined with BatchNorm
• Weight decay 5e-4: L2 regularization to prevent overfitting

Learning Rate Scheduler

scheduler = torch.optim.lr_scheduler.ReduceLROnPlateau(
    optimizer, mode='max', factor=0.5, patience=50
)

If validation accuracy does not improve for 50 epochs, the learning rate is halved. This allows:

1. Fast convergence early on
2. Fine adjustments near convergence

Early Stopping

early_stopping_patience = 50

If validation accuracy does not improve for 50 epochs, training stops. This prevents overfitting and selects the best model.

Training Loop

for epoch in range(1, 1001):
    # Training step
    model.train()
    optimizer.zero_grad()
    h, z = model(data.x, data.edge_index)
    loss = criterion(z[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()

    # Validation step
    model.eval()
    with torch.no_grad():
        _, logits = model(data.x, data.edge_index)
        val_pred = logits[data.val_mask].argmax(dim=1)
        val_acc = (val_pred == data.y[data.val_mask]).float().mean()

    # Early stopping check
    if val_acc > best_val_acc:
        best_val_acc = val_acc
        patience_counter = 0
    else:
        patience_counter += 1

    if patience_counter >= early_stopping_patience:
        print(f"Early stopping at epoch {epoch}")
        break

    scheduler.step(val_acc)

Training Logs

I recorded the following metrics during training:

• Training Loss: Loss on the training set
• Validation Accuracy: Accuracy on the validation set
• Learning Rate: The current learning rate

Training Results

Learning Curve Analysis

Training Loss (left)

• Initial loss: ~5.3 (corresponding to random prediction over 186 classes, -log(1/186) ≈ 5.22)
• Converged loss: ~0.08
• Convergence speed: Most of the loss reduction finishes within about 100 epochs

The loss drops sharply at first and then converges gradually, a typical pattern. After 50 epochs, the decrease becomes very gentle.

Validation Accuracy (right)

• Initial accuracy: ~42% (lower than the share of Class 0 - the model has not learned yet)
• Converged accuracy: ~98%
• Stabilizes at: About 150 epochs

Validation accuracy rises sharply at first, passes 90% around epoch 100, and then gradually climbs to 98%. After 150 epochs, it barely changes.

Training Statistics

Detailed Test Results

Overall Performance

model.eval()
with torch.no_grad():
    _, logits = model(data.x, data.edge_index)
    test_pred = logits[data.test_mask].argmax(dim=1)
    test_acc = (test_pred == data.y[data.test_mask]).float().mean()

print(f"Final Test Accuracy: {test_acc*100:.2f}%")

Final test accuracy: 97.86%

Of the 13,151 test nodes, 12,870 were classified correctly.

6. Results Analysis

Example Predictions

I randomly sampled 15 nodes from the test set and analyzed the predictions.

num_examples = 15
example_indices = random.sample(test_node_indices.tolist(), num_examples)

for node_idx in example_indices:
    true_id = data.y[node_idx].item()
    pred_id = all_predictions[node_idx].item()
    confidence = all_probabilities[node_idx, pred_id].item()
    status = "Correct" if pred_id == true_id else "Wrong"
    print(f"Node {node_idx}: True={true_id}, Pred={pred_id}, Conf={confidence:.4f}, {status}")

Example predictions:

Observations:

• All 15 samples were predicted correctly (100%)
• Every prediction had very high confidence, above 98%
• Class 0 predictions had especially high confidence (above 99.8%)
• Minority classes (Class 3, 8, 37) were also predicted correctly with high confidence

Per-Class Performance

I analyzed prediction accuracy for each class.

class_stats = []
for class_id in np.unique(test_true):
    mask = (test_true == class_id)
    if mask.sum() > 0:
        class_acc = (test_pred[mask] == class_id).sum() / mask.sum()
        class_stats.append((class_id, class_acc, mask.sum()))

Performance of the top 15 classes:

Grading criteria:

• Excellent: 95% or higher
• Good: 85% ~ 95%
• Fair: 70% ~ 85%
• Poor: Below 70%

Findings

Best-performing classes:

• Class 8: 100% accuracy (227 samples)
• Class 11: 100% accuracy (127 samples)
• Class 32: 100% accuracy (77 samples)

Worst-performing classes:

• Class 104: 0% accuracy (14 samples)
• Some very small classes perform poorly due to insufficient training data

Class Imbalance vs Performance

Interestingly, there is no simple correlation between class size and performance:

• Class 0 (the largest class): 99.9% accuracy
• Class 8 (medium size): 100% accuracy
• Class 37 (a small class): 77.6% accuracy

This suggests that, beyond class size, structural properties of the graph affect classification performance. Classes that are well connected in the graph and have a clear neighborhood structure are classified well even with few samples.

Confidence Analysis

I analyzed the distribution of the model's prediction confidence.

test_confidences = all_probabilities[data.test_mask].max(dim=1)[0].cpu().numpy()
high_conf = (test_confidences > 0.9).sum()
low_conf = (test_confidences < 0.5).sum()
avg_conf = test_confidences.mean()

Confidence statistics:

Average confidence: 0.974 (97.4%)

Most predictions (94.4%) have confidence above 90%. This indicates the model is making "confident" predictions.

Low-confidence predictions (1.9%) mostly involve:

• Nodes on class boundaries
• Nodes whose neighbors have mixed labels
• Nodes in very small classes

Confusion Analysis

I analyzed the class pairs most often confused.

confused_pairs = []
for true_label, pred_label in zip(test_true, test_pred):
    if true_label != pred_label:
        pair = (true_label, pred_label)
        confused_pairs.append(pair)

pair_counts = Counter(confused_pairs)
top_confused = pair_counts.most_common(5)

Most frequently confused class pairs:

Analysis:

• Most misclassifications go to Class 0 (the influence of the largest class)
• Confusion between semantically similar classes (e.g. 37 → 48)
• Overall, misclassifications are very rare (2-3 each)

Results Summary

7. Conclusions and Discussion

Summary of Results

In this project, I implemented a GCN-based node classification model for the NELL knowledge graph and achieved 97.86% test accuracy. The main results are:

1. Handling a large knowledge graph: Effectively processed a large graph with 65,755 nodes and 251,550 edges
2. Multi-class classification: Accurate classification across 186 semantic categories
3. Overcoming class imbalance: Classified minority classes, not just Class 0 (85.7%), with high accuracy
4. High confidence: 94.4% of predictions had confidence above 90%

Why Accuracy Was High Despite Class Imbalance

I analyzed why performance was high despite the extreme imbalance, with one of 186 classes (Class 0) making up 85.7%:

1. GNNs Use Structural Information

A GNN uses not only node features but also graph structure. Nodes of the same class tend to have similar neighborhood structures in the graph (homophily), and the GCN captures this information effectively.

The NELL graph's high clustering coefficient (0.1847) indicates that entities in the same semantic category are connected to each other. For example, if "Einstein," "physics," and "Nobel Prize" are connected, their class information propagates among them.

2. The Right Receptive Field with a 3-Layer GCN

A 3-layer GCN aggregates information from 3-hop neighbors. Since the NELL graph's average path length is about 4, 3 layers can reach most relevant nodes.

Receptive field analysis:

• Layer 1: Directly connected neighbors (3.83 on average)
• Layer 2: 2-hop neighbors (~15 on average)
• Layer 3: 3-hop neighbors (~60 on average)

3. Regularization from BatchNorm and Dropout

BatchNorm normalizes the activation distribution of each layer, enabling stable training while preserving differences in representation between classes. Dropout prevents overfitting to specific paths, so the model draws on a variety of neighbor information.

4. Properties of Cross-Entropy Loss

Cross-entropy loss learns a probability distribution over classes, so it pushes the model to assign high probability to the correct class even when uncertain. This helps learn the features of minority classes under class imbalance.

Why GCNs Work Well on Knowledge Graphs

Reasons the GCN is effective on knowledge graphs:

1. Capturing Semantic Similarity Through Relations

In a knowledge graph, edges represent semantic relations between entities. GCN message passing propagates information along these relations, so semantically related entities end up with similar representations.

2. Effective Compression of Sparse Features

While compressing NELL's 61,278-dimensional sparse features into a 128-dimensional dense representation, the GCN preserves semantically important information. Aggregating neighbor information reinforces common patterns and averages out noise.

3. Benefits of Semi-Supervised Learning

In the transductive setting of GNN training, unlabeled nodes indirectly receive label information through the graph structure. This helps achieve high performance with little labeled data.

Future Improvements

1. Trying Other GNN Architectures

• GAT (Graph Attention Network): Learns per-neighbor weights to focus on important relations
• GraphSAGE: Sampling-based, scales to larger graphs
• GIN (Graph Isomorphism Network): An architecture for maximum expressive power

2. Techniques for Class Imbalance

• Focal Loss: Gives more weight to hard samples
• Class-balanced Sampling: Oversamples minority classes
• SMOTE for Graphs: Oversampling suited to graphs

3. Using Relation Types

The current model uses only whether an edge exists. NELL has many relation types (e.g. "is_a", "located_in", "works_for"), and using them could improve performance.

• R-GCN (Relational GCN): A weight matrix per relation type
• CompGCN: Combines relation embeddings with node embeddings

4. Graph Augmentation

• DropEdge: Randomly removes edges during training to prevent overfitting
• GraphMix: Mixup augmentation for graphs

5. Better Interpretability

• GNNExplainer: Identifies the subgraphs important to a prediction
• Attention visualization: Analyzes relation importance when using GAT

Conclusion

This project confirmed that graph neural networks (GNNs) are highly effective for node classification on knowledge graphs. A GCN can use the structural information of a graph to predict the semantic categories of nodes accurately, and it performs robustly despite challenges such as class imbalance and sparse features.

The 97.86% test accuracy is the result of a good fit between the expressive power of the GCN and the structural properties of the NELL dataset. The high clustering of same-class nodes, a moderate average path length, and a meaningful hub structure worked in synergy with the GCN's message passing mechanism.

Going forward, I expect that experimenting with more advanced architectures, such as R-GCN, which uses relation types, or GAT, which applies an attention mechanism, will bring better performance and interpretability.