Clustering Uncertain Graphs with Node Attributes

Yafang Li, Xiangnan Kong, Caiyan Jia, Jianqiang Li
Proceedings of The 10th Asian Conference on Machine Learning, PMLR 95:232-247, 2018.

Abstract

Graph clustering has attracted much attention in recent years, which has wide applications in social and biological networks. Recent approaches on graph clustering mainly focus on either certain graphs with node attributes or uncertain graphs without node attributes. However, many real-world graphs have both uncertainty on the edges and attributes on the nodes. We refer to such networks as \emph{attributed uncertain graphs}. Different from conventional graphs, attributed uncertain graphs post two major challenges for graph clustering: 1) uncertainty on the edges, which makes it difficult to extract reliable clusters; 2) high dimensional attributes on the nodes, which contain irrelevant and noisy information. In this paper, we study the problem of node clustering on attributed uncertain graphs, where we exploit both the uncertain edges and a set of important attributes for graph clustering. The uncertain edges can help identify the set of relevant attributes in the nodes, which are called focus attributes. While the focus attributes can help reduce the uncertainty in edges for graph clustering. We propose two novel approaches: AUG-I based upon integrated attribute induced graphs and AUG-U based upon the unified partition over possible worlds of a uncertain graph. Extensive empirical studies on real-world datasets demonstrate the effectiveness of our approaches for clustering tasks on attributed uncertain graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v95-li18b, title = {Clustering Uncertain Graphs with Node Attributes}, author = {Li, Yafang and Kong, Xiangnan and Jia, Caiyan and Li, Jianqiang}, booktitle = {Proceedings of The 10th Asian Conference on Machine Learning}, pages = {232--247}, year = {2018}, editor = {Zhu, Jun and Takeuchi, Ichiro}, volume = {95}, series = {Proceedings of Machine Learning Research}, month = {14--16 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v95/li18b/li18b.pdf}, url = {https://proceedings.mlr.press/v95/li18b.html}, abstract = {Graph clustering has attracted much attention in recent years, which has wide applications in social and biological networks. Recent approaches on graph clustering mainly focus on either certain graphs with node attributes or uncertain graphs without node attributes. However, many real-world graphs have both uncertainty on the edges and attributes on the nodes. We refer to such networks as \emph{attributed uncertain graphs}. Different from conventional graphs, attributed uncertain graphs post two major challenges for graph clustering: 1) uncertainty on the edges, which makes it difficult to extract reliable clusters; 2) high dimensional attributes on the nodes, which contain irrelevant and noisy information. In this paper, we study the problem of node clustering on attributed uncertain graphs, where we exploit both the uncertain edges and a set of important attributes for graph clustering. The uncertain edges can help identify the set of relevant attributes in the nodes, which are called focus attributes. While the focus attributes can help reduce the uncertainty in edges for graph clustering. We propose two novel approaches: AUG-I based upon integrated attribute induced graphs and AUG-U based upon the unified partition over possible worlds of a uncertain graph. Extensive empirical studies on real-world datasets demonstrate the effectiveness of our approaches for clustering tasks on attributed uncertain graphs.} }
Endnote
%0 Conference Paper %T Clustering Uncertain Graphs with Node Attributes %A Yafang Li %A Xiangnan Kong %A Caiyan Jia %A Jianqiang Li %B Proceedings of The 10th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jun Zhu %E Ichiro Takeuchi %F pmlr-v95-li18b %I PMLR %P 232--247 %U https://proceedings.mlr.press/v95/li18b.html %V 95 %X Graph clustering has attracted much attention in recent years, which has wide applications in social and biological networks. Recent approaches on graph clustering mainly focus on either certain graphs with node attributes or uncertain graphs without node attributes. However, many real-world graphs have both uncertainty on the edges and attributes on the nodes. We refer to such networks as \emph{attributed uncertain graphs}. Different from conventional graphs, attributed uncertain graphs post two major challenges for graph clustering: 1) uncertainty on the edges, which makes it difficult to extract reliable clusters; 2) high dimensional attributes on the nodes, which contain irrelevant and noisy information. In this paper, we study the problem of node clustering on attributed uncertain graphs, where we exploit both the uncertain edges and a set of important attributes for graph clustering. The uncertain edges can help identify the set of relevant attributes in the nodes, which are called focus attributes. While the focus attributes can help reduce the uncertainty in edges for graph clustering. We propose two novel approaches: AUG-I based upon integrated attribute induced graphs and AUG-U based upon the unified partition over possible worlds of a uncertain graph. Extensive empirical studies on real-world datasets demonstrate the effectiveness of our approaches for clustering tasks on attributed uncertain graphs.
APA
Li, Y., Kong, X., Jia, C. & Li, J.. (2018). Clustering Uncertain Graphs with Node Attributes. Proceedings of The 10th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 95:232-247 Available from https://proceedings.mlr.press/v95/li18b.html.

Related Material