disassortative  graph
210843644
Geom GCN: Geometric Graph Convolutional Networks
Message passing neural networks (MPNNs) have been successfully applied in a wide variety of applications in the real world. However, two fundamental weaknesses of MPNNs' aggregators limit their ability to represent graph structured data: losing the structural information of nodes in neighborhoods and lacking the ability to capture long range dependencies in disassortative graphs. Few studies have noticed the weaknesses from different perspectives. From the observations on classical neural network and network geometry, we propose a novel geometric aggregation scheme for graph neural networks to overcome the two weaknesses. The behind basic idea is the aggregation on a graph can benefit from a continuous space underlying the graph. The proposed aggregation scheme is permutation invariant and consists of three modules, node embedding, structural neighborhood, and bi level aggregation. We also present an implementation of the scheme in graph convolutional networks, termed Geom GCN, to perform transductive learning on graphs. Experimental results show the proposed Geom GCN achieved state of the art performance on a wide range of open datasets of graphs.
ICLR
Hongbin Pei Bingzhen Wei Kevin Chen-Chuan Chang Yu Lei Bo Yang
219124225
Non Local Graph Neural Networks
Modern graph neural networks (GNNs) learn node embeddings through multilayer local aggregation and achieve great success in applications on assortative graphs. However, tasks on disassortative graphs usually require non local aggregation. In this work, we propose a simple yet effective non local aggregation framework with an efficient attention guided sorting for GNNs. Based on it, we develop various non local GNNs. We perform thorough experiments to analyze disassortative graph datasets and evaluate our non local GNNs. Experimental results demonstrate that our non local GNNs significantly outperform previous state of the art methods on six benchmark datasets of disassortative graphs, in terms of both model performance and efficiency.
ArXiv
Meng Liu Zhengyang Wang Shuiwang Ji
125188736
Scale free graph sequences are not disassortative
We investigate degree degree correlations for scale free graph sequences. The main conclusion of this paper is that the assortativity coecient is not the appropriate way to describe degreedependences in scale free random graphs. Indeed, we study the innite volume limit of the assortativity coecient, and show that this limit is always non negative when the degrees have nite rst but innite
Nelly Litvak Remco van der Hofstad
235324638
Graph Structure Estimation Neural Networks
Graph Neural Networks (GNNs) have drawn considerable attention in recent years and achieved outstanding performance in many tasks. Most empirical studies of GNNs assume that the observed graph represents a complete and accurate picture of node relationship. However, this fundamental assumption cannot always be satisfied, since the real world graphs from complex systems are error prone and may not be compatible with the properties of GNNs. Therefore, GNNs solely relying on original graph may cause unsatisfactory results, one typical example of which is that GNNs perform well on graphs with homophily while fail on the disassortative situation. In this paper, we propose graph estimation neural networks GEN, which estimates graph structure for GNNs. Specifically, our GEN presents a structure model to fit the mechanism of GNNs by generating graphs with community structure, and an observation model that injects multifaceted observations into calculating the posterior distribution of graphs and is the first to incorporate multi order neighborhood information. With above two models, the estimation of graph is implemented based on Bayesian inference to maximize the posterior probability, which attains mutual optimization with GNN parameters in an iterative framework. To comprehensively evaluate the performance of GEN, we perform a set of experiments on several benchmark datasets with different homophily and a synthetic dataset, where the experimental results demonstrate the effectiveness of our GEN and rationality of the estimated graph.
WWW
Ruijia Wang Shuai Mou Xiao Wang Wanpeng Xiao Qi Ju Chuan Shi Xing Xie
111386026
How Firms Choose their Partners in the Japanese Supplier Customer Network? An application of the exponential random graph model
This work aims to explain how firms behave and select their suppliers and customers in the Japanese production network. We study a supplier customer network of listed firms in Japan (3,198 firms with 20,417 links) In order to specify how firms choose their partners, the so called exponential random graph model is applied to estimate the ties formation process. For the estimation of such a large scale network, we employ a recent technique of sampling called the improved fixed density Markov Chain Monte Carlo (MCMC) Our main result shows that all of the effects (social and economic effects) are statistically significant in explaining the ties formation between firms. Social effects such as mutuality and transitivity with common partners in different directional links between suppliers and customers are shown. Moreover, homophily with the same industrial sectors and geographical locations, and disassortative mixing between low profit firms and high profit ones are also found. We argue that our method is extended to the spatially heterogeneous structure of communities reflecting industrial sectors and geographical locations and temporal changes of supplier customer relationships in such a framework of the stochastic actor oriented model.
Hazem Krichene Arata Yoshiyuki Abhijit Chakraborty Fujiwara Yoshi Inoue Hiroyasu
8934448
Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph
Most previous analysis of Twitter user behavior has focused on individual information cascades and the social followers graph, in which the nodes for two users are connected if one follows the other. We instead study aggregate user behavior and the retweet graph with a focus on quantitative descriptions. We find that the lifetime tweet distribution is a type II discrete Weibull stemming from a power law hazard function, that the tweet rate distribution, although asymptotically power law, exhibits a lognormal cutoff over finite sample intervals, and that the inter tweet interval distribution is a power law with exponential cutoff. The retweet graph is small world and scale free, like the social graph, but less disassortative and has much stronger clustering. These differences are consistent with it better capturing the real world social relationships of and trust between users than the social graph. Beyond just understanding and modeling human communication patterns and social networks, applications for alternative, decentralized microblogging systems both predicting real word performance and detecting spam are discussed.
ACM Trans. Internet Techn.
David R Bild Yue Liu Robert P Dick Z Morley Mao Dan S Wallach
36180470
A Visibility Graph Approach to CNY Exchange Rate Networks and Characteristic Analysis
We find that exchange rate networks are significantly similar from the perspective of topological structure, though with relatively great differences in fluctuation characteristics from perspective of exchange rate time series. First, we transform central parity rate time series of US dollar, Euro, Yen, and Sterling against CNY into exchange rate networks with visibility graph algorithm and find consistent topological characteristics in four exchange rate networks, with their average path lengths 5 and average clustering coefficients 0.7. Further, we reveal that all four transformed exchange rate networks show hierarchical structure and small world and scale free properties, with their hierarchy indexes 0.5 and power exponents 1.5. Both of the US dollar network and Sterling network exhibit assortative mixing features, while the Euro network and Yen network exhibit disassortative mixing features. Finally, we research community structure of exchange rate networks and uncover the fact that the communities are actually composed by large amounts of continuous time point fractions and small amounts of discrete time point fractions. In this way, we can observe that the spread of time series values corresponding to nodes inside communities is significantly lower than the spread of those values corresponding to nodes of the whole networks.
Canzhong Yao Ji-Nan Lin
18378783
Comparison of graph sampling algorithms using normalized Laplacian spectra
The normalized Laplacian spectrum is a good indicator of connectivity for comparing graphs with different sizes (i.e. the number of nodes) This paper shows the performances of several random walk sampling algorithms using the spectral indicator. Based on two types of complex network models with exponential and power law degree distributions, we determine that the sampling algorithms do not perform well on the spectral indicator, and find that the spectral indicator of biased sampling graphs is much closer to that of original graphs when the assortative mixing coefficient of original graphs decreases. Especially, for disassortative networks, biased sampling graphs perform better than unbiased sampling graphs on the spectral indicator.
2016 7th IEEE International Conference on Software Engineering and Service Science (ICSESS)
Bo Jiao Chengdong Huang Yuanping Nie Fei Jie Huang Ying Zhou Jing Du
14617468
Application of Graph Coloring to Biological Networks
The author explores the application of graph colouring to biological networks, specifically protein protein interaction (PPI) networks. First, the author finds that given similar conditions (i.e. graph size, degree distribution and clustering) fewer colours are needed to colour disassortative than assortative networks. Fewer colours create fewer independent sets which in turn imply higher concurrency potential for a network. Since PPI networks tend to be disassortative, the author suggests that in addition to functional specificity and stability proposed previously by Maslov and Sneppen (Science, 296, 2002) the disassortative nature of PPI networks may promote the ability of cells to perform multiple, crucial and functionally diverse tasks concurrently. Second, because graph colouring is closely related to the presence of cliques in a graph, the significance of node colouring information to the problem of identifying protein complexes (dense subgraphs in PPI networks) is investigated. The author finds that for PPI networks where 1 11% of nodes participate in at least one identified protein complex, such as H. sapien, DSATUR (a well known complete graph colouring algorithm) node colouring information can improve the quality (homogeneity and separation) of initial candidate complexes. This finding may help improve existing protein complex detection methods, and/or suggest new methods. [Includes supplementary material]
IET systems biology
Susan Khor
224855288
Assortativity Properties of Barabasi Albert Networks
Nodes distribution by degrees is the most important characteristic of complex networks. For SF networks it follows a power law. While degree distribution is a first order graph metric, the assortativity is a second order one. The concept of assortativity is extensively using in network analysis. In general degree distribution forms an essential restriction both on the network structure and on assortativity coefficient boundaries. The problem of determining the structure of BA networks having an extreme assortativity coefficient is considered. Greedy algorithms for generating BA networks with extreme assortativity have been proposed. As it was found, an extremely disassortative BA network is asymptotically bipartite, while an extremely assortative one is close to be a set of complete and disconnected clusters. The estimates of boundaries for assortativity coefficient have been found. These boundaries are narrowing with increasing the network size and are significantly narrower than for networks having an arbitrary structure.
Vadim Shergin Serhii Udovenko Larysa Chala