Source-linked AI summary
Attributed Graph Clustering: A Deep Attentional Embedding Approach
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Chengqi Zhang
TL;DR
Existing graph-clustering pipelines commonly learn embeddings and cluster in separate steps, leaving the embedding not specifically directed toward clustering. DAEGC jointly learns an attentional attributed-graph embedding and self-training clusters, and experiments report superiority over state-of-the-art methods.
Problem
Two-step graph-clustering methods may produce embeddings that do not fit clustering and provide no mutual benefit between embedding learning and clustering.
Method
DAEGC jointly optimizes a graph attentional autoencoder and self-training clustering module using structure, node content, and confident assignments as soft labels.
Results
DAEGC outperforms state-of-the-art graph clustering methods across most evaluation metrics, including relative gains of 18.97% in accuracy and 29.49% in NMI against VGAE on Cora.
Takeaways & Limitations
The unified framework simultaneously learns graph embeddings specialized for clustering and produces clustering results during training.
Takeaways & Limitations
Earlier compared methods may capture only parts of network information or shallow content–structure relationships and operate directly on sparse original graphs.
Abstract
from arXiv · showhide
Graph clustering is a fundamental task which discovers communities or groups in networks. Recent studies have mostly focused on developing deep learning approaches to learn a compact graph embedding, upon which classic clustering methods like k-means or spectral clustering algorithms are applied. These two-step frameworks are difficult to manipulate and usually lead to suboptimal performance, mainly because the graph embedding is not goal-directed, i.e., designed for the specific clustering task. In this paper, we propose a goal-directed deep learning approach, Deep Attentional Embedded Graph Clustering (DAEGC for short). Our method focuses on attributed graphs to sufficiently explore the two sides of information in graphs. By employing an attention network to capture the importance of the neighboring nodes to a target node, our DAEGC algorithm encodes the topological structure and node content in a graph to a compact representation, on which an inner product decoder is trained to reconstruct the graph structure. Furthermore, soft labels from the graph embedding itself are generated to supervise a self-training graph clustering process, which iteratively refines the clustering results. The self-training process is jointly learned and optimized with the graph embedding in a unified framework, to mutually benefit both components. Experimental results compared with state-of-the-art algorithms demonstrate the superiority of our method.
1 Introduction
Graph clustering on attributed graphs must jointly capture structure and node content, but prevailing embedding-then-cluster pipelines are not goal-directed. DAEGC addresses this gap by jointly learning an attentional graph embedding and clustering with self-training.
- Graph clustering partitions nodes into disjoint groups while seeking structural proximity and similar attribute values within each group.
- Deep embedding methods learn compact representations from graph content and structure, then apply clustering algorithms such as k-means.
- Two-step methods may learn embeddings that do not fit the subsequent clustering task, leaving embedding learning and clustering without mutual benefit.
- DAEGC uses a graph attentional autoencoder to integrate graph structure and node content into latent representations.
- DAEGC jointly optimizes embedding learning and clustering through self-training, using confident clustering assignments as soft labels.
- The paper reports that DAEGC outperforms state-of-the-art graph clustering methods.
2 Related Work
Prior graph clustering methods either incompletely model graph information or learn embeddings separately from clustering. Deep clustering frameworks provide specialized clustering objectives, but their graph-data use remains limited.
- Early graph clustering methods used shallow approaches such as centrality indices and belief propagation for community detection.
- These methods capture only parts of network information or shallow content–structure relationships and operate directly on sparse original graphs.
- Many deep graph clustering algorithms use autoencoders to learn deep representations, but they remain two-step methods unlike the unified approach presented here.
- Deep Embedded Clustering pre-trains a stacked denoising autoencoder and fine-tunes its encoder with a Kullback–Leibler divergence clustering loss.
- Deep clustering frameworks were designed mainly for flat-table data, leaving goal-directed clustering for graph data as an open problem.
3 Problem Definition and Overall Framework
The paper formulates clustering for attributed graphs using both adjacency structure and node attributes. Its framework combines a graph attentional autoencoder with a self-training clustering module in one optimization process.
- An attributed graph is represented as G = (V, E, X), with nodes V, edges E, adjacency matrix A, and attribute vectors X.
- Graph clustering seeks k disjoint groups whose nodes are generally close structurally and similar in attribute values.
- The overall framework consists of a graph attentional autoencoder and a self-training clustering module.
- The autoencoder uses attribute values and graph structure to learn a latent embedding by minimizing reconstruction loss.
- The self-training module clusters the learned representation and feeds current clustering results back to manipulate the latent representation during unified learning.
4 Proposed Method
DAEGC jointly learns an attributed-graph embedding and clustering assignment by combining graph attention, structure reconstruction, and self-training. The unified objective uses clustering feedback to specialize the embedding while preserving graph reconstruction.
- Graph Attentional Autoencoder: DAEGC encodes graph structure and node content into latent representations with a graph attentional autoencoder.The encoder attends over neighbors, while stacked layers build a deep embedding architecture.
- Graph Attentional Encoder: Attention coefficients measure neighbor importance using both attribute similarity and topological distance.The encoder extends neighborhood modeling beyond first-order neighbors through a t-order proximity matrix M.
- Graph Reconstruction: An inner product decoder reconstructs the graph structure from embeddings, minimizing reconstruction error between A and A-hat.The decoder predicts links through the reconstructed structure matrix.
- Self-training Clustering: Self-training forms soft clustering assignments from node embeddings and uses confident assignments as soft labels for embedding learning.The target distribution emphasizes high-probability assignments and guides the current distribution Q toward P.
- Self-training Clustering: The model is initialized with one k-means clustering, then jointly updates cluster centers and embeddings using stochastic gradient descent.The target distribution and clustering loss are recalculated during training, while P is updated every 5 iterations to reduce instability.
- Joint Optimization: The total objective combines reconstruction and clustering losses as L = Lr + γLc, enabling unified embedding and clustering optimization.The final clustering labels can be obtained directly from the optimized soft assignment distribution Q.
5 Experiments
Experiments evaluate DAEGC against ten graph-clustering algorithms on three citation networks, examining benchmark performance, embedding dimension, and training visualization. DAEGC generally performs best, while combining graph structure and node content supports stronger clustering.
- Experimental setup: Experiments compare DAEGC with ten algorithms spanning attribute-only, structure-only, combined-information, and deep representation-learning approaches.The evaluation uses three standard citation networks, whose publications are categorized by research sub-fields.
- Evaluation metrics: The evaluation uses Accuracy, NMI, F-score, and ARI, where higher values indicate better clustering results.Baseline parameters are selected following the original papers’ procedures.
- Experiment results: DAEGC clearly outperforms the baselines across most evaluation metrics on the three benchmark datasets.Tables 2, 3, and 4 summarize the results, with bold values marking the best performance.
- Methods using both structure and content: Methods using both graph structure and node content generally perform better than methods using only one information source.On Cora, TADW, GAE, VGAE, and DAEGC outperform all baselines using one side of the information.
- Experiment results: 18.97% accuracy and 29.49% NMI relative increases are reported for DAEGC against VGAE on Cora.The paper states that the increase is even greater on Citeseer and attributes the gains to integrating content and structure with attention and self-training clustering.
- Parameter study: Clustering performance rises from a 4-neuron to a 16-neuron embedding, then fluctuates as the embedding grows to 1024 neurons while ACC and NMI remain generally good.The parameter study varies embedding dimensions from 4 to 1024 neurons.
- Network visualization: During Cora training, self-training progressively reduces embedding overlap and gathers node groups more clearly after the graph attentional autoencoder produces an initially meaningful embedding.The visualization applies t-SNE to learned embeddings during training.
6 Conclusion
DAEGC jointly learns graph embeddings and clustering results in an unsupervised unified framework, integrating graph structure and node content for clustering.
- DAEGC jointly performs graph clustering and graph embedding learning in a unified unsupervised framework.
- The learned graph embedding integrates graph structure and node content and is specialized for clustering tasks.
- A self-training clustering component generates soft labels from confident assignments to supervise embedding updates.
- Clustering and autoencoder reconstruction losses are jointly optimized to produce both embeddings and clustering results.
- Experiments against various state-of-the-art algorithms validate DAEGC’s graph clustering performance.