Consistent integration of models based on views of meta models

The complexity of large system models in software engineering nowadays is mastered by using different views. View-based modelling aims at creating small, partial models, each one of them describing some aspect of the system. Existing formal techniques supporting view-based visual modelling are based on typed attributed graphs, where views are related by typed attributed graph morphisms. Such morphisms up to now require a meta model given by a fixed type graph, as well as a fixed data signature and domain. This is in general not adequate for view-oriented modeling where only parts of the complete meta model are known and necessary when modelling a partial view of the system. The aim of this paper is to extend the framework of typed attributed graph morphisms to generalized typed attributed graph morphisms, short GAG-morphisms, which involve changes of the type graph, data signature, and domain. This allows the modeller to formulate type hierarchies and views of visual languages defined by GAG-morphisms between type graphs, short GATG-morphisms. In this paper, we study the interaction and integration of views, and the restriction of views along type hierarchies. In the main result, we present suitable conditions for the integration and decomposition of consistent view models (Theorem 4.1) and extend these conditions to view models defined over meta models with constraints (Theorem 5.1). As a running example, we use a visual domain-specific modelling language to model coarse-grained IT components and their connectors in decentralized IT infrastructures. Using constraints, we formulate connection properties as invariants.     

GMB: A tool for manipulating and animating graph data structures

This paper describes a tool graph originally developed for the Faust environment. Faust is a scientific program development environment being implemented at the Center for Supercomputing Research and Development at the University of Illinois at Urbana-Champaign. The graph tool comprises two major components: the Graph Manager that implements an abstract graph data type, and the Graph Browser that handles the details of displaying a subgraph of a graph created through the Graph Manager. The Graph Browser displays graph views, where a graph view is a subgraph of its parent graph. The concept of graph views is analogous to the concept of views in the traditional database sense. Several graph views may simultaneously exist for a single parent graph, where each view's subgraph depends on the context of the application requesting the view. Goals of the graph tool, GMB, included providing an abstract graph data type for general use and animating graphs efficiently.     

Coherent time-varying graph drawing with multifocus+context interaction

We present a new approach for time-varying graph drawing that achieves both spatiotemporal coherence and multifocus+context visualization in a single framework. Our approach utilizes existing graph layout algorithms to produce the initial graph layout, and formulates the problem of generating coherent time-varying graph visualization with the focus+context capability as a specially tailored deformation optimization problem. We adopt the concept of the super graph to maintain spatiotemporal coherence and further balance the needs for aesthetic quality and dynamic stability when interacting with time-varying graphs through focus+context visualization. Our method is particularly useful for multifocus+context visualization of time-varying graphs where we can preserve the mental map by preventing nodes in the focus from undergoing abrupt changes in size and location in the time sequence. Experiments demonstrate that our method strikes a good balance between maintaining spatiotemporal coherence and accentuating visual foci, thus providing a more engaging viewing experience for the users.     

RailwayDB: adaptive storage of interaction graphs

We are living in an ever more connected world, where data recording the interactions between people, software systems, and the physical world is becoming increasingly prevalent. These data often take the form of a temporally evolving graph, where entities are the vertices and the interactions between them are the edges. We call such graphs interaction graphs. Various domains, including telecommunications, transportation, and social media, depend on analytics performed on interaction graphs. The ability to efficiently support historical analysis over interaction graphs requires effective solutions for the problem of data layout on disk. This paper presents an adaptive disk layout called the railway layout for optimizing disk block storage for interaction graphs. The key idea is to divide blocks into one or more sub-blocks. Each sub-block contains the entire graph structure, but only a subset of the attributes. This improves query I/O, at the cost of increased storage overhead. We introduce optimal integer linear program (ILP) formulations for partitioning disk blocks into sub-blocks with overlapping and nonoverlapping attributes. Additionally, we present greedy heuristics that can scale better compared to the ILP alternatives, yet achieve close to optimal query I/O. We provide an implementation of the railway layout as part of RailwayDB—an open-source graph database we have developed. To demonstrate the benefits of the railway layout, we provide an extensive experimental evaluation, including model-based as well as empirical results comparing our approach to baseline alternatives.     

Interactive and iterative visual exploration of knowledge graphs based on shareable and reusable visual configurations

