U Kang

U Kang
Ph.D.
Computer Science Department
Carnegie Mellon University
5000 Forbes Ave., Pittsburgh, PA 15213

Email: ukang at cs dot cmu dot edu
Office: 7701 Gates and Hillman Centers

I received my Ph.D. degree in Computer Science from Carnegie Mellon University. My advisor is Prof. Christos Faloutsos. Here is my short biography.

What's New

I graduated in May 20, 2012.
- Curriculum Vitae [PDF]
- Research Statement [PDF]
- Teaching Statement [PDF]
- Representative Publications
  - U Kang, Charalampos E. Tsourakakis, and Christos Faloutsos, PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations. IEEE International Conference on Data Mining (ICDM) 2009, Miami, Florida, USA. [PDF]
  - U Kang, Charalampos E. Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec, HADI: Mining Radii of Large Graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 2011. [PDF]
  - U Kang, Brendan Meeder, and Christos Faloutsos, Spectral Analysis for Billion-Scale Graphs: Discoveries and Implementation. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2011, Shenzhen, China. [PDF]
I gave the tutorial "Managing and Mining Billion-scale Graphs: Patterns and Algorithms" at SIGMOD 2012, with Christos Faloutsos.

Research Interests

Data mining in big graphs: bridging data mining and systems research for extremely scalable graph analysis with applications on knowledge discovery and anomaly detection.

