389 citations · 1.1k across the 26 of their papers we have counts for
32 papers
On the Complexity of Graph Edit Distance in Restricted Graph Classes
Maximilian Limmer, Nils M. Kriege
The graph edit distance generalizes several well-known NP-hard problems and is therefore NP-hard itself. However, the relationship between the considered graph class, the edit cost…
Approximating the Graph Edit Distance with Compact Neighborhood Representations
Franka Bause, Christian Permann, Nils M. Kriege
The graph edit distance is used for comparing graphs in various domains. Due to its high computational complexity it is primarily approximated. Widely-used heuristics search for an…
On the Two Sides of Redundancy in Graph Neural Networks
Franka Bause, Samir Moustafa, Johannes Langguth +2
Message passing neural networks iteratively generate node embeddings by aggregating information from neighboring nodes. With increasing depth, information from more distant nodes i…
A Higher-Order Temporal H-Index for Evolving Networks
Lutz Oettershagen, Nils M. Kriege, Petra Mutzel
The H-index of a node in a static network is the maximum value such that at least of its neighbors have a degree of at least . Recently, a generalized version, the -t…
Improved Exact and Heuristic Algorithms for Maximum Weight Clique
Roman Erhardt, Kathrin Hanauer, Nils Kriege +2
We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interl…
A Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks
Lutz Oettershagen, Nils M. Kriege, Claude Jordan +1
We introduce the \emph{temporal graphlet kernel} for classifying dissemination processes in labeled temporal graphs. Such dissemination processes can be spreading (fake) news, infe…
Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
Franka Bause, Nils M. Kriege
The classical Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning with kernels and neural networks. Originally developed for graph isomorphism testing…
Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Nils M. Kriege
Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weisfeiler-Leman test for graph isomorphism. We…
Temporal Walk Centrality: Ranking Nodes in Evolving Networks
Lutz Oettershagen, Petra Mutzel, Nils M. Kriege
We propose the Temporal Walk Centrality, which quantifies the importance of a node by measuring its ability to obtain and distribute information in a temporal network. In contrast…
Weisfeiler and Leman go Machine Learning: The Story so far
Christopher Morris, Yaron Lipman, Haggai Maron +5
In recent years, algorithms and neural architectures based on the Weisfeiler--Leman algorithm, a well-known heuristic for the graph isomorphism problem, have emerged as a powerful…
EmbAssi: Embedding Assignment Costs for Similarity Search in Large Graph Databases
Franka Bause, Erich Schubert, Nils M. Kriege
The graph edit distance is an intuitive measure to quantify the dissimilarity of graphs, but its computation is NP-hard and challenging in practice. We introduce methods for answer…
Metric Indexing for Graph Similarity Search
Franka Bause, David B. Blumenthal, Erich Schubert +1
Finding the graphs that are most similar to a query graph in a large database is a common task with various applications. A widely-used similarity measure is the graph edit distanc…
The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs
Christopher Morris, Matthias Fey, Nils M. Kriege
In recent years, algorithms and neural architectures based on the Weisfeiler-Leman algorithm, a well-known heuristic for the graph isomorphism problem, emerged as a powerful tool f…
TUDataset: A collection of benchmark datasets for learning with graphs
Christopher Morris, Nils M. Kriege, Franka Bause +3
Recently, there has been an increasing interest in (supervised) learning with graph data, especially using graph neural networks. However, the development of meaningful benchmark d…
Deep Graph Matching Consensus
Matthias Fey, Jan E. Lenssen, Christopher Morris +2
This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph…
Temporal Graph Kernels for Classifying Dissemination Processes
Lutz Oettershagen, Nils M. Kriege, Christopher Morris +1
Many real-world graphs or networks are temporal, e.g., in a social network persons only interact at specific points in time. This information directs dissemination processes on the…
Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning
Nils M. Kriege
Kernels for structured data are commonly obtained by decomposing objects into their parts and adding up the similarities between all pairs of parts measured by a base kernel. Assig…
A Survey on Graph Kernels
Nils M. Kriege, Fredrik D. Johansson, Christopher Morris
Graph kernels have become an established and widely-used technique for solving classification tasks on graphs. This survey gives a comprehensive overview of techniques for kernel-b…
Maximum Cut Parameterized by Crossing Number
Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke +3
Given an edge-weighted graph on nodes, the NP-hard Max-Cut problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximiz…
Computing Optimal Assignments in Linear Time for Approximate Graph Matching
Nils M. Kriege, Pierre-Louis Giscard, Franka Bause +1
Finding an optimal assignment between two sets of objects is a fundamental problem arising in many applications, including the matching of `bag-of-words' representations in natural…
Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs
Christine Dahn, Nils M. Kriege, Petra Mutzel +1
We propose two fixed-parameter tractable algorithms for the weighted Max-Cut problem on embedded 1-planar graphs parameterized by the crossing number of the given embedding. A…
Largest Weight Common Subtree Embeddings with Distance Penalties
Andre Droschinsky, Nils M. Kriege, Petra Mutzel
The largest common embeddable subtree problem asks for the largest possible tree embeddable into two input trees and generalizes the classical maximum common subtree problem. Sever…
A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs
Nils M. Kriege, Andre Droschinsky, Petra Mutzel
Schietgat, Ramon and Bruynooghe proposed a polynomial-time algorithm for computing a maximum common subgraph under the block-and-bridge preserving subgraph isomorphism (BBP-MCS) fo…
Recognizing Cuneiform Signs Using Graph Based Methods
Nils M. Kriege, Matthias Fey, Denis Fisseler +2
The cuneiform script constitutes one of the earliest systems of writing and is realized by wedge-shaped marks on clay tablets. A tremendous number of cuneiform tablets have already…