Ex Parte Yan et al

Board of Patent Appeals and Interferences

Nov 24, 2010

10835729 (B.P.A.I. Nov. 24, 2010)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
10/835,729 04/30/2004 Xifeng Yan YOR920040013US1 9458
48062 7590 11/24/2010
RYAN, MASON & LEWIS, LLP
1300 POST ROAD
SUITE 205
FAIRFIELD, CT 06824
EXAMINER
LEE, WILSON
ART UNIT PAPER NUMBER
2163
MAIL DATE DELIVERY MODE
11/24/2010 PAPER
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
____________________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________________

Ex parte XIFENG YAN and PHILIP SHI-LUNG YU
____________________

Appeal 2009-0058321
Application 10/835,729
Technology Center 2100
____________________

Before JOSEPH L. DIXON, LANCE LEONARD BARRY, and
JEAN R. HOMERE, Administrative Patent Judges.

HOMERE, Administrative Patent Judge.

DECISION ON APPEAL2

1 Filed April 30, 2004. The real party in interest is International Business
Machines. (App. Br. 1.)
2 The two-month time period for filing an appeal or commencing a civil
action, as recited in 37 C.F.R. § 1.304, or for filing a request for rehearing,
as recited in 37 C.F.R. § 41.52, begins to run from the “MAIL DATE”
(paper delivery mode) or the “NOTIFICATION DATE” (electronic delivery
mode) shown on the PTOL-90A cover letter attached to this decision.

Appeal 2009-005832
Application 10/835,729

2
I. STATEMENT OF THE CASE
Appellants appeal under 35 U.S.C. § 134(a) (2002) from the
Examiner’s final rejection of claims 1-21. (App. Br. 2.) We have
jurisdiction under 35 U.S.C. § 6(b) (2008).
We affirm-in-part.
Appellants’ Invention
Appellants invented a method and system for indexing graphs in a
database by using frequent subgraphs extracted therefrom (Spec. 2, ll. 19-
24.)
Illustrative Claim
Independent claim 1 further illustrates the invention. It reads as
follows:
1. A method for indexing graphs in a database, the graphs
comprising graphic data, the method comprising the steps of:

identifying frequent subgraphs among one or more of the
graphs in the database, the frequent subgraphs appearing in at
least a threshold number of the graphs in the database; and

using one or more of the frequent subgraphs to create an
index of the graphs in the database.

Prior Art Relied Upon
The Examiner relies on the following prior art as evidence of
unpatentability:
Inokuchi US 2003/0225743 A1 Dec. 4, 2003

Appeal 2009-005832
Application 10/835,729

3
Rejection on Appeal
The Examiner rejects the claims on appeal as follows:
Claims 1-21 stand rejected under 35 U.S.C. § 102(e) as being
anticipated by Inokuchi.

Appellants’ Contentions
Appellants contend that Inokuchi does not teach using a frequent
subgraph to create an index of a graph in a database, as recited in
independent claim 1. (App. Br. 4.) According to Appellants, while Inokuchi
discloses an index for determining whether an algorithm should extract
frequent subgraphs from a graph database in the ascending order of their
sizes, the disclosed index is a simple threshold value as opposed to a data
structure used to facilitate the finding of information. (Id. 4-5, Reply Br. 2-
3) Further, Appellants contend that the disclosed extraction of graph data in
the ascending order does not necessarily imply that an index is used to
extract such data. (Id.)

Examiner’s Findings and Conclusions
The Examiner finds that Inokuchi’s disclosure of extracting frequent
graphs in the ascending order and using a specific subgraph threshold value
as an index to determine whether a graph should be extracted, teaches the
disputed limitations. (Ans. 6-7.)

Appeal 2009-005832
Application 10/835,729

4
II. ISSUE
Have Appellants shown that the Examiner erred in finding that
Inokuchi teaches using a frequent subgraph to create an index of a graph in a
database, as recited in independent claim 1?