Knowledge graphs denote structured data which represent entities and relationships between them in a form of a graph, often expressed in the RDF data model. It may be hard for lay users to explore existing knowledge graphs, especially when graphs from different data sources need to be integrated. In this paper, we present an approach to knowledge graph visual exploration based on the concept of shareable and reusable visual configurations. A visual configuration comprises domain specific views on a knowledge graph which define operations such as node detail or expansion. These operations are easy to understand for lay users who can use them to explore a graph while complexities unnecessary in a given application context remain hidden. We introduce an ontology which enables to express and publish visual configurations and reuse their components in other configurations. We also provide an experimental implementation called KGBrowser. We evaluate the proposed approach with real users. We also compare our implementation KGBrowser with other existing tools for knowledge graph visualization and exploration.     

Exploration of networks using overview+detail with constraint-based cooperative layout

A standard approach to large network visualization is to provide an overview of the network and a detailed view of a small component of the graph centred around a focal node. The user explores the network by changing the focal node in the detailed view or by changing the level of detail of a node or cluster. For scalability, fast force-based layout algorithms are used for the overview and the detailed view. However, using the same layout algorithm in both views is problematic since layout for the detailed view has different requirements to that in the overview. Here we present a model in which constrained graph layout algorithms are used for layout in the detailed view. This means the detailed view has high-quality layout including sophisticated edge routing and is customisable by the user who can add placement constraints on the layout. Scalability is still ensured since the slower layout techniques are only applied to the small subgraph shown in the detailed view. The main technical innovations are techniques to ensure that the overview and detailed view remain synchronized, and modifying constrained graph layout algorithms to support smooth, stable layout. The key innovation supporting stability are new dynamic graph layout algorithms that preserve the topology or structure of the network when the user changes the focus node or the level of detail by in situ semantic zooming. We have built a prototype tool and demonstrate its use in two application domains, UML class diagrams and biological networks.      

HybridVis: An adaptive hybrid-scale visualization of multivariate graphs

Existing network visualizations support hierarchical exploration, which rely on user interactions to create and modify graph hierarchies based on the patterns in the data attributes. It will take a relatively long time for users to identify the impact of different attributes on the cluster structure. To address this problem, this paper proposes a visual analytical approach, called HybridVis, creating an interactive layout to reveal clusters of obvious characteristics on one or more attributes at different scales. HybridVis can help people gain social insight and better understand the roles of attributes within a cluster. First, an approximate optimal graph hierarchy based on an energy model is created, considering both data attributes and relationships among data items. Then a layout algorithm and a level-dependent perceptual view for multi-scale graphs are proposed to show the attribute-driven graph hierarchy. Several views, which interact with each other, are designed in HybridVis, including a graphical view of the relationships among clusters; a cluster tree revealing the cluster scales and the details of attributes on parallel coordinates augmented with histograms and interactions. From the meaningful and globally approximate optimal abstraction, users can navigate a large multivariate graph with an overview+detail to explore and rapidly find the potential correlations between the graph structure and the attributes of data items. Finally, experiments using two real world data sets are performed to demonstrate the effectiveness of our methods.     

Selection of views to materialize in a data warehouse

A data warehouse stores materialized views of data from one or more sources, with the purpose of efficiently implementing decision-support or OLAP queries. One of the most important decisions in designing a data warehouse is the selection of materialized views to be maintained at the warehouse. The goal is to select an appropriate set of views that minimizes total query response time and the cost of maintaining the selected views, given a limited amount of resource, e.g., materialization time, storage space, etc. In This work, we have developed a theoretical framework for the general problem of selection of views in a data warehouse. We present polynomial-time heuristics for a selection of views to optimize total query response time under a disk-space constraint, for some important special cases of the general data warehouse scenario, viz.: 1) an AND view graph, where each query/view has a unique evaluation, e.g., when a multiple-query optimizer can be used to general a global evaluation plan for the queries, and 2) an OR view graph, in which any view can be computed from any one of its related views, e.g., data cubes. We present proofs showing that the algorithms are guaranteed to provide a solution that is fairly close to (within a constant factor ratio of) the optimal solution. We extend our heuristic to the general AND-OR view graphs. Finally, we address in detail the view-selection problem under the maintenance cost constraint and present provably competitive heuristics.     

用多层次聚类法完成的大规模关系图的可视化

提出了一种新的大规模图形可视化技术.它可显示含有几万个接点和边的大规模关系图.为了完成对图形的抽象化。一个多层次的聚类图形从原始的大规模关系图中抽取了出来.这种抽取是建立在大规模关系图的内在结构基础上来完成的.一种递规封入式的几何划分算法被应用来完成对几何空间的优化,在具体的制图技术上,使用了一种用力导向布局算法和环形制图法相结合的新方法,从而完成了对显示空间的优化和美擘上的优化.同时也讨论了相关的人机交互技术,所采用的人机交互算法不仅能让使用者从上到下层次式地浏览整个聚类图形。同时也能提供多层次聚类图形的并行浏览.动画技术也同时被运用,以保护使用者的精神图不被打乱.     

