The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
RolX: structural role extraction & mining in large graphs
Abstract
Given a network, intuitively two nodes belong to the same role if they have similar structural behavior. Roles should be automatically determined from the data, and could be, for example, "clique-members," "periphery-nodes," etc. Roles enable numerous novel and useful network-mining tasks, such as sense-making, searching for similar nodes, and node classification. This paper addresses the question: Given a graph, how can we automatically discover roles for nodes? We propose RolX (Role eXtraction), a scalable (linear in the number of edges), unsupervised learning approach for automatically extracting structural roles from general network data. We demonstrate the effectiveness of RolX on several network-mining tasks: from exploratory data analysis to network transfer learning. Moreover, we compare network role discovery with network community discovery. We highlight fundamental differences between the two (e.g., roles generalize across disconnected networks, communities do not); and show that the two approaches are complimentary in nature.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Information Theory and an Extension of the Maximum Likelihood Principle
Akaike, H. (1998) · Springer Series in Statistics · doi:10.1007/978-1-4612-1694-0_15 · Cited by 17,781
Least squares quantization in PCM
Lloyd, S. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056489 · Cited by 15,836
Learning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
Finding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
A Method for the Construction of Minimum-Redundancy Codes
Huffman, D. (1952) · Proceedings of the IRE · doi:10.1109/jrproc.1952.273898 · Cited by 6,334
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
Finding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
Quantizing for minimum distortion
Max, J. (1960) · IEEE Transactions on Information Theory · doi:10.1109/tit.1960.1057548 · Cited by 2,038
Inferring friendship network structure by using mobile phone data
Eagle, N., Pentland, A. (., & Lazer, D. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0900282106 · Cited by 1,856
Projected Gradient Methods for Nonnegative Matrix Factorization
Lin, C.-J. (2007) · Neural Computation · doi:10.1162/neco.2007.19.10.2756 · Cited by 1,737
(2014) · African Studies Companion Online · doi:10.1163/1872-9037_afco_dum_r0022a · Cited by 1,664
Unsupervised feature selection for multi-cluster data
Cai, D., Zhang, C., & He, X. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835848 · Cited by 1,112
New perspectives and methods in link prediction
Lichtenwalter, R. N., Lussier, J. T., & Chawla, N. V. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835837 · Cited by 664
oddball: Spotting Anomalies in Weighted Graphs
Akoglu, L., McGlohon, M., & Faloutsos, C. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13672-6_40 · Cited by 533
Self-citationGeneralized Nonnegative Matrix Approximations with Bregman Divergences
Sra, S., & Dhillon, I. S. (2005) · MPG.PuRe (Max Planck Society) · Cited by 522
Topic and Role Discovery in Social Networks with Experiments on Enron and Academic Email
McCallum, A., Wang, X., & Corrada-Emmanuel, A. (2007) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2229 · Cited by 447
Eggert, J., & Korner, E. (2005) · 2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541) · doi:10.1109/ijcnn.2004.1381036 · Cited by 272
It's who you know: graph mining using recursive structural features
Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020512 · Cited by 223 · cited 3×
“Thus, unless otherwise stated RolX employs the feature extraction algorithm described in [15], non-negative matrix factorization for clustering, MDL for model selection, and KL divergence to measure likelihood.”
MethodInfluentialSelf-citationSemi-supervised protein classification using cluster kernels
Weston, J., Leslie, C., Ie, E., Zhou, D., Elisseeff, A., & Noble, W. S. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti497 · Cited by 203
Using ghost edges for classification in sparsely labeled networks
Gallagher, B. J., Tong, H., Eliassi‐Rad, T., & Faloutsos, C. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401925 · Cited by 164
Self-citationTransfer Learning for Collective Link Prediction in Multiple Heterogenous Domains
Cao, B., Liu, N., & Yang, Q. (2010) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 150
Evaluating role mining algorithms
Molloy, I., Li, N., Li, T., Mao, Z., Wang, Q., & Lobo, J. (2009) · ACM Symposium on Access Control Models and Technologies (SACMAT) · doi:10.1145/1542207.1542224 · Cited by 130
Generalized Nonnegative Matrix Approximations with Bregman Divergences
Dhillon, I. S., & Sra, S. (2005) · Cited by 123
Dai, W., Jin, O., Xue, G.-R., Yang, Q., & Yu, Y. H. (2009) · International Conference on Machine Learning · doi:10.1145/1553374.1553399 · Cited by 108
Gallagher, B. J., & Eliassi‐Rad, T. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14929-0_1 · Cited by 73
Self-citationMetric forensics: a multi-level approach for mining volatile graphs
Henderson, K., Eliassi‐Rad, T., Faloutsos, C., Akoglu, L., Li, L., Maruhashi, K., Prakash, B. A., & Tong, H. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835828 · Cited by 64
Self-citationSemi-supervised semantic role labeling
Fürstenau, H., & Lapata, M. (2009) · Conference of the European Chapter of the Association for Computational Linguistics · doi:10.3115/1609067.1609091 · Cited by 55
Cross-Guided Clustering: Transfer of Relevant Supervision across Domains for Improved Clustering
Bhattacharya, I., Godbole, S., Joshi, S., & Verma, A. K. (2009) · Proceedings · doi:10.1109/icdm.2009.33 · Cited by 13
Cited by
node2vec: Scalable Feature Learning for Networks
Grover, A., & Leskovec, J. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939754 · Cited by 10,926
“In contrast, under the structural equivalence hypothesis [10] nodes that have similar structural roles in networks should be embedded closely together ( e.g. , nodes u and s 6 in Figure 1 act as hubs of their corresponding communities).”
Backgroundmetapath2vec: Scalable Representation Learning for Heterogeneous Networks
Dong, Y., Chawla, N. V., & Swami, A. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098036 · Cited by 2,210
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
“…measures such as eigenvector [Bonacich and Lloyd, 2001], closeness [Noh and Rieger, 2004], and betweenness [Freeman, 1977] centralities, local clustering coefficient [Watts and Strogatz, 1998], radius [Kang et al., 2011c], degree assortativity, and most recently, roles [Henderson et al., 2012].”
BackgroundMethodResultInfluentialSelf-citationstruc2vec: Learning Node Representations from Structural Identity
Ribeiro, L. F. R., Saverese, P. H. P., & Figueiredo, D. R. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098061 · Cited by 1,011
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Qiu, J., Chen, Q., Dong, Y., Zhang, J., Yang, H., Ding, M., Wang, K., & Tang, J. (2020) · Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3394486.3403168 · Cited by 777
Metadata
- Authors
- Henderson, K., Gallagher, B., Eliassi-Rad, T., Tong, H., Basu, S., Akoglu, L., Koutra, D., Faloutsos, C., & Li, L.
- Venue
- Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2012-08-12
- Pages
- 1231-1239
- OpenAlex
- W2057685268
- Cited by
- 376
- References
- 28
- FWCI
- 13.12
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.