Advancement: Local and Global Subgraph Counting in Simple and Typed Graphs

Speaker Name: 
Noujan Pashanasangi
Speaker Title: 
PhD Candidate
Start Time: 
Friday, November 22, 2019 - 10:00am
Baskin Engineering, Room 318


Subgraph counting is the problem of counting the frequency of small subgraph "patterns" in large networks. Subgraph counting, also called motif analysis, is a fundamental technique in network analysis with applications in a broad range of domains, mostly in bioinformatics and social networks. The (global) subgraph counting problem asks for the number of copies of a pattern, but many applications require local subgraph counts (also called vertex orbit counts), where for each vertex v, we are interested in the number of copies of a pattern incident to v. We present EVOKE, an algorithmic framework for vertex orbit counting for k-vertex patterns for k <= 5 , which is typically hundreds of times faster than the previous state of the art algorithms. EVOKE scales to graphs with tens of millions of edges, which is beyond the reach of previous algorithms.

In a classic result, Chiba and Nishizeki (SICOMP 85) implicitly gave linear time algorithms for counting all subgraphs of size up to 4 in bounded degeneracy graphs. We give linear time algorithms for counting all  k-vertex subgraph patterns for k < 6, and prove that for all k >= 6, it cannot be solved even in near-linear time, assuming a standard conjecture in fine-grained complexity. We also discuss future directions for fully characterizing all subgraph patterns which are countable in linear time.

Typical work in subgraph and orbit counting assume the input graph to be simple and undirected. But many graphs observed in real world have vertices and edges of different types. Our subgraph and orbit counting approach has the possibility to be generalized to graphs with typed vertices. This gives us a promising approach for building a system for motif analysis in attributed networks.

Event Type: 
Seshadhri Comandur
Graduate Program: 
Computer Science PhD