7 papers · 1 filter
A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation
Alex Crane, Pål Grønås Drange, Eli Friedman +6
The algorithmic differentiation (AD) of mathematical functions can be interpreted as a sequence of vertex eliminations in an underlying directed acyclic graph. The problem of deter…
Aggregating maximal cliques in real-world graphs
Noga Alon, Sabyasachi Basu, Shweta Jain +3
Maximal clique enumeration is a fundamental graph mining task, but its utility is often limited by computational intractability and highly redundant output. To address these challe…
Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobi…
Equalizing Closeness Centralities via Edge Additions
Alex Crane, Sorelle A. Friedler, Mihir Patel +1
Graph modification problems with the goal of optimizing some measure of a given node's network position have a rich history in the algorithms literature. Less commonly explored are…
Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Alex Crane, Thomas Stanley, Blair D. Sullivan +1
We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions th…
Optimizing Probabilistic Propagation in Graphs by Adding Edges
Aditya Bhaskara, Alex Crane, Shweta Jain +3
Probabilistic graphs are an abstraction that allow us to study randomized propagation in graphs. In a probabilistic graph, each edge is "active" with a certain probability, indepen…