Abstract
Mining outliers in graph data is a rapidly growing area of research. Traditional methods focus either on static graphs, or restrict relationships to be pairwise. In this work we address both of these limitations directly, and propose the first approach for mining outliers in hyperedge streams. Hyperedges, which generalize edges, faithfully capture higher order relationships that naturally occur in complex systems. Our model annotates every incoming hyperedge with an outlier score, which is based on the incident vertices and the historical relationships among them. Additionally, we describe an approximation scheme that ensures our model is suitable for being run in streaming environments. Experimental results on several real-world datasets show our model effectively identifies outliers, and that our approximation provides speedups between 33–775x.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
To handle the first object in the stream we take the score to be 1. Another approach is to use \(m+1\) in the denominator, which as the stream grows is approximately equal to using m.
- 2.
We use the uppercase MinHash when referring to the scheme, and the lowercase minhash when referring to a computed value.
References
Enron network dataset—KONECT. http://konect.uni-koblenz.de/networks/enron. May 2015
Akoglu, L., McGlohon, M., Faloutsos, C.: Oddball: Spotting anomalies in weighted graphs. In: Advances in Knowledge Discovery and Data Mining, pp. 410–421. Springer (2010)
Akoglu, L., Tong, H., Koutra, D.: Graph based anomaly detection and description: a survey. Data Min. Knowl. Disc. 29(3), 626–688 (2014)
Akoglu, L., Tong, H., Koutra, D.: Graph based anomaly detection and description: a survey. Data Min. Knowl. Disc. 29(3), 626–688 (2015)
Broder, A.: Identifying and filtering near-duplicate documents. In: Combinatorial Pattern Matching, pp. 1–10. Springer (2000)
Broder, A.Z.: On the resemblance and containment of documents. In: Compression and Complexity of Sequences 1997. Proceedings, pp. 21–29. IEEE (1997)
Broder, A.Z., Glassman, S.C., Manasse, M.S., Zweig, G.: Syntactic clustering of the web. Comput. Netw. ISDN Syst. 29(8), 1157–1166 (1997)
El-Yaniv, R., Nisenson, M.: Optimal single-class classification strategies. In: Advances in Neural Information Processing Systems, pp. 377–384 (2007)
Hodge, V.J., Austin, J.: A survey of outlier detection methodologies. Artif. Intell. Rev. 22(2), 85–126 (2004)
Leskovec, J., Rajaraman, A., Ullman, J.D.: Mining of Massive Datasets. Cambridge university press (2014)
Park, Y., Priebe, C., Marchette, D., Youssef, A.: Anomaly detection using scan statistics on time series hypergraphs. In: Link Analysis, Counterterrorism and Security (LACTS) Conference, p. 9 (2009)
Priebe, C.E., Conroy, J.M., Marchette, D.J., Park, Y.: Scan statistics on enron graphs. Comput. Math. Organ. Theory 11(3), 229–247 (2005)
Ranshous, S., Harenberg, S., Sharma, K., Samatova, N.F.: A scalable approach for outlier detection in edge streams using sketch-based approximations. In: Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 189–197. SIAM (2016)
Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C., Samatova, N.F.: Anomaly detection in dynamic networks: a survey. Wiley Interdiscip. Rev. Comput. Stat. 7(3), 223–247 (2015)
Scott, C., Kolaczyk, E.: Nonparametric assessment of contamination in multivariate data using generalized quantile sets and fdr. J. Comput. Graph. Stat. 19(2), 439–456 (2010)
Silva, J., Willett, R.: Hypergraph-based anomaly detection of high-dimensional co-occurrences. IEEE Trans. Pattern Anal. Mach. Intell. 31(3), 563–569 (2009)
Sun, J., Qu, H., Chakrabarti, D., Faloutsos, C.: Neighborhood formation and anomaly detection in bipartite graphs. In: Fifth IEEE International Conference on Data Mining (ICDM’05), p. 8. IEEE (2005)
Wei, L., Qian, W., Zhou, A., Jin, W., Jeffrey, X.Y.: Hot: Hypergraph-based outlier test for categorical data. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 399–410. Springer (2003)
Acknowledgements
This material is based on work supported in part by the Department of Energy National Nuclear Security Administration under Award Number(s) DE-NA0002576, NSF grant 1029711, the DOE SDAVI Institute, and the U.S. National Science Foundation (Expeditions in Computing program).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Ranshous, S., Chaudhary, M., Samatova, N.F. (2018). Efficient Outlier Detection in Hyperedge Streams Using MinHash and Locality-Sensitive Hashing. In: Cherifi, C., Cherifi, H., Karsai, M., Musolesi, M. (eds) Complex Networks & Their Applications VI. COMPLEX NETWORKS 2017. Studies in Computational Intelligence, vol 689. Springer, Cham. https://doi.org/10.1007/978-3-319-72150-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-72150-7_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72149-1
Online ISBN: 978-3-319-72150-7
eBook Packages: EngineeringEngineering (R0)