More Web Proxy on the site http://driver.im/

short-paper

gl2vec: learning feature representation using graphlets for directed networks

Authors:

Liam D. TurnerAuthors Info & Claims

ASONAM '19: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Pages 216 - 221

https://doi.org/10.1145/3341161.3342908

Published: 15 January 2020 Publication History

Abstract

Learning network representation has a variety of applications, such as network classification. Most existing work in this area focuses on static undirected networks and does not account for presence of directed edges or temporal changes. Furthermore, most work focuses on node representations that do poorly on tasks like network classification. In this paper, we propose a novel network embedding methodology, gl2vec, for network classification in both static and temporal directed networks. gl2vec constructs vectors for feature representation using static or temporal network graphlet distributions and a null model for comparing them against random graphs. We demonstrate the efficacy and usability of gl2vec over existing state-of-the-art methods on network classification tasks such as network type classification and subgraph identification in several real-world static and temporal directed networks. We argue that gl2vec provides additional network features that are not captured by state-of-the-art methods, which can significantly improve their classification accuracy by up to 10% in real-world applications.

References

[1]

B. Adhikari, Y. Zhang, N. Ramakrishnan, and B. A. Prakash. Sub2vec: Feature Learning for Subgraphs. In PAKDD, 2018.

Digital Library

[2]

E. G. Allan Jr, W. H. Turkett, and E. W. Fulp. Using network motifs to identify application protocols. In IEEE GLOBECOM, 2009.

[3]

T. Chen and C. Guestrin. Xgboost: A Scalable Tree Boosting System. In ACM SIGKDD, 2016.

Digital Library

[4]

C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273--297, 1995.

Digital Library

[5]

H. Dai, B. Dai, and L. Song. Discriminative embeddings of latent variable models for structured data. In ICML, 2016.

Digital Library

[6]

P.-T. De Boer, D. P. Kroese, S. Mannor, and R. Y. Rubinstein. A Tutorial on the Cross-Entropy Method. Annals of operations research, 134(1):19--67, 2005.

[7]

M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In NIPS, 2016.

Digital Library

[8]

M. Doroud, P. Bhattacharyya, S. F. Wu, and D. Felmlee. The evolution of ego-centric triads: A microscopic approach toward predicting macroscopic network properties. In IEEE SocialCom, 2011.

[9]

A. Grover and J. Leskovec. node2vec: Scalable Feature Learning for Networks. In ACM SIGKDD, 2016.

Digital Library

[10]

A. Grover and J. Leskovec. node2vec: Scalable Feature Learning for Networks. In ACM SIGKDD, 2016.

Digital Library

[11]

W. L. Hamilton, R. Ying, and J. Leskovec. Representation learning on graphs: Methods and applications. arXiv:1709.05584, 2017.

[12]

P. Holme and J. Saramäki. Temporal Networks. Physics reports, 519(3):97--125, 2012.

[13]

R. Kaspar and B. Horst. Graph Classification and Clustering based on Vector Space Embedding, volume 77. World Scientific, 2010.

[14]

T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907, 2016.

[15]

L. Kovanen, M. Karsai, K. Kaski, J. Kertész, and J. Saramäki. Temporal Motifs in Time-Dependent Networks. Journal of Statistical Mechanics: Theory and Experiment, 2011(11):P11005, 2011.

[16]

M. Kretzschmar and M. Morris. Measures of concurrency in networks and the spread of infectious disease. Mathematical biosciences, 133(2):165--195, 1996.

[17]

J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.

[18]

A. Mellor. Classifying Conversation in Digital Communication. arXiv:1801.10527, 2018.

[19]

R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon. Superfamilies of Evolved and Designed Networks. Science, 303(5663):1538--1542, 2004.

[20]

A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, and S. Jaiswal. graph2vec: Learning Distributed Representations of Graphs. Arxiv preprint arXiv:1707.05005, 2018.

[21]

M. Newman. Networks: an Introduction. Oxford university press, 2010.

[22]

M. E. Newman. Modularity and community structure in networks. PNAS, 103(23):8577--8582, 2006.

[23]

M. E. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physical review E, 69(2):026113, 2004.

[24]

M. E. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. Physical review E, 64(2):026118, 2001.

[25]

C. Olsson, P. Petrov, J. Sherman, and A. Perez-Lopez. Finding and explaining similarities in linked data. In STIDS, 2011.

[26]

A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In ACM WSDM, 2017.

Digital Library

[27]

B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online Learning of Social Representations. In ACM SIGKDD, 2014.

Digital Library

[28]

L. F. Ribeiro, P. H. Saverese, and D. R. Figueiredo. struc2vec: Learning Node Representations from Structural Identity. In ACM SIGKDD, 2017.

Digital Library

[29]

N. Shervashidze, P. Schweitzer, E. J. v. Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539--2561, 2011.

[30]

V. Svetnik, A. Liaw, C. Tong, J. C. Culberson, R. P. Sheridan, and B. P. Feuston. Random Forest: a Classification and Regression Tool for Compound Classification and QSAR Modeling. Journal of chemical information and computer sciences, 43(6):1947--1958, 2003.

[31]

J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-Scale Information Network Embedding. In WWW, 2015.

Digital Library

[32]

K. Tu. Jmotif, 2018.

[33]

K. Tu, J. Li, D. Towsley, D. Braines, and L. Turner. gl2vec: Learning feature representation using graphlets for directed networks. Arxiv preprint arXiv:1812.05473, 2018.

[34]

K. Tu, J. Li, D. Towsley, D. Braines, and L. Turner. Network classification in temporal networks using motifs. In ECML/PKDD-AALTD, 2018.

