We propose a new representation of $k$-partite, $k$-uniform hypergraphs (i.e. a hypergraph with a partition of vertices into $k$ parts such that each hyperedge contains exactly one vertex of each type; we call them $k$-hypergraphs for short) by a finite set $P$ of points in $\mathbb{R}^d$ and a parameter $\ell\leq d-1$. Each point in $P$ is covered by $k={d\choose\ell}$ many axis-aligned affine $\ell$-dimensional subspaces of $\mathbb{R}^d$, which we call $\ell$-subspaces for brevity. We interpret each point in $P$ as a hyperedge that contains each of the covering $\ell$-subspaces as a vertex. The class of $(d,\ell)$-hypergraphs is the class of $k$-hypergraphs that can be represented in this way, where $k={d\choose\ell}$. The resulting classes of hypergraphs are fairly rich: Every $k$-hypergraph is a $(k,k-1)$-hypergraph. On the other hand, $(d,\ell)$-hypergraphs form a proper subclass of the class of all $d\choose\ell$-hypergraphs for $\ell<d-1$. In this paper we give a natural structural characterization of $(d,\ell)$-hypergraphs based on vertex cuts. This characterization leads to a polynomial-time recognition algorithm that decides for a given $d\choose\ell$-hypergraph whether or not it is a $(d,\ell)$-hypergraph and that computes a representation if existing. We assume that the dimension $d$ is constant and that the partitioning of the vertex set is prescribed.
相關內容
In this paper, we show several parameterized problems to be complete for the class XNLP: parameterized problems that can be solved with a non-deterministic algorithm that uses $f(k)\log n$ space and $f(k)n^c$ time, with $f$ a computable function, $n$ the input size, $k$ the parameter and $c$ a constant. The problems include Maximum Regular Induced Subgraph and Max Cut parameterized by linear clique-width, Capacitated (Red-Blue) Dominating Set parameterized by pathwidth, Odd Cycle Transversal parameterized by a new parameter we call logarithmic linear clique-width (defined as $k/\log n$ for an $n$-vertex graph of linear clique-width $k$), and Bipartite Bandwidth.
Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set $V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed \emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$, and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set for short) if no two vertices in $G$ have the same set of neighbors in $S$, and each vertex in $S$ is open-dominated exactly once by $S$. The problem of deciding whether or not $G$ has an $OLD_{oind}$-set has important applications that have been reported elsewhere. As the problem is known to be $\mathcal{NP}$-complete, it appears to be notoriously difficult as we show that its complexity remains the same even for just planar bipartite graphs of maximum degree five and girth six, and also for planar subcubic graphs of girth nine. Also, we present characterizations of both $P_4$-tidy graphs and the complementary prisms of cographs that have an $OLD_{oind}$-set.
A family of sets is $(p,q)$-intersecting if every nonempty subfamily of $p$ or fewer sets has at least $q$ elements in its total intersection. A family of sets has the $(p,q)$-Helly property if every nonempty $(p,q)$-intersecting subfamily has total intersection of cardinality at least $q$. The $(2,1)$-Helly property is the usual Helly property. A hypergraph is $(p,q)$-Helly if its edge family has the $(p,q)$-Helly property and hereditary $(p,q)$-Helly if each of its subhypergraphs has the $(p,q)$-Helly property. A graph is $(p,q)$-clique-Helly if the family of its maximal cliques has the $(p,q)$-the Helly property and hereditary $(p,q)$-clique-Helly if each of its induced subgraphs is $(p,q)$-clique-Helly. The classes of $(p,q)$-biclique-Helly and hereditary $(p,q)$-biclique-Helly graphs are defined analogously. We prove several characterizations of hereditary $(p,q)$-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. We give an improved time bound for the recognition of $(p,q)$-Helly hypergraphs for each fixed $q$ and show that the recognition of hereditary $(p,q)$-Helly hypergraphs can be solved in polynomial time if $p$ and $q$ are fixed but co-NP-complete if $p$ is part of the input. In addition, we generalize to $(p,q)$-clique-Helly graphs the characterization of $p$-clique-Helly graphs in terms of expansions and give different characterizations of hereditary $(p,q)$-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of $(p,q)$-clique-Helly graphs and prove that the recognition problem of hereditary $(p,q)$-clique-Helly graphs is polynomial-time solvable for $p$ and $q$ fixed but NP-hard if $p$ or $q$ is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (hereditary) $(p,q)$-biclique-Helly graphs.
One of the fundamental problems in Artificial Intelligence is to perform complex multi-hop logical reasoning over the facts captured by a knowledge graph (KG). This problem is challenging, because KGs can be massive and incomplete. Recent approaches embed KG entities in a low dimensional space and then use these embeddings to find the answer entities. However, it has been an outstanding challenge of how to handle arbitrary first-order logic (FOL) queries as present methods are limited to only a subset of FOL operators. In particular, the negation operator is not supported. An additional limitation of present methods is also that they cannot naturally model uncertainty. Here, we present BetaE, a probabilistic embedding framework for answering arbitrary FOL queries over KGs. BetaE is the first method that can handle a complete set of first-order logical operations: conjunction ($\wedge$), disjunction ($\vee$), and negation ($\neg$). A key insight of BetaE is to use probabilistic distributions with bounded support, specifically the Beta distribution, and embed queries/entities as distributions, which as a consequence allows us to also faithfully model uncertainty. Logical operations are performed in the embedding space by neural operators over the probabilistic embeddings. We demonstrate the performance of BetaE on answering arbitrary FOL queries on three large, incomplete KGs. While being more general, BetaE also increases relative performance by up to 25.4% over the current state-of-the-art KG reasoning methods that can only handle conjunctive queries without negation.
Knowledge graph (KG) embeddings learn low-dimensional representations of entities and relations to predict missing facts. KGs often exhibit hierarchical and logical patterns which must be preserved in the embedding space. For hierarchical data, hyperbolic embedding methods have shown promise for high-fidelity and parsimonious representations. However, existing hyperbolic embedding methods do not account for the rich logical patterns in KGs. In this work, we introduce a class of hyperbolic KG embedding models that simultaneously capture hierarchical and logical patterns. Our approach combines hyperbolic reflections and rotations with attention to model complex relational patterns. Experimental results on standard KG benchmarks show that our method improves over previous Euclidean- and hyperbolic-based efforts by up to 6.1% in mean reciprocal rank (MRR) in low dimensions. Furthermore, we observe that different geometric transformations capture different types of relations while attention-based transformations generalize to multiple relations. In high dimensions, our approach yields new state-of-the-art MRRs of 49.6% on WN18RR and 57.7% on YAGO3-10.
Node classification is an important problem in graph data management. It is commonly solved by various label propagation methods that work iteratively starting from a few labeled seed nodes. For graphs with arbitrary compatibilities between classes, these methods crucially depend on knowing the compatibility matrix that must be provided by either domain experts or heuristics. Can we instead directly estimate the correct compatibilities from a sparsely labeled graph in a principled and scalable way? We answer this question affirmatively and suggest a method called distant compatibility estimation that works even on extremely sparsely labeled graphs (e.g., 1 in 10,000 nodes is labeled) in a fraction of the time it later takes to label the remaining nodes. Our approach first creates multiple factorized graph representations (with size independent of the graph) and then performs estimation on these smaller graph sketches. We define algebraic amplification as the more general idea of leveraging algebraic properties of an algorithm's update equations to amplify sparse signals. We show that our estimator is by orders of magnitude faster than an alternative approach and that the end-to-end classification accuracy is comparable to using gold standard compatibilities. This makes it a cheap preprocessing step for any existing label propagation method and removes the current dependence on heuristics.
Recent advances in Graph Convolutional Neural Networks (GCNNs) have shown their efficiency for non-Euclidean data on graphs, which often require a large amount of labeled data with high cost. It it thus critical to learn graph feature representations in an unsupervised manner in practice. To this end, we propose a novel unsupervised learning of Graph Transformation Equivariant Representations (GraphTER), aiming to capture intrinsic patterns of graph structure under both global and local transformations. Specifically, we allow to sample different groups of nodes from a graph and then transform them node-wise isotropically or anisotropically. Then, we self-train a representation encoder to capture the graph structures by reconstructing these node-wise transformations from the feature representations of the original and transformed graphs. In experiments, we apply the learned GraphTER to graphs of 3D point cloud data, and results on point cloud segmentation/classification show that GraphTER significantly outperforms state-of-the-art unsupervised approaches and pushes greatly closer towards the upper bound set by the fully supervised counterparts.
Learning embeddings of entities and relations existing in knowledge bases allows the discovery of hidden patterns in data. In this work, we examine the geometrical space's contribution to the task of knowledge base completion. We focus on the family of translational models, whose performance has been lagging, and propose a model, dubbed HyperKG, which exploits the hyperbolic space in order to better reflect the topological properties of knowledge bases. We investigate the type of regularities that our model can capture and we show that it is a prominent candidate for effectively representing a subset of Datalog rules. We empirically show, using a variety of link prediction datasets, that hyperbolic space allows to narrow down significantly the performance gap between translational and bilinear models.
Graph Neural Networks (GNN) come in many flavors, but should always be either invariant (permutation of the nodes of the input graph does not affect the output) or equivariant (permutation of the input permutes the output). In this paper, we consider a specific class of invariant and equivariant networks, for which we prove new universality theorems. More precisely, we consider networks with a single hidden layer, obtained by summing channels formed by applying an equivariant linear operator, a pointwise non-linearity and either an invariant or equivariant linear operator. Recently, Maron et al. (2019) showed that by allowing higher-order tensorization inside the network, universal invariant GNNs can be obtained. As a first contribution, we propose an alternative proof of this result, which relies on the Stone-Weierstrass theorem for algebra of real-valued functions. Our main contribution is then an extension of this result to the equivariant case, which appears in many practical applications but has been less studied from a theoretical point of view. The proof relies on a new generalized Stone-Weierstrass theorem for algebra of equivariant functions, which is of independent interest. Finally, unlike many previous settings that consider a fixed number of nodes, our results show that a GNN defined by a single set of parameters can approximate uniformly well a function defined on graphs of varying size.
Recent years have witnessed the enormous success of low-dimensional vector space representations of knowledge graphs to predict missing facts or find erroneous ones. Currently, however, it is not yet well-understood how ontological knowledge, e.g. given as a set of (existential) rules, can be embedded in a principled way. To address this shortcoming, in this paper we introduce a framework based on convex regions, which can faithfully incorporate ontological knowledge into the vector space embedding. Our technical contribution is two-fold. First, we show that some of the most popular existing embedding approaches are not capable of modelling even very simple types of rules. Second, we show that our framework can represent ontologies that are expressed using so-called quasi-chained existential rules in an exact way, such that any set of facts which is induced using that vector space embedding is logically consistent and deductively closed with respect to the input ontology.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191