Thesis (M.S. in Computer Science and M.S. in Software Engineering)--Naval Postgraduate School, September 2006. / Thesis Advisor(s): Mikhail Auguston, Man-Tak Shing. "September 2006." Includes bibliographical references (p. 71-). Also available in print.

Attributed Relational Graph (ARG) is a powerful representation for model based object recognition due to its inherent robustness in handling noisy and incomplete data. In the past few years, the availability of efficient ARG matching algorithms and their theoretical underpinnings have greatly contributed to many successful applications of ARG representation in tackling high level vision problems. During my past three year investigation into object recognition using ARG representation, we have developed a number of novel theories and techniques in the subject area. Some are image processing techniques which help to segment and generate primitive features for building ARG representation (Chapter 2 and 4). Some are about projective invariance in ARG representations (Chapter 3 and 5). Some are about new ARG matching algorithms (Chapter 6). This thesis serves as a summary document of these theories and techniques. The most important contributions of our work to the domain of computer vision, in my opinion, are in two areas: Firstly, in the area of projective invariant ARG representation for object recognition. Here, we demonstrated for the first time, a way to systematically derive ARG representation for objects under complex projective transform by exploiting the knowledge of invariance. The methodology developed by us is a sound strategy that generates ARG representations with a number of desirable and provable properties, amongst which, the most important one is the ability to capture global transformation constraint using binary relations only. The approach significantly reduces the heuristic nature of designing relational measurements and paves the way for wider application of ARG representation in 2D and 3D object recognition. Secondly, in the area of ARG matching. A new mathematical framework for deterministic relaxation algorithms was developed to overcome a number of problems appeared in the existing theories and practises of efficient ARG labelling. A novel labelling algorithm was proposed based on the new theoretical framework. The algorithm has a number of desirable properties compared to existing algorithms. In particular, the resulting algorithm delivers more consistent, faithful-to-observation results in the presence of ambiguities and multiple interpretations compared to other algorithms.

abstract: Graph is a ubiquitous data structure, which appears in a broad range of real-world scenarios. Accordingly, there has been a surge of research to represent and learn from graphs in order to accomplish various machine learning and graph analysis tasks. However, most of these efforts only utilize the graph structure while nodes in real-world graphs usually come with a rich set of attributes. Typical examples of such nodes and their attributes are users and their profiles in social networks, scientific articles and their content in citation networks, protein molecules and their gene sets in biological networks as well as web pages and their content on the Web. Utilizing node features in such graphs---attributed graphs---can alleviate the graph sparsity problem and help explain various phenomena (e.g., the motives behind the formation of communities in social networks). Therefore, further study of attributed graphs is required to take full advantage of node attributes. In the wild, attributed graphs are usually unlabeled. Moreover, annotating data is an expensive and time-consuming process, which suffers from many limitations such as annotators’ subjectivity, reproducibility, and consistency. The challenges of data annotation and the growing increase of unlabeled attributed graphs in various real-world applications significantly demand unsupervised learning for attributed graphs. In this dissertation, I propose a set of novel models to learn from attributed graphs in an unsupervised manner. To better understand and represent nodes and communities in attributed graphs, I present different models in node and community levels. In node level, I utilize node features as well as the graph structure in attributed graphs to learn distributed representations of nodes, which can be useful in a variety of downstream machine learning applications. In community level, with a focus on social media, I take advantage of both node attributes and the graph structure to discover not only communities but also their sentiment-driven profiles and inter-community relations (i.e., alliance, antagonism, or no relation). The discovered community profiles and relations help to better understand the structure and dynamics of social media. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

