Graph neural networks (GNNs) have been extensively utilized in various fields due to their efficient and strong capability in processing graph-structured data. However, as the scale of real-world graphs continues to grow, processing large-scale graphs with GNNs has become increasingly storage-intensive and time-consuming. Graph condensation, which aims to synthesize a smaller yet informative substitute graph, has emerged as a promising solution. Most existing approaches, however, primarily focus on feature condensation while paying less attention to faithfully reconstructing structural information. Moreover, the condensed representations are typically dense, which not only limits storage and computational efficiency but also risks retaining noise and redundancy. To address these limitations, we propose DGC, a Discrete Graph Condensation framework, where numerous nodes in the original graph can be represented by the discrete codes in the codebook while maintaining the original structure information. Specifically, we leverage high-order proximity between nodes to capture the original graph's structure and transfer it to the condensed graph via low-rank approximation. Meanwhile, node features are discretized and compressed through a vector quantized variational autoencoder, effectively reducing redundancy and enhancing storage efficiency while retaining critical information. Extensive experiments on multiple real-world graphs demonstrate the effectiveness of our proposed model against nine competitive baseline methods across different condensation ratios.

In recent years, Message Passing Neural Networks (MPNNs) have emerged as a leading paradigm for learning over graph-structured data, owing to their simple architecture and excellent scalability. However, their expressive power is strictly limited by the one-dimensional Weisfeiler–Leman (1-WL) test. A common approach to enhance expressivity is designing models based on higher-order k -WL and k -Folklore WL ( k -FWL) tests, collectively referred to as tuple-based GNNs. Despite their greater expressive power, these methods face two major challenges: (1) The neighboring tuples in k -WL/FWL are generated by replacing any node in the graph, disregarding adjacency relationships and thus failing to capture structural dependencies between tuples. (2) The design of k -WL/FWL lacks flexibility, while increasing k enhances expressivity, it also results in an exponential surge in time and space complexity. To overcome these limitations, we propose Trail-WL, a more expressive variant of the WL test, along with its neural network counterpart, Trail-based Tuple Neural Network (TTNN). We redefine node tuples as collections of trail structures, providing a more intuitive representation of graph connectivity compared to prior tuple-based methods. By incorporating variable trail lengths and node distance constraints, our model adaptively balances expressivity and scalability while preserving essential structural features. Furthermore, we propose and formally prove three theoretical expressivity theorems for Trail-WL. Finally, we conduct comprehensive experiments on both synthetic and real-world datasets, demonstrating that our approach consistently matches or outperforms baseline methods, thereby substantiating its effectiveness.

Graph Neural Networks (GNNs) have shown great power for learning and mining on graphs, and Graph Structure Learning (GSL) plays an important role in boosting GNNs with a refined graph. In the literature, most GSL solutions either primarily focus on structure refinement with task-specific supervision (i.e., node classification), or overlook the inherent weakness of GNNs themselves (e.g., over-squashing), resulting in suboptimal performance despite sophisticated designs. In light of these limitations, we propose to study self-supervised graph structure-feature co-refinement for effectively alleviating the issue of over-squashing in typical GNNs. In this paper, we take a fundamentally different perspective of the Ricci curvature in Riemannian geometry, in which we encounter the challenges of modeling, utilizing and computing Ricci curvature. To tackle these challenges, we present a self-supervised Riemannian model, DeepRicci. Specifically, we introduce a latent Riemannian space of heterogeneous curvatures to model various Ricci curvatures, and propose a gyrovector feature mapping to utilize Ricci curvature for typical GNNs. Thereafter, we refine node features by geometric contrastive learning among different geometric views, and simultaneously refine graph structure by backward Ricci flow based on a novel formulation of differentiable Ricci curvature. Finally, extensive experiments on public datasets show the superiority of DeepRicci, and the connection between backward Ricci flow and over-squashing. Codes of our work are given in https://github.com/RiemanGraph/.

