Biological network comparison using graphlet degree distribution

Abstract

Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics such as the degree distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes 'touching' k edges, into distributions measuring the number of nodes 'touching' k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions (GDDs) of graphlets with 2-5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets). Furthermore, we show a way to combine the 73 GDDs into a network 'agreement' measure. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, are better modeled by geometric random graphs than by Erdos-Reny, random scale-free, or Barabasi-Albert scale-free networks.

Proceedings of the 2006 European Conference on Computational Biology, ECCB'06, Eilat, Israel, January 21-24, 2007

References in corpus (10)

• Emergence of scaling in random networks
• Lethality and centrality in protein networks
• The large-scale organization of metabolic networks
• Specificity and stability in topology of protein networks
• Renormalization group analysis of the small-world network model
• Scaling and percolation in the small-world network model
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Local graph alignment and motif search in biological networks
• Spectral Analysis and the Dynamic Response of Complex Networks
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)

Cited by in corpus (127)

• Geometric deep learning: going beyond Euclidean data
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Scale-free networks are rare
• Predicting multicellular function through multi-layer tissue networks
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Network Enhancement: a general method to denoise weighted biological networks
• InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization
• Triadic Measures on Graphs: The Power of Wedge Sampling
• A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
• Current and future directions in network biology
• Discovery of Self-Assembling $\pi$-Conjugated Peptides by Active Learning-Directed Coarse-Grained Molecular Simulation
• Emergent Complex Network Geometry
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Graph Capsule Convolutional Neural Networks
• Graph Kernels: A Survey
• What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• Representation Learning for Dynamic Graphs: A Survey
• Higher order molecular organisation as a source of biological function
• The Power of Pivoting for Exact Clique Counting
• Degree Relations of Triangles in Real-world Networks and Models
• Spatio-Temporal Graph Convolution for Skeleton Based Action Recognition
• FLEET: Butterfly Estimation from a Bipartite Graph Stream
• Motif-based Convolutional Neural Network on Graphs
• Combinatorial algorithm for counting small induced graphs and orbits
• Generalized Stability Approach for Regularized Graphical Models
• Hierarchical stochastic graphlet embedding for graph-based pattern recognition
• GraphCrop: Subgraph Cropping for Graph Classification
• Stochastic Graphlet Embedding
• Pairwise versus multiple network alignment
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Network comparison using directed graphlets
• Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics
• Proper network randomization is key to assessing social balance
• A Framework for Generalizing Graph-based Representation Learning Methods
• odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks
• Metrics in the Space of High Order Networks
• Walk-Steered Convolution for Graph Classification
• HONE: Higher-Order Network Embeddings
• Counterfactual Learning on Graphs: A Survey
• Human Mobility Networks Manifest Dissimilar Resilience Characteristics at Macroscopic, Substructure, and Microscopic Scales
• Testing biological network motif significance with exponential random graph models
• A General Framework for Estimating Graphlet Statistics via Random Walk
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• Discriminative structural graph classification
• Graph Meta Learning via Local Subgraphs
• Towards a Networks-of-Networks Framework for Cyber Security
• Revealing effective classifiers through network comparison
• Learning Universal Graph Neural Network Embeddings With Aid Of Transfer Learning
• Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
• Convexity in complex networks
• Ultra High-Dimensional Nonlinear Feature Selection for Big Biological Data
• Heterogeneous Network Motifs
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• DwarvesGraph: A High-Performance Graph Mining System with Pattern Decomposition
• Graph Convolutional Neural Networks via Motif-based Attention
• Evolution of Directed Triangle Motifs in the Google+ OSN
• A novel similarity measure for mining missing links in long-path networks
• Higher-order temporal network effects through triplet evolution
• A Fast Sampling Method of Exploring Graphlet Degrees of Large Directed and Undirected Graphs
• Modeling Graphs with Vertex Replacement Grammars
• Estimating Subgraph Frequencies with or without Attributes from Egocentrically Sampled Data
• Growing Graphs with Hyperedge Replacement Graph Grammars
• Arabesque: A System for Distributed Graph Mining - Extended version
• Kaleido: An Efficient Out-of-core Graph Mining System on A Single Machine
• Modeling and Measuring Graph Similarity: The Case for Centrality Distance
• Mining and modeling character networks
• Network Motifs Analysis of Croatian Literature
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• SubGraph2Vec: Highly-Vectorized Tree-likeSubgraph Counting
• Metrics for network comparison using egonet feature distribution
• Fair Evaluation of Global Network Aligners
• Temporal Network Motifs: Models, Limitations, Evaluation
• Comparing directed networks via denoising graphlet distributions
• Compression-based inference of network motif sets
• Edge crossings in random linear arrangements
• Revealing missing parts of the interactome
• Joint Subgraph-to-Subgraph Transitions -- Generalizing Triadic Closure for Powerful and Interpretable Graph Modeling
• The Infinity Mirror Test for Graph Models
• Local, global and scale-dependent node roles
• A GraphBLAS Approach for Subgraph Counting
• GraphZip: Dictionary-based Compression for Mining Graph Streams
• GraLSP: Graph Neural Networks with Local Structural Patterns
• A sampling framework for counting temporal motifs
• Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
• Construction of edge-ordered multidirected graphlets for comparing dynamics of spatial temporal neural networks
• Quantum Motif Clustering
• The Infinity Mirror Test for Analyzing the Robustness of Graph Generators
• Self-Coordinated Corona Graphs: a model for complex networks
• Nonparametric Two-Sample Test for Networks Using Joint Graphon Estimation
• Provenance Graph Kernel
• ThunderRW: An In-Memory Graph Random Walk Engine (Complete Version)
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels
• Distributed Subgraph Enumeration via Backtracking-based Framework
• A Visual Analytics Framework for Contrastive Network Analysis
• DDSL: Efficient Subgraph Listing on Distributed and Dynamic Graphs
• Graph Pattern Mining and Learning through User-defined Relations (Extended Version)
• GoT-WAVE: Temporal network alignment using graphlet-orbit transitions
• Functional geometry of protein-protein interaction networks
• Fast counting of medium-sized rooted subgraphs
• Active Network Alignment: A Matching-Based Approach
• The Structurally Smoothed Graphlet Kernel
• Predictive Functional Connectivity of Real-World Systems
• Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
• Persistent Homology Lower Bounds on High Order Network Distances
• GREAT: GRaphlet Edge-based network AlignmenT
• Learning an Integrated Distance Metric for Comparing Structure of Complex Networks
• Growing Better Graphs With Latent-Variable Probabilistic Graph Grammars
• A Return to Biased Nets: New Specifications and Approximate Bayesian Inference
• Network approach integrates 3D structural and sequence data to improve protein structural comparison
• Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)
• An egonet-based approach to effective weighted network comparison
• Permutation-Invariant Subgraph Discovery
• Differential analysis of biological networks
• Graphlet-based lazy associative graph classification
• Sampling Graphlets of Multi-layer Networks: A Restricted Random Walk Approach
• One Node at a Time: Node-Level Network Classification
• Attributed-graphs kernel implementation using local detuning of neutral-atoms Rydberg Hamiltonian
• Graphlets in multilayer networks
• An interdisciplinary survey of network similarity methods
• A Temporal Tree Decomposition for Generating Temporal Graphs
• Network Medicine in the age of biomedical big data
• Graph Kernels based on High Order Graphlet Parsing and Hashing
• Investigating cognitive ability using action-based models of structural brain networks
• Hierarchical sequencing of online social graphs
• Ranking Users in Social Networks with Motif-based PageRank
• The Many Faces of Graph Dynamics