Recent research in feature learning has been extended to sequence data, where each instance consists of a sequence of heterogeneous items with a variable length. However, in many real-world applications, the data exists in the form of attributed sequences, which is composed of a set of fixed-size attributes and variable-length sequences with dependencies between them. In the attributed sequence context, feature learning remains challenging due to the dependencies between sequences and their associated attributes. In this dissertation, we focus on analyzing and building deep learning models for four new problems on attributed sequences. First, we propose a framework, called NAS, to produce feature representations of attributed sequences in an unsupervised fashion. The NAS is capable of producing task independent embeddings that can be used in various mining tasks of attributed sequences. Second, we study the problem of deep metric learning on attributed sequences. The goal is to learn a distance metric based on pairwise user feedback. In this task, we propose a framework, called MLAS, to learn a distance metric that measures the similarity and dissimilarity between attributed sequence feedback pairs. Third, we study the problem of one-shot learning on attributed sequences. This problem is important for a variety of real-world applications ranging from fraud prevention to network intrusion detection. We design a deep learning framework OLAS to tackle this problem. Once the OLAS is trained, we can then use it to make predictions for not only the new data but also for entire previously unseen new classes. Lastly, we investigate the problem of attributed sequence classification with attention model. This is challenging that now we need to assess the importance of each item in each sequence considering both the sequence itself and the associated attributes. In this work, we propose a framework, called AMAS, to classify attributed sequences using the information from the sequences, metadata, and the computed attention. Our extensive experiments on real-world datasets demonstrate that the proposed solutions significantly improve the performance of each task over the state-of-the-art methods on attributed sequences.

A transformação entre linguagens, ou entre diferentes formatos de uma mesma linguagem, é um assunto que desperta interesse há vários anos e desta forma alguns trabalhos tem surgido para tentar automatizar o processo de transformação entre notações diferentes. Este trabalho descreve as Gramáticas Transformacionais empregados para descrever as transformag6es necessárias para converter uma notação em uma linguagem fonte (LF) para uma notação equivalente em uma linguagem objeto (LO). Nesta Gramática é embutido o conceito de Gramáticas de Atributos, criando assim as Gramáticas Transformacionais com Atributos (GTAs). Para validação das GTAs é apresentado um protótipo de ferramenta transformacional, que gera um tradutor, de LF para LO, a partir da descrição da gramática da LF e das regras de transformações para a LO. Tanto a LF quanto a LO são gramáticas do tipo LALR(1). Como objetivo de construir a ferramenta mais genérica possível, foram realizados estudos sobre três ferramentas, com as quais as transformações são possíveis. São elas: YACC, SINLEX e GG. É feita uma breve descrição destas três ferramentas e uma comparação com o protótipo implementado. / Languages transformation or transformation among differents formats of the same language is a subject that , has had a lot of interest for t many years. Thus, research has been done aiming to automatize the proccess of transformation from one notation to another. This work describes the use of Transformation Grammars to describe the necessary transformations to convert from a Source Language (SL) notation to an equivalent Object Language (OL). The concept of Attribute Grammars is embbeded to these grammars, defining an Attributed Transformation Grammar (ATG). A transformation tool prototype to evaluate the ATGs is presented. This tool generates a translator from SL to OL using the SL grammar description and the corresponding transformation rules to the OL. Both the SL and OL are LALR(1) grammars. Studies on YACC, SINLEX and GG (tools wich allow transformations) were done trying to reach the most generic tool. A brief descriptions of these tools and a comparision with the prototype is presented.

