# US 2017/0286190 A1 · Structural and temporal semantics heterogeneous information network (hin) for process trace clustering

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286190 A1
- Document ID: US20170286190A1
- Status: Published application
- Kind: A1
- Application number: 15/482,488
- Filed: 2017-04-07
- Published: 2017-10-05
- Earliest claimed: 2016-03-31
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: VATCHE ISHAKIAN; VINOD MUTHUSAMY; ALEKSANDER SLOMINSKI
- Web page: https://patentgrep.com/patent/US20170286190A1

## CPC

- G06F 9/542: {Event management; Broadcasting; Multicasting; Notifications}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06Q 10/0633: Workflow analysis
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A method of generating process trace clusters includes receiving a set of process traces, where a process trace is an application level event log from a computer system; receiving an identification of node types and edge types of the application event log to generate a heterogeneous information network (HIN) graph, where a temporal node type value is a difference between a current system time and a reference timestamp divided by a user chosen time granularity parameter, performing dimension reduction of the HIN to generate clusters of new event types, generating a set of meta-paths that connect nodes of a same reduced event type in the application event log, calculating similarities between process traces using the new event type clusters, and clustering the set of process traces to generate a plurality of disjoint graph models of processes in the application event log based on the clusters of new event types.

## Claims

### Claim 1

A computer-implemented method of generating process trace clusters, the method executed by a computer comprising the steps of:
receiving a set of process traces, wherein a process trace is an application level event log from a computer system;
receiving an identification of node types and edge types of the application event log to generate a heterogeneous information network (HIN) graph of the application event log, wherein node types of said HIN include events, traces and temporal nodes, wherein each trace is a finite sequence of event type nodes, wherein a temporal node type value is set to be a difference between a current system time and a reference timestamp, divided by a user chosen time granularity parameter,
performing dimension reduction of the HIN by reducing a number of event types of the set of input traces to generate clusters of new event types;
generating a set of meta-paths that connect nodes of a same reduced event type in the application event log;
calculating similarities between process traces using the new event type clusters; and
clustering the set of process traces to generate a plurality of disjoint partitions based on the clusters of new event types, wherein each partition is a graph model of a process in the application event log.

### Claim 2 (depends on 1)

The method of claim 1, further comprising repeating said steps of receiving an identification of node types and edge types, generating a set of meta-paths, performing dimension reduction, calculating similarities, and clustering the set of process traces using one of said plurality of disjoint partitions as input.

### Claim 3 (depends on 1)

The method of claim 1, wherein edge types of said HIN are associated with different types of interactions between different node types, wherein an edge relationship between a trace node type and a temporal node type includes a starts-on edge that indicates a start time of a trace, an ends-on edge that indicates an end time of a trace, and a joined-on edge that indicates a time when a particular resource became available to a trace.

### Claim 4 (depends on 1)

The method of claim 1, wherein calculating similarities between process traces using the new event type clusters comprises calculating one or more of a structural metapath between similar new event type clusters and a temporal metapath between similar new event type clusters.

### Claim 5 (depends on 4)

The method of claim 4, wherein a structural path similarity between each pair of events type clusters connected by a meta-path P is calculated using
σ
P

(
e
j
,
e
k
)
=
2
×
|
Γ
P

(
e
j
,
e
k
)
|
|
Γ
P

(
e
j
,
e
j
)
|
+
|
Γ
P

(
e
k
,
e
k
)
|
wherein ej and ek represent event-type clusters and ΓP(ej,ek) is a set of paths from ej to ek following meta-path P, and |ΓP( )| represents a cardinality of the set of paths represented by ΓP( ).

### Claim 6 (depends on 5)

The method of claim 5, wherein a temporal path similarity between each pair of events type clusters connected by a meta-path P is calculated from SeqPathSim (x,y) of traces x=(a1, a2, . . . , am) and y=(b1, b2, . . . , bn), wherein ai, bi are event type clusters, wherein SeqPathSim(x,y) generates a matrix vmn(x,y) defined by
v
m
,
n

