Home Archive
Archive
2024 Volume 61 Issue 8  Published: 2024-08-01
    Special Issue on Graph Machine Learning
  • Hanzhi Wang , Lu Yi , Zhewei Wei , Junhao Gan , Ye Yuan , Jirong Wen , Xiaoyong Du
    doi: 10.7544/issn1000-1239.202440148

    Computing random-walk probabilities on graphs is the subject of extensive research in both graph theory and data mining research. However, existing work mainly focuses on static graphs, and cannot efficiently support dynamic weighted graphs, which are ubiquitous in real-world applications. We study the problem of computing random-walk probabilities on dynamic weighted graphs. We propose to use a sampling schema called coin flip sampling, rather than the more commonly adopted weighted sampling schema, for simulating random walks in dynamic weighted graphs. We demonstrate that simulations based on coin-flip sampling maintain the unbiasedness of the resulting random-walk probability approximations. Moreover, this approach allows us to simultaneously achieve a near-optimal query time complexity and an optimal $ O\left(1\right) $ update time overhead per edge insertion or deletion. This is a significant improvement over existing methods, which typically incur substantial sampling costs or rely on intricate auxiliary structures that are hard to maintain in a dynamic setting. We present both theoretical analysis and empirical evaluations to substantiate the superiority of our method on dynamic weighted graphs.

  • Special Issue on Graph Machine Learning
  • Yulin He , Bo Wu , Dingming Wu , Zhexue Huang , Fournier-Viger Philippe
    doi: 10.7544/issn1000-1239.202440120

    Triangle counting is a classical problem in large-scale graph analysis and widely applied in areas such as social network analysis, anomaly detection, and graph mining. In dynamic graph data streams, the topological structure of graph is constantly changing, involving edge insertions and deletions. Recent researches mainly focus on static streaming graphs and the corresponding streaming graph sampling algorithms only deal with edge insertions. Only a few single-machine sampling algorithms with low accuracy can handle edge deletion operations. We propose the edge hashing assignment-based distributed sampling (EHADS) algorithm, which is a distributed streaming algorithm designed for estimating the number of triangles in dynamic graph data streams. EHADS algorithm can rapidly and accurately estimate the counts of global triangles and local triangles associated with each vertex in dynamic streaming graphs. EHADS algorithm processes the input graph stream only once and samples edges across multiple machines. Compared with state-of-the-art single-machine streaming algorithms, the experimental results reflect that EHADS algorithm has the following advantages: 1) with the same sample capacity, EHADS algorithm achieves smaller estimation errors with less runtime, reducing the average estimation error of global triangle count by 31.79% and local triangle count by 23.35%; 2) EHADS algorithm provides unbiased estimations of the triangle count in streaming graph, and mathematical proofs demonstrate that the above-mentioned unbiased estimation has smaller variance.

  • Special Issue on Graph Machine Learning
  • Chao Li , Wenbin Li , Yang Gao
    doi: 10.7544/issn1000-1239.202440189

    Numerous multi-agent tasks exhibit a nearly decomposable structure, wherein interactions among agents within the same interaction set are strong while interactions between different sets are weak. Efficiently modeling this structure and leveraging it to coordinate agents can enhance the learning efficiency of multi-agent reinforcement learning algorithms for cooperative multi-agent tasks, while existing work typically neglects and fails. To address this limitation, we model the nearly decomposable structure using a dynamic graph and accordingly propose a novel algorithm named coordinated subtask pattern (CSP) that enhances both local and global coordination among agents. Specifically, CSP identifies agents’ interaction sets as subtasks and utilizes a bi-level structure to periodically distribute agents into multiple subtasks, which ensures accurate characterizations regarding their interactions on the dynamic graph. Based on the subtask assignment, CSP proposes intra-subtask and inter-subtask pattern constraints to facilitate both local and global coordination among agents. These two constraints ensure that partial agents within the same subtask are aware of their action selections and all agents select superior joint actions that maximize the overall task performance. Experimentally, we evaluate CSP across multiple maps of SMAC benchmark, and its superior performance against multiple baseline algorithms demonstrates its effectiveness on efficiently coordinating agents.

  • Special Issue on Graph Machine Learning
  • Xiaokai Lu , Jun Feng , Yongqiang Han , Hao Wang , Enhong Chen
    doi: 10.7544/issn1000-1239.202440137

    In the domain of multi-behavior sequence recommendation, Graph Neural Networks (GNNs) have been widespreadly adopted, yet they have limitations, notably in terms of adequately modeling the collaborative signals that exist between different sequences and addressing the challenges posed by long-distance dependencies. To bridge these gaps, a novel framework named GraphMLP-Mixer has been introduced. This innovative framework begins by constructing a global item graph, which is designed to bolster the model’s capacity to encapsulate the collaborative signals that are present across sequences. It then merges the perceptron-mixer architecture with graph neural networks, resulting in a graph-perceptron mixer model capable of delving deep into the intricacies of user interests. GraphMLP-Mixer stands out for its two principal strengths: It not only succeeds in effectively capturing the global dependencies inherent in user behaviors but also manages to alleviate the issue of excessive information compression. Furthermore, the framework boasts remarkable improvements in terms of time and space efficiency, with its complexity scaling in a linear fashion with the number of user interactions, thus outperforming existing GNN-based models in the realm of multi-behavior sequence recommendation. The robustness and efficiency of GraphMLP-Mixer in tackling the complexities of multi-behavior sequence recommendation have been thoroughly validated through extensive experimentation on three diverse and publicly available datasets.

  • Special Issue on Graph Machine Learning
  • Jinyu Zhang , Chenxi Ma , Chao Li , Zhongying Zhao
    doi: 10.7544/issn1000-1239.202440197

    Cross-domain sequential recommendation (CSR) aims to capture the behavioral preferences of users by modeling their historical interaction sequences in multiple domains, thus providing personalized cross-domain recommendations. Recently, researchers have started integrating graph convolution networks (GCNs) into CSR to model complicated associations among users and items. However, due to their complicated structure, most graph-based CSR methods are usually accompanied by high computational complexity or memory overhead, making them difficult to deploy on resource-constrained edge devices. Besides, existing lightweight graph-based CSR methods tend to employ single layer aggregating protocol (SLAP) to propagate embeddings on cross-domain sequential graphs (CSG). Such a strategy indeed aids the GCNs in circumventing cross-domain noise interference caused by high-order neighborhood aggregation strategies. However, it also shields GCN from mining high-order sequential relationships within individual domains. To this end, we introduce a lightweight tri-branches graph external attention network (TEA-Net). Specifically, we separate the original CSG into three parts including two inner-domain sequential graphs and an inter-domain sequential graph and devise a parallel tri-branches graph convolution network to learn the node representations. This structure can simultaneously consider the first-order inter-domain correlations and the high-order inner-domain connectivity without introducing additional cross-domain noises. Besides, we propose an improved external attention (EA) component without the nonlinear channel, which captures the sequential dependency among items at a lower cost and shares attention weights across multiple branches. We conduct extensive experiments on two large-scale real-world datasets to verify the performance of TEA-Net. The experimental results demonstrate the superiority of TEA-Net in both the lightweight performance and the prediction accuracy compared with several state-of-the-art methods.

  • Special Issue on Graph Machine Learning
  • Jing Shang , Zhihui Wu , Zhiwen Xiao , Yifei Zhang
    doi: 10.7544/issn1000-1239.202440190

    Most computing systems utilize caching to reduce data access latency, speed up data processing and balance service load. The key to cache management is to determine the appropriate data to be loaded into or discarded from the cache, as well as the appropriate timing for cache replacement, which is critical to improving cache hit rate.The existing caching schemes face with two problems: In real-time and online caching scenarios, it is difficult to discern the heat information of user access to data while ignoring the complex high-order information among data-access-sequences. In this paper, we propose a GNN-based cache prefetching network named Graph4Cache. We model a single access sequence into a directed graph (ASGraph), where virtual nodes are used to aggregate the features of all nodes in graph and represent the whole sequence. Then a cross sequence undirected graph (CSGraph) is constructed from the virtual nodes of ASGraphs to learn cross-sequence features, which greatly complements the limited item transitions in a single sequence. By fusing the information of these two graphs , we learn the high-order correlations among sequences and get abundant user intents. Experimental results on multiple public data sets demonstrate the effectiveness of this method. Graph4Cache outperforms the existing cache prediction algorithms on P@20 and MRR@20.

  • Special Issue on Graph Machine Learning
  • Shaopeng Wei , Ting Liang , Yu Zhao , Fuzhen Zhuang , Fuji Ren
    doi: 10.7544/issn1000-1239.202440126

    Credit risk assessment for enterprises is a critical issue, significantly impacting investor decisions. It also plays a crucial role in enabling government warnings and the handling of financial risks in a timely manner. Given the numerous heterogeneous relationships in the financial market, graph neural networks are naturally suitable for modeling enterprise credit risk. However, most existing research primarily focuses on modeling either the intra-risk of enterprises based on their financial information or the inter-enterprise contagion risk using simulation methods. Therefore, these approaches fail to fully capture the comprehensive credit risk of enterprises in complex financial networks. To address this limitation in current research, we propose a multi-perspective heterogeneous graph neural network method CRGNN for enterprise credit risk assessment. This method includes an enterprise intra-risk encoder and an enterprise contagion risk encoder, where the enterprise intra-risk encoder models the intra-risk based on enterprise feature information, and the enterprise contagion risk encoder consists of two sub-modules: a hierarchical heterogeneous graph Transformer network and a hierarchical heterogeneous graph feature attention network newly proposed in this paper. These two modules respectively explore contagion risks from the views of different neighbors and different feature dimensions. To fully utilize heterogeneous relationship information, both modules employ hierarchical mechanisms. With these designs, the model proposed in this study can adequately capture the comprehensive credit risk faced by enterprises. Extensive experiments are conducted on the SMEsD bankruptcy prediction dataset and the ECAD enterprise credit assessment dataset, resulting in an improvement of 3.98% and 3.47% in AUC compared with the best baseline model, respectively.

  • Special Issue on Graph Machine Learning
  • Fu Lin , Mingkang Li , Xuexiong Luo , Shuhao Zhang , Yue Zhang , Zitong Wang
    doi: 10.7544/issn1000-1239.202440177

    Graph anomaly detection plays a crucial role in identifying abnormal patterns within complex data structures, and finds applications in various domains such as malicious molecule identification, financial fraud detection, and social network analysis. While existing research in graph anomaly detection predominantly focuses on node-level anomaly detection, there is a scarcity of methods specifically designed for graph-level anomaly detection. Moreover, these methods often fail to adequately explore anomalous graph data, are sensitive to anomaly labels, struggle to capture features of anomalous samples effectively, exhibit poor model generalization, and suffer from performance reversal issues. There is a need for improvement in anomaly detection capabilities. we propose an anomaly-aware variational graph autoencoder based graph-level anomaly detection algorithm (VGAE-D), which utilizes an anomaly-aware variational graph autoencoder to simultaneously extract features from normal and anomalous graph data. This algorithm distinguishes the encoding information of normal and anomalous graphs in the encoding space, further exploring the graph encoding information to compute anomaly scores. Experimental evaluations on eight publicly available datasets from diverse domains demonstrate the effectiveness of the proposed graph-level anomaly detection algorithm. The results indicate that VGAE-D can efficiently identify anomalous graphs in different datasets, outperforming mainstream graph-level anomaly detection methods. Additionally, the algorithm exhibits a capability for learning from few anomalous samples, mitigating the issue of performance inversion to a large extent.

  • Special Issue on Graph Machine Learning
  • Zhi Zeng , Shuqing Zhao , Huan Liu , Xiang Zhao , Minnan Luo
    doi: 10.7544/issn1000-1239.202440136

    Rumor detection with propagation chain remains an important topic in the research of social network analysis. Previous studies mostly oversimplify this task as detecting rumor in propagation chains of comments. However, real-world news posts usually share complex user and event interactions, which can provide potential detection clues. Therefore, we propose an event-driven HyperGraph convolutional network (EHGCN), which makes the first attempt to model news, user and event correlations into a unified hypergraph convolutional network for rumor detection. Specifically, it exploits egocentric network of users to construct homogeneous users circles for enhancing user-aware rumor verification. Moreover, EHGCN jointly leverages the main event and sub-event patterns at the intra-event level for rumor detection. The extensive experimental results show that EHGCN could improve the performance of rumor detection. Studies also confirm that EHGCN can detect rumors at an early stage by acquiring rich user circle and event information.

  • Special Issue on Graph Machine Learning
  • Ping Li , Shuhan Song , Yuan Zhang , Huawei Cao , Xiaochun Ye , Zhimin Tang
    doi: 10.7544/issn1000-1239.202440142

    In recent years, with the extensive application of graph neural network (GNN) technology in the fields such as social network, information, chemistry and biology, the interpretability of GNN has attracted widespread attention. However, prevailing explanation methods fail to capture the hierarchical explanation information, and these hierarchical information has not been fully utilized to improve the classification accuracy of graph tasks. To address this issue, we propose a hierarchical self-explanation graph representation learning model called HSEGRL (hierarchical self-explanation graph representation learning). This model, by discovering hierarchical information in the graph structure, predicts graph classifications while outputting hierarchical self-explanation results. Specifically, we design the basic unit for extracting hierarchical information—interpreters. These interpreters consist of an encoder that extracts node features, a pooling layer that perceives hierarchical explanation-aware subgraphs, and a decoder that refines higher-order explanation information. We refine the pooling mechanism with an explanation-aware strategy, enabling the hierarchical selection of subgraphs based on the evaluation of the model’s topology and feature importance, thereby facilitating hierarchical self-explanation in conjunction with graph classification. HSEGRL is a functionally comprehensive and transferable self-explanatory graph representation learning framework that can hierarchically consider the model’s topological information and node feature information. We conduct extensive experiments on datasets from molecular, protein, and social network, and demonstrate that HSEGRL surpasses existing advanced self-explanatory graph neural network models and graph neural network models in terms of graph classification performance. Furthermore, the visualization of layered explanation outcomes substantiates the credibility of our proposed explanation methodology.

  • Special Issue on Graph Machine Learning
  • Chuanzhen Zhu , Xuan Wang , Qiang Zheng
    doi: 10.7544/issn1000-1239.202440143

    Currently, graph convolutional network (GCN) holds significant potential in processing graph data and other unstructured data. However, GCN faces challenges when dealing with densely connected graphs, as their node-based neighborhood information aggregation mechanism can lead to excessive smoothing, thereby weakening the expressive power of the network graph. The construction of sparse graphs can alleviate the phenomenon of excessive smoothing during the convolution process to some extent, but sparse graphs are prone to information loss and the sparsification process lacks unified standards, affecting the model’s consistency and interpretability. To address this, we propose element separation and holistic attention graph convolutional network framework (EH-GCN). This framework does not require the basis of sparse graphs and can learn the connectivity and node features of densely connected graphs separately. Moreover, it employs a global attention mechanism to integrate connectivity and node features, thus overcoming the limitations of traditional GCN frameworks in handling densely connected graphs and enhancing the feature expression capability of the network graph. We firstly construct fully connected brain networks on three brain imaging datasets: ADNI, ABIDE, and AIBL, verifying the effectiveness of the EH-GCN model in classifying densely connected graphs. Subsequently, the model is tested on the FRANKENSTEIN chemical molecular graph dataset, demonstrating its robust generalization capability. Additionally, the interpretability analysis of the framework aligns with previous neuropathological research, further substantiating the biological basis of the framework.

  • Special Issue on Graph Machine Learning
  • Peiyuan Lai , Cheng Li , Zenghui Wang , Changdong Wang , Dezhang Liao
    doi: 10.7544/issn1000-1239.202440113

    Traffic flow prediction is a crucial foundational aspect in the development of smart cities, holding significant implications for urban traffic management and user travel planning. The expanding dimensions of both time and space contribute to the increasing volume of traffic flow data, with real-time updates presenting a challenge in deploying cost-effective forecasting models to meet diverse traffic prediction demands. Inspired by the success of the emerging paradigm of graph-based finetuning in downstream tasks of natural language processing, we introduce, for the first time to our best knowledge, graph based finetuning to enhance the generalization capabilities of traditional traffic flow prediction models, called TPGPF (traffic flow prediction based on graph prompt-finetuning), which could enhance the generality and effectiveness of self-supervised learning. In the context of spatiotemporal multidimensional traffic flow prediction models, our approach involves pretraining the model based on historical datasets and introducing learnable prompt vectors. With the pretrained model solidified, a self-supervised learning model is guided by the introduced prompt vectors to adapt to new data prediction tasks, thereby enhancing the generality and effectiveness of traffic flow prediction models. Extensive experiments on five real-world public datasets validate the effectiveness of our work, which provides an effective method to overcome the cost challenge brought by quasi real-time training of traffic flow data.

  • Special Issue on Graph Machine Learning
  • Yuanning Cui , Zequn Sun , Wei Hu
    doi: 10.7544/issn1000-1239.202440133

    A knowledge graph (KG) is a structured knowledge base that stores a massive amount of real-world knowledge, providing data support for numerous knowledge-driven downstream tasks. KGs often suffer from incompleteness, with many missing facts. Therefore, the KG reasoning task aims to infer new conclusions based on known facts to complete the KG. With the research and development of knowledge engineering and its commercial applications, numerous general and domain-specific KGs have been constructed. Existing KG reasoning models mostly focus on completing a single KG but lack general reasoning capabilities. Inspired by the general capabilities of pre-trained large language models in recent years, some pre-trained universal KG reasoning models have been proposed. Addressing the issue of existing pre-trained model being unable to identify high-quality reasoning patterns, we introduce a rule-based pre-trained universal KG reasoning model called RulePreM. It discovers and filters high-quality reasoning rules to enhance the reasoning abilities. The proposed model first constructs a relational IO graph based on reasoning rules and uses an encoder, RuleGNN, to encode the relations. The encoded relations are then used as prompts to encode entities in the KG. Finally, candidate entities are scored for prediction. Additionally, an attention mechanism that combines rule confidence is introduced to further reduce the impact of low-quality reasoning patterns. Experimental results demonstrate that the proposed model exhibits universal reasoning abilities on 43 different KGs, with average performance surpassing existing supervised and pre-trained models.

  • Special Issue on Graph Machine Learning
  • Pengfei Jiao , Shuxin Chen , Xuan Guo , Dongxiao He , Dong Liu
    doi: 10.7544/issn1000-1239.202440192

    Graph neural networks (GNNs) are powerful tools for handling graph-structured data, capable of capturing complex relationships and features among nodes. However, the discrete architecture of GNNs leads to numerous challenges in representing graph structures, modeling graph evolution, adapting to irregular data, and managing computational costs. In response to these challenges, neural ordinary differential equations (ODEs) have been introduced as a novel method to address the challenges faced by GNNs, as they can simulate the continuous evolution of system states, providing continuous deep encoding and inference capabilities. However, neural ODEs are designed for Euclidean structured data and cannot directly capture the characteristics of graphs. Therefore, researchers have proposed graph neural ODEs, a new type of architectures that combines neural ODEs with GNNs, which can better adapt to graph-structured data and fully utilize its characteristics. In recent years, research related to graph neural ODEs has delved into various directions of graph machine learning, sparking a new research trend. In this context, we systematically review the relevant research of graph neural ODEs in a timely manner. Firstly, we review the key advantages of GNNs and the challenges they face, and elucidate the theoretical basis and practical significance of introducing neural ODEs and combining them with GNNs. Subsequently, we elaborate on the background and basic concepts of graph neural ODEs, proposing a novel taxonomy, and comprehensively describe some important current methods on the taxonomy. Then, we introduce commonly used verification methods in related research, including downstream tasks and datasets. Furthermore, we delve into the applications of graph neural ODEs in multiple practical fields. Finally, we summarize and prospect the challenges and future development trends of graph neural ODEs.

  • Special Issue on Graph Machine Learning
  • Zhuang Liu , Zichen Dong , Yilin Dong , Jiaming Shang , Fan Zhang , Yuran Chen , Peiyan Lou , Xinran Sun , Yu Wang , Jun Zhao , Lin Wayne
    doi: 10.7544/issn1000-1239.202440204

    Lifelong Graph Learning (LGL) is an emerging field aimed at achieving continuous learning on graph-structured data, addressing the catastrophic forgetting issue in existing tasks and enabling models to adapt to newly emerging graph tasks in a sequential manner. Despite demonstrating strong learning capabilities, improving LGL's sustained performance remains a crucial challenge. To address the gaps in existing research, we provide a comprehensive survey and summary of recent developments in the field of LGL. Firstly, we reclassify existing methods of LGL, focusing particularly on approaches to overcome catastrophic forgetting. Secondly, we systematically analyze the strengths and weaknesses of these methods, and discuss potential solutions for achieving sustained performance improvements. Our study emphasizes on how to avoid forgetting old tasks during the continual learning process while swiftly adapting to the challenges of new tasks. Finally, we also discuss the future directions of LGL, covering potential impacts in the application domains, open issues, and specifically analyze their potential effects on sustained performance improvements. These discussions will help guide future research directions in LGL, promoting further development and application in this field.

  • Information Security
  • Chuang Wang , Yan Ding , Chenlin Huang , Liantao Song
    doi: 10.7544/issn1000-1239.202220531

    SM4 algorithm is a commercial block cipher algorithm independently designed by China, and its encryption and decryption performance has become one of the critical factors affecting the data confidentiality of the information system. The existing optimizations mainly focus on hardware designs and software look-up tables, which have problems such as dependence on specific hardware environments, low efficiency, and vulnerability to side-channel attacks. Bit slicing technology efficiently processes block ciphers in parallel by reorganizing input data, and can resist side-channel attacks against caches. However, the existing researches on bitsliced block ciphers are highly dependent on the hardware platforms and only support a single processor architecture, and the parallel processing pipeline starts slowly. It is difficult for the encryption and decryption operations for small-scale data to give full play to the advantages of advanced instruction sets such as SIMD (single instruction multiple data) instructions. To resolve the above problems, we firstly propose a cross-platform general bitsliced block cipher algorithm model, which supports a general data slicing method that provides consistent data slicing for different processor instructions. Based on that, a fine-grained bitsliced SM4 optimization algorithm for SIMD instructions is proposed, which can effectively shorten the startup time of the algorithm through fine-grained plaintext slicing reorganization and linear transformation optimization. The experiments show that, compared with the look-up table-based SM4 algorithm, the encryption rate can reach up to 438.0 MBps. The clock cycles required for encrypting a byte are up to 7.0 CPB (cycle/B), and the encryption performance is improved by an average of 80.4% to 430.3%.

  • Information Security
  • Haibo Wu , Hui Liu , Yi Sun , Jun Li
    doi: 10.7544/issn1000-1239.202220644

    With the prevalence of blockchain technology, Hyperledger Fabric (Fabric for short), as a well-known open source blockchain platform, has received wide attention. However, Fabric still suffers from conflicts between concurrent transactions. Conflicts will cause a large number of invalid transactions entering the chain, resulting in a decrease in throughput and hindering its development. For this problem, existing intra-block-conflict-oriented schemes lack efficient conflict detection and avoidance methods, and ignore the adverse impact of inter-block conflicts on throughput. We propose an optimization scheme for Fabric, Fabric-HT (Fabric with high throughput), from both intra-block and inter-block aspects to effectively reduce concurrency inter-transaction conflicts and improve system throughput. For intra-block transaction conflicts, we present a transaction scheduling mechanism, in which an efficient data structure (the dependency chain) is defined to identify and abort transactions with “dangerous structures” in advance, reasonably schedule transactions and eliminate conflicts; for inter-block transaction conflicts, the conflict transaction detection is moved to the sorting node to complete, and an early conflict transaction avoidance mechanism following “push-match” pattern is established. A large number of experiments are carried out in multiple scenarios, and the results show that Fabric-HT overperforms existing schemes in terms of throughput, transaction abort rate, average transaction execution time, and invalid transaction space occupancy. The results show that the throughput of Fabric-HT can reach up to 9.51x that of Fabric and 1.18x of the latest optimized scheme FabricSharp; compared with FabricSharp, the space utilization is increased by 14%. In addition, Fabric-HT also shows good robustness and anti-attack ability in solving concurrent transaction conflict.