Sequential interaction networks (SIN) have been commonly adopted in many applications such as recommendation systems, search engines and social networks to describe the mutual influence between users and items/products. Efforts on representing SIN are mainly focused on capturing the dynamics of networks in Euclidean space, and recently plenty of work has extended to hyperbolic geometry for implicit hierarchical learning. Previous approaches which learn the embedding trajectories of users and items achieve promising results. However, there are still a range of fundamental issues remaining open. For example, is it appropriate to place user and item nodes in one identical space regardless of their inherent discrepancy? Instead of residing in a single fixed curvature space, how will the representation spaces evolve when new interaction occurs?

Social network alignment, which aims to uncover the correspondence across different social networks, shows fundamental importance in a wide spectrum of applications such as cross-domain recommendation and information propagation. In the literature, the vast majority of the existing studies focus on the social network alignment at user level. In practice, the user-level alignment usually relies on abundant personal information and high-quality supervision, which is expensive and even impossible in the real-world scenario. Alternatively, we propose to study the problem of social group alignment across different social networks, focusing on the interests of social groups rather than personal information. However, social group alignment is non-trivial and faces significant challenges in both (i) feature inconsistency across different social networks and (ii) group discovery within a social network. To bridge this gap, we present a novel GroupAligner , a deep reinforcement learning with domain adaptation for social group alignment. In GroupAligner , to address the first issue, we propose the cycle domain adaptation approach with the Wasserstein distance to transfer the knowledge from the source social network, aligning the feature space of social networks in the distribution level. To address the second issue, we model the group discovery as a sequential decision process with reinforcement learning in which the policy is parameterized by a proposed p roximity-enhanced G raph N eural N etwork (pGNN) and a GNN-based discriminator to score the reward. Finally, we utilize pre-training and teacher forcing to stabilize the learning process of GroupAligner . Extensive experiments on several real-world datasets are conducted to evaluate GroupAligner , and experimental results show that GroupAligner outperforms the alternative methods for social group alignment.

Representation learning on temporal graphs has drawn considerable research attention owing to its fundamental importance in a wide spectrum of real-world applications. Though a number of studies succeed in obtaining time-dependent representations, it still faces significant challenges. On the one hand, most of the existing methods restrict the embedding space with a certain curvature. However, the underlying geometry in fact shifts among the positive curvature hyperspherical, zero curvature Euclidean and negative curvature hyperbolic spaces in the evolvement over time. On the other hand, these methods usually require abundant labels to learn temporal representations, and thereby notably limit their wide use in the unlabeled graphs of the real applications. To bridge this gap, we make the first attempt to study the problem of self-supervised temporal graph representation learning in the general Riemannian space, supporting the time-varying curvature to shift among hyperspherical, Euclidean and hyperbolic spaces. In this paper, we present a novel self-supervised Riemannian graph neural network (SelfℛGNN). Specifically, we design a curvature-varying Riemannian GNN with a theoretically grounded time encoding, and formulate a functional curvature over time to model the evolvement shifting among the positive, zero and negative curvature spaces. To enable the self-supervised learning, we propose a novel reweighting self-contrastive approach, exploring the Riemannian space itself without augmentation, and propose an edge-based self-supervised curvature learning with the Ricci curvature. Extensive experiments show the superiority of SelfRGNN, and moreover, the case study shows the time-varying curvature of temporal graph in reality.

Knowledge graph embedding aims to learn representations of entities and relations in low-dimensional space. Recently, extensive studies combine the characteristics of knowledge graphs with different geometric spaces, including Euclidean space, complex space, hyperbolic space and others, which achieves significant progress in representation learning. However, existing methods are subject to at least one of the following limitations: 1) ignoring the uncertainty, 2) incapability of complex relation patterns. To address the above issues simultaneously, we propose a novel model named DiriE, which embeds entities as Dirichlet distributions and relations as multinomial distributions. DiriE employs Bayesian inference to measure the relations between entities and learns binary embeddings of knowledge graphs for modeling complex relation patterns. Additionally, we propose a two-step negative triple generation method that generates negative triples of both entities and relations. We conduct a solid theoretical analysis to demonstrate the effectiveness and robustness of our method, including the expressiveness of complex relation patterns and the ability to model uncertainty. Furthermore, extensive experiments show that our method outperforms state-of-the-art methods in link prediction on benchmark datasets.