Graph Neural Networks: From Fundamentals to NP-Hard Optimization

Understanding why GNNs work — and then using them to attack the Maximum Clique problem, an NP-hard task, with a learned GNN + Replicator Dynamics hybrid.

---

What's in here

This repo covers two connected pieces of work on graph learning:

1. GNN Fundamentals — message passing, the over-smoothing problem, and a controlled study of when graph structure actually helps (MLP vs GCN).
2. Maximum Clique — solving an NP-hard combinatorial problem four ways, culminating in a GNN that learns to initialise a continuous solver.

The thread connecting them: graph structure is only useful when it carries signal, and learning to exploit it can beat classical methods on hard problems.

---

Part 1 — When does graph structure help?

The core question: node features alone (MLP) vs features + graph structure (GCN). The answer depends entirely on homophily — whether connected nodes tend to share a label.

I built two synthetic datasets with identical features but opposite structure, and trained both models across 10 runs each.

High homophily — structure carries the signal

Model	Test Accuracy
MLP (features only)	0.4895 ± 0.015
GCN (features + graph)	1.0000 ± 0.000

When neighbours share a class, the GCN reaches perfect classification while the MLP is stuck near random. The t-SNE tells the whole story:

MLP embeddings	GCN embeddings
Classes fully entangled	Five clean, separated clusters

Low homophily — structure is noise

Model	Test Accuracy
MLP (features only)	0.4950 ± 0.026
GCN (features + graph)	0.5297 ± 0.034

Same features, but now the edges connect nodes at random. The GCN's advantage almost vanishes — aggregating over meaningless neighbours adds nothing.

MLP embeddings	GCN embeddings

Takeaway: the GCN isn't magic. It's a bet that neighbours are informative. When that holds, it wins by a landslide (0.53 → 1.00); when it doesn't, it's barely better than ignoring the graph.

Training dynamics

The curves also reveal the MLP overfitting on the homophilic set — climbing on train while validation stalls — whereas the GCN generalises immediately.

High homophily	Low homophily

Real benchmarks

On standard citation networks (2-layer GCN):

Dataset	Test Accuracy
Cora	0.8160
Citeseer	0.6970

The over-smoothing problem

A key limitation studied here: stacking too many message-passing layers makes all node representations converge to the same value. After enough layers, h_A ≈ h_B ≈ [0.5, 0.5] for every node — all discriminative information is lost. This is why GNNs are typically shallow (2–3 layers), and why the models above use exactly 2.

---

Part 2 — Maximum Clique: an NP-hard problem, four ways

A clique is a set of vertices where every pair is connected. Finding the maximum clique is NP-hard, with applications from social network analysis to bioinformatics. I implemented four progressively smarter approaches and benchmarked them on the IMDB-BINARY and COLLAB datasets.

1. Brute force — the wall

Checking every subset is O(2^n). Empirically: on IMDB-BINARY (small graphs), only 15 of the first 20 graphs finished under a 25-node cap. On COLLAB (32–209 nodes, avg 58), not a single graph was feasible — the smallest already implies 2³² ≈ 4 billion subsets. This is the wall that motivates everything else.

2. Motzkin-Straus — discrete → continuous

The Motzkin-Straus theorem reframes the discrete problem as continuous optimisation over the simplex: maximise f(x) = xᵀAx. But naive f admits spurious solutions — points that maximise the objective without being cliques.

I verified this on the "cherry graph": the spurious solution x=[0.25, 0.25, 0.5] scores f=0.5000, tying the true clique. Adding regularisation f̂(x) = xᵀ(A + 0.5I)x breaks the tie — the true clique now scores 0.7500 vs the spurious 0.6875.

3. Replicator Dynamics — an evolutionary solver

Replicator Dynamics, from evolutionary game theory, iteratively maximises the regularised objective while staying on the simplex. Nodes in the maximum clique "survive" (mass ≈ 1/k); the rest die out.

RD on the cherry graph: the objective climbs monotonically, and the population concentrates on the true clique.

Benchmarked across both datasets:

COLLAB graphs have much larger cliques than IMDB-BINARY, and compute time scales with graph size — yet RD stays feasible where brute force is impossible.

4. GNN + Replicator Dynamics — learning a better start

RD always starts from the uniform barycenter, ignoring graph structure. The idea: train a GNN to predict a better starting point. The GNN outputs a simplex point, RD refines it, and gradients flow through a few RD iterations during training so the GNN learns what initialisations RD can improve.

Ablation: the more RD iterations during training, the fewer RD iterations the model needs at test time to reach the same clique size. The GNN learns to do RD's work up front.

---

Tech stack

Core	Python · PyTorch · PyTorch Geometric
Graphs	NetworkX · TU Dortmund datasets (IMDB-BINARY, COLLAB) · Planetoid (Cora, Citeseer)
Analysis	scikit-learn (t-SNE) · matplotlib · NumPy

---

Structure

notebooks/
  Practica_0.ipynb   → GNN fundamentals: message passing, MLP vs GCN, over-smoothing
  Practica_1.ipynb   → Maximum Clique: brute force → Motzkin-Straus → RD → GNN+RD
assets/              → figures

Running it

pip install -r requirements.txt
jupyter lab notebooks/

---

Key references

• Kipf & Welling (2017). Semi-Supervised Classification with Graph Convolutional Networks.
• Motzkin & Straus (1965). Maxima for graphs and a new proof of a theorem of Turán.
• Pelillo (1999). Replicator Equations, Maximal Cliques, and Graph Isomorphism. Neural Computation.

---

Academic work for Intelligent Agents, BSc in Artificial Intelligence Engineering, Universidad de Alicante (2025/26).

Dennis García Solera — GitHub · LinkedIn