An Euler tour of a hypergraph is a closed walk that traverses every edge exactly once; if a hypergraph admits such a walk, then it is called eulerian. Although this notion is one of the progenitors of graph theory --- dating back to the eighteenth century --- treatment of this subject has only begun on hypergraphs in the last decade. Other authors have produced results about rank-2 universal cycles and 1-overlap cycles, which are equivalent to our definition of Euler tours. In contrast, an Euler family is a collection of nontrivial closed walks that jointly traverse every edge of the hypergraph exactly once and cannot be concatenated simply. Since an Euler tour is an Euler family comprising a single walk, having an Euler family is a weaker attribute than being eulerian; we call a hypergraph quasi-eulerian if it admits an Euler family. Due to a result of Lovász, it can be much easier to determine that some classes of hypergraphs are quasi-eulerian, rather than eulerian; in this thesis, we present some techniques that allow us to make the leap from quasi-eulerian to eulerian. A triple system of order n and index λ (denoted TS(n,λ)) is a 3-uniform hypergraph in which every pair of vertices lies together in exactly λ edges. A Steiner triple system of order n is a TS(n,1). We first give a proof that every TS(n,λ) with λ ⩾ 2 is eulerian. Other authors have already shown that every such triple system is quasi-eulerian, so we modify an Euler family in order to show that an Euler tour must exist. We then give a proof that every Steiner triple system (barring the degenerate TS(3,1)) is eulerian. We achieve this by first constructing a near-Hamilton cycle out of some of the edges, then demonstrating that the hypergraph consisting of the remaining edges has a decomposition into closed walks in which each edge is traversed exactly once. In order to extend these results on triple systems, we define a type of hypergraph called an ℓ-covering k-hypergraph, a k-uniform hypergraph in which every ℓ-subset of the vertices lie together in at least one edge. We generalize the techniques used earlier on TS(n,λ) with λ ⩾ 2 and define interchanging cycles. Such cycles allow us to transform an Euler family into another Euler family, preferably of smaller cardinality. We first prove that all 2-covering 3-hypergraphs are eulerian by starting with an Euler family that has the minimum cardinality possible, then demonstrating that if there are two or more walks in the Euler family, then we can rework two or more of them into a single walk. We then use this result to prove by induction that, for k ⩾ 3, all (k-1)-covering k-hypergraphs are eulerian. We attempt to extend these results further to all ℓ-covering k-hypergraphs for ℓ ⩾ 2 and k ⩾ 3. Using the same induction technique as before, we only need to give a result for 2-covering k-hypergraphs. We are able to use Lovász's condition and some counting techniques to show that these are all quasi-eulerian. Finally, we give some constructive results on hypergraphs with small edge cuts. There has been analogous work by other authors on hypergraphs with small vertex cuts. We reduce the problem of finding an Euler tour in a hypergraph to finding an Euler tour in each of the connected components of the edge-deleted subhypergraph, then show how these individual Euler tours can be concatenated.

We study the facial structure of the independent set polytope using the concept of conflict hypergraphs. A conflict hypergraph is a hypergraph whose vertices correspond to the binary variables, and edges correspond to covers in the constraint matrix of the independent set polytope. Various structures such as cliques, odd holes, odd anti-holes, webs and anti-webs are identified on the conflict hypergraph. These hypergraph structures are shown to be generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments on market-share (also referred to as market-split) problems. These instances consist of 100% dense multiple-knapsack constraints. They are small in size but are extremely hard to solve by traditional means. Their difficult nature is attributed mainly to the dense and symmetrical structure. We employ a special branching strategy in combination with the hypergraph inequalities to solve many of the particularly difficult instances. Results are reported for serial as well as parallel implementations.

In this thesis we consider the problem of clustering the data lying in a union of subspaces using spectral methods. Though the data generated may have high dimensionality, in many of the applications, such as motion segmentation and illumination invariant face clustering, the data resides in a union of subspaces having small dimensions. Furthermore, for a number of classification and inference problems, it is often useful to identify these subspaces and work with data in this smaller dimensional manifold. If the observations in each cluster were to be distributed around a centric, applying spectral clustering on an a nifty matrix built using distance based similarity measures between the data points have been used successfully to solve the problem. But it has been observed that using such pair-wise distance based measure between the data points to construct a similarity matrix is not sufficient to solve the subspace clustering problem. Hence, a major challenge is to end a similarity measure that can capture the information of the subspace the data lies in. This is the motivation to develop methods that use an affinity tensor by calculating similarity between multiple data points. One can then use spectral methods on these tensors to solve the subspace clustering problem. In order to keep the algorithm computationally feasible, one can employ column sampling strategies. However, the computational costs for performing the tensor factorization increases very quickly with increase in sampling rate. Fortunately, the advances in GPU computing has made it possible to perform many linear algebra operations several order of magnitudes faster than traditional CPU and multicourse computing. In this work, we develop parallel algorithms for subspace clustering on a GPU com-putting environment. We show that this gives us a significant speedup over the implementations on the CPU, which allows us to sample a larger fraction of the tensor and thereby achieve better accuracies. We empirically analyze the performance of these algorithms on a number of synthetically generated subspaces con gyrations. We ally demonstrate the effectiveness of these algorithms on the motion segmentation, handwritten digit clustering and illumination invariant face clustering and show that the performance of these algorithms are comparable with the state of the art approaches.

