How can we quickly explain large-scale directed and weighted graphs? We present Spectral Lens (SL) to analyze a variety of real-world networks with both negative and positive edge weights, like DBLP relationships, email communications and Bitcoin trust votings. SL offers value on three levels: (a) Diagnostics: Spectral Lens combines spectral properties from Singular Value Decomposition to create an SL-Dictionary (SLD) to enhance understanding of any directed, weighted graph. (b) Tools: the SL-Algorithm (SLA) automatically extracts the top groups of nodes with similar connectivity, finds groups of shared connectivity and detects suspicious behaviour in a graph. (c) Discoveries: Experiments on several real-world networks illustrate the effectiveness of SLA. Observations from synthetic and real-world networks reveal relations between spectral and graph properties. We show that SLA is highly scalable and linear on the size of a graph. Analyzing a graph with over 2 million edges takes less than 5 minutes. Overall, SL provides an easy-to-use tool for practitioners to explain a weighted and directed graph quickly, to understand its connectivity and identify regular and anomalous behaviors.

How can we fully structure a graph into pieces of meaningful information? Into structures that provide us with insights and carry a meaning beyond simple clustering. How can we also exploit these patterns to compress the graph for fast transmission and easier storage? In many applications of graph analysis like network analysis or medical information extraction we are searching for special patterns. Here, it is not sufficient to extract only parts of the relevant information in a graph, but to understand the complete underlying structure. Therefore, we propose our algorithm MeGS (Partitioning Meaningful Subgraph Structures using Minimum Description Length) to fully understand how a graph is constructed. The most common primitives (clique, hub, tree, bipartite, and sparse) serve as models to split a graph into meaningful structures. Using the principle of Minimum Description Length (MDL) structure types and counts are determined by the best fitting model. These structures achieve the best compression of the adjacency matrix. As result, every node is part of exactly one structure and has an interpretable context. No unknown areas remain in the graph. The higher a model compresses its section of the graph, the stronger its match with the corresponding structural assumption. MeGS, a fast and parameter-free split-and-merge algorithm, automatically finds the optimal structures achieving the best compression. We compare to state-of-the-art algorithms to prove MeGS' ability for interpretation and compression.

Multi-scale data which contains structures at different scales of size and density is a big challenge for spectral clustering. Even given a suitable locally scaled affinity matrix, the first k eigenvectors of such a matrix still cannot separate clusters well. Thus, in this paper, we exploit the fusion of the cluster-separation information from all eigenvectors to achieve a better clustering result. Our method FUll Spectral ClustEring (FUSE) is based on Power Iteration (PI) and Independent Component Analysis (ICA). PI is used to fuse all eigenvectors to one pseudo-eigenvector which inherits all the cluster-separation information. To conquer the cluster-collision problem, we utilize PI to generate p (p > k) pseudo-eigenvectors. Since these pseudo-eigenvectors are redundant and the cluster-separation information is contaminated with noise, ICA is adopted to rotate the pseudo-eigenvectors to make them pairwise statistically independent. To let ICA overcome local optima and speed up the search process, we develop a self-adaptive and self-learning greedy search method. Finally, we select k rotated pseudo-eigenvectors (independent components) which have more cluster-separation information measured by kurtosis for clustering. Various synthetic and real-world data verifies the effectiveness and efficiency of our FUSE method.

The ability to simplify and categorize things is one of the most important elements of human thought, understanding, and learning. The corresponding explorative data analysis techniques -- dimensionality reduction and clustering -- have initially been studied by our community as two separate research topics. Later algorithms like CLIQUE, ORCLUS, 4C, etc. Performed clustering and dimensionality reduction in a joint, alternating process to find clusters residing in low-dimensional subspaces. Such a low-dimensional representation is extremely useful, because it allows us to visualize the relationships between the various objects of a cluster. However, previous methods of subspace, correlation or projected clustering determine an individual subspace for each cluster. In this paper, we demonstrate that it is even much more valuable to find clusters in one common low-dimensional subspace, because then we can study not only the intra-cluster but also the inter-cluster relationships of objects, and the relationships of the whole clusters to each other. We develop the mathematical foundation ORT (Optimal Rigid Transform) to determine an arbitrarily-oriented subspace, suitable for a given cluster structure. Based on ORT, we propose FOSSCLU (Finding the Optimal Sub Space for Clustering), a new iterative clustering algorithm. Our extensive experiments demonstrate that FOSSCLU outperforms the previous methods even in both aspects: clustering and dimensionality reduction.

Recently, fiber segmentation has become an emerging technique in neuroscience. Grouping fiber tracts into anatomical meaningful bundles allows to study the structure of the brain and to investigate onset and progression of neurodegenerative and mental diseases. In this paper, we propose a novel technique for fiber tracts based on shape similarity and connection similarity. For shape similarity, we propose some new techniques adapted from existing similarity measures for trajectory data. We also propose a new technique called Warped Longest Common Subsequence (WLCS) for which we additionally developed a lower-bounding distance function to speed up the segmentation process. Our segmentation is based on an outlier-robust density-based clustering algorithm. Extensive experiments on diffusion tensor images demonstrate the efficiency and effectiveness of our technique.

Car rides are often perceived as dull by the passengers, especially children. Therefore, we aim to introduce a system fostering a collaborative and communicative experience in this environment. This paper presents the design for a game played together by all car-occupants, including the driver, according to their abilities and capacities. A fully implemented prototype of our system called nICE: nice In-Car Experience is evaluated under real world conditions in a user study with five families using a qualitative approach.