In:
Proceedings of the VLDB Endowment, Association for Computing Machinery (ACM), Vol. 10, No. 6 ( 2017-02), p. 697-708
Abstract:
Node similarity is fundamental in graph analytics. However, node similarity between nodes in different graphs (inter-graph nodes) has not received enough attention yet. The inter-graph node similarity is important in learning a new graph based on the knowledge extracted from an existing graph (transfer learning on graphs) and has applications in biological, communication, and social networks. In this paper, we propose a novel distance function for measuring inter-graph 〈 u 〉 n 〈 /u 〉 ode similarity with 〈 u 〉 e 〈 /u 〉 dit 〈 u 〉 d 〈 /u 〉 istance, called NED . In NED, two nodes are compared according to their local neighborhood topologies which are represented as unordered k -adjacent trees, without relying on any extra information. Due to the hardness of computing tree edit distance on unordered trees which is NP-Complete, we propose a modified tree edit distance, called TED* , for comparing unordered and unlabeled k -adjacent trees. TED* is a metric distance, as the original tree edit distance, but more importantly, TED* is polynomially computable. As a metric distance, NED admits efficient indexing, provides interpretable results, and shows to perform better than existing approaches on a number of data analysis tasks, including graph deanonymization. Finally, the efficiency and effectiveness of NED are empirically demonstrated using real-world graphs.
Type of Medium:
Online Resource
ISSN:
2150-8097
DOI:
10.14778/3055330.3055336
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2017
detail.hit.zdb_id:
2478691-3
Bookmarklink