Graph learning is an inference problem of estimating the nodes’ connectivity from a collection of epidemic cascades, with many useful applications in the areas of in online/offline social networks, p2p networks, computer security, and epidemiology. We consider a case when the information of cascade samples are only partially observed under the IC (Independent Cascade) epidemic model, where our interest is to compute the sample complexity, i.e., a required number of cascade samples to achieve a given target inference accuracy. We first provide a fundamental lower bound on the sample complexity. Then, motivated by the fact that the famous Maximum Likelihood Estimator (MLE) is computationally intractable, we propose a greedy heuristic that works based on counting the estimated number of possible activation path, which we call counting of virtual activation paths, where the key strength lies in having much smaller computational complexity than the algorithm based on the approximation of MLE. We analyze the sample complexity of our greedy heuristic, which is close to optimal for some graphs where activation propagates ceaselessly. We evaluate the performance of our algorithm over various types of graph topologies.
그래프 학습은 확산 샘플 군집으로부터 노드 연결성을 추정하는 추론으로, 컴퓨터 보안, 역학, p2p 네트워크 등 많은 온라인/오프라인 사회 연결망에서 유용하게 사용되고 있다. 본 논문은 불완전한 확산 샘플을 통해 목표 정확도를 달성하는 탐욕적 그래프 연결성 학습 알고리즘을 제안하고 이에 필요한 샘플 수를 연구하였다. 제안된 탐욕적인 알고리즘은 실제 확산 경로일 가능성이 있는 가상의 활성 경로에 대한 계산을 바탕으로 낮은 계산복잡도로 높은 정확도를 달성한다. 본 논문은 알고리즘의 샘플 복잡도를 이론적으로 분석하여 탐욕 알고리즘이 최적에 근사함을 보여주고 이를 다양한 유형의 상황에 적용하여 실험적으로 평가하였다.
