It's who you know: graph mining using recursive structural features
Open accessAbstract
Given a graph, how can we extract good features for the nodes? For example, given two large graphs from the same domain, how can we use information in one to do classification in the other (i.e., perform across-network classification or transfer learning on graphs)? Also, if one of the graphs is anonymized, how can we use information in one to de-anonymize the other? The key step in all such graph mining tasks is to find effective node features. We propose ReFeX (Recursive Feature eXtraction), a novel algorithm, that recursively combines local (node-based) features with neighborhood (egonet-based) features; and outputs regional features -- capturing "behavioral" information. We demonstrate how these powerful regional features can be used in within-network and across-network classification and de-anonymization tasks -- without relying on homophily, or the availability of class labels. The contributions of our work are as follows: (a) ReFeX is scalable and (b) it is effective, capturing regional ("behavioral") information in large graphs. We report experiments on real graphs from various domains with over 1M edges, where ReFeX outperforms its competitors on typical graph mining tasks like network classification and de-anonymization.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Most methods require global information and are offline.
“Most methods require global information and are offline [16,39-41].”
From DeepWalk: online learning of social representations (2014) · cites this paper as [16]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Data Mining: Practical Machine Learning Tools and Techniques
Witten, I. H., Frank, E., & Hall, M. A. (2011) · Elsevier eBooks · doi:10.1016/c2009-0-19715-5 · Cited by 25,493 · see citing works
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502 · see citing works
Witten, I. H. (2008) · Cited by 9,115 · see citing works
Newman (2005) · doi:10.1080/00107510500052444 · Cited by 5,749 · see citing works
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · doi:10.1145/316188.316229 · Cited by 4,245 · see citing works
Self-citationDiameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (1999) · Nature · doi:10.1038/43601 · Cited by 4,240 · see citing works
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,621 · see citing works
Self-citationGraphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281 · see citing works
Self-citation(2007) · Cited by 2,018 · see citing works
Boosting for transfer learning
Dai, W., Yang, Q., Xue, G.-R., & Yu, Y. H. (2007) · International Conference on Machine Learning · doi:10.1145/1273496.1273521 · Cited by 1,788 · see citing works
Scale-free characteristics of random networks: the topology of the world-wide web
Barabási, A.-Ĺ., Albert, R., & Jeong, H. (2000) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(00)00018-2 · Cited by 1,426 · see citing works
R-MAT: A Recursive Model for Graph Mining
Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.43 · Cited by 1,275 · see citing works
Self-citationThe Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48686-0_1 · Cited by 1,027 · see citing works
Self-organization and identification of Web communities
Flake, G. W., Lawrence, S., Giles, C. L., & Coetzee, F. M. (2002) · Computer · doi:10.1109/2.989932 · Cited by 1,021 · see citing works
Witten, I. H., & Frank, E. (2005) · Cited by 815 · see citing works
New perspectives and methods in link prediction
Lichtenwalter, R. N., Lussier, J. T., & Chawla, N. V. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835837 · Cited by 665 · see citing works
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 545 · see citing works
Self-citationNoble, C. C., & Cook, D. J. (2003) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956831 · Cited by 478 · see citing works
Collective multi-label classification
Ghamrawi, N., & McCallum, A. (2005) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/1099554.1099591 · Cited by 412 · see citing works
Knowledge transfer via multiple model local structure mapping
Gao, J., Fan, W., Jiang, J., & Han, J. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401928 · Cited by 336 · see citing works
A Simple Relational Classifier
Macskassy, S. A., & Provost, F. (2003) · doi:10.21236/ada452802 · Cited by 255 · see citing works
Learning a meta-level prior for feature relevance from multiple related tasks
Lee, S., Chatalbashev, V., Vickrey, D., & Koller, D. (2007) · International Conference on Machine Learning · doi:10.1145/1273496.1273558 · Cited by 166 · see citing works
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 149 · see citing works
Self-citationOn the Vulnerability of Large Graphs
Tong, H., Prakash, B. A., Tsourakakis, C. E., et al. (2010) · Proceedings · doi:10.1109/icdm.2010.54 · Cited by 141 · see citing works
Self-citationMining Behavior Graphs for “Backtrace” of Noncrashing Bugs
Liu, C., Yan, X., Yu, H., Han, J., & Yu, P. S. (2005) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.26 · Cited by 129 · see citing works
Learning Multiple Related Tasks using Latent Independent Component Analysis
Zhang, J. A., Ghahramani, Z., & Yang, Y. (2005) · Cited by 115 · see citing works
Collective Cross-Document Relation Extraction Without Labelled Data
Yao, L., Riedel, S., & McCallum, A. (2010) · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · Cited by 110 · see citing works
Brandenburg, H. (2002) · Harvard International Journal of Press/Politics · doi:10.1177/1081180x0200700303 · Cited by 92 · see citing works
Gallagher, B. J., & Eliassi‐Rad, T. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14929-0_1 · Cited by 61 · see citing works
Self-citationCross lingual text classification by mining multilingual topics from wikipedia
Ni, X., Sun, J.-T., Hu, J., et al. (2011) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/1935826.1935887 · Cited by 59 · see citing works
Herd, A. (2003) · Cited by 57 · see citing works
Henderson, K. A., 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 53 · see citing works
Self-citationMulti-label Feature Selection for Graph Classification
Kong, X., & Yu, P. S. (2010) · Proceedings · doi:10.1109/icdm.2010.58 · Cited by 32 · see citing works
Structure feature selection for graph classification
Fei, H., & Huan, J. (2008) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/1458082.1458212 · Cited by 32 · see citing works
He, J., Liu, Y., & Lawrence, R. D. (2009) · doi:10.1145/1645953.1646073 · Cited by 24 · see citing works
Sewage and sewerage of farm homes
Warren, G. M. (2010) · Cited by 1 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
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 · see citing works
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123 · see citing works
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 · see citing works
Self-citation
- Authors
- Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C.
- Affiliations
- Lawrence Livermore National Laboratory (US)
- Carnegie Mellon University (US)
- Rutgers University, Piscataway, NJ, USA
- IBM (United States) (US)
- Venue
- Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2011-08-21
- Pages
- 663-671
- OpenAlex
- W2001325956
- Cited by
- 223
- References
- 36
- Citations by year
- 2026: 4 · 2025: 2 · 2024: 8 · 2023: 16 · 2022: 14 · 2021: 24 · 2020: 26 · 2019: 18 · 2018: 25 · 2017: 13 · 2016: 19 · 2015: 19 · 2014: 14 · 2013: 10 · 2012: 10
- FWCI
- 8.76
- Type
- conference paper
- Language
- en
- Open access
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- University of North Texas Digital Library (University of North Texas) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- Funders
- U.S. Department of Energy (DEAC5207NA27344, AC52‐07NA27344)
- Lawrence Livermore National Laboratory (DE‐AC5207NA27344, AC52-07NA27344)
- Army Research Laboratory (W911NF, W911NF-09-2-0053)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Keywords
- graph mining, RefEx, neighborhood characteristics, regional characteristics, network classification, de-anonymization
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
