Conference Papers

Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506

Browse

Author: search.filters.author.Goyal, S.

Search Results

Now showing 1 - 4 of 4
  • No Thumbnail Available
    Item
    Dynamic structure for web graphs with extended functionalities
    (Association for Computing Machinery acmhelp@acm.org, 2016) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.
    The hyperlink structure of World Wide Web is modeled as a directed, dynamic, and huge web graph. Web graphs are analyzed for determining page rank, fighting web spam, detecting communities, and so on, by performing tasks such as clustering, classification, and reachability. These tasks involve operations such as graph navigation, checking link existence, and identifying active links, which demand scanning of entire graphs. Frequent scanning of very large graphs involves more I/O operations and memory overheads. To rectify these issues, several data structures have been proposed to represent graphs in a compact manner. Even though the problem of representing graphs has been actively studied in the literature, there has been much less focus on representation of dynamic graphs. In this paper, we propose Tree- Dictionary-Representation (TDR), a compressed graph representation that supports dynamic nature of graphs as well as the various graph operations. Our experimental study shows that this representation works efficiently with limited main memory use and provides fast traversal of edges. © 2016 ACM.
  • No Thumbnail Available
    Item
    In-memory representations for mining big graphs
    (Institute of Electrical and Electronics Engineers Inc., 2017) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.
    Graphs are ubiquitous and are the best data structure for representing linked data because of their flexibility, scalability, and power to deal with complexity. Storing big graphs in graph databases leads to difficult computation and increased time complexity. The best alternative is to use inmemory representations such as compact data structures. They compress the graph sufficiently such that it can be stored in memory and can allow all the possible operations in compressed form itself. In this paper we discuss about five compression techniques: WebGraph, Re-pair, BFS, k2, and dk2. In addition, we compare them based on four parameters: compression ratio, supported functionalities, supported graph types, and dynamic support. The paper is concluded by bringing out the need to have a more advanced, dynamic, and versatile compression technique. © 2016 IEEE.
  • No Thumbnail Available
    Item
    DROCC: Deep Robust One-Class Classification
    (ML Research Press, 2020) Goyal, S.; Raghunathan, A.; Jain, M.; Simhadri, H.; Jain, P.
    Classical approaches for one-class problems such as one-class SVM and isolation forest require careful feature engineering when applied to structured domains like images. State-of-the-art methods aim to leverage deep learning to learn appropriate features via two main approaches. The first approach based on predicting transformations (Golan & El-Yaniv, 2018; Hendrycks et al., 2019a) while successful in some domains, crucially depends on an appropriate domain-specific set of transformations that are hard to obtain in general. The second approach of minimizing a classical one-class loss on the learned final layer representations, e.g., DeepSVDD (Ruff et al., 2018) suffers from the fundamental drawback of representation collapse. In this work, we propose Deep Robust One Class Classification (DROCC) that is both applicable to most standard domains without requiring any side-information and robust to representation collapse. DROCC is based on the assumption that the points from the class of interest lie on a well-sampled, locally linear low dimensional manifold. Empirical evaluation demonstrates that DROCC is highly effective in two different one-class problem settings and on a range of real-world datasets across different domains: tabular data, images (CIFAR and ImageNet), audio, and time-series, offering up to 20% increase in accuracy over the state-of-the-art in anomaly detection. Code is available at https://github.com/microsoft/EdgeML. © 2020 by the author(s).
  • No Thumbnail Available
    Item
    DROCC: Deep robust one-class classification
    (International Machine Learning Society (IMLS), 2020) Goyal, S.; Raghunathan, A.; Jain, M.; Simhadri, H.; Jain, P.
    Classical approaches for one-class problems such as one-class SVM and isolation forest require careful feature engineering when applied to structured domains like images. State-of-the-art methods aim to leverage deep learning to learn appropriate features via two main approaches. The first approach based on predicting transformations (Golan & El-Yaniv, 2018; Hendrycks et al., 2019a) while successful in some domains, crucially depends on an appropriate domain-specific set of transformations that are hard to obtain in general. The second approach of minimizing a classical one-class loss on the learned final layer representations, e.g., DeepSVDD (Ruff et al., 2018) suffers from the fundamental drawback of representation collapse. In this work, we propose Deep Robust One Class Classification (DROCC) that is both applicable to most standard domains without requiring any side-information and robust to representation collapse. DROCC is based on the assumption that the points from the class of interest lie on a well-sampled, locally linear low dimensional manifold. Empirical evaluation demonstrates that DROCC is highly effective in two different one-class problem settings and on a range of real-world datasets across different domains: tabular data, images (CIFAR and ImageNet), audio, and time-series, offering up to 20% increase in accuracy over the state-of-the-art in anomaly detection. Code is available at https://github.com/microsoft/EdgeML. © 2020 by the author(s).