PhD, University of Cincinnati, 2020, Engineering and Applied Science: Computer Science and Engineering

Graphs arise naturally in many complex systems where they are used to represent entities and relationships between them. The analysis of graph-based models has wide applications like evaluating the significance of interactions between individual entities, identifying important subcomponents, discovering hidden interactions, and making complex inferences about the functions of the underlying systems. Many of these applications require meaningful representation of nodes, and several graph-embedding algorithms have recently been developed to embed nodes in meaningful vector spaces. However, it is not clear how the performance of these algorithms depends on the structural features of graphs, which can vary a lot across real world domains. It would thus be useful to identify the main features that influence the performance of embedding approaches, and to develop a method that can determine the most suitable method for any given graph. The research described in this dissertation applies a systematic approach to comparing various graph-embedding methods on several types of graphs, relates their performance to the structural features of the graphs, and develops a system to select the best embedding method based on graph features. By evaluating the node embedding algorithms for link prediction on several synthetic graph models and real-world network datasets, this study demonstrates the fact that the structural properties of a graph have a significant effect on how well any given node embedding algorithm performs on it. For a particular graph, the performance of a node embedding algorithm can be predicted based on the structural properties, and this relationship holds across a wide range of network types and real-world networks. The results in this dissertation lead to several insights about which algorithms work for various types of graphs.

Committee: Ali Minai Ph.D. (Committee Chair); Raj Bhatnagar Ph.D. (Committee Member); Yizong Cheng Ph.D. (Committee Member); Jaroslaw Meller Ph.D. (Committee Member); Carla Purdy Ph.D. (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2019, Computer Science and Engineering

Taxonomy graphs that capture hyponymy or meronymy relationships through directed edges are expected to be acyclic. However, in practice, they may have thousands of cycles, as they are often created in a crowd-sourced way. Since these cycles represent logical fallacies, they need to be removed for many web applications. In this thesis, we first address the problem of breaking cycles while preserving the logical structure (hierarchy) of a directed graph as much as possible. Existing approaches for this problem either need manual intervention or use heuristics that can critically alter the taxonomy structure. In contrast, our approach infers graph hierarchy using a range of features, including a Bayesian skill rating system and a social agony metric. We also devise several strategies to leverage the inferred hierarchy for removing a small subset of edges to make the graph acyclic. We then apply our breaking cycles technique to address the problem of Question Difficulty and Expertise Estimation (QDEE) in Community Question Answer (CQA) sites such as Yahoo! Answers and Stack Overflow. Our framework QDEE tackles a fundamental challenge in crowdsourcing: how to appropriately route and assign questions to users with suitable expertise. This problem domain has been the subject of much research and includes both language-agnostic as well as language conscious solutions. We bring to bear a key language-agnostic insight: that users gain expertise and therefore tend to ask as well as answer more difficult questions over time. We use this insight within the popular competition (directed) graph model to estimate question difficulty and user expertise by identifying key hierarchical structure within the said model. Difficulty levels of newly posted questions (the cold-start problem) are estimated by using our QDEE framework and additional textual features. We also propose a model to route newly posted questions to appropriate users based on the difficulty level of the question (open full item for complete abstract)

Committee: Srinivasan Parthasarathy (Advisor); Huan Sun (Committee Member); Eric Fosler-Lussier (Committee Member); Darren Drewry (Committee Member) Subjects: Computer Engineering; Computer Science

Doctor of Philosophy, The Ohio State University, 2018, Computer Science and Engineering

Machine learning is the process of learning meaningful patterns and extracting useful knowledge from data using computational and statistical techniques. While the overall goal is to help humans better understand the data and learn how to perform specific tasks, most of the current methodologies fail to fulfill it because they do not closely involve humans in the process and cannot apprehend human demands. This limitation has drawn more and more attention of researchers, and there is an increasing amount of study on human-in-the-loop machine learning. However, we are still facing a series of challenges in this area, especially 1) to fully capture the supervision and demands of the humans; 2) to effectively incorporate human supervision into machine learning; 3) to scale up the human-guided machine learning to large-scale datasets. In this dissertation, we show how to tackle these challenges on a few particular machine learning tasks and present some promising results towards this direction. First, we discuss how to conduct outlier detection robustly and efficiently with contextual information provided by humans. In this problem, we ask users to select some of the attributes as context and study anomalous behavior with the rest of attributes. Second, we show methods to mine relationships in heterogeneous information networks (HINs) following the interests of the humans. In this problem, the users provide the pair of targeted entities and the type of relationship that they are interested in, and we propose a novel method (called PRO-HEAPS) to efficiently discover most suitable relationship instances from the information networks. Third, we investigate how humans can be involved in a practical medical data analysis framework for a game-based stroke rehabilitation system, called RehabANLYS. Specifically, we study how to integrate the domain knowledge from doctors with the participation of patients to provide effective analysis on rehabilitation measurements. Fourth, (open full item for complete abstract)

Committee: Srinivasan Parthasarathy (Advisor); Arnab Nandi (Committee Member); Huan Sun (Committee Member); Guo-Liang Wang (Committee Member) Subjects: Computer Science

PhD, University of Cincinnati, 2011, Engineering and Applied Science: Computer Science and Engineering

