HyperGraph Convolution Based Attributed HyperGraph Clustering

Barakeel Fanseu Kamhoua; Lin Zhang; Kaili Ma; James Sheung Chak Cheng; Bo Li; Bo Han

doi:10.1145/3459637.3482437

HyperGraph Convolution Based Attributed HyperGraph Clustering

Barakeel Fanseu Kamhoua, Lin Zhang, Kaili Ma, James Sheung Chak Cheng, Bo Li, Bo Han

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

5 Citations (Scopus)

Abstract

Attributed Graph Clustering (AGC) and Attributed Hypergraph Clustering (AHC) are important topics in graph mining with many applications. For AGC, amongst the unsupervised methods that combine the graph structure with node attributes, graph convolution has been shown to achieve impressive results. However, the effects of graph convolution on AGC have not yet been adequately studied. In this paper, we show that graph convolution attempts to find the best trade-off between node attribute distance and the number of inter-cluster edges. On the one hand, we show that compared to clustering node attributes directly, graph convolution produces a greater distance between node attributes in the same cluster and a smaller distance between node attributes in different clusters (which is detrimental for clustering). On the other hand, we show that graph convolution benefits clustering by considerably reducing the number of edges among different clusters. We then extend our result on AGC to AHC and leverage the hypergraph convolution to propose an unsupervised, fast, and memory-efficient algorithm (GRAC) for AHC, which achieves excellent performance on popular supervised clustering measures.

Original language	English
Title of host publication	CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management
Publisher	Association for Computing Machinery (ACM)
Pages	453-463
Number of pages	11
ISBN (Print)	9781450384469
DOIs	https://doi.org/10.1145/3459637.3482437
Publication status	Published - 26 Oct 2021
Event	30th ACM International Conference on Information and Knowledge Management, CIKM 2021 - Virtual, Online, Gold Coast, Queensland, Australia Duration: 1 Nov 2021 → 5 Nov 2021 https://www.cikm2021.org/ https://dl.acm.org/doi/proceedings/10.1145/3459637

Publication series

Name	Proceedings of International Conference on Information and Knowledge Management

Conference

Conference	30th ACM International Conference on Information and Knowledge Management, CIKM 2021
Country/Territory	Australia
City	Gold Coast, Queensland
Period	1/11/21 → 5/11/21
Internet address	https://www.cikm2021.org/ https://dl.acm.org/doi/proceedings/10.1145/3459637

Scopus Subject Areas

Business, Management and Accounting(all)
Decision Sciences(all)

User-Defined Keywords

(hyper)graph convolution
attributed (hyper)graph clustering

Access to Document

10.1145/3459637.3482437

Cite this

Fanseu Kamhoua, B., Zhang, L., Ma, K., Cheng, J. S. C., Li, B., & Han, B. (2021). HyperGraph Convolution Based Attributed HyperGraph Clustering. In CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management (pp. 453-463). (Proceedings of International Conference on Information and Knowledge Management). Association for Computing Machinery (ACM). https://doi.org/10.1145/3459637.3482437

@inproceedings{76ee9d1caa2446b68799a8d34592ba85,

title = "HyperGraph Convolution Based Attributed HyperGraph Clustering",

abstract = "Attributed Graph Clustering (AGC) and Attributed Hypergraph Clustering (AHC) are important topics in graph mining with many applications. For AGC, amongst the unsupervised methods that combine the graph structure with node attributes, graph convolution has been shown to achieve impressive results. However, the effects of graph convolution on AGC have not yet been adequately studied. In this paper, we show that graph convolution attempts to find the best trade-off between node attribute distance and the number of inter-cluster edges. On the one hand, we show that compared to clustering node attributes directly, graph convolution produces a greater distance between node attributes in the same cluster and a smaller distance between node attributes in different clusters (which is detrimental for clustering). On the other hand, we show that graph convolution benefits clustering by considerably reducing the number of edges among different clusters. We then extend our result on AGC to AHC and leverage the hypergraph convolution to propose an unsupervised, fast, and memory-efficient algorithm (GRAC) for AHC, which achieves excellent performance on popular supervised clustering measures.",

keywords = "(hyper)graph convolution, attributed (hyper)graph clustering",

author = "{Fanseu Kamhoua}, Barakeel and Lin Zhang and Kaili Ma and Cheng, {James Sheung Chak} and Bo Li and Bo Han",

note = "Funding Information: We thank the reviewers for their valuable comments. This work was partially supported by GRF 14208318 from the RGC of HKSAR and the National Natural Science Foundation of China (NSFC) (Grant No. 61672552). Lin Zhang and Bo Li were supported in part by RGC RIF grant R6021-20 and RGC GRF grant under contracts 16207818 and 16209120. Bo Han was supported by the RGC Early Career Scheme No. 22200720 and NSFC Young Scientists Fund No. 62006202. ; 30th ACM International Conference on Information and Knowledge Management, CIKM 2021 ; Conference date: 01-11-2021 Through 05-11-2021",

year = "2021",

month = oct,

day = "26",

doi = "10.1145/3459637.3482437",

language = "English",

isbn = "9781450384469",

series = "Proceedings of International Conference on Information and Knowledge Management",

publisher = "Association for Computing Machinery (ACM)",

pages = "453--463",

booktitle = "CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management",

address = "United States",

url = "https://www.cikm2021.org/, https://dl.acm.org/doi/proceedings/10.1145/3459637",

}

