Abstract:

Graphs are an increasingly important data source. Examples include
such important graphs as the Internet and the Web. Other familiar
graphs include CAD circuits, phone records, gene sequences, city
streets, social networks and academic citations. Finding common and
frequently occurring graph patterns is therefore an important
problem and its efficient solution is useful in many applications,
from finding robust areas in networks, to finding common molecular
structures, to discovering a compact representation of the
information contained in a source which can be useful for Indexing,
and more.

Whereas data-mining in structured data focuses on frequent data
values, in semi-structured and graph data mining, the issue is
frequent labels and common specific topologies. Here, the structure
of the data is just as important as its content. We study the
problem of discovering typical patterns of graph data. The
discovery task is impacted by structural features of graph data in
a non-trivial way, making traditional data mining approaches
inapplicable. Difficulties result from the complexity of some of
the required sub-tasks, such as sub-graph isomorphism.

In this presentation we will first review the best known algorithms
for graph mining, such as FSG (A breadth-first Aprriori like)
algorithm and the gSpan (a dept-first) algorithm. We will then
present our own work on the topic, which include the Path-based
algorithm, the Diagonal FSG algorithm and a constraint-based
technique for graph mining.