Source-linked AI summary
Clustering attributed graphs: models, measures and methods
Cecile Bothorel, Juan David Cruz, Matteo Magnani, Barbora Micenkova
TL;DR
Attributed graph clustering addresses the limited representation provided by structure-only graphs for social systems containing node and edge attributes. This survey organizes recent methods for clustering such graphs, compares their concepts, and discusses evaluation, applicability, and open problems. It synthesizes approaches spanning edge- and node-attributed graphs, including methods based on attribute weighting, latent-variable inference, and subspace selection.
Problem
Structure-only graphs provide a partial representation of social systems because actor features and multiple relationship types can be relevant to community identification.
Method
The article surveys recent attributed graph clustering research in a uniform framework, covering edge- and node-attributed methods plus evaluation and applicability issues.
Results
The survey characterizes the main clustering methods, highlights their conceptual differences, and identifies evaluation challenges and open problems.
Takeaways & Limitations
Attributed graph clustering brings structural graph analysis and compositional data clustering together as a distinct research area studied across disciplines.
Takeaways & Limitations
Single-layer approaches to weighted edge-attributed graphs require domain knowledge to merge weights with different semantics and do not fully exploit edge-type information.
Abstract
from arXiv · showhide
Clustering a graph, i.e., assigning its nodes to groups, is an important operation whose best known application is the discovery of communities in social networks. Graph clustering and community detection have traditionally focused on graphs without attributes, with the notable exception of edge weights. However, these models only provide a partial representation of real social systems, that are thus often described using node attributes, representing features of the actors, and edge attributes, representing different kinds of relationships among them. We refer to these models as attributed graphs. Consequently, existing graph clustering methods have been recently extended to deal with node and edge attributes. This article is a literature survey on this topic, organizing and presenting recent research results in a uniform way, characterizing the main existing clustering methods and highlighting their conceptual differences. We also cover the important topic of clustering evaluation and identify current open problems.
1 Introduction
Social graphs capture relationships but can miss compositional and multiplex dimensions of social systems. This survey examines attributed graph clustering as a recent convergence of graph clustering and multidimensional data clustering, organizing methods and practical issues across disciplines.
- Motivation: Graphs model social relationships and support measuring structural properties and identifying communities through clustering.Nodes and relationships can represent individuals and their ties, while centrality, prestige, and community structure are derived from the graph.
- Motivation: Simple nodes and edges may lose information about actors, relationship contexts, and multiple interaction types.These correspond to compositional and multiplex dimensions that complement the structural social graph.
- Motivation: Attributed graphs connect actor attributes and relationship structure, reflecting observed dependencies such as social influence and homophily.Linked people may become similar through interaction, while people with similar attributes may be more likely to form relationships.
- Current trends: Artificial graph generators support algorithm experiments, what-if scenarios, forecasts, and sampling when real graphs are difficult or impractical to analyze.Recent generators extend structure-focused models by incorporating affiliation or social-attribute information.
- Survey scope: The survey addresses a recent research gap by bringing together attributed graph clustering work largely absent from graph-clustering and tabular-clustering surveys.It reviews edge-attributed and node-attributed methods, then discusses evaluation, applicability, terminology, and open problems.
2 Clustering edge-attributed graphs
Edge-attributed graphs represent multiple relationship types through alternative multigraph or multilayer models, leading to distinct clustering strategies. The section contrasts flattening, multilayer quality measures, exclusive-connection methods, and the unresolved possibility that clusters emerge only from selected layers.
- Models: Edge-attributed graphs encode relationship types either as labeled multigraph edges or as named layers containing separate graphs.The two representations can be equivalent for a given example but emphasize different aspects of the data.
- Single-layer approaches: Flattening reconstructs a single weighted graph, allowing classical weighted-graph clustering but potentially discarding the differing importance of edge types.A basic weight can count the number of layers in which two nodes are directly connected; flattening is unsuitable when different edge types have substantially different community structures.
- Multilayer approaches: Multilayer methods extend graph-quality measures such as modularity and quasi-cliques to clusters spanning multiple layers, where nodes may belong to different clusters by edge type.Extended modularity can be optimized with existing modularity heuristics, while quasi-clique approaches assess dense relations across the multilayer structure.
- Clique-finding methods: Adding edge types can weaken quasi-clique support for groups that are strongly connected only in selected relationships, even when those groups are meaningful.A group sharing school and basketball-team ties may be important despite lacking cohesion in other relationship types.
- Emerging clusters: A still-unverified hypothesis is that clusters may appear for a specific combination of layers and disappear when additional layers are included.This shifts attention from choosing the best cut alone toward data modeling, preprocessing, and feature selection.
3 Clustering node-attributed graphs
Node-attributed graph clustering groups nodes using both graph position and node characteristics, with models ranging from attribute vectors to heterogeneous graph representations. Reviewed methods combine these dimensions through weighted similarities, statistical inference, or selected attribute subspaces, while evaluation and parameterization remain practical concerns.
- Node-attributed clustering detects groups sharing characteristics while considering both node attributes and graph position.
- Most methods use partitioning and homophily, whereas subspace clustering can generate overlapping groups from different attribute combinations.
- The common model represents an attributed graph as G = (V,E,F), with each node associated with an attribute vector F(v).Alternative representations include adding attribute tuples to nodes or introducing additional node types in a heterogeneous graph.
- Weight-modification methods reduce the node-attributed graph to a weighted graph whose edge weights encode attribute similarity before applying weighted-graph clustering.The resulting clustering depends on the similarity function and on how the modified edge weights are updated.
- Spectral clustering appears robust to irrelevant attributes and graphs with low linkage in experiments on artificial datasets.
- High subspace-clustering complexity and many required parameters can reduce practical usability, while attributed-graph cluster evaluation remains under study.The cited parameters include minimum cluster size, dimensionality, density, and redundancy.
4 Practical aspects
Evaluating attributed-graph clusterings requires comparing structures against ground truth when available and assessing intrinsic, structural, and attribute-based qualities otherwise. Because attributes introduce multiple objectives, practical evaluation uses several complementary measures and faces scalability and information-integration limits.
- Evaluation motivation: Clustering evaluation supports algorithm selection, stopping conditions, greedy decisions, and comparison of alternative clusterings, but defining a good cluster remains an open problem.Open issues include interpretability, benchmark datasets, and quality functions that explain evaluations.
- External evaluation: With ground truth, external evaluation compares the found partition with externally provided class information using pair-counting or information-theoretic measures.Pair-counting measures require disjoint partitions and equal element weights.
- External evaluation: Mutual-information measures quantify information shared by two partitions using entropy and joint entropy, with normalized variants constrained to [−1,1] or [0,1].The measures use a contingency matrix whose entries summarize agreements between partitions.
- Internal evaluation: Without ground truth, internal measures evaluate intrinsic clustering characteristics, including density, sparsity, coverage, conductance, and performance.Gaertler’s general index combines density and sparsity through a normalization function based on the maximum possible combined value.
- Attribute-aware evaluation: Node-attributed evaluation can target attribute homogeneity by assigning documents topic vectors and minimizing within-community entropy.The objective is to increase partition homogeneity.
- Practical limitations: Hand-defined group labels are acceptable for small networks but become prohibitive for large networks with high-dimensional feature spaces.This limitation concerns evaluation approaches that compare algorithmic assignments with an expected partition.
- Practical limitations: Flattening edge types enables scalable clustering with existing algorithms but can discard layer-specific information and requires domain knowledge to merge semantically different weights.The limitation is especially clear when edge weights represent incomparable quantities such as message counts and friendship duration.
5 Open problems and discussion
Attributed-graph clustering remains active because combining structure, node attributes, and multiple edge types creates additional objectives, parameters, views, and evolutionary configurations. Open problems span extensions of ordinary graph clustering and challenges specific to integrating these information sources.
- Scope: Open problems include issues inherited from graph clustering and problems created specifically by combining network structure with attributes.The survey organizes these challenges into two corresponding categories.
- Partitioning and overlap: Most methods find disjoint communities, but real individuals may belong to multiple communities, motivating overlapping approaches and renewed debate for edge-attributed graphs.When edge attributes represent different networks, overlap may correspond to participation across layers.
- Evaluation and interpretation: Quality and interpretation of attributed-graph communities remain open questions even though node attributes can make resulting communities easier to interpret.Interpretability gains therefore do not resolve evaluation concerns.
- Multiple views: Attribute-value combinations can grow exponentially during clustering, while edge-labeled graphs also create many views from combinations of edge values.The survey identifies both issues as major open problems requiring further research.
- Usability: Tools for combining precomputed partitions and visualizing results require advances in usability, simplicity, and efficiency to support user feedback.These needs apply in attributed-graph settings as well as in non-attributed graphs.
- Dynamic attributed graphs: Attributed-community evolution may require revising create, merge, and split concepts because communities can span multiple interconnected graphs.Early work has focused on static communities as a preliminary step toward studying evolution.
- Generative models: Attributed network-creation models must explain dense connections, attribute-value distributions, and how relationships develop across graph layers or edge types.The question extends network-creation research beyond explaining modular structure alone.
- Complexity: Adding attributes increases the number of evaluation views, parameters, and system configurations, making algorithmic applicability dependent on these additional degrees of freedom.The survey identifies increasing complexity at several levels rather than a single computational obstacle.