Customizing a Fisheye View Algorithm to Preserve the Mental Map

Frequently, large knowledge bases are represented by graphs. Many visualization tools allow users or other applications to interact with and adjust the layouts of these graphs. One layout adjustment problem is that of showing more detail without eliding parts of the graph. Approaches based on a fisheye lens paradigm seem well suited to this task. However, many of these techniques are non-trivial to implement and their distortion techniques often cannot be altered to suit different graph layouts. When distorting a graph layout, it is often desirable to preserve various properties of the original graph in an adjusted view. Pertinent properties may include straightness of lines, graph topology, orthogonalities and proximities. However, it is normally not possible to preserve all of the original properties of the graph layout. The type of layout and its application should be considered when deciding which properties to preserve or distort. This paper describes a fisheye view algorithm which can be customized to suit various different graph layouts. In contrast to other methods, the user can select which properties of the original graph layout to preserve in an adjusted view. The technique is demonstrated through its application to visualizing structures in large software systems.     

Interactive 3D Force‐Directed Edge Bundling

Interactive analysis of 3D relational data is challenging. A common way of representing such data are node‐link diagrams as they support analysts in achieving a mental model of the data. However, naïve 3D depictions of complex graphs tend to be visually cluttered, even more than in a 2D layout. This makes graph exploration and data analysis less efficient. This problem can be addressed by edge bundling. We introduce a 3D cluster‐based edge bundling algorithm that is inspired by the force‐directed edge bundling (FDEB) algorithm [ HvW09b ] and fulfills the requirements to be embedded in an interactive framework for spatial data analysis. It is parallelized and scales with the size of the graph regarding the runtime. Furthermore, it maintains the edge's model and thus supports rendering the graph in different structural styles. We demonstrate this with a graph originating from a simulation of the function of a macaque brain.     

Graph structure analysis based on complex network

In this paper, we propose a novel method to characterize graph structures based on complex network model. First, we show that a structural graph can be modeled as a small-world complex network, and, then, Complex Network Characteristics (including topological and dynamic characteristics) Representation of a Graph (CNCRG) is obtained. Based on these characteristics, graph classification/clustering for objects viewed from different directions and characteristic views identification for single objects are investigated on one synthetic image dataset and two real image datasets. Our experimental results showed that CNCRG achieves better object classification/clustering performance and also provides well-structured view spaces based on multi-dimensional scaling (MDS) and principal component analysis (PCA) embedding methods for graphs extracted from 2D views of 3D objects.     

QA-KGNet: 一种语言模型驱动的知识图谱问答模型

基于知识图谱的问答系统可以解析用户问题,已成为一种检索知识、自动回答所询问题的有效途径.知识图谱问答系统通常是利用神经程序归纳模型,将自然语言问题转化为逻辑形式,在知识图谱上执行该逻辑形式能够得到答案.然而,使用预训练语言模型和知识图谱的知识问答系统包含两个挑战:(1)给定问答(questionanswering, QA)上下文,需要从大型知识图谱(knowledge graph, KG)中识别相关知识;(2)对QA上下文和KG进行联合推理.基于此,提出一种语言模型驱动的知识图谱问答推理模型QA-KGNet,将QA上下文和KG连接起来形成一个工作图,使用语言模型计算给定QA上下文节点与KG节点的关联度,并使用多头图注意力网络更新节点表示.在Commonsense QA、OpenBookQA和Med QA-USMLE真实数据集上进行实验来评估QA-KGNet的性能,实验结果表明:QA-KGNet优于现有的基准模型,表现出优越的结构化推理能力.     

Towards Defense Against Adversarial Attacks on Graph Neural Networks via Calibrated Co-Training

Graph neural networks (GNNs) have achieved significant success in graph representation learning. Nevertheless, the recent work indicates that current GNNs are vulnerable to adversarial perturbations, in particular structural perturbations. This, therefore, narrows the application of GNN models in real-world scenarios. Such vulnerability can be attributed to the model’s excessive reliance on incomplete data views (e.g., graph convolutional networks (GCNs) heavily rely on graph structures to make predictions). By integrating the information from multiple perspectives, this problem can be effectively addressed, and typical views of graphs include the node feature view and the graph structure view. In this paper, we proposeC²oG, which combines these two typical views to train sub-models and fuses their knowledge through co-training. Due to the orthogonality of the views, sub-models in the feature view tend to be robust against the perturbations targeted at sub-models in the structure view.C²oGallows sub-models to correct one another mutually and thus enhance the robustness of their ensembles. In our evaluations,C²oGsignificantly improves the robustness of graph models against adversarial attacks without sacrificing their performance on clean datasets.     