Graphs serve as an important tool for discrete data representation. Recently, graph representations have made possible very powerful machine learning algorithms, such as manifold learning, kernel methods, semi-supervised learning. With the advent of large-scale real world networks, such as biological networks (disease network, drug target network, etc.), social networks (DBLP Co-authorship network, Facebook friendship, etc.), machine learning and data mining algorithms have found new application areas and have contributed to advance our understanding of properties, and phenomena governing real world networks. When dealing with real world data represented as networks, two problems arise quite naturally: I) How to integrate and align the knowledge encoded in multiple and heterogeneous networks? For instance, how to find out the similar genes in co-disease and protein-protein interaction networks? II) How to model and predict the evolution of a dynamic network? A real world example is, given N years snapshots of an evolving social network, how to build a model that can capture the temporal evolution and make reliable prediction? In this dissertation, we present an innovative graph embedding framework, which identifies the key components of modeling the evolution in time of a dynamic graph. Different from the many state-of-the-art graph link prediction and modeling algorithms, it formulates the link prediction problem from a geometric perspective that can capture the dynamics of the intrinsic continuous graph manifold evolution. It is attractive due to its simplicity and the potential to relax the mining problem into a feasible domain which enables standard machine learning and regression models to utilize historical graph time series data. To address the first problem, we first propose a novel probability-based similarity measure which led to promising applications in content based image retrieval and image annotation, followed by a manifold alignment framework t (open full item for complete abstract)

Committee: Anca Ralescu PhD (Committee Chair); Anil Jegga DVMMRes (Committee Member); Fred Annexstein PhD (Committee Member); Kenneth Berman PhD (Committee Member); Yizong Cheng PhD (Committee Member); Dan Ralescu PhD (Committee Member) Subjects: Computer Science

Master of Science (MS), Wright State University, 2024, Computer Science

The effectiveness of a deployed knowledge graph is commonly evaluated with defined use-cases from domain experts. This poses challenges during the development cycle in determining how to represent data. Developers of a knowledge graph can optionally include semantics into a knowledge graph by abstracting the data representation in such a way that mirrors information as it exists in the real world. Consequently, the abstraction is represented by additional layers, resulting in performant differences in knowledge graph embedding; such as, the embedded model's ability to infer facts between entities through link predictions. This thesis presents a comprehensive analysis of the performance impact observed across a range of knowledge graph embedding models trained on FB15k-237, a widely recognized benchmark dataset for knowledge graph completion. Additionally, the experiment is performed with augmented versions of FB15k-237, serving to introduce semantics into the knowledge graph.

Committee: Cogan Shimizu Ph.D. (Advisor); Wen Zhang Ph.D. (Committee Member); Lingwei Chen Ph.D. (Committee Member) Subjects: Computer Science

Master of Science (MS), Wright State University, 2021, Computer Science

Link prediction in the domain of scientific collaborative networks refers to exploring and determining whether a connection between two entities in an academic network may emerge in the future. This study aims to analyze the relevance of academic collaborations and identify the factors that drive co-author relationships in a heterogeneous bibliographic network. Using topological, semantic, and graph representation learning techniques, we measure the authors' similarities w.r.t their structural and publication data to identify the reasons that promote co-authorships. Experimental results show that the proposed approach successfully infer the co-author links by identifying authors with similar research interests. Such a system can be used to recommend potential collaborations among the authors.

Committee: Tanvi Banerjee Ph.D. (Advisor); Krishnaprasad Thirunarayan Ph.D. (Committee Member); Michael L. Raymer Ph.D. (Committee Member) Subjects: Artificial Intelligence; Computer Science

Master of Computer Science (M.C.S.), University of Dayton, 2019, Computer Science

Google and other search engines feature the entity search by representing a knowledge card summarizing related facts about the user-supplied entity. However, the knowledge card is limited to certain entities which have a Wiki page or an entry in encyclopedias such as Freebase. The current encyclopedias are limited to highly popular entities which are far fewer compared with the emerging entities. Despite the availability of knowledge about the emerging entities on the search results, yet there are no approaches to capture, abstract, summarize, fuse, and validate fragmented pieces of knowledge about them. Thus, in this paper, we develop approaches to capture two types of knowledge about the emerging entities from a corpus extended from top-n search snippets of a given emerging entity. The first kind of knowledge identifies the role(s) of the emerging entity as, e.g., who is s/he? The second kind captures the entities closely associated with the emerging entity. As the testbed, we considered a collection of 20 emerging entities and 20 popular entities as the ground truth. Our approach is an unsupervised approach based on text analysis and entity embeddings. Our experimental studies show promising results as the accuracy of more than 87% for recognizing entities and 75% for ranking them. Beside 87% of the entailed types were recognizable. Our testbed and source codes are available on Github (https://github.com/sunnyUD/research_source_code).

Committee: Saeedeh Shekarpour Ph.D (Committee Chair); Ju Shen Ph.D (Committee Member); Zhongmei Yao Ph.D (Committee Member); Tam Nguyen Ph.D (Committee Member); James Buckley Ph.D (Advisor) Subjects: Computer Science; Information Systems

Master of Science, The Ohio State University, 2019, Computer Science and Engineering

There is growing interest for learning representations for nodes in a network. Several embedding generation algorithms have been proposed in the last few years that generate high quality representations for downstream tasks like node classification and link prediction. NetMF is one such algorithm that provides the theoretical foundations for proving that several network representation learning techniques implicitly factorize a closed form matrix derived from the graph. However, the NetMF algorithm is slow and does not scale well, owing to the multiple dense matrix multiplication steps and Singular Value Decomposition (SVD). We present Fast-NetMF, a fast, highly scalable version of the NetMF algorithm with reduced running time. In this work, we investigate the acceleration of NetMF under single-GPU and multi-core CPU settings. We also investigate replacing the slow SVD based matrix factorization step for faster and more parallel-friendly factorization techniques like Non-negative Matrix Factorization (NMF).

Committee: Srinivasan Parthasarathy (Advisor); Sadayappan P (Committee Member) Subjects: Computer Engineering; Computer Science