Abstract:

A large body of research has focused on analyzing large networks and graphs. However, network and graph data is often anonymized for reasons such as protecting data privacy. Under such circumstances, it is difficult to verify the source of network data, which leads to questions such as: Given an anonymized graph, can we identify the network from which it is collected? Or if one claims the graph is sampled from a certain network, can we verify it? The intuitive approach is to check for subgraph isomophism. However, subgraph isomophism is NP-complete; hence, infeasible for most large networks. Inspired by biometrics studies, we address these challenges by formulating two new problems: network identification and network authentication. To tackle these problems, similar to research on human fingerprints, we introduce two versions of a network identity: (1) embedding-based identity and (2) distribution-based identity. We demonstrate the effectiveness of these network identities on twenty real-world networks. Using these identities, we propose two approaches for network identification. One method uses supervised learning and can achieve an identification accuracy of 84.4%, and the other, which is easier to implement, relies on distances between identities and achieves an accuracy rate of 70.8%. For network authentication, we propose two methods to build a network authentication system. The first is a supervised learner and provides a low false accept rate and the other method allows one to control the false reject rate with a reasonable false accept rate across networks. We demonstrate that network authentication can also be used for biometrics, authenticating users based on their touch data on phones and tablets. Our study can help identify or verify the source of network data, validate network-based research, and be used for network-based biometrics.

Download paper here

Recommended citation: Shengmin Jin, Vir Phoha and Reza Zafarani. “Graph-based Identification and Authentication: A Stochastic Kronecker Approach.” IEEE Transactions on Knowledge and Data Engineering. 2020.