In this thesis, we investigate graphs and hypergraphs that have (relaxed) product structures. In the class of graphs, we discuss in detail \\emph{RSP-relations}, a relaxation of relations fulfilling the square property and therefore of the product relation $\\sigma$, that identifies the copies of the prime factors of a graph w.r.t. the Cartesian product. For $K_{2,3}$-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially. Explicit constructions of such relations in complete and complete bipartite graphs are given. Furthermore, we establish the close connection of (\\emph{well-behaved}) RSP-relations to \\mbox{(quasi-)covers} of graphs and equitable partitions. Thereby, we characterize the existence of non-trivial RSP-relations by means of the existence of spanning subgraphs that yield quasi-covers of the graph under investigation. We show, how equitable partitions on the vertex set of a graph $G$ arise in a natural way from well-behaved RSP-relations on $E(G)$. These partitions in turn give rise to quotient graphs that have rich product structure even if $G$ itself is prime. This product structure of the quotient graph is still retained even for RSP-relations that are not well-behaved. Furthermore, we will see that a (finest) RSP-relation of a product graph can be obtained easily from (finest) RSP-relations on the prime factors w.r.t. certain products and in what manner the quotient graphs of the product w.r.t. such an RSP-relation result from the quotient graphs of the factors and the respective product. In addition, we examine relations on the edge sets of \\emph{hyper}graphs that satisfy the grid property, the hypergraph analog of the square property. We introduce the \\emph{strong} and the \\emph{relaxed} grid property as variations of the grid property, the latter generalizing the relaxed square property. We thereby show, that many, although not all results for graphs and the (relaxed) square property can be transferred to hypergraphs. Similar to the graph case, any equivalence relation $R$ on the edge set of a hypergraph $H$ that satisfies the relaxed grid property induces a partition of the vertex set of $H$ which in turn determines quotient hypergraphs that have non-trivial product structures. Besides, we introduce the notion of \\emph{(Cartesian) hypergraph bundles}, the analog of (Cartesian) graph bundles and point out the connection between the grid property and hypergraph bundles. Finally, we show that every connected thin hypergraph $H$ has a unique prime factorization with respect to the normal and strong (hypergraph) product. Both products coincide with the usual strong \\emph{graph} product whenever $H$ is a graph. We introduce the notion of the Cartesian skeleton of hypergraphs as a natural generalization of the Cartesian skeleton of graphs and prove that it is uniquely defined for thin hypergraphs. Moreover, we show that the Cartesian skeleton of thin hypergraphs and its PFD w.r.t. the strong and the normal product can be computed in polynomial time.

<p>Graph diffusion is the process of spreading information from one or few nodes to the rest of the graph through edges. The resulting distribution of the information often implies latent structure of the graph where nodes more densely connected can receive more signal. This makes graph diffusions a powerful tool for local clustering, which is the problem of finding a cluster or community of nodes around a given set of seeds. Most existing literatures on using graph diffusions for local graph clustering are linear diffusions as their dynamics can be fully interpreted through linear systems. They are also referred as eigenvector, spectral, or random walk based methods. While efficient, they often have difficulty capturing the correct boundary of a target label or target cluster. On the contrast, maxflow-mincut based methods that can be thought as 1-norm nonlinear variants of the linear diffusions seek to "improve'' or "refine'' a given cluster and can often capture the boundary correctly. However, there is a lack of literature to adopt them for problems such as community detection, local graph clustering, semi-supervised learning, etc. due to the complexity of their formulation. We addressed these issues by performing extensive numerical experiments to demonstrate the performance of flow-based methods in graphs from various sources. We also developed an efficient LocalGraphClustering Python Package that allows others to easily use these methods in their own problems. While studying these flow-based methods, we find that they cannot grow from small seed set. Although there are hybrid procedures that incorporate ideas from both linear diffusions and flow-based methods, they have many hard to set parameters. To tackle these issues, we propose a simple generalization of the objective function behind linear diffusion and flow-based methods which we call generalized local graph min-cut problem. We further show that by involving p-norm in this cut problem, we can develop a nonlinear diffusion procedure that can find local clusters from small seed set and capture the correct boundary simultaneously. Our method can be thought as a nonlinear generalization of the Anderson-Chung-Lang push procedure to approximate a personalized PageRank vector efficiently and is a strongly local algorithm-one whose runtime depends on the size of the output rather than the size of the graph. We also show that the p-norm cut functions improve on the standard Cheeger inequalities for linear diffusion methods. We further extend our generalized local graph min-cut problem and the corresponding diffusion solver to hypergraph-based machine learning problems. Although many methods for local graph clustering exist, there are relatively few for localized clustering in hypergraphs. Moreover, those that exist often lack flexibility to model a general class of hypergraph cut functions or cannot scale to large problems. Our new hypergraph diffusion method on the other hand enables us to compute with a wide variety of cardinality-based hypergraph cut functions and still maintains the strongly local property. We also show that the clusters found by solving the new objective function satisfy a Cheeger-like quality guarantee.</p> <p>Besides clustering, recent work on graph-based learning often focuses on node embeddings and graph neural networks. Although these GNN based methods can beat traditional ones especially when node attributes data is available, it is challenging to understand them because they are highly over-parameterized. To solve this issue, we propose a novel framework that combines topological data analysis and diffusion to transform the complex prediction space into human understandable pictures. The method can be applied to other datasets not in graph formats and scales up to large datasets across different domains and enable us to find many useful insights about the data and the model.</p>

