Search

As data structures and mathematical objects used for complex systems modeling, hypergraphs sit nicely poised between on the one hand the world of network models, and on the other that of higher-order mathematical abstractions from algebra, lattice theory, and topology. They are able to represent complex systems interactions more faithfully than graphs and networks, while also being some of the simplest classes of systems representing topological structures as collections of multidimensional objects connected in a particular pattern. In this paper we discuss the role of (undirected) hypergraphs in the science of complex networks, and provide a mathematical overview of the core concepts needed for hypernetwork modeling, including duality and the relationship to bicolored graphs, quantitative adjacency and incidence, the nature of walks in hypergraphs, and available topological relationships and properties. We close with a brief discussion of two example applications: biomedical databases for disease analysis, and domain-name system (DNS) analysis of cyber data.

In this paper, we discuss our experience in implementing homology computation, in particular the Betti number calculations in Chapel hypergraph Library (CHGL). Given a dataset represented as a hypergraph, a Betti number for a particular dimension k indicates how many k-dimensional `voids' are present in the dataset. Computing the Betti numbers involve various array-centric and linear algebra operations. We demonstrate that implementing these operations in Chapel is both concise and intuitive. In addition, we show that Chapel provides language constructs for implementing parallel and distributed execution of the linear algebra kernels with minimal effort. Syntactically, Chapel provides succinctness of Python, while delivering comparable and better performance than C++-based and Julia-based packages for calculating the Betti numbers respectively.

Background Representing biological networks as graphs is a powerful approach to reveal underlying patterns, signatures, and critical components from high-throughput biomolecular data. However, graphs do not natively capture the multi-way relationships present among genes and proteins in biological systems. Hypergraphs are generalizations of graphs that naturally model multi-way relationships and have shown promise in modeling systems such as protein complexes and metabolic reactions. In this paper we seek to understand how hypergraphs can more faithfully identify, and potentially predict, important genes based on complex relationships inferred from genomic expression data sets. Results We compiled a novel data set of transcriptional host response to pathogenic viral infections and formulated relationships between genes as a hypergraph where hyperedges represent significantly perturbed genes, and vertices represent individual biological samples with specific experimental conditions. We find that hypergraph betweenness centrality is a superior method for identification of genes important to viral response when compared with graph centrality. Conclusions Our results demonstrate the utility of using hypergraphs to represent complex biological systems and highlight central important responses in common to a variety of highly pathogenic viruses.

Backdoor data poisoning attacks have recently been demonstrated in computer vision research as a potential safety risk for machine learning (ML) systems. Traditional data poisoning attacks manipulate training data to induce unreliability of an ML model, whereas backdoor data poisoning attacks maintain system performance unless the ML model is presented with an input containing an embedded "trigger " that provides a predetermined response advantageous to the adversary. Our work builds upon prior backdoor data-poisoning research for ML image classifiers and systematically assesses different experimental conditions including types of trigger patterns, persistence of trigger patterns during retraining, poisoning strategies, architectures (ResNet-50, NasNet, NasNet-Mobile), datasets (Flowers, CIFAR-10), and potential defensive regularization techniques (Contrastive Loss, Logit Squeezing, Manifold Mixup, Soft-Nearest-Neighbors Loss). Experiments yield four key findings. First, the success rate of backdoor poisoning attacks varies widely, depending on several factors, including model architecture, trigger pattern and regularization technique. Second, we find that poisoned models are hard to detect through performance inspection alone. Third, regularization typically reduces backdoor success rate, although it can have no effect or even slightly increase it, depending on the form of regularization. Finally, backdoors inserted through data poisoning can be rendered ineffective after just a few epochs of additional training on a small set of clean data without affecting the model's performance.

We report on the use of novel mathematical methods in hypergraph analytics over a large quantity of DNS data. Hypergraphs generalize graphs, as used in network science, to better model complex multiway relations in cyber data. Specifically, casting DNS data from Georgia Tech’s ActiveDNS repository as hypergraphs allows us to fully represent the interactions between collections of domains and IP addresses. To facilitate large-scale analytics, we fielded an analytical pipeline of two capabilities: HyperNetX (HNX) is a Python package for the exploration and visualization of hypergraphs; while on the backend, the Chapel HyperGraph Library (CHGL) is a library for high performance hypergraph analytics written in the exascale programming language Chapel. CHGL was used to process gigascale DNS data, performing compute-intensive calculations for data reduction and segmentation. Identified portions are then sent to HNX for both exploratory analysis and knowledge discovery targeting known tactics, techniques, and procedures.

We propose high-order hypergraph walks as a framework to generalize graph-based network science techniques to hypergraphs. Edge incidence in hypergraphs is quantitative, yielding hypergraph walks with both length and width. Graph methods which then generalize to hypergraphs include connected component analyses, graph distance-based metrics such as closeness centrality, and motif-based measures such as clustering coefficients. We apply high-order analogs of these methods to real world hypernetworks, and show they reveal nuanced and interpretable structure that cannot be detected by graph-based methods. Lastly, we apply three generative models to the data and find that basic hypergraph properties, such as density and degree distributions, do not necessarily control these new structural measurements. Our work demonstrates how analyses of hypergraph-structured data are richer when utilizing tools tailored to capture hypergraph-native phenomena, and suggests one possible avenue towards that end., Updated to address referee comments, to appear in EPJ Data Science

Integration of heterogeneous sensors is a challenging problem across a range of applications. Prominent among these are multi-target tracking, where one must combine observations from different sensor types in a meaningful way to track multiple targets. Because sensors have differing error models, we seek a theoretically-justified quantification of the agreement among ensembles of sensors, both overall for a sensor collection, and also at a fine-grained level specifying pairwise and multi-way interactions among sensors. We demonstrate that the theory of mathematical sheaves provides a unified answer to this need, supporting both quantitative and qualitative data. The theory provides algorithms to globalize data across the network of deployed sensors, and to diagnose issues when the data do not globalize cleanly. We demonstrate the utility of sheaf-based tracking models based on experimental data of a wild population of black bears in Asheville, North Carolina. A measurement model involving four sensors deployed among the bears and the team of scientists charged with tracking their location is deployed. This provides a sheaf-based integration model which is small enough to fully interpret, but of sufficient complexity to demonstrate the sheaf's ability to recover a holistic picture of the locations and behaviors of both individual bears and the bear-human tracking system. A statistical approach was developed for comparison, a dynamic linear model which was estimated using a Kalman filter. This approach also recovered bear and human locations and sensor accuracies. When the observations are normalized into a common coordinate system, the structure of the dynamic linear observation model recapitulates the structure of the sheaf model, demonstrating the canonicity of the sheaf-based approach. But when the observations are not so normalized, the sheaf model still remains valid., Comment: Submitted

As data accumulate faster and bigger, building representational models has turned into an art form. Despite sharing common data types, each scientific discipline often takes a different approach. In this work, we propose representational models grounded in the mathematics of algebraic topology to understand foundational data types. We present hypergraphs for multi-relational data, point clouds for vector data, and sheaf models when both data types are present and interrelated. These three models use similar principles from algebraic topology and provide a domain-agnostic framework. We will discuss each method, provide references to their foundational mathematical papers, and give examples of their use.

Using self similar tilings we represent the elements of RI as digit expansions with digits in RI being operated on by powers of an expansive linear map. We construct Markov partitions for hyperbolic toral automorphisms by considering a special class of self similar tilings modulo the integer lattice. We use the digit expansions inherited from these tilings to give a symbolic representation for the toral automorphisms. FRactals and fractal tilings have captured the imaginations of a wide spectrum of disciplines. Computer generated images of fractal sets are displayed in public science centers, museums, and on the covers of scientific journals. Fractal tilings which have interesting properties are finding applications in many areas of mathematics. For example, number theorists have linked fractal tilings of JR2 with numeration systems for JR2 in complex bases [16], [8]. We will see that fractal self similar tilings of R' provide natural building blocks for numeration systems of IR'. These numeration systems generalize the 1-dimensional cases in [14],[10],[11] as well as the 2-dimensional cases mentioned above. Our motivation for studying fractal tilings comes from ergodic theory. In [2] Adler and Weiss show that topological entropy is a complete invariant for metric equivalence of continuous ergodic automorphisms of the two-dimensional torus. Their method of proof is to construct a partition of the 2-torus which satisfies certain properties. The partition is called a Markov partition. By assigning each element of the partition a symbol, it is possible to assign each point in the 2-torus a bi-infinite sequence of symbols which corresponds to the orbit of the point. The objective is to represent the continuous dynamical system as a symbolic one in such a way that periodicity and transitivity is preserved in the representation. In [4] Bowen shows that every Anosov diffeomorphism has a Markov partition. In particular every hyperbolic toral automorphism has a Markov partition. His construction uses a recursive definition which deforms rectangles in the stable and unstable directions. While existence is shown, the proof does not indicate an efficient way to actually construct the partitions. In [5] Bowen shows that in the case of the 3-torus the boundary sets of the Markov partition have fractional Hausdorff dimension. In [3] Bedford constructs examples of Markov partitions for the 3-torus and describes the sets as crinkly tin cans. In [6] Cawley generalizes Bowen's results to higher dimensional tori. Since Markov partitions have properties which resemble those of self similar tilings and the boundary sets of these partitions have fractional dimension, it is Received by the editors October 2, 1996. 1991 Mathematics Subject Classification. Primary 58F03, 34C35, 54H20. ( 1999 Arnerican Mathematical Society 3315 This content downloaded from 157.55.39.170 on Tue, 20 Sep 2016 05:07:32 UTC All use subject to http://about.jstor.org/terms 3316 BRENDA PRAGGAS'TIS natural to suggest that an explicit finite construction of Markov partitions for hyperbolic toral automorphisms may be given using fractal self similar tilings. Moreover, there is a natural way to represent points in a tiled space using a symbolic system. The representations correspond to digit expansions. The set of sequences of digits used in these expansions will in turn generate a symbolic dynamical system which is metrically similar to the continuous system defined by the corresponding toral automorphism. 1. SUBDIVIDING AND SELF SIMILAR TILINGS In this first section we review the definition and properties of self similar tilings. Much of this information may be found in [17] and [10]. We then indicate how a self similar tiling of Rn provides a numeration system for Rt. Let X be a subset of RT which is the closure of its interior. Definition. A collection T of compact subsets of X is a tiling if it satisfies the following properties. (1) The union of the sets in T is equal to X. (2) Each set in T is the closure of its interior. (3) Each compact set in X ilntersects a finite number of sets in T. (In this case we say that T is locally finite.) (4) The interiors of the sets in T are mutually disjoint. The sets in T are called tiles. Suppose G is a subgroup of RW. A tiling T of X is G -finite if there exists a finite partition {Ij}GJ of T such that if T E Tj, then TS C {T+g: 9 EG}. The collection {T}jlj is a tile type partition for T. Suppose T is a G-finite tiling of X with a tile type partition {T}jgJ. If T', T2 E Tj for some j E J, then we will say that T1 and T2 are of the same type. This implies that there exists g E G such that T' + g = T2. We say that T2 is a G-translate of T'. This does not mean that if T', T2 E T and g E G such that T1 + g = T2, then T1 and T2 are of the same type. We will see that there will often exist tile type partitions which contain elements Tij and T1j2 such that every tile in Tj, is a G-translate of every tile in 2h. It follows that there are arbitrarily many different ways to define a tile type partition for a G-finite tiling. For now, let {Tj }jGJ define a tile type partition for T. Let 93 be the set of all finite unions of tiles in T. Let 93 be the set of all bounded subsets of X. Note that q3 C 93. Definition. Let Pl; p2 E q3, then there is a finite collection of tiles {Tk}kCK such that Pl = UkeK Tk. The sets P' and p2 have the same pattern if there exists g E G such that Pl + g = UkEK Tk + g = p2 and for each k E K, Tk + g is a tile in T of the same type as Tk. In particular tiles of the same type have the same pattern. If U E X, then there is a finite union of tiles P E q3 such that U C P. If g E G, then U and U + g have the same pattern if for some P E q3 such that U C P we have that P + g E v and P + g and P have the same pattern. If V is a subset of X and U E 93, then V contains the pattern of U if for some g E G, U + g C V and U + g has the same pattern as U. Let 0 be an expansive linear map on RI such that OX = X. To be expansive means that the eigenvalues for q all have modulus greater than 1. We adapt a This content downloaded from 157.55.39.170 on Tue, 20 Sep 2016 05:07:32 UTC All use subject to http://about.jstor.org/terms NUMERATION SYSTEMS AND MARKOVKOV PARTITIONS 3317 norm for R' which reflects the expansiveness of q as in [12]. More specifically, let {A j}j=j be the eigenvalues of q ordered so that 1 0 we have that the set {P E q4: diameter(P) 0 there exists R = R(r) > 0 such that every open ball of radius R contained in X contains the pattern of Br(x) n x for all x e X. Let G be a subgroup of R' such that bG = G. Definition. A G-finite tiling T of X with tile type partition {fT}.jEJ is subdividing with expansion map 0, if for each T E i, XT is a finite union of tiles and if T and T' are tiles of the same type, then XT and XT' have the same pattern. For each T E Ti we may think of the pattern of XT as defining a subdivision rule for Tj. A quasi-periodic subdividing tiling of T of X with expansion map 0 is called a self similar tiling. Example 1. Let 0 be the expansive map on R given by multiplication by 2 Note that A is a zero of x2 x 1. Let X+ = [0,oo). We construct a Z[A finite subdividing tiling T of X+ with expansion map q. Let TA = [0, 1] and TB = [0, A 1]We will partition T into two sets TA and TB. The tiles in TA will be Z[A]-translates of TA and the tiles in TB will be Z[A]-translates of TB. We define T by inductively defining TA and TB. Let TA E TA. If x E Z[A] and TA + X E TA, then o(TA+x) = [O,A]+Ax = ([O,1]+?x)U([1,A]+Ax) = (TA+Ax)U(TB+1+Ax). Let TA + AX E TA and let TB + 1 + Ax E TB. If y E Z[A] and TB + Y E TB, then q(TB+y) = [0,A2-A]+ Ay = [0,1]+Ay = TA+AY. This content downloaded from 157.55.39.170 on Tue, 20 Sep 2016 05:07:32 UTC All use subject to http://about.jstor.org/terms 3318 BRENDA PRAGGASTIS Let TA + Ay E TA. The tiling T is a Z[A ]-finite subdividing tiling of X+ with expansion map 0 and tile type partition {TA, JB}. We can represent the subdivision rules for T in terms of a substitution map. Let A represent a tile in WA and B represent a tile in TB. Define a substitution map 0 on the words in {A, B} by letting 0(A) = AB and letting 0(B) = A. We define 0 on each finite or infinite string of symbols in {A, B} by applying it to each symbol in the string. We see that T is represented by the fixed word w = ABAABABAABAAB....