[Note]Triangle Counting over Large-scale Directed Graphs

What problem?

Exact and scalable triangle counting on large-scale directed graphs, where triangles have seven different types determined by edge directions and the graph may be too large for a single machine.

Defects of previous solution

Existing solutions are mostly designed for undirected graphs.

Existing degree-based pruning methods such as NodeIter++ and EdgeIte++ can undercount triangle when multiple vertices have equal degrees, while vertex-centric approaches can generate huge numbers of candidates and severe data skew.

Core innovation

The paper proposes T-COUNT, a distributed edge-centric algorithm with three main ideas: (1) duplicate and tag edges as OUT, IN, or RE to recover direction/reciprocity information; (2) use a two-step ordering based on vertex degree and vertex ID to reduce neighbor tables while guaranteeing each triangle is counted exactly once; and (3) infer one of the seven directed-triangle types from the three edge tags using a lookup table.

Unresolved vulnerabilities and possible improvement

This part is more interesting because the paper itself does not explicitly present a limitations section. The following are therefore my analysis based on its design and experiments.

• CPU/MapReduce-oriented implementation. T-COUNT is implemented using GraphX/MapReduce on CPU clusters; although the authors say it could be implemented on other graph engines, they do not evaluate GPU or multi-GPU implementations.

  Possible improvement: investigate a GPU/multi-GPU T-COUNT variant, particularly whether its edge-centric neighbor intersections and triangle-type lookup can be efficiently mapped to GPU kernels while minimizing inter-GPU communication.

• Communication and memory overhead remain important. T-COUNT first duplicates every directed edge and later performs distributed groupBy/join operations on neighbor tables. On very large graphs, these operations can increase intermediate storage, network traffic, and synchronization costs even though the two-step reduction decreases later computation.

  Possible improvement: compressed adjacency representations, communication-aware graph partitioning, or locality-aware placement of high-degree vertices.

• Load balancing is only partially addressed. The degree-based reduction substantially reduces the problems caused by super vertices, but real-world power-law graphs can still create highly uneven neighbor-intersection workloads; the evaluation itself emphasizes candidate skew and very large candidate sets as major causes of failure for competing methods.

  Possible improvement: workload-aware partitioning or splitting the processing of high-degree vertices/edges across workers or GPUs rather than assigning work mainly according to graph partitions.

• Only static, exact triangle counting is considered. T-COUNT assumes a graph dataset is processed as a whole; the paper does not develop incremental algorithms for continuously changing directed graphs.

  Possible improvement: an incremental T-COUNT that updates the seven triangle counts after edge insertion/deletion rather than recomputing the entire graph.