کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
529893 869719 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding the best not the most: regularized loss minimization subgraph selection for graph classification
ترجمه فارسی عنوان
بهترین انتخاب را انتخاب نمی کنید: انتخاب زیرگرافی به حداقل رساندن ضرر و زیان قانونی برای طبقه بندی گراف
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر چشم انداز کامپیوتر و تشخیص الگو
چکیده انگلیسی


• Our algorithm selects the optimal subgaphs for graph classification.
• We generalize the column generation technique of gBoost for graph classification.
• We use the elastic net to produce sparse and robust solutions for subgraph selection.
• We derive an effective pruning rule for search space reduction.
• We demonstrate the effectiveness of our algorithm.

Classification on structure data, such as graphs, has drawn wide interest in recent years. Due to the lack of explicit features to represent graphs for training classification models, extensive studies have been focused on extracting the most discriminative subgraphs features from the training graph dataset to transfer graphs into vector data. However, such filter-based methods suffer from two major disadvantages: (1) the subgraph feature selection is separated from the model learning process, so the selected most discriminative subgraphs may not best fit the subsequent learning model, resulting in deteriorated classification results; (2) all these methods rely on users to specify the number of subgraph features K, and suboptimally specified K values often result in significantly reduced classification accuracy.In this paper, we propose a new graph classification paradigm which overcomes the above disadvantages by formulating subgraph feature selection as learning a K-dimensional feature space from an implicit and large subgraph space, with the optimal K value being automatically determined. To achieve the goal, we propose a regularized loss minimization-driven (RLMD) feature selection method for graph classification. RLMD integrates subgraph selection and model learning into a unified framework to find discriminative subgraphs with guaranteed minimum loss w.r.t. the objective function. To automatically determine the optimal number of subgraphs K from the exponentially large subgraph space, an effective elastic net and a subgradient method are proposed to derive the stopping criterion, so that K can be automatically obtained once RLMD converges. The proposed RLMD method enjoys gratifying property including proved convergence and applicability to various loss functions. Experimental results on real-life graph datasets demonstrate significant performance gain.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Pattern Recognition - Volume 48, Issue 11, November 2015, Pages 3783–3796
نویسندگان
, , , , ,