Next: 5 SAMPLING, HISTOGRAMS, AND Up: Online Electronic Catalog of Previous: 3 DATA COMPRESSION AND
We consider the computational complexity of learning by neural nets. We
are interested in how hard it is to design appropriate neural net
architectures and to train neural nets for general and specialized
learning tasks. Our main result shows that the training problem for
2-cascade neural nets (which have only two non-input nodes, one of which
is hidden) is 
-complete, which implies that finding an optimal
net (in terms of the number of non-input units) that is consistent with
a set of examples is also -complete. This result also
demonstrates a surprising gap between the computational complexities of
one-node (perceptron) and two-node neural net training problems, since
the perceptron training problem can be solved in polynomial time by
linear programming techniques. We conjecture that training a
-cascade neural net, which is a classical threshold network training
problem, is also -complete, for each fixed 
. We also
show that the problem of finding an optimal perceptron (in terms of the
number of non-zero weights) consistent with a set of training examples
is -hard.
Our neural net learning model encapsulates the idea of modular neural nets, which is a popular approach to overcoming the scaling problem in training neural nets. We investigate how much easier the training problem becomes if the class of concepts to be learned is known a priori and the net architecture is allowed to be sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy.
In this paper, we extend Valiant's sequential model of concept learning
from examples [Valiant 1984] and introduce models for the efficient
learning of concept classes from examples in parallel. We say
that a concept class is 
-learnable if it can be
learned in polylog time with a polynomial number of processors. We show
that several concept classes which are polynomial-time learnable are
-learnable in constant time. Some other classes can be shown
to be -learnable in logarithmic time, but not in constant
time. Our main result shows that other classes, such as 
-fold unions
of geometrical objects in Euclidean space, which are polynomial-time
learnable by a greedy set cover technique, are -learnable
using a non-greedy technique. We also show that (unless
) several polynomial-time learnable concept
classes related to linear programming are not -learnable.
Equivalence of various parallel learning models and issues of
fault-tolerance are also discussed.
Caching and prefetching are important mechanisms for speeding up access
time to data on secondary storage. Recent work in competitive online
algorithms has uncovered several promising new algorithms for caching.
In this paper, we apply a form of the competitive philosophy for the
first time to the problem of prefetching to develop an optimal universal
prefetcher in terms of fault ratio, with particular applications to
large-scale databases and hypertext systems. Our algorithms for
prefetching are novel in that they are based on data compression
techniques that are both theoretically optimal and good in practice.
Intuitively, in order to compress data effectively, you have to be able
to predict future data well, and thus good data compressors should be
able to predict well for purposes of prefetching. We show for powerful
models such as Markov sources and 
th order Markov sources that the
page fault rates incurred by our prefetching algorithms are optimal in
the limit for almost all sequences of page accesses.
An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem is to use prefetching, in which we predict the user's next page requests and get those pages into cache in the background. Current databases perform limited prefetching using techniques derived from older virtual memory systems. A novel idea of using data compression techniques for prefetching was recently advocated by Vitter in Krishnan in which the prefetchers based on the Lempel-Ziv data compressor (the UNIX compress command) were shown theoretically to be optimal in the limit. In this paper we analyze the practical aspects of using data compression techniques for prefetching. We adapt three well-known data compressors to get three simple, deterministic, and universal prefetchers. We simulate our prefetchers on sequences of page accesses derived from the OO1 and OO7 benchmarks and from CAD applications, and demonstrate significant reductions in fault-rate. We examine the important issues of cache replacement, size of the data structure used by the prefetcher, and problems arising from bursts of “fast” page requests (that leave virtually no time between adjacent requests for prefetching and book keeping). We conclude that prediction for prefetching based on data compression techniques holds great promise.
Response time delays caused by I/O is a major problem in many systems and database applications. Prefetching and cache-replacement methods are attracting renewed attention because of their success in avoiding costly I/Os. Prefetching can be looked upon as a type of online sequential prediction, where the predictions must be accurate as well as made in a computationally efficient way. Unlike other online problems, prefetching cannot admit a competitive analysis, since the optimal offline prefetcher incurs no cost when it knows the future page requests. Previous analytical work on prefetching by Vitter and Krishnan consisted of modeling the user as a probabilistic Markov source.
In this paper, we look at the much stronger form of worst-case analysis and derive a randomized algorithm that we prove analytically converges almost surely to the optimal fault rate in the worst case for every sequence of page request with respect to the important class of finite state prefetchers. In particular, we make no assumption about how the sequence of page requests is generated. This analysis model can be looked upon as a generalization of the competitive framework, in that it compares an online algorithm in a worst-case manner over all sequences against a powerful yet non-clairvoyant opponent. We simultaneously achieve the computational goal of implementing our prefetcher in optimal constant expected time per prefetched page, using the optimal dynamic discrete random variate generator of Matias, Vitter, and Ni.
We examine the complexity of testing different program constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik-Chervonenkis dimension, and applying it to classes of programs, where all programs in a class share the same syntactic structure. VCP-dimension gives bounds on the number of test points needed to determine that a program is approximately correct, so by studying it for a class of programs we gain insight into the difficulty of testing the program construct represented by the class. We investigate the VCP-dimension of straight line code, if-then-else statements, and for loops. We also compare the VCP-dimension of nested and sequential if-then-else statements as well as that of two types of for loops with embedded if-then-else statements. Finally, we perform an empirical study to estimate the expected complexity of straight line code.
A memory-based learning system is an extended memory management system
that decomposes the input space either statically or dynamically into
subregions for the purpose of storing and retrieving functional
information. The main generalization techniques employed by memory-based
learning systems are the nearest-neighbor search, space decomposition
techniques, and clustering. Research on memory-based learning is still
in its early stage. In particular, there are very few rigorous
theoretical results regarding memory requirement, sample size, expected
performance, and computational complexity. In this paper, we propose a
model for memory-based learning and use it to analyze several
methods -- 
-covering, hashing, clustering, tree-structured
clustering, and receptive-fields -- for learning smooth functions. The
sample size and system complexity are derived for each method. Our
model is built upon the generalized PAC learning model of Haussler and
is closely related to the method of vector quantization in data
compression. Our main result is that we can build memory-based learning
systems using new clustering algorithms of Lin and Vitter to PAC-learn
in polynomial time using only polynomial storage in typical situations.
In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one approach, the effects of accumulated error are eliminated by the use of local sensing methods that never mislead but occasionally fail to produce an answer. In another approach, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems.
In the single rent-to-buy decision problem, without a priori
knowledge of the amount of time a resource will be used we need to
decide when to buy the resource, given that we can rent the resource
for $1 per unit time or buy it once and for all for $
. In this
paper we study algorithms that make a sequence of single rent-to-buy
decisions, using the assumption that the resource use times are
independently drawn from an unknown probability distribution. Our
study of this rent-to-buy problem is motivated by important systems
applications, specifically, problems arising from deciding when to
spindown disks to conserve energy in mobile computers [DKM, LKH,
MDK], thread blocking decisions during lock acquisition in
multiprocessor applications [KLM], and virtual circuit holding times
in IP-over-ATM networks [KLP, SaK].
We develop a provably optimal and computationally efficient algorithm
for the rent-to-buy problem and evaluate its practical merit for the
disk spindown scenario via simulation studies. Our algorithm uses
time and space, and its expected cost for the 
th
resource use converges to optimal as
, for any
bounded probability distribution on the resource use
times. Alternatively, using 
time and space, the algorithm
almost converges to optimal.
We describe the results of simulating our algorithm for the disk
spindown problem using disk access traces obtained from an HP
workstation environment. We introduce the natural notion of
effective cost which merges the effects of energy
conservation and response time performance into one metric based on a
user specified parameter 
, the relative importance of response time
to energy conservation. (The buy cost varies linearly with .)
We observe that by varying , we can model the tradeoff between
power and response time well. We also show that our algorithm is best
in terms of effective cost for almost all values of , saving
effective cost by 6-25% over the optimal online algorithm in the
competitive model (i.e., the 2-competitive algorithm that spins down
the disk after waiting seconds). In addition, for small values
of (corresponding to when saving energy is critical), our
algorithm when compared against the optimal online algorithm in the
competitive model reduces excess energy by 17-60%, and when compared
against the 5 second threshold reduces excess energy by 6-42%.
We consider a cache shared by several concurrently running application
processes and propose a provably efficient application-controlled
global strategy for the shared cache. Using future information
implicitly in the form of good decisions by application processes, we
are able to break through the 
lower bound on competitive ratio
proved for classical paging for a -sized cache.
For a size- cache shared by 
application processes that always
make good cache replacement decisions, we develop an online
application-controlled paging algorithm with a competitive ratio of
. Typically, is much smaller than , perhaps by
several orders of magnitude. Our competitive ratio improves upon the
competitive ratio achieved by Cao et al. We show
for this problem that no online algorithm 
can have a competitive
ratio better than 
even if the application processes aiding
have perfect knowledge of individual request sequences. Our results
are with respect to a worst-case interleaving of the individual request
sequences of the applications.
We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm is not only fair, but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.
Success of commercial query optimizers and database management systems (object-oriented or relational) depend on accurate cost estimation of various query reorderings [BGI]. Estimating predicate selectivity, or the fraction of rows in a database that satisfy a selection predicate, is key to determining the optimal join order. Previous work has concentrated on estimating selectivity for numeric fields [ASW, HaSa, IoP, LNS, SAC, WVT]. With the popularity of textual data being stored in databases, it has become important to estimate selectivity accurately for alphanumeric fields. A particularly problematic predicate used against alphanumeric fields is the SQL LIKE predicate [Dat]. Techniques used for estimating numeric selectivity are not suited for estimating alphanumeric selectivity.
In this paper, we study for the first time the problem of estimating alphanumeric selectivity in the presence of wildcards. Based on the intuition that the model built by a data compressor on an input text encapsulates information about common substrings in the text, we develop a technique based on the suffix tree data structure to estimate alphanumeric selectivity. In a statistics generation pass over the database, we construct a compact suffix tree-based structure from the columns of the database. We then look at three families of methods that utilize this structure to estimate selectivity during query plan costing, when a query with predicates on alphanumeric attributes contains wildcards in the predicate.
We evaluate our methods empirically in the context of the TPC-D benchmark. We study our methods experimentally against a variety of query patterns and identify five techniques that hold promise.
We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread applicability to key I/O-bound applications such as external merging and concurrent playback of multiple video streams. Two realistic lookahead models, global lookahead and local lookahead, are defined. Algorithms NOM and GREED based on these two forms of lookahead are analyzed for shared buffer and distributed buffer configurations, both of which occur frequently in existing systems. An important aspect of our work is that we show how to implement both the models of lookahead in practice using the simple techniques of forecasting and flushing.
Given a 
-disk parallel I/O system and a globally shared I/O buffer
that can hold up to 
disk blocks, we derive a lower bound of
on the competitive ratio of any deterministic
online prefetching algorithm with 
lookahead. NOM is shown to match
the lower bound using global -block lookahead. In contrast, using only
local lookahead results in an 
competitive ratio. When the
buffer is distributed into portions of 
blocks each, the algorithm
GREED based on local lookahead is shown to be optimal, and NOM is within a
constant factor of optimal. Thus we provide a theoretical basis for the
intuition that global lookahead is more valuable for prefetching in the
case of a shared buffer configuration whereas it is enough to provide local
lookahead in case of the distributed configuration. Finally, we analyze the
performance of these algorithms for reference strings generated by a
uniformly-random stochastic process and we show that they achieve the
minimal expected number of I/Os. These results also give bounds on the
worst-case expected performance of algorithms which employ randomization in
the data layout.
Query optimization is an integral part of relational database
management systems. One important task in query optimization is
selectivity estimation, that is, given a query , we need to
estimate the fraction of records in the database that satisfy .
Many commercial database systems maintain histograms to approximate
the frequency distribution of values in the attributes of relations.
In this paper, we present a technique based upon a multiresolution wavelet decomposition for building histograms on the underlying data distributions, with applications to databases, statistics, and simulation. Histograms built on the cumulative data distributions give very good approximations with limited space usage. We give fast algorithms for constructing histograms and using them in an on-line fashion for selectivity estimation. Our histograms also provide quick approximate answers to OLAP queries when the exact answers are not required. Our method captures the joint distribution of multiple attributes effectively, even when the attributes are correlated. Experiments confirm that our histograms offer substantial improvements in accuracy over random sampling and other previous approaches.
Classification is a key function of many “business intelligence”
toolkits and a fundamental building
block in data mining.
Immense data may be needed to train a classifier for good accuracy.
The state-of-art classifiers need an in-memory data structure of size 
, where 
is the size of the training data, to achieve
efficiency.
For large data sets, such a data structure will not fit in the internal
memory.
The best previously known classifier
does a quadratic number of I/Os for large .
In this paper, we propose a novel classification algorithm (classifier) called MIND (MINing in Databases). MIND can be phrased in such a way that its implementation is very easy using the extended relational calculus SQL, and this in turn allows the classifier to be built into a relational database system directly. MIND is truly scalable with respect to I/O efficiency, which is important since scalability is a key requirement for any data mining algorithm.
We built a prototype of MIND in the relational database manager DB2 and benchmarked its performance. We describe the working prototype and report the measured performance with respect to the previous method of choice. MIND scales not only with the size of the datasets but also with the number of processors on an IBM SP2 computer system. Even on uniprocessors, MIND scales well beyond the dataset sizes previously published for classifiers. We also give some insights that may have an impact on the evolution of the extended relational calculus SQL.
There has recently been an explosion of interest in the analysis of data in data warehouses in the field of On-Line Analytical Processing (OLAP). Data warehouses can be extremely large, yet obtaining quick answers to queries is important. In many situations, obtaining the exact answer to an OLAP query is prohibitively expensive in terms of time and/or storage space. It can be advantageous to have fast, approximate answers to queries.
In this paper, we present an I/O-efficient technique based upon a multiresolution wavelet decomposition that yields an approximate and space-efficient representation of the data cube, which is one of the core OLAP operators. We build our compact data cube on the logarithms of the partial sums of the raw data values of a multidimensional array. We get excellent approximations for on-line range-sum queries with limited space usage and computational cost. Multiple data cubes can be handled simultaneously. Each query can generally be answered, depending upon the accuracy supported, in one I/O or a small number of I/Os. Experiments show that our method performs significantly better than other approximation techniques such as histograms and random sampling.
Computing multidimensional aggregates in high dimensions is a performance bottleneck for many OLAP applications. Obtaining the exact answer to an aggregation query can be prohibitively expensive in terms of time and/or storage space in a data warehouse environment. It is advantageous to have fast, approximate answers to OLAP aggregation queries.
In this paper, we present a novel method that provides approximate answers to high-dimensional OLAP aggregation queries in massive sparse data sets in a time-efficient and space-efficient manner. We construct a compact data cube, which is an approximate and space-efficient representation of the underlying multidimensional array, based upon a multiresolution wavelet decomposition. In the on-line phase, each aggregation query can generally be answered using the compact data cube in one I/O or a small number of I/Os, depending upon the desired accuracy.
We present two I/O-efficient algorithms to construct the compact data cube for the important case of sparse high-dimensional arrays, which often arise in practice. The traditional histogram methods are infeasible for the massive high-dimensional data sets in OLAP applications. Previously developed wavelet techniques are efficient only for dense data. Our on-line query processing algorithm is very fast and capable of refining answers as the user demands more accuracy. Experiments on real data show that our method provides significantly more accurate results for typical OLAP aggregation queries than other efficient approximation techniques such as random sampling.
In this paper, we introduce an efficient method for the dynamic maintenance of wavelet-based histograms (and other transform-based histograms). Previous work has shown that wavelet-based histograms provide more accurate selectivity estimation than traditional histograms, such as equi-depth histograms. But since wavelet-based histograms are built by a nontrivial mathematical procedure, namely, wavelet transform decomposition, it is hard to maintain the accuracy of the histogram when the underlying data distribution changes over time. In particular, simple techniques, such as split and merge, which works well for equi-depth histograms, and updating a fixed set of wavelet coefficients, are not suitable here.
We propose a novel approach based upon probabilistic counting and sampling to maintain wavelet-based histograms with very little online time and space costs. The accuracy of our method is robust to changing data distributions, and we get a considerable improvement over previous methods for updating transform-based histograms. A very nice feature of our method is that it can be extended naturally to maintain multidimensional wavelet-based histograms, while traditional multidimensional histograms can be less accurate and prohibitively expensive to build and maintain.
The extensible mark-up language (XML) is gaining widespread use as a format for data exchange and storage on the World Wide Web. Queries over XML data require accurate selectivity estimation of path expressions to optimize query execution plans. Selectivity estimation of XML path expression is usually done based on summary statistics about the structure of the underlying XML repository. All previous methods require an off-line scan of the XML repository to collect the statistics.
In this paper, we propose XPathLearner, a method for estimating selectivity of the most commonly used types of path expressions without looking at the XML data. XPathLearner gathers and refines the statistics using query feedback in an on-line manner and is especially suited to queries in Internet scale applications since the underlying XML repositories are likely to be inaccessible or too large to be scanned entirely. Besides the on-line property, our method also has two other novel features: (a) XPathLearner is workload aware in collecting the statistics and thus can be dramatically more accurate than the more costly off-line method under tight memory constraints, and (b) XPathLearner automatically adjusts the statistics using query feedback when the underlying XML data change. We show empirically the estimation accuracy of our method using several real data sets.
We investigate the problem of smoothing multiplexed network traffic, when either a streaming server transmits data to multiple clients, or a server accesses data from multiple storage devices or other servers. We introduce efficient algorithms for lexicographically optimally smoothing the aggregate bandwidth requirements over a shared network link. In the data transmission problem, we consider the case in which the clients have different buffer capacities but no bandwidth constraints, or no buffer capacities but different bandwidth constraints. For the data access problem, we handle the general case of a shared buffer capacity and individual network bandwidth constraints. Previous approaches in the literature for the data access problem handled either the case of only a single stream or did not compute the lexicographically optimal schedule.
Lexicographically optimal smoothing (lexopt smoothing) has several advantages. By provably minimizing the variance of the required aggregate bandwidth, maximum resource requirements within the network become more predictable, and useful resource utilization increases. Fairness in sharing a network link by multiple users can be improved, and new requests from future clients are more likely to be successfully admitted without the need for frequently rescheduling previously accepted traffic. Efficient resource management at the network edges can better meet quality of service requirements without restricting the scalability of the system.
Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries. These selectivities are typically used for cost-based query optimization. While the problem of building an accurate histogram for a given attribute or attribute set has been well-studied, little attention has been given to the problem of building and tuning a set of histograms collectively for multidimensional queries in a self-managed manner based only on query feedback.
In this paper, we present SASH, a Self-Adaptive Set of Histograms that addresses the problem of building and maintaining a set of histograms. SASH uses a novel two-phase method to automatically build and maintain itself using query feedback information only. In the online tuning phase, the current set of histograms is tuned in response to the estimation error of each query in an online manner. In the restructuring phase, a new and more accurate set of histograms replaces the current set of histograms. The new set of histograms (attribute sets and memory distribution) is found using information from a batch of query feedback. We present experimental results that show the effectiveness and accuracy of our approach.
Parallel disks provide a cost effective way of speeding up
I/Os in applications that work with large amounts of data.
The main challenge is to achieve as much parallelism as
possible, using prefetching to avoid bottlenecks in disk
access.
Efficient algorithms have been developed for some particular
patterns of accessing the disk blocks. In this paper, we
consider general request sequences. When the request
sequence consists of unique block requests, the problem is
called prefetching and is a well-solved problem for
arbitrary request sequences. When the reference sequence can
have repeated references to the same block, we need to
devise an effective caching policy as well. While optimum
offline algorithms have been recently designed for the
problem, in the online case, no effective algorithm was
previously known.
Our main contribution is a deterministic online algorithm
threshold-LRU which achieves
competitive
ratio and a randomized online algorithm threshold-MARK which
achieves
competitive ratio for
the caching/prefetching problem on the parallel disk model
(PDM), where is the number of disks, is the size of fast
memory buffer, and 
is the amount of lookahead
available in the request sequence. The best-known lower
bound on the competitive ratio is
for
lookahead 
in both models. We also show that if the
deterministic online algorithm is allowed to have twice the
memory of the offline then a tight competitive ratio of
can be achieved. This problem generalizes the
well-known paging problem on a single disk to the parallel
disk model.
Query optimization in IBM's System RX, the first truly hybrid relational-XML data management system, requires accurate selectivity estimation of path-value pairs, i.e., the number of nodes in the XML tree reachable by a given path with the given text value. Previous techniques have been inadequate, because they have focused mainly on the tag-labeled paths (tree structure) of the XML data. For most real XML data, the number of distinct string values at the leaf nodes is orders of magnitude larger than the set of distinct rooted tag paths. Hence, the real challenge lies in accurate selectivity estimation of the string predicates on the leaf values reachable via a given path.
In this paper, we present CXHist, a novel workload-aware histogram technique that provides accurate selectivity estimation on a broad class of XML string-based queries. CXHist builds a histogram in an on-line manner by grouping queries into buckets using their true selectivity obtained from query feedback. The set of queries associated with each bucket is summarized into feature distributions. These feature distributions mimic a Bayesian classifier that is used to route a query to its associated bucket during selectivity estimation. We show how CXHist can be used for two general types of (path,string) queries: exact match queries and substring match queries. Experiments using a prototype show that CXHist provides accurate selectivity estimation for both exact match queries and substring match queries.
We consider the natural extension of the well-known single
disk caching problem to the parallel disk I/O model (PDM)
[17]. The main challenge is to achieve as much parallelism
as possible and avoid I/O bottlenecks. We are given a fast
memory (cache) of size memory blocks along with a
request sequence
where
each block 
resides on one of disks. In each
parallel I/O step, at most one block from each disk can be
fetched. The task is to serve in the minimum number of
parallel I/Os. Thus, each I/O is analogous to a page fault.
The difference here is that during each page fault, up to
blocks can be brought into memory, as long as all of the new
blocks entering the memory reside on different disks. The
problem has a long history. Note that this problem is
non-trivial even if all requests in 
are unique.
This restricted version is called read-once. Despite the
progress in the online ver- sion and read-once version, the
general online problem still remained open. Here, we provide
comprehensive results with a full general solution for the
problem with asymptotically tight competitive ratios.
To exploit parallelism, any parallel disk algorithm needs a
certain amount of lookahead into future requests. To provide
effective caching, an online algorithm must achieve 
competitive ratio. We show a lower bound that states, for
lookahead 
, that any online algorithm must be
-competitive. For lookahead 
greater than
, where is a constant, the tight
upper bound of
on competitive ratio is
achieved by our algorithm SKEW. The previous algorithm tLRU
was
competitive and this was also shown to
be tight for an LRU-based strategy. We achieve the tight
ratio using a fairly different strategy than LRU. We also
show tight results for randomized algorithms against
oblivious adversary and give an algorithm achieving better
bounds in the resource augmentation model.
Classification and recognition of graph data are crucial problems in many fields, such as bioinformatics, chemoinformatics, and data mining. In graph kernel-based classification methods, the similarity among substructures is not fully considered; in addition, poorly discriminative substructures will affect the graph classification accuracy. To improve the graph classification accuracy, we propose a feature reduction algorithm based on semantic similarity for graph classification in this paper. In the algorithm, we first learn vector representations of subtree patterns using neural language models and then merge semantically similar subtree patterns into a new feature. We then provide a new feature discrimination score to select highly discriminative features. Comprehensive experiments on real datasets demonstrate that the proposed algorithm achieves a significant improvement in classification accuracy over compared graph classification methods.