III. FINDINGS OF FACT
The following Findings of Fact (FF) are shown by a preponderance of
the evidence.

Appellants’ Specification
1. Appellants’ Specification indicates that frequent subgraphs are
subgraphs that appear at least in a threshold number of graphs in a database,
and that such subgraphs are used to create an index by enumerating and
selecting features in the graph database to form a graph feature set F. (Spec.
5, ll 5-11.)

Inokuchi
2. Inokuchi discloses an Apriori-based Graph Mining (AGM)
algorithm for extracting from a graph structured database all graph structures
included therein as an induced subgraph having a support level equal or
greater than a specific threshold value. The support level of the graph is used
as an index for determining whether the graph data should be extracted from
the database. (Abstract, ¶ [0043].)
Appeal 2009-005832
Application 10/835,729

5
3. Inokuchi discloses frequent graph data are extracted in the
ascending order of their sizes. (¶ [0094].)
4. Inokuchi discloses deleting mth row and mth column from an
adjacency matrix to produce a frequent graph. (¶¶ [0103, 0107].)

IV. ANALYSIS

Claims 1 and 19-21
Based on the record before us, we find no error in the Examiner’s
anticipation rejection of independent claim 1, which calls for, in pertinent
part, using one or more frequent subgraphs to create an index of graphs in a
database. Appellants and the Examiner mainly disagree upon whether
Inokuchi’s disclosure teaches the cited limitations. We give the claims their
broadest reasonable construction in light of the specification and as
understood by an ordinarily skilled artisan. In re Am. Acad. of Sci. Tech
Ctr., 367 F.3d 1359, 1364 (Fed. Cir. 2004) (internal citations and quotations
omitted). See also Phillips v. AWH Corp., 415 F.3d 1303, 1316 (Fed. Cir.
2005) (en banc) (internal citations omitted). Our review of Appellants’
Specification indicates that frequent subgraphs (i.e. subgraphs that appear in
a specified threshold number of graphs) are identified in a graph database in
order to create an index therefor by listing and selecting corresponding graph
features from the database. (See FF 1.) We therefore construe the disputed
limitations of independent claim 1 above broadly but reasonably as, upon
identifying a subgraph that appears in a specified minimum number of
Appeal 2009-005832
Application 10/835,729

6
graphs in the graph database, using the identified subgraph to represent and
locate the graphs associated therewith in the database.3
Inokuchi discloses an algorithm that determines whether a graph
should be extracted from a graph database depending on whether the support
level of the graph meets or exceeds a specified threshold value or index.
(See FF 2.) In particular, the algorithm extracts all graph structures in the
database that are included as an induced subgraph having a frequency that
meets or exceeds the specified threshold value or index. (See id.) We find
that upon identifying the total number of graphs in the database that are
induced as a subgraph, Inokuchi’s algorithm extracts the identified graphs
from the database if the total number meets or exceeds a specified threshold.
Therefore, the graph structures extracted from the database can be
represented or located by a frequent subgraph associated therewith.
Consistent with our claim interpretation above, Inokuchi’s frequent subgraph
serves as an index for representing or locating the extracted graphs since the
subgrap lists the corresponding graph structures obtained from the database.
Consequently, we find that Inokuchi’s disclosure teaches using the frequent
subgraph to create an index for the graph structures included therein. It

3 We adopt Appellants’ proffered definition of an index as a “data structure
used to make finding information easier” (Reply Br. 3) since the cited
definition is consistent with the Specification. That is, the identified
frequent subgraph is used to quickly locate graphs associated therewith (i.e.
the subgraph is used to create an index of the associated graphs) in the graph
database.
Appeal 2009-005832
Application 10/835,729

