AI Glossary / Graphs and symbolic AI / Intermediate

Graph clustering

Definition

Graph clustering groups data points represented as nodes of a graph using the relationships encoded by its edges. In a similarity graph, strongly related points are often intended to fall into the same group, while weaker connections separate groups. The precise meaning of a good cluster depends on the graph construction and the clustering objective.

What it means

Instead of looking only at isolated feature vectors, graph clustering uses a network of pairwise relationships. Edges may be observed directly or constructed from a similarity measure, and weights can express the strength of those relationships.
There is no single definition of the correct partition for every graph. Some methods favor dense internal connections, some optimize cut-based criteria, and others use probabilistic models. Community detection and graph clustering overlap in many applications, but the intended interpretation should be stated. This entry follows the supplied dictionary's node-clustering meaning, rather than clustering a collection of whole graphs.

How it works

Construct or select the graph, define edge meanings and weights, and choose a clustering criterion. The algorithm then groups nodes according to that criterion, possibly requiring a chosen number of groups or another resolution setting.
Spectral clustering is one approach: use a graph Laplacian to obtain a numerical representation from selected eigenvectors, then cluster that representation. Other approaches work more directly with graph structure. Preprocessing choices such as which neighbors become edges can substantially affect the result. An output should therefore be interpreted together with the graph-generation rule, not as an independent discovery of indisputable categories.

Three practical examples

• A document-analysis experiment connects similar documents and groups them to support exploratory browsing.
• A collaboration-network study identifies densely connected groups while checking whether the observed links reflect the activity of interest.
• An image-processing lesson represents pixels or regions as nodes and uses weighted relationships to explore segmentation.

Think of it this way

Think of arranging people into discussion groups by looking at who has many connections with whom. The analogy illustrates relational grouping. Its limitation is that a mathematical cluster is defined by a chosen objective, and social or semantic categories may not align with connection density or form cleanly separated groups.

Worked example

Consider six nodes forming two triangles: A-B-C-A and D-E-F-D. Add one bridge edge C-D. Give every edge weight 1. A natural two-group partition is {A, B, C} and {D, E, F}. It cuts only C-D, so its cut weight is 1.
Each group's volume, defined here as the sum of its nodes' degrees in the full graph, is 7: the first triangle has degrees 2, 2, and 3, and the second has 3, 2, and 2. Its normalized-cut score is therefore 1/7 + 1/7 = 2/7, about 0.286.
Compare the partition {A} and {B, C, D, E, F}. It cuts two edges. The volumes are 2 and 12, giving 2/2 + 2/12 = 7/6, about 1.167. Under this specific lower-is-better normalized-cut criterion, the two-triangle partition is better than the singleton split. The comparison illustrates one objective; it does not prove that every clustering method must return the same groups.

Illustrative case study

In a fictional archive project, the Hazel team groups documents using a similarity graph. Its first graph connects every pair sharing a common generic word, producing links that obscure topic structure. The team revises the similarity representation and compares the resulting clusters with representative documents.
It records how the groups change when the neighbor threshold changes and avoids naming every cluster before inspecting its contents. This invented case illustrates sensitivity to graph construction. It does not claim that any particular threshold creates the true or most useful taxonomy.

Common misconceptions and mistakes

Graph clustering is not the same as a graph's clustering coefficient, which measures local triangle-related structure under a specified definition. It is also different from supervised node classification, where labeled examples define a prediction task.
Do not assume that a cluster is a causal or socially meaningful group. Sparse observations, edge thresholds, and resolution choices can alter the partition. Minimizing raw cut weight alone may favor an unhelpful tiny group, which is one reason balanced or normalized criteria are used. Those criteria introduce their own preferences rather than removing all modeling judgment.

Business use

The concept is useful for exploration when relationships carry information beyond individual records. Clusters can organize navigation, suggest candidate segments, or reveal areas for closer review. Their usefulness should be assessed against the intended task rather than only a single internal score.
Document graph construction, edge weights, the clustering method, and parameter settings. Inspect isolated nodes and unstable memberships. If clusters will influence decisions about people or services, examine what the relationships actually measure and avoid treating an exploratory partition as a complete description of the individuals involved.

People also ask

Must graph clustering know the number of groups in advance?

Some methods require it; others determine groups through different criteria or resolution settings.

Is it identical to finding connected components?

No. A connected graph can contain several useful clusters linked by a few edges.

Can two methods disagree?

Yes. Different objectives and assumptions can produce different partitions of the same graph.

Check your understanding

Why are the two triangles in the worked example not separate connected components?

Answer: Edge C-D connects them, so all six nodes are in one component. A clustering method can still separate them because it evaluates internal and cross-group connections rather than requiring complete disconnection.

Related terms

• Similarity graph
• Spectral clustering
• Normalized cuts
• Edge weight
• community detection
• graph Laplacian
• normalized cut
• connected component
• clustering coefficient

Learn next

Learn next about similarity-graph construction. Remove the bridge in the worked example, then increase its weight instead. Recalculate the stated cut and volume quantities, and explain why the graph's construction can change which partition an objective favors.

• Similarity graph

More in Graphs and symbolic AI

• Gomory-Hu Tree - A Gomory-Hu tree is a weighted tree that compactly represents the minimum cut values between every pair of vertices in an undirected capacitated graph.
• Grammar - A grammar is a formal description of how valid expressions can be structured in a language.
• Graph - A graph is a mathematical structure made of vertices, also called nodes, and edges that represent relationships between them.
• Graph coloring - Graph coloring assigns labels, traditionally called colors, to graph elements under specified compatibility rules.
• Graph Convolutional Network - A Graph Convolutional Network, or GCN, is a neural-network architecture that learns representations using a graph's connections together with features...
• Graph Convolutional Policy Network - Graph Convolutional Policy Network, or GCPN, is a model introduced for goal-directed graph generation using reinforcement learning.

Sources

Aalto Dictionary of Machine Learning, graph clustering and spectral clustering entries: https://aaltodictionaryofml.github.io/ADictML_Main.pdf Scikit-learn official SpectralClustering documentation: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html

Previous: Graph Next: Graph Coarsening Algorithm