NDLI: Nested Subtree Hash Kernels for Large-Scale Graph Classification over Streams

Content Provider	IEEE Xplore Digital Library
Author	Bin Li Xingquan Zhu Lianhua Chi Chengqi Zhang
Copyright Year	2012
Abstract	Most studies on graph classification focus on designing fast and effective kernels. Several fast subtree kernels have achieved a linear time-complexity w.r.t. the number of edges under the condition that a common feature space (e.g., a subtree pattern list) is needed to represent all graphs. This will be infeasible when graphs are presented in a stream with rapidly emerging subtree patterns. In this case, computing a kernel matrix for graphs over the entire stream is difficult since the graphs in the expired chunks cannot be projected onto the unlimitedly expanding feature space again. This leads to a big trouble for graph classification over streams -- Different portions of graphs have different feature spaces. In this paper, we aim to enable large-scale graph classification over streams using the classical ensemble learning framework, which requires the data in different chunks to be in the same feature space. To this end, we propose a Nested Subtree Hashing (NSH) algorithm to recursively project the multi-resolution subtree patterns of different chunks onto a set of common low-dimensional feature spaces. We theoretically analyze the derived NSH kernel and obtain a number of favorable properties: 1) The NSH kernel is an unbiased and highly concentrated estimator of the fast subtree kernel. 2) The bound of convergence rate tends to be tighter as the NSH algorithm steps into a higher resolution. 3) The NSH kernel is robust in tolerating concept drift between chunks over a stream. We also empirically test the NSH kernel on both a large-scale synthetic graph data set and a real-world chemical compounds data set for anticancer activity prediction. The experimental results validate that the NSH kernel is indeed efficient and robust for graph classification over streams.
Starting Page	399
Ending Page	408
File Size	406012
Page Count	10
File Format	PDF
ISBN	9781467346498
ISSN	15504786
DOI	10.1109/ICDM.2012.101
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-12-10
Publisher Place	Belgium
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Kernel Feature extraction Vectors Data mining Convergence Chemical compounds Robustness nested subtree hashing Graph classification data stream mining graph hash kernels
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Feature selection for graph kernels

G-hash: towards fast kernel-based similarity search in large graph databases

Towards Combining Structured Pattern Mining and Graph Kernels

Chemically Augmented String Kernel for Extraction and Classification of Chemical Compounds from Text

Hash kernels for structured data (2009)

Hash Kernels for Structured Data (2009)

Hash kernels for structured data.

Weisfeiler-lehman graph kernels (2011).

Semisupervised nonlinear feature extraction for image classification

Nested Subtree Hash Kernels for Large-Scale Graph Classification over Streams

Similar Documents

Feature selection for graph kernels

G-hash: towards fast kernel-based similarity search in large graph databases

Towards Combining Structured Pattern Mining and Graph Kernels

Chemically Augmented String Kernel for Extraction and Classification of Chemical Compounds from Text

Hash kernels for structured data (2009)

Hash Kernels for Structured Data (2009)

Hash kernels for structured data.

Weisfeiler-lehman graph kernels (2011).

Semisupervised nonlinear feature extraction for image classification

Nested Subtree Hash Kernels for Large-Scale Graph Classification over Streams