(
x
,
y
)
=
{
v
m
-
1
,
n
-
1

(
x
,
y
)
for


a
m
=
b
n
,
min
v

for


a
m
≠
b
n
,


with

:


min
v
=
{
v
m
-
1
,
n

(
x
,
y
)
+
σ
P
EE

(
a
m
,
b
n
)
v
m
,
n
-
1

(
x
,
y
)
+
σ
P
EE

(
a
m
,
b
n
)
v
m
-
1
,
n
-
1

(
x
,
y
)
+
σ
P
ERE
,
P
ETE

(
a
m
,
b
n
)
.

### Claim 7 (depends on 6)

The method of claim 6, further comprising combining meta-path similarities using the following formula:
σ*(x,y)=ΣPiwi×σPi(x,y),
where σPi(x,y) is a similarity between two traces x and y via meta-path Pi, and wi is a weight associated with meta-path Pi.

### Claim 8

A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for generating process trace clusters, the method executed by a computer comprising the steps of:
receiving a set of process traces, wherein a process trace is an application level event log from a computer system;
receiving an identification of node types and edge types of the application event log to generate a heterogeneous information network (HIN) graph of the application event log, wherein node types of said HIN include events, traces and temporal nodes, wherein each trace is a finite sequence of event type nodes, wherein a temporal node type value is set to be a difference between a current system time and a reference timestamp, divided by a user chosen time granularity parameter;
performing dimension reduction of the HIN by reducing a number of event types of the set of input traces to generate clusters of new event types;
generating a set of meta-paths that connect nodes of a same reduced event type in the application event log;
calculating similarities between process traces using the new event type clusters; and
clustering the set of process traces to generate a plurality of disjoint partitions based on the clusters of new event types, wherein each partition is a graph model of a process in the application event log.

### Claim 9 (depends on 8)

The computer readable program storage device of claim 8, the method further comprising repeating said steps of receiving an identification of node types and edge types, generating a set of meta-paths, performing dimension reduction, calculating similarities, and clustering the set of process traces using one of said plurality of disjoint partitions as input.

### Claim 10 (depends on 8)

The computer readable program storage device of claim 8, wherein edge types of said HIN are associated with different types of interactions between different node types, wherein an edge relationship between a trace node type and a temporal node type includes a starts-on edge that indicates a start time of a trace, an ends-on edge that indicates an end time of a trace, and a joined-on edge that indicates a time when a particular resource became available to a trace.

### Claim 11 (depends on 8)

The computer readable program storage device of claim 8, wherein calculating similarities between process traces using the new event type clusters comprises calculating one or more of a structural metapath between similar new event type clusters and a temporal metapath between similar new event type clusters.

### Claim 12 (depends on 11)

The computer readable program storage device of claim 11, wherein a structural path similarity between each pair of events type clusters connected by a meta-path P is calculated using
σ
P

(
e
j
,
e
k
)
=
2
×
|
Γ
P

(
e
j
,
e
k
)
|
|
Γ
P

(
e
j
,
e
j
)
|
+
|
Γ
P

(
e
k
,
e
k
)
|
wherein ej and ek represent event-type clusters and ΓP(ej,ek) is a set of paths from ej to ek following meta-path P, and |ΓP( )| represents a cardinality of the set of paths represented by ΓP( ).

### Claim 13 (depends on 12)

The computer readable program storage device of claim 12, wherein a temporal path similarity between each pair of events type clusters connected by a meta-path P is calculated from SeqPathSim(x,y) of traces x=(a1, a2, . . . , am) and y=(b1, b2, . . . , bn), wherein ai, bi are event type clusters, wherein SeqPathSim(x,y) generates a matrix vmn(x,y) defined by
v
m
,
n

(
x
,
y
)
=
{
v
m
-
1
,
n
-
1

(
x
,
y
)
for


a
m
=
b
n
,
min
v

for


a
m
≠
b
n
,


with

:


min
v
=
{
v
m
-
1
,
n

(
x
,
y
)
+
σ
P
EE

(
a
m
,
b
n
)
v
m
,
n
-
1

(
x
,
y
)
+
σ
P
EE

(
a
m
,
b
n
)
v
m
-
1
,
n
-
1

(
x
,
y
)
+
σ
P
ERE
,
P
ETE

(
a
m
,
b
n
)
.

### Claim 14 (depends on 13)

The computer readable program storage device of claim 13, the method further comprising combining meta-path similarities using the following formula:
σ*(x,y)=ΣPiwi×σPi(x,y),
where σPi(x,y) is a similarity between two traces x and y via meta-path Pi, and wi is a weight associated with meta-path Pi.