Learning representations of sets of nodes in a graph is crucial for applications ranging from noderole discovery to link prediction and molecule classification. Graph Neural Networks (GNNs) have achieved great success in graph representation learning. However, expressive power of GNNs is limited by the 1WeisfeilerLehman (WL) test and thus GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higherorderWL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph. Here we propose and mathematically analyze a general class of structure related features, termed Distance Encoding (DE). DE assists GNNs in representing any set of nodes, while providing strictly more expressive power than the 1WL test. DE captures the distance between the node set whose representation is to be learned and each node in the graph. To capture the distance DE can apply various graphdistance measures such as shortest path distance or generalized PageRank scores. We propose two ways for GNNs to use DEs (1) as extra node features, and (2) as controllers of message aggregation in GNNs. Both approaches can utilize the sparse structure of the underlying graph, which leads to computational efficiency and scalability. We also prove that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. We evaluate DE on three tasks over six real networks: structural role prediction, link prediction, and triangle prediction. Results show that our models outperform GNNs without DE by upto 15% in accuracy and AUROC. Furthermore, our models also significantly outperform other stateoftheart methods especially designed for the above tasks.
more »
« less
Can Graph Neural Networks Count Substructures?
The ability to detect and count certain substructures in graphs is important for solving many tasks on graphstructured data, especially in the contexts of computa tional chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation. We distinguish between two types of substructure counting: inducedsubgraphcount and subgraphcount, and establish both positive and negative answers for popular GNN architectures. Specifically, we prove that Message Passing Neural Networks (MPNNs), 2WeisfeilerLehman (2WL) and 2Invariant Graph Networks (2IGNs) cannot perform inducedsubgraphcount of any connected substructure consisting of 3 or more nodes, while they can perform subgraphcount of starshaped sub structures. As an intermediary step, we prove that 2WL and 2IGNs are equivalent in distinguishing nonisomorphic graphs, partly answering an open problem raised in [38]. We also prove positive results for kWL and kIGNs as well as negative results for kWL with a finite number of iterations. We then conduct experiments that support the theoretical results for MPNNs and 2IGNs. Moreover, motivated by substructure counting and inspired by [45], we propose the Local Relational Pooling model and demonstrate that it is not only effective for substructure counting but also able to achieve competitive performance on molecular prediction tasks.
more »
« less
 Award ID(s):
 1845360
 NSFPAR ID:
 10233869
 Date Published:
 Journal Name:
 Advances in neural information processing systems
 ISSN:
 10495258
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Focusing on graphstructured prediction tasks, we demon strate the ability of neural networks to provide both strong predictive performance and easy interpretability, two proper ties often at odds in modern deep architectures. We formulate the latter by the ability to extract the relevant substructures for a given task, inspired by biology and chemistry appli cations. To do so, we utilize the Local Relational Pooling (LRP) model, which is recently introduced with motivations from substructure counting. In this work, we demonstrate that LRP models can be used on challenging graph classification tasks to provide both stateoftheart performance and inter pretability, through the detection of the relevant substructures used by the network to make its decisions. Besides their broad applications (biology, chemistry, fraud detection, etc.), these models also raise new theoretical questions related to com pressed sensing and to computational thresholds on random graphs.more » « less

Counting the frequency of subgraphs in large networks is a classic research question that reveals the underlying substructures of these networks for important applications. However, subgraph counting is a challenging problem, even for subgraph sizes as small as five, due to the combinatorial explosion in the number of possible occurrences. This article focuses on the fivecycle, which is an important special case of fivevertex subgraph counting and one of the most difficult to count efficiently. We design two new parallel fivecycle counting algorithms and prove that they are work efficient and achieve polylogarithmic span. Both algorithms are based on computing low outdegree orientations, which enables the efficient computation of directed twopaths and threepaths, and the algorithms differ in the ways in which they use this orientation to eliminate doublecounting. Additionally, we present new parallel algorithms for obtaining unbiased estimates of fivecycle counts using graph sparsification. We develop fast multicore implementations of the algorithms and propose a work scheduling optimization to improve their performance. Our experiments on a variety of realworld graphs using a 36core machine with twoway hyperthreading show that our best exact parallel algorithm achieves 10–46× selfrelative speedup, outperforms our serial benchmarks by 10–32×, and outperforms the previous stateoftheart serial algorithm by up to 818×. Our best approximate algorithm, for a reasonable probability parameter, achieves up to 20× selfrelative speedup and is able to approximate fivecycle counts 9–189× faster than our best exact algorithm, with between 0.52% and 11.77% error.more » « less

To achieve a graph representation, most Graph Neural Networks (GNNs) follow two steps: first, each graph is decomposed into a number of subgraphs (which we call the recursion step), and then the collection of subgraphs is encoded by several iterative pooling steps. While recently proposed higherorder networks show a remarkable increase in the expressive power through a single recursion on larger neighborhoods followed by iterative pooling, the power of deeper recursion in GNNs without any iterative pooling is still not fully understood. To make it concrete, we consider a pure recursionbased GNN which we call Recursive Neighborhood Pooling GNN (RNPGNN). The expressive power of an RNPGNN and its computational cost quantifies the power of (pure) recursion for a graph representation network. We quantify the power by means of counting substructures, which is one main limitation of the Message Passing graph Neural Networks (MPNNs), and show how RNPGNN can exploit the sparsity of the underlying graph to achieve lowcost powerful representations. We also compare the recent lower bounds on the time complexity and show how recursionbased networks are near optimal.more » « less

Cliquecounting is a fundamental problem that has application in many areas eg. dense subgraph discovery, community detection, spam detection, etc. The problem of kcliquecounting is difficult because as k increases, the number of kcliques goes up exponentially. Enumeration algorithms (even parallel ones) fail to count kcliques beyond a small k. Approximation algorithms, like TuránShadow have been shown to perform well upto k = 10, but are inefficient for larger cliques. The recently proposed Pivoter algorithm significantly improved the stateoftheart and was able to give exact counts of all kcliques in a large number of graphs. However, the clique counts of some graphs (for example, comlj) are still out of reach of these algorithms. We revisit the TuránShadow algorithm and propose a generalized framework called YACC that leverages several insights about realworld graphs to achieve faster cliquecounting. The bottleneck in TuránShadow is a recursive subroutine whose stopping condition is based on a classic result from extremal combinatorics called Turán's theorem. This theorem gives a lower bound for the kclique density in a subgraph in terms of its edge density. However, this stopping condition is based on a worstcase graph that does not reflect the nature of realworld graphs. Using techniques for quickly discovering dense subgraphs, we relax the stopping condition in a systematic way such that we get a smaller recursion tree while still maintaining the guarantees provided by TuránShadow. We deploy our algorithm on several realworld data sets and show that YACC reduces the size of the recursion tree and the running time by over an order of magnitude. Using YACC, we are able to obtain clique counts for several graphs for which cliquecounting was infeasible before, including comlj.more » « less