BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Christian Schulz

Christian Schulz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingSocial and Information NetworksArtificial IntelligenceLogic in Computer ScienceMachine LearningComputational ComplexityComputer Visioncond-mat.mtrl-scicond-mat.str-elDiscrete MathematicsInformation Retrievalmath.COmath.LO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
26works
0followers
14topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

26 published item(s)

preprint2025arXiv

Electronic Energy Scales of Cr$X_3$ ($X$ = Cl, Br, and I) using High-resolution X-ray Scattering

Chromium tri-halides Cr$X_3$ ($X$ = Cl, Br, and I) have recently become a focal point of research due to their intriguing low-temperature,layer-dependent magnetism that can be manipulated by an electric field. This makes them essential candidates for spintronics applications. These magnetic orders are often related to the electronic structure parameters, such as spin-orbit coupling (SOC), Hund's coupling ($J_H$), $p-d$ covalency, and inter-orbital Coulomb interactions. Accurately determining such parameters is paramount for understanding Cr$X_3$ physics. We have used ultra high-resolution resonant inelastic x-ray scattering (RIXS) spectroscopy to study Cr$X_3$ across phase transition temperatures. Ligand field multiplet calculations were used to determine the electronic structure parameters by incorporating the crystal field interactions in a distorted octahedral with $C_3$ symmetry. These methods provide the most detailed description of Cr$X_3$ magneto-optical and electronic energetic (terms) to date. For the first time, the crystal field distortion parameters $Dσ$ and $Dτ$ were calculated, and the energies of $d$ orbitals have been reported. Our RIXS spectroscopic measurements reveal a clear energy separation between spin-allowed quartet states and spin-forbidden doublet states in Cr$X_3$. The role of SOC in Cr $2p$ orbitals for the spin-flip excitations has been demonstrated. The determined 10$Dq$ values are in good agreement with the spectrochemical series, and Racah B follows the Nephelauxetic effect. Such precise measurements offer insights into the energy design of spintronic devices that utilize quantum state tuning within 2D magnetic materials.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Engineering Fully Dynamic $Δ$-Orientation Algorithms

A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers certain queries that are specific to the problem under consideration. There has been a lot of research on dynamic algorithms for graph problems that are solvable in polynomial time by a static algorithm. However, while there is a large body of theoretical work on efficient dynamic graph algorithms, a lot of these algorithms were never implemented and empirically evaluated. In this work, we consider the fully dynamic edge orientation problem, also called fully dynamic $Δ$-orientation problem, which is to maintain an orientation of the edges of an undirected graph such that the out-degree is low. If edges are inserted or deleted, one may have to flip the orientation of some edges in order to avoid vertices having a large out-degree. While there has been theoretical work on dynamic versions of this problem, currently there is no experimental evaluation available. In this work, we close this gap and engineer a range of new dynamic edge orientation algorithms as well as algorithms from the current literature. Moreover, we evaluate these algorithms on real-world dynamic graphs. The best algorithm considered in this paper in terms of quality, based on a simple breadth-first search, computes the optimum result on more than 90% of the instances and is on average only 2.4% worse than the optimum solution.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Faster Local Motif Clustering via Maximum Flows

Local clustering aims to identify a cluster within a given graph that includes a designated seed node or a significant portion of a group of seed nodes. This cluster should be well-characterized, i.e., it has a high number of internal edges and a low number of external edges. In this work, we propose SOCIAL, a novel algorithm for local motif clustering which optimizes for motif conductance based on a local hypergraph model representation of the problem and an adapted version of the max-flow quotient-cut improvement algorithm (MQI). In our experiments with the triangle motif, SOCIAL produces local clusters with an average motif conductance lower than the state-of-the-art, while being up to multiple orders of magnitude faster.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Electronic Excitations of Hematite Heteroepitaxial Films Measured by Resonant Inelastic X-Ray Scattering at the Fe L-edge

