ORCA: Outlier detection and Robust Clustering for Attributed graphs

Srinivas Eswar; Ramakrishnan Kannan; Richard Vuduc; Haesun Park

doi:10.1007/s10898-021-01024-z

ORCA: Outlier detection and Robust Clustering for Attributed graphs

Srinivas Eswar, Ramakrishnan Kannan, Richard Vuduc, Haesun Park

Discrete Algorithms

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

A framework is proposed to simultaneously cluster objects and detect anomalies in attributed graph data. Our objective function along with the carefully constructed constraints promotes interpretability of both the clustering and anomaly detection components, as well as scalability of our method. In addition, we developed an algorithm called Outlier detection and Robust Clustering for Attributed graphs (ORCA) within this framework. ORCA is fast and convergent under mild conditions, produces high quality clustering results, and discovers anomalies that can be mapped back naturally to the features of the input data. The efficacy and efficiency of ORCA is demonstrated on real world datasets against multiple state-of-the-art techniques.

Original language	English
Pages (from-to)	967-989
Number of pages	23
Journal	Journal of Global Optimization
Volume	81
Issue number	4
DOIs	https://doi.org/10.1007/s10898-021-01024-z
State	Published - Dec 2021

Funding

This material is based in part upon work supported by the U.S. National Science Foundation (NSF) under Grant Nos. OAC-1642410, CCF-1533768, and OAC-1710371. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF or DOE. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan ( http://energy.gov/downloads/doe-public-access-plan ) This material is based in part upon work supported by the U.S. National Science Foundation (NSF) under Grant Nos. OAC-1642410, CCF-1533768, and OAC-1710371. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF or DOE.

Funders	Funder number
National Science Foundation	DE-AC05-00OR22725, OAC-1642410, OAC-1710371, CCF-1533768
U.S. Department of Energy
Office of Science

Keywords

Anomaly detection
Attributed graphs
Joint matrix low rank approximation
Robust clustering

Access to Document

10.1007/s10898-021-01024-z

Cite this

@article{3bc41175a9254715b9f2a949cc92a2df,

title = "ORCA: Outlier detection and Robust Clustering for Attributed graphs",

abstract = "A framework is proposed to simultaneously cluster objects and detect anomalies in attributed graph data. Our objective function along with the carefully constructed constraints promotes interpretability of both the clustering and anomaly detection components, as well as scalability of our method. In addition, we developed an algorithm called Outlier detection and Robust Clustering for Attributed graphs (ORCA) within this framework. ORCA is fast and convergent under mild conditions, produces high quality clustering results, and discovers anomalies that can be mapped back naturally to the features of the input data. The efficacy and efficiency of ORCA is demonstrated on real world datasets against multiple state-of-the-art techniques.",

keywords = "Anomaly detection, Attributed graphs, Joint matrix low rank approximation, Robust clustering",

author = "Srinivas Eswar and Ramakrishnan Kannan and Richard Vuduc and Haesun Park",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2021",

month = dec,

doi = "10.1007/s10898-021-01024-z",

language = "English",

volume = "81",

pages = "967--989",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - ORCA

T2 - Outlier detection and Robust Clustering for Attributed graphs

AU - Eswar, Srinivas

AU - Kannan, Ramakrishnan

AU - Vuduc, Richard

AU - Park, Haesun

PY - 2021/12

Y1 - 2021/12

N2 - A framework is proposed to simultaneously cluster objects and detect anomalies in attributed graph data. Our objective function along with the carefully constructed constraints promotes interpretability of both the clustering and anomaly detection components, as well as scalability of our method. In addition, we developed an algorithm called Outlier detection and Robust Clustering for Attributed graphs (ORCA) within this framework. ORCA is fast and convergent under mild conditions, produces high quality clustering results, and discovers anomalies that can be mapped back naturally to the features of the input data. The efficacy and efficiency of ORCA is demonstrated on real world datasets against multiple state-of-the-art techniques.

AB - A framework is proposed to simultaneously cluster objects and detect anomalies in attributed graph data. Our objective function along with the carefully constructed constraints promotes interpretability of both the clustering and anomaly detection components, as well as scalability of our method. In addition, we developed an algorithm called Outlier detection and Robust Clustering for Attributed graphs (ORCA) within this framework. ORCA is fast and convergent under mild conditions, produces high quality clustering results, and discovers anomalies that can be mapped back naturally to the features of the input data. The efficacy and efficiency of ORCA is demonstrated on real world datasets against multiple state-of-the-art techniques.

KW - Anomaly detection

KW - Attributed graphs

KW - Joint matrix low rank approximation

KW - Robust clustering

UR - http://www.scopus.com/inward/record.url?scp=85105476096&partnerID=8YFLogxK

U2 - 10.1007/s10898-021-01024-z

DO - 10.1007/s10898-021-01024-z

M3 - Article

AN - SCOPUS:85105476096

SN - 0925-5001

VL - 81

SP - 967

EP - 989

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 4

ER -

ORCA: Outlier detection and Robust Clustering for Attributed graphs

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this