Distributed Subgraph Counting: A General Approach

Speaker: Professor Jeffrey Xu YU
         Department of Systems Engineering and Engineering Management
         The Chinese University of Hong Kong

Title:  "Distributed Subgraph Counting: A General Approach"

Date:   Monday, 27 September 2021

Time:   4:00pm - 5:00pm

Venue:  Lecture Theater F (Leung Yat Sing Lecture Theater)
        (near lift 25/26, HKUST)

Zoom link:
https://hkust.zoom.us/j/95532049042?pwd=UjkvVG9oZEhqZ1A5M2NJbWplelRJQT09

Meeting ID:     955 3204 9042
Passcode:       CSE

**Note to CSE PGs with NIHK status, please attend the seminar via zoom**


Abstract:

Local subgraph counting has played an important role to characterize
high-order local structures that exhibit in a large graph, and has been
widely used in denser and relevant communities mining, graphlet degree
distribution, discriminative features selection for link prediction,
relational classification and recommendation.  In brief, the problem is to
count the occurrences of a user-given pattern graph p around every node v
in a large data graph G, when v matches to a given orbit o in p, where the
orbit serves the purpose as a center. In general, the orbit can be a node,
an edge, or a set of nodes in p.  In the literature, almost all the
existing work support a k-node pattern graph, for k <= 5, with either 1
node orbit or 1 edge orbit. Their approaches are difficult to support
larger k due to the fact that subgraph counting is to count by subgraph
isomorphism. In this talk, we discuss a new general approach to count
larger k pattern graphs with any orbits selected. The key idea behind our
approach is that we do local subgraph counting by homomorphism counting,
which can be solved by relational algebra using joins, group-by and
aggregation. By homomorphism counting, we do local subgraph counting by
eliminating counts for those that are not subgraph isomerism matchings
from the total count for any possible matchings. We have developed a
distributed system named DISC on top of Spark, and we report some
experimental results in this talk.


******************
Biography:

Dr Jeffrey Xu Yu is a Professor in the Department of Systems Engineering
and Engineering Management, The Chinese University of Hong Kong. His
current main research interests include graph algorithms, graph processing
systems, and query processing in database systems. Dr. Yu served as an
Information Director and a member in ACM SIGMOD executive committee
(2007-2011), an associate editor of IEEE Transactions on Knowledge and
Data Engineering (2004-2008), and an associate editor in VLDB Journal
(2007-2013). Currently he servers as an associate editor of ACM
Transactions on Database Systems (TODS), WWW Journal, Data Science and
Engineering, the International Journal of Cooperative Information Systems,
the Journal on Health Information Science and Systems (HISS), and Journal
of Information Processing. Dr. Yu served/serves in many organization
committees and program committees in international conferences/workshops
including PC Co-chair of APWeb'04, WAIM'06, APWeb/WAIM'07, WISE'09,
PAKDD'10, DASFAA'11, ICDM'12, NDBC'13, ADMA'14, CIKM'15, Bigcomp17,
DSAA'19, CIKM'19, and DASFAA'20, and conference general Co-chair of
APWeb'13, ICDM'18, and ADC'22.