No description available.

Combinatorial Group Testing (CGT) is a process of identifying faulty interactions (“errors”) within a particular set of items. Error Locating Arrays (ELAs) are combinatorial designs that can be built from Covering Arrays (CAs) to not only cover all errors in a system (each involving up to a certain number of items), but to locate and identify the errors as well. In this thesis, we survey known results for CGT, as well as CAs, ELAs, and some other types of related arrays. More importantly, we give several new results. First, we give a new algorithm that can be used to test a system in which each component (factor) has two options (values), and at most two errors are present. We show that, for systems with at most two errors, our algorithm improves upon a related algorithm by Mart´ınez et al. in terms of both robustness and efficiency. Second, we give the first adaptive CGT algorithm that can identify, among a given set of k items, all faulty interactions involving up to three items. We then compare it, performance-wise, to current-best nonadaptive method that can identify faulty interactions involving up to three items. We also give the first adaptive ELA-building algorithm that can identify all faulty interactions involving up to three items when safe values are known. Both of our new algorithms are generalizations of ones previously given by Mart´ınez et al. for identifying all faulty interactions involving up to two items.

No description available.

Combinatorial Group Testing (CGT) is a process of identifying faulty interactions (“errors”) within a particular set of items. Error Locating Arrays (ELAs) are combinatorial designs that can be built from Covering Arrays (CAs) to not only cover all errors in a system (each involving up to a certain number of items), but to locate and identify the errors as well. In this thesis, we survey known results for CGT, as well as CAs, ELAs, and some other types of related arrays. More importantly, we give several new results. First, we give a new algorithm that can be used to test a system in which each component (factor) has two options (values), and at most two errors are present. We show that, for systems with at most two errors, our algorithm improves upon a related algorithm by Mart´ınez et al. in terms of both robustness and efficiency. Second, we give the first adaptive CGT algorithm that can identify, among a given set of k items, all faulty interactions involving up to three items. We then compare it, performance-wise, to current-best nonadaptive method that can identify faulty interactions involving up to three items. We also give the first adaptive ELA-building algorithm that can identify all faulty interactions involving up to three items when safe values are known. Both of our new algorithms are generalizations of ones previously given by Mart´ınez et al. for identifying all faulty interactions involving up to two items.

The NP-complete k-SAT problem - decide wether a given formula is satisfiable - is of fundamental importance in theoretical computer science. In this dissertation we study random 4-SAT formulas with > 116 n^2 clauses. These formulas are almost surly unsatisfiable. Here we show the existence of a polynomial time algorithm that certifies the unsatisfiability. Therefore we study the discrepancy of hypergraphs and multigraphs. We also combine spectral techniques with approximation algorithms to achieve the new result. Our new algorithm is adaptable for Not-All-Equal-4-SAT and the 2-colouring of 4-uniform hypergraphs. We also extends the Hajos construction of non k-colourable graphs to non k-colourable uniform hypergraphs. / Das NP-vollständige Problem k-SAT ist von zentraler Bedeutung in der theoretischen Informatik. In der Dissertation werden zufällige 4-SAT-Formeln mit > n^2 vielen Klauseln studiert. Diese Formeln sind mit hoher Wahrscheinlichkeit unerfüllbar. Hier wird erstmalig die Existenz eines Algorithmus gezeigt, der diese Unerfüllbarkeit effizient verifiziert. Hierfür wird die geringe Diskrepanz von Hypergrpahen und Multigraphen betrachtet. Der Schlüssel zu diesem Algorithmus liegt in der Kombination von spektralen Techniken mit Approximationsalgorithmen der klassischen kombinatorischen Optimierung. Der vorgestellte Algorithmus kann auf den effizienten Nachweis der Unerfüllbarkeit von Not-All-Equal-4-SAT-Formeln und die Nicht-2-Färbbarkeit von 4-uniformen Hypergraphen erweitert werden. Es wird ebenfalls eine Erweiterung der Hajos-Konstruktion nicht k-färbbarer Graphen auf nicht k-färbbare uniforme Hypergraphen angegeben.