7
follows that Appellants have not shown error in the Examiner’s finding that
Inokuchi anticipates independent claim 1.
Because Appellants argue the rejection of claims 1 and 19-21 as a
single group, claims 19-21 fall with claim 1 in accordance with 37 C.F.R.
§ 41.37(c)(1)(vii).
Claims 3, 4, and 14
Appellants argue that while Inokuchi discloses deleting graphs that
are not frequent graphs, the reference does not teach eliminating a redundant
frequent subgraph based on its size such that only one frequent subgraph
with the least number of features is retained. (Br. 6, Reply Br. 6.) In
response, the Examiner finds that Inokuchi’s disclosure of deleting a certain
row and column in an adjacency matrix of a frequent subgraph Xk teaches
deleting a redundant frequent subgraph. (Ans. 7.) We do not agree with the
Examiner. While the adjacency matrix may represent a frequent graph, we
find that the Inokuchi’s disclosure being relied upon here by the Examiner
teaches at best deleting a certain row and column from the matrix to yield a
frequent subgraph. (FF. 4.) Simply put, the deletion of data from the
frequent subgraph is not tantamount to deleting the frequent subgraph itself,
let alone a redundant one. Therefore, we find Inokuchi’s disclosure to be
devoid of any teaching that the frequent subgraph itself is a redundant one,
which is deleted to retain only a single frequent subgraph with the least
number of features. It therefore follows that Appellants have shown error in
the Examiner’s finding that Inokuchi anticipates claims 3, 4, 14, as well as
claims 15 and 16 depending therefrom.
Appeal 2009-005832
Application 10/835,729

8
Claims 6 and 7
Appellants argue that Inokuchi does not teach the use of a frequent
subgraph to thereby create an index of the graphs includes translating the
frequent subgraph into sequences, which are placed in a prefix tree. (Br. 6-7,
Reply Br. 7.) In response, the Examiner finds that Inokuchi’s disclosure of
performing numerous steps to transform an adjacent matrix Ck+1 of a
frequent graph to C’k+1 teaches the disputed limitations since C’K+1 is a
matrix where K represents row sequences. (Ans. 7-8.) We note that
Appellants’ response does not persuasively rebut the Examiner’s rejection.
Appellants are reminded that merely reciting what a claim recites or making
a general allegation of patentability is not a separate patentability argument.
See Ex parte Belinne, No. 2009-004693, slip op. at 7-8 (BPAI Aug. 10,
2009) Therefore, we find that Appellants’ mere recitation of the claim
language and re-statement of the Examiner’s position without showing
deficiencies therein does not constitute a persuasive rebuttal of the
Examiner’s rejection. (informative). It follows that Appellants have not
shown error in the Examiner’s finding that Inokuchi anticipates claims 6
and 7.
Claim 9
Appellants merely allege that Inokuchi does not teach mapping a
frequent graph to an edge sequence, and further summarily restate the
Examiner’s position without pointing out any deficiencies therein. (Br. 7,
Reply Br. 7-8.) As discussed above, we find such a response to be
Appeal 2009-005832
Application 10/835,729

9
unavailing. It follows that Appellants have not shown error in the
Examiner’s finding that Inokuchi anticipates claims 9.

Appellants did not provide separate patentability arguments for claims
2, 4, 5, 8, 10-13, 17, and 18. Therefore, they fall with claims 1, 6, 7, and 9
in accordance with 37 C.F.R. § 41.37(c)(1)(vii).

V. SUMMARY
1. Appellants have not established that the Examiner erred in rejecting
claims 1, 2, 5-13, and 17-21 under 35 U.S.C. § 102(e) as being anticipated
by Inokuchi. We therefore affirm this rejection.
2. Appellants have established that the Examiner erred in rejecting
claims 3, 4, and 14-16 under 35 U.S.C. § 102(e) as being anticipated by
Inokuchi. We therefore reverse this rejection.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv) (2009).

AFFIRMED-IN-PART

Vsh

RYAN, MASON & LEWIS, LLP
1300 POST ROAD
SUITE 205
FAIRFIELD, CT 06824