Fanseu Kamhoua, B, Zhang, L, Ma, K, Cheng, JSC, Li, B & Han, B 2021, HyperGraph Convolution Based Attributed HyperGraph Clustering. in CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. Proceedings of International Conference on Information and Knowledge Management, Association for Computing Machinery (ACM), pp. 453-463, 30th ACM International Conference on Information and Knowledge Management, CIKM 2021, Gold Coast, Queensland, Australia, 1/11/21. https://doi.org/10.1145/3459637.3482437

HyperGraph Convolution Based Attributed HyperGraph Clustering. / Fanseu Kamhoua, Barakeel; Zhang, Lin; Ma, Kaili et al.
CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. Association for Computing Machinery (ACM), 2021. p. 453-463 (Proceedings of International Conference on Information and Knowledge Management).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - HyperGraph Convolution Based Attributed HyperGraph Clustering

AU - Fanseu Kamhoua, Barakeel

AU - Zhang, Lin

AU - Ma, Kaili

AU - Cheng, James Sheung Chak

AU - Li, Bo

AU - Han, Bo

N1 - Funding Information: We thank the reviewers for their valuable comments. This work was partially supported by GRF 14208318 from the RGC of HKSAR and the National Natural Science Foundation of China (NSFC) (Grant No. 61672552). Lin Zhang and Bo Li were supported in part by RGC RIF grant R6021-20 and RGC GRF grant under contracts 16207818 and 16209120. Bo Han was supported by the RGC Early Career Scheme No. 22200720 and NSFC Young Scientists Fund No. 62006202.

PY - 2021/10/26

Y1 - 2021/10/26

N2 - Attributed Graph Clustering (AGC) and Attributed Hypergraph Clustering (AHC) are important topics in graph mining with many applications. For AGC, amongst the unsupervised methods that combine the graph structure with node attributes, graph convolution has been shown to achieve impressive results. However, the effects of graph convolution on AGC have not yet been adequately studied. In this paper, we show that graph convolution attempts to find the best trade-off between node attribute distance and the number of inter-cluster edges. On the one hand, we show that compared to clustering node attributes directly, graph convolution produces a greater distance between node attributes in the same cluster and a smaller distance between node attributes in different clusters (which is detrimental for clustering). On the other hand, we show that graph convolution benefits clustering by considerably reducing the number of edges among different clusters. We then extend our result on AGC to AHC and leverage the hypergraph convolution to propose an unsupervised, fast, and memory-efficient algorithm (GRAC) for AHC, which achieves excellent performance on popular supervised clustering measures.

AB - Attributed Graph Clustering (AGC) and Attributed Hypergraph Clustering (AHC) are important topics in graph mining with many applications. For AGC, amongst the unsupervised methods that combine the graph structure with node attributes, graph convolution has been shown to achieve impressive results. However, the effects of graph convolution on AGC have not yet been adequately studied. In this paper, we show that graph convolution attempts to find the best trade-off between node attribute distance and the number of inter-cluster edges. On the one hand, we show that compared to clustering node attributes directly, graph convolution produces a greater distance between node attributes in the same cluster and a smaller distance between node attributes in different clusters (which is detrimental for clustering). On the other hand, we show that graph convolution benefits clustering by considerably reducing the number of edges among different clusters. We then extend our result on AGC to AHC and leverage the hypergraph convolution to propose an unsupervised, fast, and memory-efficient algorithm (GRAC) for AHC, which achieves excellent performance on popular supervised clustering measures.

KW - (hyper)graph convolution

KW - attributed (hyper)graph clustering

UR - http://www.scopus.com/inward/record.url?scp=85119192768&partnerID=8YFLogxK

U2 - 10.1145/3459637.3482437

DO - 10.1145/3459637.3482437

M3 - Conference proceeding

AN - SCOPUS:85119192768

SN - 9781450384469

T3 - Proceedings of International Conference on Information and Knowledge Management

SP - 453

EP - 463

BT - CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

PB - Association for Computing Machinery (ACM)

T2 - 30th ACM International Conference on Information and Knowledge Management, CIKM 2021

Y2 - 1 November 2021 through 5 November 2021

ER -

Fanseu Kamhoua B, Zhang L, Ma K, Cheng JSC, Li B, Han B. HyperGraph Convolution Based Attributed HyperGraph Clustering. In CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. Association for Computing Machinery (ACM). 2021. p. 453-463. (Proceedings of International Conference on Information and Knowledge Management). doi: 10.1145/3459637.3482437

HyperGraph Convolution Based Attributed HyperGraph Clustering

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this