Polyhedral object recognition by indexing

In computer vision, the indexing problem is the problem of recognizing a few objects in a large database of objects while avoiding the help of the classical image-feature-to-object-feature matching paradigm. In this paper we address the problem of recognizing three-dimensional (3-D) polyhedral objects from 2-D images by indexing. Both the objects to be recognized and the images are represented by weighted graphs. The indexing problem is therefore the problem of determining whether a graph extracted from the image is present or absent in a database of model graphs. We introduce a novel method for performing this graph indexing process which is based both on polynomial characterization of binary and weighted graphs and on hashing. We describe in detail this polynomial characterization and then we show how it can be used in the context of polyhedral object recognition. Next we describe a practical recognition-by-indexing system that includes the organization of the database, the representation of polyhedral objects in terms of 2-D characteristic views, the representation of this views in terms of weighted graphs and the associated image processing. Finally, some experimental results allow the evaluation of the system performance.     

SetCoLa: High‐Level Constraints for Graph Layout

Constraints enable flexible graph layout by combining the ease of automatic layout with customizations for a particular domain. However, constraint‐based layout often requires many individual constraints defined over specific nodes and node pairs. In addition to the effort of writing and maintaining a large number of similar constraints, such constraints are specific to the particular graph and thus cannot generalize to other graphs in the same domain. To facilitate the specification of customized and generalizable constraint layouts, we contribute SetCoLa: a domain‐specific language for specifying high‐level constraints relative to properties of the backing data. Users identify node sets based on data or graph properties and apply high‐level constraints within each set. Applying constraints to node sets rather than individual nodes reduces specification effort and facilitates reapplication of customized layouts across distinct graphs. We demonstrate the conciseness, generalizability, and expressiveness of SetCoLa on a series of real‐world examples from ecological networks, biological systems, and social networks.     

基于张量图卷积的多视图聚类

针对多视图聚类进行的数据表示学习,通常采用浅层模型与线性函数实现数据嵌入,该方式无法有效挖掘多种视图间丰富的数据关系.为充分表示不同视图间的一致性信息与互补性信息,本文提出基于张量图卷积的多视图聚类方法(TGCNMC).该方法首先将传统的平面图拼接为张量图,并采用张量图卷积学习各视图中数据的近邻结构;接着利用图间卷积进...     

知识图谱与图嵌入在个性化教育中的应用综述

面对当前日益庞大的教育大数据, 如何在海量数据中高效、准确地提取出高价值的知识, 以满足个性化教学需求, 已成为当前智慧教育的一个研究热点. 作为一种可视化分析技术, 知识图谱可有效构建和挖掘知识及知识间的相互联系, 现已成功应用于诸多领域. 而图嵌入技术的引入, 则有利于提升大数据背景下知识图谱的处理效率.针对个性化...     

多视图对比增强的异质图结构学习方法

异质图神经网络作为一种异质图表示学习的方法,可以有效地抽取异质图中的复杂结构与语义信息,在节点分类和连接预测任务上取得了优异的表现,为知识图谱的表示与分析提供了有力的支撑.现有的异质图由于存在一定的噪声交互或缺失部分交互,导致异质图神经网络在节点聚合、更新时融入错误的邻域特征信息,从而影响模型的整体性能.为解决该问题,提出了多视图对比增强的异质图结构学习模型.该模型首先利用元路径保持异质图中的语义信息,并通过计算每条元路径下节点之间特征相似度生成相似度图,将其与元路径图融合,实现对图结构的优化.通过将相似度图与元路径图作为不同视图进行多视图对比,实现无监督信息的情况下优化图结构,摆脱对监督信号的依赖.最后,为解决神经网络模型在训练初期学习能力不足、生成的图结构中往往存在错误交互的问题,设计了一个渐进式的图结构融合方法.通过将元路径图和相似度图递增地加权相加,改变图结构融合过程中相似度图所占的比例,在抑制了因模型学习能力弱引入过多的错误交互的同时,达到了用相似度图中的交互抑制原有干扰交互或补全缺失交互的目的,实现了对异质图结构的优化.选择节点分类与节点聚类作为图结构学习的验证任务,在4种...     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.