community detection in node-attributed social network 논문 정리

정리한 논문: Chunaev, Petr. “Community detection in node-attributed social networks: a survey.” Computer Science Review 37 (2020): 100286.

social network에 connection 정보 뿐만 아니라 attribute 정보가 있는 경우, 두 정보 모두 이용해서 community detection을 할 수 있다. 두 정보를 어떻게 함께 이용하는지에 따라 methods가 크게 3가지로 나뉘고, 각 method 안에서도 세부적인 내용에 따라 또 나뉘는데 분류를 대강 정리하기 위해 포스팅한다.

Community detection problem for node-attributed social networks

Basic notation

node-attributed graph G는 다음과 같이 나타낼 수 있다. \[G = (V, E, A)\] V는 vertex의 집합, E는 edge의 집합, 벡터 A는 각 vertex의 attribute이다. 이런 그래프를 가지고 community detection을 한다는 것은 결국 집합 V를 n개의 부분집합으로 나누는 unsupervised partitioning을 한다는 것이고, partition을 할 때에는 structural closeness와 attribute homogeneity가 균형을 맞추며 획득되어야 한다.

The effect of fusing structure and attributes

두 정보가 서로 보완적이라 함께 쓸 경우 community detection의 질을 높인다는 걸 많은 연구들이 이미 보였다. 물론 그에 대해 반대되는 논문도 많은데 structure와 attribute가 orthogonal할 경우 굉장히 애매모호한 결과가 나온다는 것이다. 또한 structure와 attribute의 관계가 굉장히 비선형적일 수 있고 거기에서 파생되는 어려움이 있다. 그렇기 때문에 저런 경우들까지 고려해 어떻게 structure 및 attribute 정보를 잘 이용할 수 있을지 생각해보는건 의미있는 일이고, 이 survey에서는 그런 methods들을 소개, 분류하고 있다.

Classification of community detection methods for node-attributed social networks

fusion과 community detection이 어느 시점에 이루어지는가에 따라 나누고 있다.

• early fusion methods: detection 전에 fuse.
• simultaneous fusion methods: 말그대로 동시에 하는 것. 프로그래밍적으로는 제일 어려울 수 있다.
• late fusion methods: 각 성질을 바탕으로 partition하고 그걸로 fuse.

이 큰 분류들을 바탕으로 각 분류의 세부적인 method에 대해서 알아본다.

Early fusion methods

Weight-based methods

쉽게 말해 structure와 attribute의 유사성에 따라 edge의 weight를 달리하는 방법이다. 이렇게 그래프가 다시 만들어지면 그 다음부터는 Weighted Louvain 같은 classical graph clustering algorithm을 쓸 수 있다. vertex i, j 사이의 edge weight를 계산하기 위한 수식은 다음과 같다: \[{W}_{\alpha} = {\alpha}w_S(v_i, v_j) + (1- {\alpha})w_A(v_i,v_j) \]

\(w_s\)는 structure를 반영하는 함수(주로 연결이 있으면 1, 없으면 0의 값)이고 \(w_a\)는 attribute간의 유사도를 계산하는 함수(예를 들어 코사인 유사도 계산 함수)이다. \(\alpha\)는 hyperparameter로 휴리스틱하게 정해야한다.

Distance-based methods

앞선 방법은 정보를 통합해 새로운 그래프로 재표현했던 한편, 이 방법은 graph representation을 의도적으로 버린다. 대신 structure와 attribute 정보를 갖고 있는 distance matrix로 재표현한다. 그리고 이 matrix로 distance-based clustering algorithm(예를 들어 k-means)을 사용할 수 있다. distance function은 다음과 같다: \[{D}_{\alpha} = {\alpha}d_S(v_i, v_j) + (1- {\alpha})d_A(v_i,v_j) \]

Node-augmented graph-based methods

원래 graph \(G\)에, attribute vertex들을 증강하여 새로운 그래프 \(\tilde{G}\)를 만들어내는 방법이다. 예를 들어, n차원의 attribute vector A가 있을 때 A의 element \(a_i\)가 가질 수 있는 값이 \(l\)개 있다고 하면, \(l\)개 각각의 attribute에 해당하는 attribute vertex를 추가하는 것이다. 물론 \(a_i\) 뿐만 아니라 A의 모든 요소에 대해서 동일한 작업을 한다. 원 그래프 \(G\)의 vertex는, 각 attribute 값에 따라 attribute vertex에 연결되거나, 되지 않거나 한다. 이렇게 증강된 그래프로 community detection을 한다. 당연히 연속적인 값을 가지는 attribute로는 표현할 수 없다. 또한 vertex와 edge의 증가로 computaional cost가 크다.