A transformação entre linguagens, ou entre diferentes formatos de uma mesma linguagem, é um assunto que desperta interesse há vários anos e desta forma alguns trabalhos tem surgido para tentar automatizar o processo de transformação entre notações diferentes. Este trabalho descreve as Gramáticas Transformacionais empregados para descrever as transformag6es necessárias para converter uma notação em uma linguagem fonte (LF) para uma notação equivalente em uma linguagem objeto (LO). Nesta Gramática é embutido o conceito de Gramáticas de Atributos, criando assim as Gramáticas Transformacionais com Atributos (GTAs). Para validação das GTAs é apresentado um protótipo de ferramenta transformacional, que gera um tradutor, de LF para LO, a partir da descrição da gramática da LF e das regras de transformações para a LO. Tanto a LF quanto a LO são gramáticas do tipo LALR(1). Como objetivo de construir a ferramenta mais genérica possível, foram realizados estudos sobre três ferramentas, com as quais as transformações são possíveis. São elas: YACC, SINLEX e GG. É feita uma breve descrição destas três ferramentas e uma comparação com o protótipo implementado. / Languages transformation or transformation among differents formats of the same language is a subject that , has had a lot of interest for t many years. Thus, research has been done aiming to automatize the proccess of transformation from one notation to another. This work describes the use of Transformation Grammars to describe the necessary transformations to convert from a Source Language (SL) notation to an equivalent Object Language (OL). The concept of Attribute Grammars is embbeded to these grammars, defining an Attributed Transformation Grammar (ATG). A transformation tool prototype to evaluate the ATGs is presented. This tool generates a translator from SL to OL using the SL grammar description and the corresponding transformation rules to the OL. Both the SL and OL are LALR(1) grammars. Studies on YACC, SINLEX and GG (tools wich allow transformations) were done trying to reach the most generic tool. A brief descriptions of these tools and a comparision with the prototype is presented.

A transformação entre linguagens, ou entre diferentes formatos de uma mesma linguagem, é um assunto que desperta interesse há vários anos e desta forma alguns trabalhos tem surgido para tentar automatizar o processo de transformação entre notações diferentes. Este trabalho descreve as Gramáticas Transformacionais empregados para descrever as transformag6es necessárias para converter uma notação em uma linguagem fonte (LF) para uma notação equivalente em uma linguagem objeto (LO). Nesta Gramática é embutido o conceito de Gramáticas de Atributos, criando assim as Gramáticas Transformacionais com Atributos (GTAs). Para validação das GTAs é apresentado um protótipo de ferramenta transformacional, que gera um tradutor, de LF para LO, a partir da descrição da gramática da LF e das regras de transformações para a LO. Tanto a LF quanto a LO são gramáticas do tipo LALR(1). Como objetivo de construir a ferramenta mais genérica possível, foram realizados estudos sobre três ferramentas, com as quais as transformações são possíveis. São elas: YACC, SINLEX e GG. É feita uma breve descrição destas três ferramentas e uma comparação com o protótipo implementado. / Languages transformation or transformation among differents formats of the same language is a subject that , has had a lot of interest for t many years. Thus, research has been done aiming to automatize the proccess of transformation from one notation to another. This work describes the use of Transformation Grammars to describe the necessary transformations to convert from a Source Language (SL) notation to an equivalent Object Language (OL). The concept of Attribute Grammars is embbeded to these grammars, defining an Attributed Transformation Grammar (ATG). A transformation tool prototype to evaluate the ATGs is presented. This tool generates a translator from SL to OL using the SL grammar description and the corresponding transformation rules to the OL. Both the SL and OL are LALR(1) grammars. Studies on YACC, SINLEX and GG (tools wich allow transformations) were done trying to reach the most generic tool. A brief descriptions of these tools and a comparision with the prototype is presented.

Graphs have attracted researchers in various fields in that many different kinds of real-world entities and relationships between them can be represented and analyzed effectively and efficiently using graphs. In particular, researchers in data mining and machine learning areas have developed algorithms and models to understand the complex graph data better and perform various data mining tasks. While a large body of work exists on graph mining, most existing work does not fully exploit attributes attached to graph nodes or edges.<div><br></div><div>In this dissertation, we exploit node attributes to generate better solutions to several graph data mining problems addressed in the literature. First, we introduce the notion of statistically significant attribute associations in attribute graphs and propose an effective and efficient algorithm to discover those associations. The effectiveness analysis on the results shows that our proposed algorithm can reveal insightful attribute associations that cannot be identified using the earlier methods focused solely on frequency. Second, we build a probabilistic generative model for observed attributed graphs. Under the assumption that there exist hidden communities behind nodes in a graph, we adopt the idea of latent topic distributions to model a generative process of node attribute values and link structure more precisely. This model can be used to detect hidden communities and profile missing attribute values. Lastly, we investigate how to employ node attributes to learn latent representations of nodes in lower dimensional embedding spaces and use the learned representations to improve the performance of data mining tasks over attributed graphs.<br></div>