Resonant Inelastic X-Ray Scattering (RIXS) spectra of hematite were measured at the Fe L3-edge for heteroepitaxial thin films which were undoped and doped with 1% Ti, Sn or Zn, in the energy loss range in excess of 1 eV to study electronic transitions. The spectra were measured for several momentum transfers (q), conducted at both low temperature (T=14K) and room temperature. While we can not rule out dispersive features possibly owing to propagating excitations, the coarse envelopes of the general spectra did not appreciably change shape with q, implying that the bulk of the observed L-edge RIXS intensity originates from (mostly) non-dispersive ligand field (LF) excitations. Summing the RIXS spectra over q and comparing the results at T=14 K to those at T=300 K, revealed pronounced temperature effects, including an intensity change and energy shift of the 1.4 eV peak, a broadband intensity increase of the 3-4 eV range, and higher energy features. The q-summed spectra and their temperature dependences are virtually identical for nearly all of the samples with different dopants, save for the temperature dependence of the Ti-doped sample's spectrum, which we attribute to being affected by a large number of free charge carriers. Comparing with magnetization measurements for different temperatures and dopings likewise did not show a clear correlation between the RIXS spectra and the magnetic ordering states. To clarify the excited states, we performed spin multiplet calculations which were in excellent agreement with the RIXS spectra over a wide energy range and provide detailed electronic descriptions of the excited states. The implications of these findings to the photoconversion efficiency of hematite photoanodes is discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fractal dimensions of $k$-automatic sets

This paper seeks to build on the extensive connections that have arisen between automata theory, combinatorics on words, fractal geometry, and model theory. Results in this paper establish a characterization for the behavior of the fractal geometry of "$k$-automatic" sets, subsets of $[0,1]^d$ that are recognized by Büchi automata. The primary tools for building this characterization include the entropy of a regular language and the digraph structure of an automaton. Via an analysis of the strongly connected components of such a structure, we give an algorithmic description of the box-counting dimension, Hausdorff dimension, and Hausdorff measure of the corresponding subset of the unit box. Applications to definability in model-theoretic expansions of the real additive group are laid out as well.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Local Motif Clustering via (Hyper)Graph Partitioning

A widely-used operation on graphs is local clustering, i.e., extracting a well-characterized community around a seed node without the need to process the whole graph. Recently local motif clustering has been proposed: it looks for a local cluster based on the distribution of motifs. Since this local clustering perspective is relatively new, most approaches proposed for it are extensions of statistical and numerical methods previously used for edge-based local clustering, while the available combinatorial approaches are still few and relatively simple. In this work, we build a hypergraph and a graph model which both represent the motif-distribution around the seed node. We solve these models using sophisticated combinatorial algorithms designed for (hyper)graph partitioning. In extensive experiments with the triangle motif, we observe that our algorithm computes communities with a motif conductance value being one third on average in comparison against the communities computed by the state-of-the-art tool MAPPR while being 6.3 times faster on average.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

More Recent Advances in (Hyper)Graph Partitioning

In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the last decade in practical algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic. In particular, the survey extends the previous survey by also covering hypergraph partitioning and streaming algorithms, and has an additional focus on parallel algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping

Partitioning a graph into balanced blocks such that few edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge graphs are streaming algorithms, which use low computational resources. In this work, we present a shared-memory streaming multi-recursive partitioning scheme that performs recursive multi-sections on the fly without knowing the overall input graph. Our approach has a considerably lower running time complexity in comparison with state-of-the-art non-buffered one-pass partitioning algorithms for the standard graph partitioning case. Moreover, if the topology of a distributed system is known, it is possible to further optimize the communication costs by mapping partitions onto processing elements. Our experiments indicate that our algorithm is both faster and produces better process mappings than competing tools. In case of graph partitioning, our framework is up to two orders of magnitude faster at the cost of 5% more cut edges compared to Fennel.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Weakly Supervised Semantic Segmentation of Remote Sensing Images for Tree Species Classification Based on Explanation Methods

The collection of a high number of pixel-based labeled training samples for tree species identification is time consuming and costly in operational forestry applications. To address this problem, in this paper we investigate the effectiveness of explanation methods for deep neural networks in performing weakly supervised semantic segmentation using only image-level labels. Specifically, we consider four methods:i) class activation maps (CAM); ii) gradient-based CAM; iii) pixel correlation module; and iv) self-enhancing maps (SEM). We compare these methods with each other using both quantitative and qualitative measures of their segmentation accuracy, as well as their computational requirements. Experimental results obtained on an aerial image archive show that:i) considered explanation techniques are highly relevant for the identification of tree species with weak supervision; and ii) the SEM outperforms the other considered methods. The code for this paper is publicly available at https://git.tu-berlin.de/rsim/rs_wsss.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

