2015-05-09, Bayer, Immanuel, Nagel, Uwe, Rendle, Steffen

Statistical Relational Learning (SRL) methods have shown that classification accuracy can be improved by integrating relations between samples. Techniques such as iterative classification or relaxation labeling achieve this by propagating information between related samples during the inference process. When only a few samples are labeled and connections between samples are sparse, collective inference methods have shown large improvements over standard feature-based ML methods. However, in contrast to feature based ML, collective inference methods require complex inference procedures and often depend on the strong assumption of label consistency among related samples. In this paper, we introduce new relational features for standard ML methods by extracting information from direct and indirect relations. We show empirically on three standard benchmark datasets that our relational features yield results comparable to collective inference methods. Finally we show that our proposal outperforms these methods when additional information is available.

2011, Nagel, Uwe, Thiel, Kilian, Kötter, Tobias, Piatek, Dawid, Berthold, Michael R.

The discovery of surprising relations in large, heterogeneous information repositories is gaining increasing importance in real world data analysis. If these repositories come from diverse origins, forming different domains, domain bridging associations between otherwise weakly connected domains can provide insights into the data that can otherwise not be accomplished. In this paper, we propose a first formalization for the detection of such potentially interesting, domain-crossing relations based purely on structural properties of a relational knowledge description.

2009, Berthold, Michael R., Brandes, Ulrik, Kötter, Tobias, Mader, Martin, Nagel, Uwe, Thiel, Kilian

Almost every application of spreading activation is accompanied by its own set of often heuristic restrictions on the dynamics. We show that in constraint-free scenarios spreading activation would actually yield query-independent results, so that the specific choice of restrictions is not only a pragmatic computational issue, but crucially determines the outcome.

2012, Nagel, Uwe, Thiel, Kilian, Kötter, Tobias, Piatek, Dawid, Berthold, Michael R.

The discovery of surprising relations in large, heterogeneous information repositories is gaining increasing importance in real world data analysis. If these repositories come from diverse origins, forming different domains, domain bridging associations between otherwise weakly connected domains can provide insights into the data that are not accomplished by aggregative approaches. In this paper, we propose a first formalization for the detection of such potentially interesting, domaincrossing relations based purely on structural properties of a relational knowledge description.

2010, Brandes, Ulrik, Lerner, Jürgen, Lubbers, Miranda J., McCarty, Chris, Molina, José Luis, Nagel, Uwe

An individual's personal network encodes social contacts as well as relations among them. Personal networks are therefore considered to be characteristic and meaningful variables of individuals supplementing more traditional characteristics such as age, gender, race, or job position.
We analyze an ensemble of several hundred personal networks of migrants using a recently introduced classification method. As a result, individuals are partitioned into groups defined by similarity of their personal networks, and abstract summaries of classes are obtained. From the analysis we can conclude that Berry's modes of acculturation feature prominently in the empirical data.

2009, Brandes, Ulrik, Lerner, Jürgen, Nagel, Uwe, Nick, Bobo

2011, Nagel, Uwe

Subject of this dissertation is the assessment of graph similarity. The application context and ultimate aim is the analysis of network ensembles, i.e. collections of networks, in the sense of identifying structure among them, e.g. groups of highly similar networks. Structure is in this context understood as some form of regularity or description of the similarities among the considered networks.

As an illustration, consider a collection of two types of networks, where networks of the same type are very similar, while networks of different types are very dissimilar. These two groups form some kind of similarity that is of interest when the ensemble is the object to be analyzed.

Consequently, graphs are in this situation the elementary entities and the main interest is the measurement of structural similarities between them.


The interest in graphs as opposed to e.g. vectors as basic objects is motivated by their descriptive capabilities: some objects, e.g. electric circuits, social networks, comprehend important structural properties that can be expressed directly by modeling them as graphs. They have also found to be a powerful description mechanism for objects that do not incorporate an obvious relational structure as for example in image recognition.


Using graphs to describe objects leads to sets or collections of graphs on which problems of supervised and unsupervised learning are to be solved. A fundamental prerequisite in such approaches is the ability to compare the elementary objects, i.e. assess similarity or dissimilarity between them. For a number supervised and unsupervised learning algorithms a similarity or distance on the objects of analysis is even the sole prerequisite for their application, a prominent example given by support vector machines (c.f.Vapnik(1998)). Motivated by these considerations, three approaches for assessing and measuring similarity between graphs are developed.

2010, Brandes, Ulrik, Lerner, Jürgen, Nagel, Uwe

We present a clustering method for collections of graphs based on the assumptions that graphs in the same cluster have a similar role structure and that the respective roles can be founded on implicit vertex types. Given a network ensemble (a collection of attributed graphs with some substantive commonality), we start by partitioning the set of all vertices based on attribute similarity. Projection of each graph onto the resulting vertex types yields feature vectors of equal dimensionality, irrespective of the original graph sizes. These feature vectors are then subjected to standard clustering methods. This approach is motivated by social network concepts, and we demonstrate its utility on an ensemble of personal networks of migrants, where we extract structurally similar groups and show their resemblance to predicted acculturation strategies.