Graph Structure Analysis
- Mining the structure of large graphs, including connected component, PageRank, and random walk with restart (related paper: [ICDM'09] [KAIS'11], project: PEGASUS)
- Mining the radius/diameter of large graphs (related paper: [SDM'10] [TKDD'11])
- Centralities in large graphs (related paper: [SDM'11])
- Models and observations on the evolution of connected components (related paper: [ICDM'10])
Spectral Graph Analysis
- Eigensolver on large graphs (related paper: [PAKDD'11])
- Tensor analysis (related paper: under submission)
- Triangle counting (related paper: [KDD'09])
Machine Learning on Graphs
- Belief propagation on large graphs (related paper: [ICDE'11])
- Unifying guilt-by-association approaches (related paper: [PKDD'11])
- Clustering multi dimensional data (related paper: [KDD'11])
- Fast random walk graph kernel (related paper: [SDM'12])
- Axiomatic analysis of node similarity functions (related paper: [CMU Tech Report])
Graph Management
- Graph storage and indexing (related paper: [KDD'11])
- Graph compression and community detection (related paper: [ICDM'11])

Software

PEGASUS (Peta-Scale Graph Mining System) is an award-winning open-source software for mining very large graphs in Hadoop platform.

Publications

(Google Scholar, DBLP)

2012

GBASE: An Efficient Analysis Platform for Large Graphs.
U Kang, Hanghang Tong, Jimeng Sun, Ching-Yung Lin, and Christos Faloutsos.
VLDB Journal, 2012 (to appear)
Mining Tera-Scale Graphs: Theory, Engineering and Discoveries.
U Kang.
Ph.D. Thesis, Computer Science Department, Carnegie Mellon Univeristy, May 2012.
[PDF] [BIBTEX]
Large Graph Mining System for Patterns, Anomalies & Visualization.
Leman Akoglu*, Duen Horng Chau*, U Kang*, Danai Koutra*, and Christos Faloutsos.
Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2012, Kuala Lumpur, Malaysia.
(Demo paper)
[BIBTEX]
OPAvion: Mining and visualization in large graphs.
Leman Akoglu*, Duen Horng Chau*, U Kang*, Danai Koutra*, and Christos Faloutsos.
ACM SIGMOD Conference 2012, Scottsdale, AZ, USA.
(Demo paper)
[PDF] [BIBTEX]
Axiomatic Analysis of Co-occurrence Similarity Functions.
U Kang, Mikhail Bilenko, Dengyong Zhou, and Christos Faloutsos.
CMU Computer Science Tech Report CMU-CS-12-102, February 2012.
[PDF] [BIBTEX]
Fast Random Walk Graph Kernel.
U Kang, Hanghang Tong, and Jimeng Sun.
SIAM International Conference on Data Mining (SDM) 2012, Anaheim, California, USA. (acceptance rate 27 %)
[PDF] [BIBTEX]
PEGASUS: Mining Billion-Scale Graphs in the Cloud.
U Kang, Duen Horng Chau, and Christos Faloutsos.
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2012, Kyoto, Japan
(Special Session: Signal and Information Processing for "Big Data")
[PDF] [BIBTEX]

2011

Beyond `Caveman Communities': Hubs and Spokes for Graph Compression and Mining.
U Kang and Christos Faloutsos.
IEEE International Conference on Data Mining (ICDM) 2011, Vancouver, Canada. (acceptance rate 12.2 %)
[PDF] [BIBTEX]
Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms.
Danai Koutra, Tai-You Ke, U Kang, Duen Horng (Polo) Chau, Hsing-Kuo Kenneth Pao, and Christos Faloutsos.
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) 2011, Athens, Greece. (acceptance rate 20.2 %)
[PDF] [BIBTEX]
GBASE: A Scalable and General Graph Management System.
U Kang, Hanghang Tong, Jimeng Sun, Ching-Yung Lin, and Christos Faloutsos.
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2011, San Diego, CA, USA. (acceptance rate 17.5 %)
[PDF] [BIBTEX]
Clustering Very Large Multi-dimensional Datasets with MapReduce.
Robson L. F. Cordeiro, Caetano Traina Jr., Agma J. M. Traina, Julio Lopez, U Kang, and Christos Faloutsos.
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2011, San Diego, CA, USA. (acceptance rate 17.5 %)
[PDF] [BIBTEX]
Spectral Analysis for Billion-Scale Graphs: Discoveries and Implementation.
U Kang, Brendan Meeder, and Christos Faloutsos.
Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2011, Shenzhen, China. (acceptance rate 9.7 %)
Best Paper Award: Best Application Paper.
[PDF] [BIBTEX]
Centralities in Large Networks: Algorithms and Observations.
U Kang, Spiros Papadimitriou, Jimeng Sun, and Hanghang Tong.
SIAM International Conference on Data Mining (SDM) 2011, Mesa, Arizona, USA. (acceptance rate 25.1 %)
[PDF] [BIBTEX]
Mining Large Graphs: Algorithms, Inference, and Discoveries.
U Kang, Duen Horng Chau, and Christos Faloutsos.
IEEE International Conference on Data Engineering (ICDE) 2011, Hannover, Germany. (acceptance rate 19.8 %)
[PDF] [BIBTEX]
HADI: Mining Radii of Large Graphs.
U Kang, Charalampos E. Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec.
ACM Transactions on Knowledge Discovery from Data (TKDD), 2011.
[PDF] [BIBTEX]
PEGASUS: Mining Peta-Scale Graphs.
U Kang, Charalampos E. Tsourakakis, and Christos Faloutsos.
Knowledge and Information Systems (KAIS), Springer, 2011.
[PDF] [BIBTEX]

2010

Patterns on the Connected Components of Terabyte-Scale Graphs.
U Kang, Mary McGlohon, Leman Akoglu, and Christos Faloutsos.
IEEE International Conference on Data Mining (ICDM) 2010, Sydney, Australia. (acceptance rate 19.4 %)
[PDF] [BIBTEX]
Inference of Beliefs on Billion-Scale Graphs.
U Kang, Duen Horng "Polo" Chau, and Christos Faloutsos.
Large-scale Data Mining: Theory and Applications (LDMTA) 2010, in conjunction with KDD 2010, Washington D.C., USA.
[PDF] [BIBTEX]
Radius Plots for Mining Tera-byte Scale Graphs: Algorithms, Patterns, and Observations.
U Kang, Charalampos E. Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec.
SIAM International Conference on Data Mining (SDM) 2010, Columbus, Ohio, USA. (acceptance rate 23.4 %)
[PDF] [BIBTEX]

2009

PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations.
U Kang, Charalampos E. Tsourakakis, and Christos Faloutsos.
IEEE International Conference on Data Mining (ICDM) 2009, Miami, Florida, USA. (acceptance rate 8.9 %)
Best Paper Award: Best Application Paper (runner-up).
[PDF] [BIBTEX] [PEGASUS HOMEPAGE]
DOULION: Counting Triangles in Massive Graphs with a Coin.
Charalampos E. Tsourakakis, U Kang, Gary Miller, and Christos Faloutsos.
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) 2009, Paris, France. (acceptance rate 20 %)
[PDF] [BIBTEX]

2008

HADI: Fast Diameter Estimation and Mining in Massive Graphs with Hadoop .
U Kang, Charalampos Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec.
CMU Machine Learning Tech Report CMU-ML-08-117, December 2008.
[PDF] [BIBTEX]