O'Reach: Even Faster Reachability in Large Graphs

One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O'Reach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn't necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Practical Fully Dynamic Minimum Cut Algorithms

We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a fully-dynamic algorithm. The algorithm uses the theoretical foundation and combines it with efficient and finely-tuned implementations to give an algorithm that can maintain the global minimum cut of a graph with rapid update times. We show that our algorithm gives up to multiple orders of magnitude speedup compared to static approaches both on edge insertions and deletions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations

Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto standard approach to solve the problem to optimality in practice. In this paradigm, data reduction rules are applied to decrease the problem size. These data reduction rules ensure that given an optimum solution on the new (smaller) input, one can quickly construct an optimum solution on the original input. We introduce new generalized data reduction and transformation rules for the problem. A key feature of our work is that some transformation rules can increase the size of the input. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later throughout the algorithm. In experiments, our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than heuristic solvers DynWVC and HILS on many instances. While the increasing transformations are only efficient enough for preprocessing at this time, we see this as a critical initial step towards a new branch-and-transform paradigm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Matching Algorithms in Practice

In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient Process-to-Node Mapping Algorithms for Stencil Computations

Good process-to-compute-node mappings can be decisive for well performing HPC applications. A special, important class of process-to-node mapping problems is the problem of mapping processes that communicate in a sparse stencil pattern to Cartesian grids. By thoroughly exploiting the inherently present structure in this type of problem, we devise three novel distributed algorithms that are able to handle arbitrary stencil communication patterns effectively. We analyze the expected performance of our algorithms based on an abstract model of inter- and intra-node communication. An extensive experimental evaluation on several HPC machines shows that our algorithms are up to two orders of magnitude faster in running time than a (sequential) high-quality general graph mapping tool, while obtaining similar results in communication performance. Furthermore, our algorithms also achieve significantly better mapping quality compared to previous state-of-the-art Cartesian grid mapping algorithms. This results in up to a threefold performance improvement of an MPI_Neighbor_alltoall exchange operation. Our new algorithms can be used to implement the MPI_Cart_create functionality.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Fully Dynamic Transitive Closure in Practice

The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered. In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Parallel Multiterminal Cuts

We give an improved branch-and-bound solver for the multiterminal cut problem, based on the recent work of Henzinger et al.. We contribute new, highly effective data reduction rules to transform the graph into a smaller equivalent instance. In addition, we present a local search algorithm that can significantly improve a given solution to the multiterminal cut problem. Our exact algorithm is able to give exact solutions to more and harder problems compared to the state-of-the-art algorithm by Henzinger et al.; and give better solutions for more than two third of the problems that are too large to be solved to optimality. Additionally, we give an inexact heuristic algorithm that computes high-quality solutions for very hard instances in reasonable time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Support Vector Machines