Made available in DSpace on 2016-07-27T14:21:55Z (GMT). No. of bitstreams: 1 Daniella Holanda de Assuncao.pdf: 855594 bytes, checksum: cc8afd3a9784b399203cc4cba335b370 (MD5) Previous issue date: 2010-03-10 / This research aimed at analyzing the relationship among the meaning attributed to work, the strategies used to cope with stressful situations, some demographic variables, types of problem, and origin of adverse conditions. The sample was composed by 249 young adults from a college located in the Midwestern Region of Brazil, with mean age of 27 years (SD = 4.92) and 58.2% females. The instruments used in the assessment were: Inventário da Motivação e Significado do Trabalho (IMST, Inventory of Motivation and Meaning of Work), Coping Response Inventory (CRI Adult), and a questionnaire for the demographic variables. Through the descriptive analysis of the stressors registered in the coping scale, we detected predominance (51%) of relational problems. The most used strategies were: problem solving, positive appraisal, and logical analysis. Regarding the meaning attributed to work, we detected prevalence of valorative attributes. To analyze the meaning of work and coping strategies, we applied the correlation coefficient of Pearson r , which pointed to a low negative correlation between the valorative attribute and the active-cognitive coping. As to the assessment of the relationships among coping and the variables types of problem and origin of adverse conditions, we detected that the strategy seeking support and guidance presented more association with individual problems and attribution of the problem to the own individual in comparison with relational problems and problems attributed to the boss. Using multiple regression (stepwise) to analyze the influence of the demographic variables and the meaning attributed to work upon coping strategies, we observed that the sex of the participants and the valorative attributes presented predictive power for avoidance coping, although in a negative relationship. To evaluate the demographic variables in their relationship with coping strategies we applied the t-test for independent data samples and detected that women used more the strategy emotional discharge and avoidance coping than men. Based on these results, we conclude that when young adults think about how their work should be, they do not imagine keeping this issue at a distance until another factor modifies the situation and use more approach coping strategies to deal with problems at work, which favors their wellbeing. / Esta pesquisa objetivou analisar a relação entre o significado atribuído ao trabalho, as estratégias utilizadas para enfrentamento de situações estressantes, algumas variáveis sociodemográficas, tipos de problema e origem das condições adversas. A amostra foi composta por 249 jovens adultos de uma faculdade situada na Região Centro-Oeste do Brasil, com idade média de 27 anos (DP = 4,92), sendo 58,2% do sexo feminino. Os instrumentos de medida utilizados foram: Inventário da Motivação e Significado do Trabalho (IMST), Coping Response Inventory (CRI Adult) e um questionário para as variáveis sociodemográficas. Pela análise descritiva dos estressores relatados na escala de coping, detectou-se predominância (51%) de problemas relacionais. As estratégias mais utilizadas foram: resolução de problemas, reavaliação positiva e análise lógica. Quanto ao significado atribuído ao trabalho, houve prevalência dos atributos valorativos. Para analisar o significado do trabalho e as estratégias de enfrentamento, aplicou-se o coeficiente de correlação de Pearson r , que apontou para uma correlação baixa e negativa entre atributo valorativo e coping de evitação. Com relação à análise das relações entre coping e as variáveis tipos de problema e origem das condições adversas, verificou-se que a estratégia busca de guia e suporte social apresentou maior associação com problemas individuais e atribuição do problema ao próprio indivíduo em comparação com problemas relacionais e com problemas atribuídos à chefia. Ao aplicar a regressão múltipla (stepwise) à análise da influência das variáveis sociodemográficas e do significado do trabalho sobre as estratégias de enfrentamento, verificou-se que o sexo dos participantes e os atributos valorativos apresentaram poder preditor sobre coping de evitação, embora em uma relação negativa. Para avaliar as variáveis sociodemográficas na relação com as estratégias de coping, utilizou-se o Teste t para amostra de dados independentes e constatou-se que as mulheres utilizaram mais a estratégia descarga emocional e o coping de evitação que os homens. Com base nesses resultados, concluise que quando os jovens adultos pensam em como deveria ser o trabalho, não imaginam colocar o problema a distância até que outro fator modifique a situação e utilizam mais estratégias de coping de aproximação para enfrentar problemas laborais, o que pode favorecer seu bem-estar.

