Graph-Based Identification and Authentication: A Stochastic Kronecker Approach

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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 this claim? 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 using extensive experiments on 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 percent, and the other, which is easier to implement, relies on distances between identities and achieves an accuracy rate of 70.8 percent. For network authentication, we propose two methods to build a network authentication system. The first is a supervised learner and yields 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.

Original languageEnglish (US)
Pages (from-to)3282-3294
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
StatePublished - Jul 1 2022


  • Network identification
  • network authentication
  • network embedding
  • network representation learning

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Graph-Based Identification and Authentication: A Stochastic Kronecker Approach'. Together they form a unique fingerprint.

Cite this