Exact and Estimation of Local Edge-centric Graphlet Counts

Nesreen K. Ahmed, Theodore L. Willke, Ryan A. Rossi
Proceedings of the 5th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications at KDD 2016, PMLR 53:1-17, 2016.

Abstract

Graphlets represent small induced subgraphs and are becoming increasingly important for a variety of applications. Despite the importance of the local graphlet problem, existing work focuses mainly on counting graphlets globally over the entire graph. These global counts have been used for tasks such as graph classification as well as for understanding and summarizing the fundamental structural patterns in graphs. In contrast, this work proposes a flexible, efficient, and scalable parallel framework for the more challenging problem of counting graphlets locally for a given edge or set of edges.The local graphlet counts provide a topologically rigorous characterization of the local structure surrounding an edge. The aim of this work is to obtain the count of every graphlet of size k ∈{3, 4 } for each edge. The framework gives rise to efficient, parallel, and accurate unbiased estimation methods as well as exact graphlet algorithms for counting graphlets locally. Experiments demonstrate the effectiveness of the proposed exact and estimation methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v53-ahmed16, title = {Exact and Estimation of Local Edge-centric Graphlet Counts}, author = {Ahmed, Nesreen K. and Willke, Theodore L. and Rossi, Ryan A.}, booktitle = {Proceedings of the 5th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications at KDD 2016}, pages = {1--17}, year = {2016}, editor = {Fan, Wei and Bifet, Albert and Read, Jesse and Yang, Qiang and Yu, Philip S.}, volume = {53}, series = {Proceedings of Machine Learning Research}, address = {San Francisco, California, USA}, month = {14 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v53/ahmed16.pdf}, url = {https://proceedings.mlr.press/v53/ahmed16.html}, abstract = {Graphlets represent small induced subgraphs and are becoming increasingly important for a variety of applications. Despite the importance of the local graphlet problem, existing work focuses mainly on counting graphlets globally over the entire graph. These global counts have been used for tasks such as graph classification as well as for understanding and summarizing the fundamental structural patterns in graphs. In contrast, this work proposes a flexible, efficient, and scalable parallel framework for the more challenging problem of counting graphlets locally for a given edge or set of edges.The local graphlet counts provide a topologically rigorous characterization of the local structure surrounding an edge. The aim of this work is to obtain the count of every graphlet of size k ∈{3, 4 } for each edge. The framework gives rise to efficient, parallel, and accurate unbiased estimation methods as well as exact graphlet algorithms for counting graphlets locally. Experiments demonstrate the effectiveness of the proposed exact and estimation methods.} }
Endnote
%0 Conference Paper %T Exact and Estimation of Local Edge-centric Graphlet Counts %A Nesreen K. Ahmed %A Theodore L. Willke %A Ryan A. Rossi %B Proceedings of the 5th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications at KDD 2016 %C Proceedings of Machine Learning Research %D 2016 %E Wei Fan %E Albert Bifet %E Jesse Read %E Qiang Yang %E Philip S. Yu %F pmlr-v53-ahmed16 %I PMLR %P 1--17 %U https://proceedings.mlr.press/v53/ahmed16.html %V 53 %X Graphlets represent small induced subgraphs and are becoming increasingly important for a variety of applications. Despite the importance of the local graphlet problem, existing work focuses mainly on counting graphlets globally over the entire graph. These global counts have been used for tasks such as graph classification as well as for understanding and summarizing the fundamental structural patterns in graphs. In contrast, this work proposes a flexible, efficient, and scalable parallel framework for the more challenging problem of counting graphlets locally for a given edge or set of edges.The local graphlet counts provide a topologically rigorous characterization of the local structure surrounding an edge. The aim of this work is to obtain the count of every graphlet of size k ∈{3, 4 } for each edge. The framework gives rise to efficient, parallel, and accurate unbiased estimation methods as well as exact graphlet algorithms for counting graphlets locally. Experiments demonstrate the effectiveness of the proposed exact and estimation methods.
RIS
TY - CPAPER TI - Exact and Estimation of Local Edge-centric Graphlet Counts AU - Nesreen K. Ahmed AU - Theodore L. Willke AU - Ryan A. Rossi BT - Proceedings of the 5th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications at KDD 2016 DA - 2016/12/06 ED - Wei Fan ED - Albert Bifet ED - Jesse Read ED - Qiang Yang ED - Philip S. Yu ID - pmlr-v53-ahmed16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 53 SP - 1 EP - 17 L1 - http://proceedings.mlr.press/v53/ahmed16.pdf UR - https://proceedings.mlr.press/v53/ahmed16.html AB - Graphlets represent small induced subgraphs and are becoming increasingly important for a variety of applications. Despite the importance of the local graphlet problem, existing work focuses mainly on counting graphlets globally over the entire graph. These global counts have been used for tasks such as graph classification as well as for understanding and summarizing the fundamental structural patterns in graphs. In contrast, this work proposes a flexible, efficient, and scalable parallel framework for the more challenging problem of counting graphlets locally for a given edge or set of edges.The local graphlet counts provide a topologically rigorous characterization of the local structure surrounding an edge. The aim of this work is to obtain the count of every graphlet of size k ∈{3, 4 } for each edge. The framework gives rise to efficient, parallel, and accurate unbiased estimation methods as well as exact graphlet algorithms for counting graphlets locally. Experiments demonstrate the effectiveness of the proposed exact and estimation methods. ER -
APA
Ahmed, N.K., Willke, T.L. & Rossi, R.A.. (2016). Exact and Estimation of Local Edge-centric Graphlet Counts. Proceedings of the 5th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications at KDD 2016, in Proceedings of Machine Learning Research 53:1-17 Available from https://proceedings.mlr.press/v53/ahmed16.html.

Related Material