Au cours de la dernière décennie, les réseaux (les graphes) se sont révélés être un outil efficace pour modéliser des systèmes complexes. La problématique de détection de communautés est une tâche centrale dans l’analyse des réseaux complexes. La majeur partie des travaux dans ce domaine s’intéresse à la structure topologique des réseaux. Cependant, dans plusieurs cas réels, les réseaux complexes ont un ensemble d’attributs associés aux nœuds et/ou aux liens. Ces réseaux sont dites : réseaux attribués. Mes activités de recherche sont basées principalement sur la détection des communautés dans les réseaux attribués. Pour aborder ce problème, on s’est intéressé dans un premier temps aux attributs relatifs aux liens, qui sont un cas particulier des réseaux multiplexes. Un multiplex est un modèle de graphe multi-relationnel. Il est souvent représenté par un graphe multi-couches. Chaque couche contient le même ensemble de nœuds mais encode une relation différente. Dans mes travaux de recherche, nous proposons une étude comparative des différentes approches de détection de communautés dans les réseaux multiplexes. Cette étude est faite sur des réseaux réels. Nous proposons une nouvelle approche centrée "graine" pour la détection de communautés dans les graphes multiplexes qui a nécessité la redéfinition des métriques de bases des réseaux complexes au cas multiplex. Puis, nous proposons une approche de clustering dans les réseaux attribués qui prend en considération à la fois les attributs sur les nœuds et sur les liens. La validation de mes approches a été faite avec des indices internes et externes, mais aussi par une validation guidée par un système de recommandation que nous avons proposé et dont la détection de communautés est sa tâche principale. Les résultats obtenus sur ces approches permettent d’améliorer la qualité des communautés détectées en prenant en compte les informations sur les attributs du réseaux. De plus, nous offrons des outils d’analyse des réseaux attribués sous le langage de programmation R. / In complex networks analysis field, much effort has been focused on identifying graphs communities of related nodes with dense internal connections and few external connections. In addition to node connectivity information that are mostly composed by different types of links, most real-world networks contains also node and/or edge associated attributes which can be very relevant during the learning process to find out the groups of nodes i.e. communities. In this case, two types of information are available : graph data to represent the relationship between objects and attributes information to characterize the objects i.e nodes. Classic community detection and data clustering techniques handle either one of the two types but not both. Consequently, the resultant clustering may not only miss important information but also lead to inaccurate findings. Therefore, various methods have been developed to uncover communities in networks by combining structural and attribute information such that nodes in a community are not only densely connected, but also share similar attribute values. Such graph-shape data is often referred to as attributed graph.This thesis focuses on developing algorithms and models for attributed graphs. Specifically, I focus in the first part on the different types of edges which represent different types of relations between vertices. I proposed a new clustering algorithms and I also present a redefinition of principal metrics that deals with this type of networks.Then, I tackle the problem of clustering using the node attribute information by describing a new original community detection algorithm that uncover communities in node attributed networks which use structural and attribute information simultaneously. At last, I proposed a collaborative filtering model in which I applied the proposed clustering algorithms.