We are pleased to announce that our paper “Efficient network representation learning via cluster similarity” has been accepted to DASFAA2023 as a poster presentation.

Yasuhiro Fujiwara, Yasutoshi Ida, Atsutoshi Kumagai, Masahiro Nakano, Akisato Kimura, Naonori Ueda, “Efficient network representation learning via cluster similarity,” International Conference on Database Systems for Advanced Applications (DASFAA), 2023.

Network representation learning is a de-facto tool for graph analytics. The mainstream of the previous approaches is to factorize the proximity matrix between nodes. However, since the size of the proximity matrix is $n\times n$ for $n$-nodes graphs, it needs $O(n^3)$ time and $O(n^2)$ space to perform network representation learning, which is significantly high for large-scale graphs.

This paper introduces a novel idea of using similarities between clusters instead of proximities between nodes. We compute the representations of the clusters from similarities between clusters and compute the representations of nodes by referring to them. If $\ell$ is the number of clusters, since we have $\ell\ll n$, we can efficiently obtain the representations of clusters from a small $\ell\times\ell$ similarity matrix. Furthermore, since nodes in each cluster share similar structural properties, we can effectively compute the representation vectors of nodes.

Experiments show that our approach can perform network representation learning more efficiently and effectively than existing approaches.

The conference paper can be checked at https://link.springer.com/chapter/10.1007/978-3-031-30675-4_20 .

An extended version has been accepted for publication in Data Science and Engineering Journal.