• Complain

Ana Fred Maria Marsico - PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram

Here you can read online Ana Fred Maria Marsico - PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram full text of the book (entire story) in english for free. Download pdf and epub, get meaning, cover and reviews about this ebook. City: Cham, year: 2017, publisher: Springer International Publishing, genre: Home and family. Description of the work, (preface) as well as reviews are available. Best literature library LitArk.com created for fans of good reading and offers a wide selection of genres:

Romance novel Science fiction Adventure Detective Science History Home and family Prose Art Politics Computer Non-fiction Religion Business Children Humor

Choose a favorite category and find really read worthwhile books. Enjoy immersion in the world of imagination, feel the emotions of the characters or learn something new for yourself, make an fascinating discovery.

Ana Fred Maria Marsico PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram

PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram: summary, description and annotation

We offer to read an annotation, description, summary or preface (depends on what the author of the book "PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram" wrote himself). If you haven't found the necessary information about the book — write in the comments, we will try to find it.

Ana Fred Maria Marsico: author's other books


Who wrote PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram? Find out the surname, the name of the author of the book and a list of all author's works by series.

PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

Reset

Interval:

Bookmark:

Make
Springer International Publishing AG 2017
Ana Fred , Maria De Marsico and Gabriella Sanniti di Baja (eds.) Pattern Recognition Applications and Methods Lecture Notes in Computer Science 10163 10.1007/978-3-319-53375-9_1
Experimental Evaluation of Graph Classification with Hadamard Code Graph Kernels
Tetsuya Kataoka 1
(1)
School of Science and Technology, Kwansei Gakuin University, 2-1 Gakuen, Sanda, Hyogo, Japan
Tetsuya Kataoka
Email:
Akihiro Inokuchi (Corresponding author)
Email:
Abstract
When mining information from a database comprising graphs, kernel methods are used to efficiently classify graphs that have similar structures into the same classes. Instances represented by graphs usually have similar properties if their graph representations have high structural similarity. The neighborhood hash kernel (NHK) and WeisfeilerLehman subtree kernel (WLSK) have previously been proposed as kernels that compute more quickly than the random-walk kernel; however, they each have drawbacks. NHK can produce hash collision and WLSK must sort vertex labels. We propose a novel graph kernel equivalent to NHK in terms of time and space complexities, and comparable to WLSK in terms of expressiveness. The proposed kernel is based on the Hadamard code. Labels assigned by our graph kernel follow a binomial distribution with zero mean. The expected value of a label is zero; thus, such labels do not require large memory. This allows the compression of vertex labels in graphs, as well as fast computation. This paper presents the Hadamard code kernel (HCK) and shortened HCK (SHCK), a version of HCK that compresses vertex labels in graphs. The performance and practicality of the proposed method are demonstrated in experiments that compare the computation time, scalability and classification accuracy of HCK and SHCK with those of NHK and WLSK for both artificial and real-world datasets. The effect of assigning initial labels is also investigated.
Keywords
Graph classification Support vector machine Graph kernel Hadamard code
Introduction
A natural way of representing structured data is to use graphs [], graph classification has been widely researched worldwide. The main objective of graph classification is to classify graphs of similar structures into the same classes. This originates from the fact that instances represented by graphs usually have similar properties if their graph representations have high structural similarity.
Kernel methods such as the use of the support vector machine (SVM) are becoming increasingly popular because of their high performance in solving graph classification problems [], kernels deliberately avoid the explicit computation of feature values and instead employ efficient procedures.
One representative graph kernel is the random-walk kernel (RWK) [] are two other recently proposed kernels that compute Picture 1 more quickly than RWK. NHK uses logical operations such as the exclusive OR on the label set of adjacent vertices, while WLSK uses a concatenation of label strings of the adjacent vertices to compute Picture 2 . The labels updated by repeating the hash or concatenation propagate the label information over the graph and uniquely represent the higher-order structures around the vertices beyond the vertex or edge level. An SVM with two graph kernels works well with benchmark data consisting of graphs.
The computation of NHK is efficient because it is a logical operation between fixed-length bit strings and does not require string sorting. However, its drawback is hash collision, which occurs when different induced subgraphs have identical hash values. Meanwhile, WLSK must sort the vertex labels, but it has high expressiveness because each vertex v has a distribution of vertex labels within i steps from v . To overcome the drawbacks of NHK and WLSK, in this paper, we propose a novel graph kernel that is equivalent to NHK in terms of time and space complexities and comparable to WLSK in terms of expressiveness. The graph kernel proposed in this paper is based on the Hadamard code []. The Hadamard code is used in spread spectrum-based communication technologies such as Code Division Multiple Access to spread message signals. Because the probability of occurrences of values of 1 and Picture 3 are equivalent in each column of the Hadamard matrix except for the first column, labels assigned by our graph kernel follow a binomial distribution with zero mean under a certain assumption. Therefore, the expected value of the label is zero, and for such labels, a large memory space is not required. This characteristic is used to compress vertex labels in graphs, allowing the proposed graph kernel to be computed quickly.
Note that large portions of this paper were covered in our previous work []. Within the current work we demonstrate the performance and practicality of the proposed method in experiments that compare the computation time, scalability and classification accuracy of HCK and SHCK with those of NHK and WLSK for various artificial datasets. The effect of assigning initial labels for the graph kernels is also investigated.
The rest of this paper is organized as follows. Section .
Graph Kernels
2.1 Framework of Representative Graph Kernels
This paper tackles the classification problem of graphs. A graph is represented as PATTERN RECOGNITION APPLICATIONS AND METHODS 5th international conference icpram - image 4 , where V is a set of vertices, Picture 5 is a set of edges, Picture 6 is a set of vertex labels, and Picture 7 is a function that assigns a label to each vertex in the graph. Additionally, the set of vertices in graph g is denoted by V ( g ). Although we assume that only the vertices in the graphs have labels in this paper, the methods used in this paper can be applied to graphs where both the vertices and edges have labels. The vertices adjacent to vertex v are represented as PATTERN RECOGNITION APPLICATIONS AND METHODS 5th international conference icpram - image 8 . A sequence of vertices from v to u is called a path, and its step refers to the number of edges on that path. A path is described as being simple if and only if the path does not have repeating vertices. Paths in this paper are not always simple.
The graph classification problem is defined as follows. Given a set of n training examples PATTERN RECOGNITION APPLICATIONS AND METHODS 5th international conference icpram - image 9 , where each example is a pair consisting of a labeled graph PATTERN RECOGNITION APPLICATIONS AND METHODS 5th international conference icpram - image 10 and the class PATTERN RECOGNITION APPLICATIONS AND METHODS 5th international conference icpram - image 11
Next page
Light

Font size:

Reset

Interval:

Bookmark:

Make

Similar books «PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram»

Look at similar books to PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.


Reviews about «PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram»

Discussion, reviews of the book PATTERN RECOGNITION APPLICATIONS AND METHODS: 5th international conference, icpram and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.