The time complexity of support vector machines (SVMs) prohibits training on huge data sets with millions of data points. Recently, multilevel approaches to train SVMs have been developed to allow for time-efficient training on huge data sets. While regular SVMs perform the entire training in one -- time consuming -- optimization step, multilevel SVMs first build a hierarchy of problems decreasing in size that resemble the original problem and then train an SVM model for each hierarchy level, benefiting from the solved models of previous levels. We present a faster multilevel support vector machine that uses a label propagation algorithm to construct the problem hierarchy. Extensive experiments indicate that our approach is up to orders of magnitude faster than the previous fastest algorithm while having comparable classification quality. For example, already one of our sequential solvers is on average a factor 15 faster than the parallel ThunderSVM algorithm, while having similar classification quality.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding All Global Minimum Cuts In Practice

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fully Dynamic k-Center Clustering in Doubling Metrics

Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications where data is constantly changing and evolving. Driven by this, we study the metric $k$-center clustering problem in the fully dynamic setting, where the goal is to efficiently maintain a clustering while supporting an intermixed sequence of insertions and deletions of points. This model also supports queries of the form (1) report whether a given point is a center or (2) determine the cluster a point is assigned to. We present a deterministic dynamic algorithm for the $k$-center clustering problem that provably achieves a $(2+ε)$-approximation in poly-logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and $ε$ is a constant. An important feature of our algorithm is that the update and query times are independent of $k$. We confirm the practical relevance of this feature via an extensive experimental study which shows that for values of $k$ and $ε$ suggested by theory, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fully Dynamic Single-Source Reachability in Practice: An Experimental Study

Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subject to edge deletions and insertions. It is one of the most fundamental problems on graphs and appears directly or indirectly in many and varied applications. While there has been theoretical work on this problem, showing both linear conditional lower bounds for the fully dynamic problem and insertions-only and deletions-only upper bounds beating these conditional lower bounds, there has been no experimental study that compares the performance of fully dynamic reachability algorithms in practice. Previous experimental studies in this area concentrated only on the more general all-pairs reachability or transitive closure problem and did not use real-world dynamic graphs. In this paper, we bridge this gap by empirically studying an extensive set of algorithms for the single-source reachability problem in the fully dynamic setting. In particular, we design several fully dynamic variants of well-known approaches to obtain and maintain reachability information with respect to a distinguished source. Moreover, we extend the existing insertions-only or deletions-only upper bounds into fully dynamic algorithms. Even though the worst-case time per operation of all the fully dynamic algorithms we evaluate is at least linear in the number of edges in the graph (as is to be expected given the conditional lower bounds) we show in our extensive experimental evaluation that their performance differs greatly, both on generated as well as on real-world instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

High-Quality Hierarchical Process Mapping

Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation when processing graphs on a parallel computer. When a topology of a distributed system is known an important task is then to map the blocks of the partition onto the processors such that the overall communication cost is reduced. We present novel multilevel algorithms that integrate graph partitioning and process mapping. Important ingredients of our algorithm include fast label propagation, more localized local search, initial partitioning, as well as a compressed data structure to compute processor distances without storing a distance matrix. Experiments indicate that our algorithms speed up the overall mapping process and, due to the integrated multilevel approach, also find much better solutions in practice. For example, one configuration of our algorithm yields better solutions than the previous state-of-the-art in terms of mapping quality while being a factor 62 faster. Compared to the currently fastest iterated multilevel mapping algorithm Scotch, we obtain 16% better solutions while investing slightly more running time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

KaHIP v3.00 -- Karlsruhe High Quality Partitioning -- User Guide

This paper severs as a user guide to the graph partitioning framework KaHIP (Karlsruhe High Quality Partitioning). We give a rough overview of the techniques used within the framework and describe the user interface as well as the file formats used. Moreover, we provide a short description of the current library functions provided within the framework. Since version 3.00 we support multilevel partitioning, memetic algorithms, distributed and shared-memory parallel algorithms, node separator and ordering algorithms, edge partitioning algorithms as well as ILP solvers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recent Advances in Practical Data Reduction

Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. We survey recent trends in data reduction engineering results for selected problems. Moreover, we describe concrete techniques that may be useful for future implementations in the area and give open problems and research questions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recent Advances in Scalable Network Generation

Random graph models are frequently used as a controllable and versatile data source for experimental campaigns in various research fields. Generating such data-sets at scale is a non-trivial task as it requires design decisions typically spanning multiple areas of expertise. Challenges begin with the identification of relevant domain-specific network features, continue with the question of how to compile such features into a tractable model, and culminate in algorithmic details arising while implementing the pertaining model. In the present survey, we explore crucial aspects of random graph models with known scalable generators. We begin by briefly introducing network features considered by such models, and then discuss random graphs alongside with generation algorithms. Our focus lies on modelling techniques and algorithmic primitives that have proven successful in obtaining massive graphs. We consider concepts and graph models for various domains (such as social network, infrastructure, ecology, and numerical simulations), and discuss generators for different models of computation (including shared-memory parallelism, massive-parallel GPUs, and distributed systems).

0 citations0 reviewsNo code linkedOpen access