More Like this

1. Exact Community Recovery in Correlated Stochastic Block Models

   Gaudio, Julia ; Racz, Miklos Z. ; Sridhar, Anirudh ( July 2022 , Proceedings of Machine Learning Research)

   We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures. 

   more » « less
2. Graph Communal Contrastive Learning

   https://doi.org/10.1145/3485447.3512208  

   Li, Bolian ; Jing, Baoyu ; Tong, Hanghang ( April 2022 , Graph Communal Contrastive Learning)

   Graph representation learning is crucial for many real-world ap- plications (e.g. social relation analysis). A fundamental problem for graph representation learning is how to effectively learn rep- resentations without human labeling, which is usually costly and time-consuming. Graph contrastive learning (GCL) addresses this problem by pulling the positive node pairs (or similar nodes) closer while pushing the negative node pairs (or dissimilar nodes) apart in the representation space. Despite the success of the existing GCL methods, they primarily sample node pairs based on the node- level proximity yet the community structures have rarely been taken into consideration. As a result, two nodes from the same community might be sampled as a negative pair. We argue that the community information should be considered to identify node pairs in the same communities, where the nodes insides are seman- tically similar. To address this issue, we propose a novel Graph Communal Contrastive Learning (𝑔𝐶𝑜𝑜𝐿) framework to jointly learn the community partition and learn node representations in an end-to-end fashion. Specifically, the proposed 𝑔𝐶𝑜𝑜𝐿 consists of two components: a Dense Community Aggregation (𝐷𝑒𝐶𝐴) algo- rithm for community detection and a Reweighted Self-supervised Cross-contrastive (𝑅𝑒𝑆𝐶) training scheme to utilize the community information. Additionally, the real-world graphs are complex and often consist of multiple views. In this paper, we demonstrate that the proposed 𝑔𝐶𝑜𝑜𝐿 can also be naturally adapted to multiplex graphs. Finally, we comprehensively evaluate the proposed 𝑔𝐶𝑜𝑜𝐿 on a variety of real-world graphs. The experimental results show that the 𝑔𝐶𝑜𝑜𝐿 outperforms the state-of-the-art methods. 

   more » « less
3. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng ; Rudelson, Mark ; Tikhomirov, Konstantin ( July 2021 , Proceedings of Thirty Fourth Conference on Learning Theory)

   Belkin, Mikhail ; Samory Kpotufe (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation 1−α, our algorithm recovers the underlying matching exactly with high probability when α≤1/(loglogn)C, where n is the number of vertices in each graph and C denotes a positive universal constant. This improves the condition α≤1/(logn)C achieved in previous work. 

   more » « less
4. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng ; Rudelson, Mark ; Tikhomirov, Konstantin ( August 2021 , Proceedings of Machine Learning Research)

   Belkin, Mikhail ; Kpotufe, Samory (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation $1-\alpha$, our algorithm recovers the underlying matching exactly with high probability when $\alpha \le 1 / (\log \log n)^C$, where $n$ is the number of vertices in each graph and $C$ denotes a positive universal constant. This improves the condition $\alpha \le 1 / (\log n)^C$ achieved in previous work. 

   more » « less
5. Multi-view spectral graph convolution with consistent edge attention for molecular modeling

   https://doi.org/https://doi.org/10.1016/j.neucom.2021.02.025  

   Shang, C ; Liu, Q ; Tong, Q ; Sun, J ; Song, M ; Bi, J ( July 2021 , Neurocomputing)

   null (Ed.)

   Although graph convolutional networks (GCNs) that extend the convolution operation from images to graphs have led to competitive performance, the existing GCNs are still difficult to handle a variety of applications, especially cheminformatics problems. Recently multiple GCNs are applied to chemical compound structures which are represented by the hydrogen-depleted molecular graphs of different size. GCNs built for a binary adjacency matrix that reflects the connectivity among nodes in a graph do not account for the edge consistency in multiple molecular graphs, that is, chemical bonds (edges) in different molecular graphs can be similar due to the similar enthalpy and interatomic distance. In this paper, we propose a variant of GCN where a molecular graph is first decomposed into multiple views of the graph, each comprising a specific type of edges. In each view, an edge consistency constraint is enforced so that similar edges in different graphs can receive similar attention weights when passing information. Similarly to prior work, we prove that in each layer, our method corresponds to a spectral filter derived by the first order Chebyshev approximation of graph Laplacian. Extensive experiments demonstrate the substantial advantages of the proposed technique in quantitative structure-activity relationship prediction. 

   more » « less