Neural Gas: Learning the Shape of Data Without a Grid

A quantiser that competes instead of averages

Neural gas, introduced by Thomas Martinetz and Klaus Schulten in 1991, is an unsupervised learning algorithm that places a set of reference vectors — nodes — inside a cloud of data so that each node ends up representing the data points nearest to it. That goal is the same as k-means clustering, but the way it gets there is different in one crucial respect: instead of only updating the single closest node on every training step, neural gas updates all of them, with the amount of movement scaled by how close each node's current rank is to the winner.

The rule: rank, don't just pick a winner

For each training sample x, every node is ranked by distance to x — rank 0 is the closest (the "winner"), rank 1 the second closest, and so on. Every node is then pulled toward x by an amount that decays exponentially with its rank:

for each input x:
  rank all nodes i by distance to x   → k_i = 0, 1, 2, … (0 = closest)
  for each node i:
    w_i += ε(t) · exp(-k_i / λ(t)) · (x − w_i)

  ε(t), λ(t)   decay over training time from large (coarse, global
               ordering) to small (fine, local refinement)

Early in training, λ is large, so even distant nodes get a meaningful nudge toward every sample — this quickly spreads all nodes across the occupied region of the input space and avoids the classic k-means failure mode where a node initialised far from any data simply never gets picked and stays "dead." As λ shrinks toward zero, the rule converges to ordinary winner-take-all competitive learning, and the nodes settle into a fine-grained approximation of the data density: dense regions attract many nodes, sparse regions attract few.

Competitive Hebbian learning: building the graph for free

The base algorithm places nodes but does not connect them. A companion rule, competitive Hebbian learning, adds an edge between the two closest nodes to every sample as it arrives, and removes edges that have not been refreshed for a while. Because an edge only forms between the winner and the runner-up for some actual data point, the resulting graph is provably a very close approximation to the data's induced Delaunay triangulation restricted to the region the data occupies — the network essentially discovers its own topology instead of having one imposed on it.

Versus k-means and self-organising maps

A self-organising map (SOM) also has a neighbourhood-based update rule, but the neighbourhood is defined by fixed positions on a predetermined 1D or 2D grid — two nodes are neighbours if they sit next to each other on that grid, whether or not the data actually connects them that way. Neural gas instead defines neighbourhood purely by distance ranking in the data space itself, with no predetermined grid to warp or tear. That makes it far more forgiving of data whose intrinsic shape does not match a flat grid — a spiral, a branching manifold, disconnected clusters — and empirical studies from the original paper onward consistently show neural gas reaching lower quantisation error than both k-means and SOMs on the same data and node count, at the cost of one extra parameter to anneal.

Growing neural gas: letting the network size itself

Bernd Fritzke's 1995 extension, growing neural gas, starts with just two nodes and periodically inserts a new one next to the node that has accumulated the most local error, splitting overloaded regions automatically. Combined with competitive Hebbian edges and an ageing rule that prunes stale connections, it can track a moving or reshaping data distribution live and is used for online clustering, topology-preserving mesh generation from 3D point clouds, and robot map building, where the number of clusters needed is not known in advance.

Frequently asked questions

Try it live

Everything above runs in your browser — open Neural Gas and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.