Source-linked AI summary
Attributed Graph Clustering via Adaptive Graph Convolution
Xiaotong Zhang, Han Liu, Qimai Li, Xiao-Ming Wu
TL;DR
Attributed graph clustering lacks clear guidance for using graph convolution across diverse graphs, while existing methods mainly use fixed, low-order neighbourhood aggregation. AGC uses high-order graph convolution with adaptive order selection, and experiments show competitive or superior performance across benchmark datasets.
Problem
Existing graph convolution methods use fixed, low-order neighbourhood aggregation, limiting global structure capture and ignoring graph diversity.
Method
AGC applies k-order low-pass graph convolution to smooth node features, selects k adaptively, and then performs spectral clustering.
Results
AGC consistently outperforms existing attributed graph clustering methods and exceeds MGAE on Cora, Citeseer, and Pubmed while remaining comparable on Wiki.
Takeaways & Limitations
Adaptive order selection lets AGC use long-range information while accommodating differences between dense and sparse networks.
Abstract
from arXiv · showhide
Attributed graph clustering is challenging as it requires joint modelling of graph structures and node attributes. Recent progress on graph convolutional networks has proved that graph convolution is effective in combining structural and content information, and several recent methods based on it have achieved promising clustering performance on some real attributed networks. However, there is limited understanding of how graph convolution affects clustering performance and how to properly use it to optimize performance for different graphs. Existing methods essentially use graph convolution of a fixed and low order that only takes into account neighbours within a few hops of each node, which underutilizes node relations and ignores the diversity of graphs. In this paper, we propose an adaptive graph convolution method for attributed graph clustering that exploits high-order graph convolution to capture global cluster structure and adaptively selects the appropriate order for different graphs. We establish the validity of our method by theoretical analysis and extensive experiments on benchmark datasets. Empirical results show that our method compares favourably with state-of-the-art methods.
1 Introduction
Attributed graph clustering must jointly model graph structure and node attributes, but existing graph convolution methods use shallow, fixed-order models. AGC instead supports high-order convolution and adaptive order selection to capture broader cluster structure.
- Attributed graph clustering combines node connectivity and feature attributes to analyze communities in real-world networks.Applications include social, citation, and protein-protein interaction networks.
- Existing graph convolution methods achieve strong results on some attributed graph clustering tasks.Examples include GAE, MGAE, and ARGE.
- Most existing methods use shallow, fixed-order graph convolution that captures only nearby neighbours and may miss global cluster structures.ARGE and MGAE use two- and three-layer GCNs, respectively, while fixed models also ignore graph diversity.
- AGC applies k-order graph convolution to obtain smooth feature representations and adaptively selects k for different graphs.The method replaces deep layer stacking with high-order convolution and uses intra-cluster distance for selection.
- AGC combines high-order convolution with spectral clustering and performs competitively across four benchmark datasets.The benchmarks include three citation networks and one webpage network, with significant improvements in many cases.
2 Related Work
Attributed graph clustering extends structural clustering by jointly using node connectivity and features. Prior approaches model or factorize these information sources through generative, matrix-factorization, and spectral methods.
- Structural graph clustering methods use node connectivity without incorporating node features.Representative approaches include graph Laplacian eigenmaps and adjacency-matrix factorization.
- Attributed graph clustering jointly considers node connectivity and node features.Existing methods model their interaction with generative models or seek consistent partitions using factorization and spectral clustering.
3 The Proposed Method
The proposed method filters node features with adaptive, potentially high-order graph convolution before spectral clustering. It uses low-pass filtering to smooth features and selects the convolution order to balance global structure capture against over-smoothing.
- Graph Convolution: A graph filter performs convolution by multiplying graph signals by G, while a low-pass response suppresses high-frequency components and promotes smoothness.Each feature dimension is treated as a graph signal; lower-frequency basis signals correspond to smoother variation across nearby nodes.
- Graph Convolution: Applying the low-pass filter to X produces filtered features whose adjacent nodes have more similar values, making downstream clustering easier under the cluster assumption.
- k-Order Graph Convolution: k-order convolution repeatedly aggregates k-hop neighborhood information, enabling high-order filtering to capture long-distance relations and global graph structure.Its frequency response becomes more low-pass as k increases, producing smoother node features.
- Adaptive Order Selection: The convolution order cannot simply be maximized because excessive smoothing mixes features from different clusters and makes them indistinguishable.
- Clustering via Adaptive Graph Convolution: AGC selects an appropriate order using intra-cluster distance, then applies spectral clustering to the filtered feature matrix.The clustering stage forms a linear-kernel similarity matrix from the filtered features before spectral clustering.
4 Experiments
AGC is evaluated on four attributed networks against feature-only, structure-only, and attributed graph clustering baselines using Acc, NMI, and F1. It consistently performs strongly, with adaptive order selection supporting performance across networks of different density and scale.
- 4.1 Datasets: AGC is evaluated on Cora, Citeseer, Pubmed, and Wiki, covering three citation networks and one webpage network.Cora and Citeseer use binary word vectors, while Pubmed and Wiki use tf-idf weighted word vectors.
- 4.2 Baselines: The comparison includes feature-only, structure-only, and methods combining node features with graph structures.Baselines include k-means, spectral clustering variants, DeepWalk, DNGR, GAE, VGAE, ARGE, ARVGE, and MGAE.
- 4.4 Result Analysis: AGC consistently outperforms methods using only node features or graph structures by a very large margin.The authors attribute this to integrating complementary structural and feature information.
- 4.4 Result Analysis: AGC consistently outperforms existing attributed graph clustering methods by using automatically selected k-order convolution to aggregate information within k-hop neighborhoods.Existing GCN-based methods use fixed two- or three-hop neighborhoods, whereas AGC adapts k to the graph.
- 4.4 Result Analysis: AGC outperforms MGAE on Cora, Citeseer, and Pubmed but is comparable on Wiki, where three-hop aggregation may suffice because the network is denser.The performance gaps are wider on larger and sparser Citeseer and Pubmed, motivating adaptive order selection.
- 4.4 Result Analysis: When d intra(k) > 0, Acc, NMI, and F1 are best or near-best before performance declines, indicating that the criterion can avoid over-smoothing.Selected k values are 12, 55, 60, and 8 for Cora, Citeseer, Pubmed, and Wiki, respectively, close to the best values 12, 35, 60, and 6.
- 4.4 Result Analysis: AGC has small standard deviations across datasets and is faster than neural GCN-based baselines on three of four datasets.It is slightly slower than GAE, VGAE, ARGE, and ARVGE on Citeseer but more than twice faster on Cora, Pubmed, and Wiki.
5 Conclusion
The paper concludes that AGC combines high-order graph convolution with adaptive order selection for attributed graph clustering. This design captures global cluster structures and achieves competitive performance across different graphs.
- 5 Conclusion: AGC aggregates long-range data information with k-order graph convolution to better use available data and capture global cluster structures.The method adaptively selects an appropriate k to optimize clustering performance across different graphs.
- 5 Conclusion: The adaptive selection strategy enables competitive performance compared with classical and state-of-the-art methods.The authors identify improving robustness and efficiency of adaptive selection as future work.