[35]

L. D. Turner, R. M. Whitaker, S. M. Allen, D. E. Linden, K. Tu, J. Li, and D. Towsley. Evidence to support common application switching behaviour on smartphones. Royal Society Open Science, 6(3), 2019.

[36]

P. Yanardag and S. Vishwanathan. Deep Graph kernels. In ACM SIGKDD, 2015.

Digital Library

[37]

H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich. Local Higher-Order Graph Clustering. In ACM SIGKDD, 2017.

Digital Library

Cited By

Galdeman AZignani MGaito S(2025)Graph Evolution Rules Meet Communities: Assessing Global and Local Patterns in the Evolution of Dynamic NetworksBig Data Mining and Analytics10.26599/BDMA.2024.90200508:1(78-102)Online publication date: Feb-2025
https://doi.org/10.26599/BDMA.2024.9020050
Zhou YZhang ZZhang ZLyu LKu WSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Effective federated graph matchingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694646(62257-62293)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694646
Pušnik ŽMraz MZimic NMoškon M(2024)SAILoR: Structure-Aware Inference of Logic RulesPLOS ONE10.1371/journal.pone.030410219:6(e0304102)Online publication date: 11-Jun-2024
https://doi.org/10.1371/journal.pone.0304102
Show More Cited By

gl2vec: learning feature representation using graphlets for directed networks
1. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
2. Information systems
  1. Information systems applications

Recommendations

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite ...
GL2vec: Graph Embedding Enriched by Line Graphs with Edge Features
Neural Information Processing
Abstract
Recently, several techniques to learn the embedding for a given graph dataset have been proposed. Among them, Graph2vec is significant in that it unsupervisedly learns the embedding of entire graphs which is useful for graph classification. This ...
Analysis of Heterogeneous Complex Networks Using the Degree of Diffusion
NBIS '13: Proceedings of the 2013 16th International Conference on Network-Based Information Systems

Diffusion is the process of spreading information throughout a network. The degree of diffusion a has been used to measure the diffusion and the adoption rates of different complex networks. It is defined as the percentage between the adopters and non-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '19: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

August 2019

1228 pages

ISBN:9781450368681

DOI:10.1145/3341161

Editors:
Francesca Spezzano
Boise State University
,
Wei Chen
Microsoft Research, China
,
Xiaokui Xiao
National University of Singapore, Singapore

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Short-paper

Funding Sources

Army Research Laboratory
U.K. Ministry of Defence

Conference

ASONAM '19

Sponsor:

SIGKDD

ASONAM '19: International Conference on Advances in Social Networks Analysis and Mining

August 27 - 30, 2019

British Columbia, Vancouver, Canada

Acceptance Rates

ASONAM '19 Paper Acceptance Rate 41 of 286 submissions, 14%;

Overall Acceptance Rate 116 of 549 submissions, 21%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
464
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)3

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Galdeman AZignani MGaito S(2025)Graph Evolution Rules Meet Communities: Assessing Global and Local Patterns in the Evolution of Dynamic NetworksBig Data Mining and Analytics10.26599/BDMA.2024.90200508:1(78-102)Online publication date: Feb-2025
https://doi.org/10.26599/BDMA.2024.9020050
Zhou YZhang ZZhang ZLyu LKu WSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Effective federated graph matchingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694646(62257-62293)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694646
Pušnik ŽMraz MZimic NMoškon M(2024)SAILoR: Structure-Aware Inference of Logic RulesPLOS ONE10.1371/journal.pone.030410219:6(e0304102)Online publication date: 11-Jun-2024
https://doi.org/10.1371/journal.pone.0304102
Wang JDeng ZLin TLi WLing SBaeza-Yates RBonchi F(2024)A Novel Prompt Tuning for Graph Transformers: Tailoring Prompts to Graph TopologiesProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671804(3116-3127)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671804
Wang ZWang JShan YYu SXu XXuan QChen G(2024)Null Model-Based Data Augmentation for Graph ClassificationIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333249911:2(1821-1833)Online publication date: Mar-2024
https://doi.org/10.1109/TNSE.2023.3332499
Ironside-Smith RNoë BAllen SCostello STurner L(2024)Motif discovery in hospital ward vital signs observation networksNetwork Modeling Analysis in Health Informatics and Bioinformatics10.1007/s13721-024-00490-113:1Online publication date: 7-Oct-2024
https://doi.org/10.1007/s13721-024-00490-1
Hoang VJeon HYou EYoon YJung SLee O(2023)Graph Representation Learning and Its Applications: A SurveySensors10.3390/s2308416823:8(4168)Online publication date: 21-Apr-2023
https://doi.org/10.3390/s23084168
Bressan M(2023)Efficient and Near-optimal Algorithms for Sampling Small Connected SubgraphsACM Transactions on Algorithms10.1145/359649519:3(1-40)Online publication date: 24-Jun-2023
https://dl.acm.org/doi/10.1145/3596495
Huang RChen ZZhai GHe JChu X(2023)A Graph Entropy Measure From Urelement to Higher-Order Graphlets for Network AnalysisIEEE Transactions on Network Science and Engineering10.1109/TNSE.2022.321680310:2(631-644)Online publication date: 1-Mar-2023
https://doi.org/10.1109/TNSE.2022.3216803
Wang TBendayan RMsosa YPritchard MRoberts AStewart RDobson R(2022)Patient-centric characterization of multimorbidity trajectories in patients with severe mental illnessesJournal of Biomedical Informatics10.1016/j.jbi.2022.104010127:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.jbi.2022.104010
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents