Are users of an online social network interested equally in all connections in the network? If not, how can we obtain a summary of the network personalized to specific users? Can we use the summary for approximate query answering?
As massive graphs (e.g., online social networks, hyperlink networks, and road networks) have become pervasive, graph compression has gained importance for the efficient processing of such graphs with limited resources. Graph summarization is an extensively-studied lossy compression method. It provides a summary graph where nodes with similar connectivity are merged into supernodes, and a variety of graph queries can be answered approximately from the summary graph.
In this work, we introduce a new problem, namely personalized graph summarization, where the objective is to obtain a summary graph where more emphasis is put on connections closer to a given set of target nodes. Then, we propose PeGaSus, a linear-time algorithm for the problem. Through experiments on six real-world graphs, we demonstrate that PeGaSus is (a) Effective: node-similarity queries for target nodes can be answered significantly more accurately from personalized summary graphs than from non-personalized ones of similar size, (b) Scalable: it summarizes graphs with up to one billion edges, and (c) Applicable to distributed multi-query answering: it successfully replaces graph partitioning for communication-free multi-query processing.
온라인 소셜 네트워크에서 유저들은 다른 모든 사람들에게 관심이 있을까? 만약 아니라면, 어떻게 특정 유저에게 개인화 된 네트워크의 요약을 얻을 수 있을까? 그리고, 그 네트워크의 요약을 쿼리를 응답하는데 사용할 수 있을까?
거대한 그래프(예: 온라인 소셜 네트워크, 웹 네트워크)들이 많이 생겨남으로 인해, 그래프 압축 기법은 한정된 자원에서 거대한 그래프를 효율적으로 활용하기 위해 중요해졌다. 그래프 요약은 정보 손실이 존재하는 그래프 압축 기법 중 한 가지이다. 그래프 요약은 입력 그래프를 받아 요약 그래프를 만들어 내는데, 요약 그래프의 노드는 연결 관계가 유사한 입력 그래프 내의 여러 개의 노드로 이루어진 '수퍼노드'이다. 그리고, 다양한 그래프 쿼리들은 요약 그래프에서 응답될 수 있다.
본 논문에서, 목표 노드들이 주어졌을 때 목표 노드들에 가까운 연결 정보들을 중점으로 보존한 '개인화된 요약 그래프'를 얻는 것을 목적으로 하는 '개인화된 그래프 요약'을 새롭게 정의한다. 그리고, 그 문제를 해결하는 있는 선형 시간 알고리즘 PeGaSus를 제안한다. 또한, 6개의 실제 세계의 그래프에서의 실험을 통해 PeGaSus가 다음과 같은 특성들을 가지는 것을 보인다. (1) 효과적: 개인화된 요약 그래프에서 목표 노드들에 노드 유사도 쿼리에 대한 답변이 동일한 사이즈의 비개인화된 요약 그래프에서의 답변보다 정확함, (2) 확장 가능: 최대 10억개의 엣지를 가진 그래프를 요약함, 그리고 (3) 분산 다중 쿼리 답변에 적용 가능함: 저장소간 통신이 없는 다중 쿼리 처리에서 그래프 분할 기법을 효과적으로 대체함.