Embedding-based methods

그래프는 관련 알고리즘들이 대개 많은 연산을 필요로 하고, 그래프의 특성상 머신러닝에 사용되기 어렵다. 이 문제를 tackle하고 있는 것이 node embeddings 방법이다. 즉, network 내의 Node를 정보에 따라 embedding해 저차원의 연속적인 값을 지니는 벡터로 만드는 것이다..!!! 자세한 사항은 이미 이에 대해 survey한 다른 논문들이 있으므로 그걸 참고하라고 되어있다.

Pattern mininig-based (early fusion) methods

motif처럼 connection의 패턴을 찾아 community detection하는 방법이고, 관련 논문이 하나 있다.

Simultaneous fusion methods

Methods modifying objective functions of classical clustering

classical clustering algorithm을 수정하는 방법이다. 예를 들어 원래 structure 최적화를 위해 Louvain algorithm을 쓰는 목적함수였다면, attribute 최적화를 위해 Entropy도 도입하는 식으로 목적함수를 수정하는 것이다. 그렇게 iterative한 process를 통해 structure과 attribute 측면 동시에 최적화한다.

Metaheuristic-based methods

앞 절의 방법과 비슷하지만, objective function을 수정하는 방법이 더 휴리스틱하다.

Methods based on non-negative matrix factorization and matrix compression

• n = # of nodes, d = dim of attribute vector, N = # of required cluster 일 때

• \(S_{n{\times}n}\)를 adjacency matrix, \(A_{n{\times}d}\)를 node attribute matrix, \(U_{n{\times}N}\)를 각 node-cluster 연관성 보여주는 cluster membership matrix, \(V_{d{\times}N}\)를 각 attribute-cluster 연관성 보여주는 cluster membership matrix로 정의한다면,

matrix factorization을 이용해, \(S\)와 \(UU_t\)의 차이를 가장 작게하는 \(U\)와, \(U\)와 \(AV\)의 차이를 가장 작게하는 V를 구하는 문제로 전환할 수 있다. \(l_1\) norm을 포함해 목적 함수를 나타내면 다음과 같다: \[{\min}_{U{\ge}0, V{\ge}0}({\alpha}_1{\lVert {S-UU_T}\rVert}_F^2 + {\lVert {U-AV}\rVert}_F^2 + {\alpha}_2{\sum}{\lVert {V(・,j)}\rVert}_1^2) \]

Pattern mining-based (simultaneous fusion) methods

extracted pattern으로 community가 어떻게 형성되는지 이해할 수 있다는 측면에서 community detection에 도움이 되지만, 이 분류의 논문들은 주로 community detection을 목적으로 두고 있지 않다.

Probabilistic model-based methods

node의 community membership을 확률론적으로 추론하는 방법이다. network structure와 attribute가 어떤 분포를 따르며 발생되었다는 가정이 깔려있다. 어떤 분포를 전제로 할 것인가는 중요하다.

Dynamical system-based and agent-based methods

이 방법은 node-attributed social network를 dynamic system으로 보고 community structure를 그 결과로 본다. 즉 node간 interaction으로 community가 생성되는 것이고 attribute는 그에 영향을 미치는 요소인 셈이다. 비교적 최근에 나온 접근법이다.

Late fusion methods

Consensus-based methods

structure와 attribute 각각으로 community detection을 하고 그 결과로 나온 partition들을 융합하는 방법이다. 즉, 각 partition이 반영하는 정보를 종합해 하나의 통합된(합의된) partition을 찾는 방법이다.

Switched-based methods

이전 절의 방법은 여러 partition을 반영해 하나의 합의된 partition을 찾아냈지만, 이 방법은 여러 partition이 있을 때 그 중 가장 Preferable한 partition을 선택한다. 예를 들어, structure-based partition이 모호하다고 생각되면 attribute-based partition으로 전환한다.