A new space for comparing graphs

Anshumali Shrivastava, Ping Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

Finding a new mathematical representation for graphs, which allows direct comparison between different graph structures, is an open-ended research direction. Having such a representation is the first prerequisite for a variety of machine learning algorithms like classification, clustering, etc., over graph datasets. In this paper, we propose a symmetric positive semidefinite matrix with the (i, j)-th entry equal to the covariance between normalized vectors Aie and Aje (e being vector of all ones) as a representation for a graph with adjacency matrix A. We show that the proposed matrix representation encodes the spectrum of the underlying adjacency matrix and it also contains information about the counts of small sub-structures present in the graph such as triangles and small paths. In addition, we show that this matrix is a 'graph invariant'. All these properties make the proposed matrix a suitable object for representing graphs. The representation, being a covariance matrix in a fixed dimensional metric space, gives a mathematical embedding for graphs. This naturally leads to a measure of similarity on graph objects. We define similarity between two given graphs as a Bhattacharya similarity measure between their corresponding covariance matrix representations. As shown in our experimental study on the task of social network classification, such a similarity measure outperforms other widely used state-of-theart methodologies. Our proposed method is also computationally efficient. The computation of both the matrix representation and the similarity value can be performed in operations linear in the number of edges. This makes our method scalable in practice. We believe our theoretical and empirical results provide evidence for studying truncated power iterations, of the adjacency matrix, to characterize social networks.

Original languageEnglish (US)
Title of host publicationASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
EditorsMartin Ester, Guandong Xu, Xindong Wu, Xindong Wu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages62-71
Number of pages10
ISBN (Electronic)9781479958771
DOIs
StatePublished - Oct 10 2014
Event2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014 - Beijing, China
Duration: Aug 17 2014Aug 20 2014

Publication series

NameASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Other

Other2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014
CountryChina
CityBeijing
Period8/17/148/20/14

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A new space for comparing graphs'. Together they form a unique fingerprint.

Cite this