基于GraphSAGE网络的藏文短文本分类研究

文本分类是自然语言处理领域的重要研究方向,由于藏文数据的稀缺性、语言学特征抽取的复杂性、篇章结构的多样性等因素导致藏文文本分类任务进展缓慢。因此,该文以图神经作为基础模型进行改进。首先,在“音节-音节”“音节-文档”建模的基础上,融合文档特征,采用二元分类模型动态网络构建“文档-文档”边,以充分挖掘短文本的全局特征,增加滑动窗口,减少模型的计算复杂度并寻找最优窗口取值。其次,针对藏文短文本的音节稀疏性,首次引入GraphSAGE作为基础模型,并探究不同聚合方式在藏文短文本分类上的性能差异。最后,为捕获节点间关系的异质性,对邻居节点进行特征加权再平均池化以增强模型的特征提取能力。在TNCC标题文本数据集上,该文模型的分类准确率达到了62.50%,与传统GCN、原始GraphSAGE和预训练语言模型CINO相比,该方法在分类准确率上分别提高了2.56%、1%和2.4%。

A STABILITY RESULT FOR TRANSLATINGSPACELIKE GRAPHS IN LORENTZ MANIFOLDS

In this paper,we investigate spacelike graphs defined over a domain Ω⊂M^(n) in the Lorentz manifold M^(n)×ℝ with the metric−ds^(2)+σ,where M^(n) is a complete Riemannian n-manifold with the metricσ,Ωhas piecewise smooth boundary,and ℝ denotes the Euclidean 1-space.We prove an interesting stability result for translating spacelike graphs in M^(n)×ℝ under a conformal transformation.

A Value for Games Defined on Graphs

Given a graph g=( V,A ) , we define a space of subgraphs M with the binary operation of union and the unique decomposition property into blocks. This space allows us to discuss a notion of minimal subgraphs (minimal coalitions) that are of interest for the game. Additionally, a partition of the game is defined in terms of the gain of each block, and subsequently, a solution to the game is defined based on distributing to each player (node and edge) present in each block a payment proportional to their contribution to the coalition.

BLOW-UP CONDITIONS FOR A SEMILINEAR PARABOLIC SYSTEM ON LOCALLY FINITE GRAPHS

In this paper, we investigate a blow-up phenomenon for a semilinear parabolic system on locally finite graphs. Under some appropriate assumptions on the curvature condition CDE’(n,0), the polynomial volume growth of degree m, the initial values, and the exponents in absorption terms, we prove that every non-negative solution of the semilinear parabolic system blows up in a finite time. Our current work extends the results achieved by Lin and Wu (Calc Var Partial Differ Equ, 2017, 56: Art 102) and Wu (Rev R Acad Cien Serie A Mat, 2021, 115: Art 133).

Perfect 1-k Matchings of Bipartite Graphs

Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

Algorithm for Visualization of Zero Divisor Graphs of the Ring ℤn Using MAPLE Coding

This research investigates the comparative efficacy of generating zero divisor graphs (ZDGs) of the ring of integers ℤn modulo n using MAPLE algorithm. Zero divisor graphs, pivotal in the study of ring theory, depict relationships between elements of a ring that multiply to zero. The paper explores the development and implementation of algorithms in MAPLE for constructing these ZDGs. The comparative study aims to discern the strengths, limitations, and computational efficiency of different MAPLE algorithms for creating zero divisor graphs offering insights for mathematicians, researchers, and computational enthusiasts involved in ring theory and mathematical computations.

Depth First:Optimal Path Discovery Between Designated Nodes in Random Ring-Based Graphs

This paper focuses on optimally determining the existence of connected paths between some given nodes in random ring-based graphs.Serving as a fundamental underlying structure in network modeling,ring topology appears as commonplace in many realistic scenarios.Regarding this,we consider graphs composed of rings,with some possible connected paths between them.Without prior knowledge of the exact node permutations on rings,the existence of each edge can be unraveled through edge testing at a unit cost in one step.The problem examined is that of determining whether the given nodes are connected by a path or separated by a cut,with the minimum expected costs involved.Dividing the problem into different cases based on different topologies of the ring-based networks,we propose the corresponding policies that aim to quickly seek the paths between nodes.A common feature shared by all those policies is that we stick to going in the same direction during edge searching,with edge testing in each step only involving the test between the source and the node that has been tested most.The simple searching rule,interestingly,can be interpreted as a delightful property stemming from the neat structure of ring-based networks,which makes the searching process not rely on any sophisticated behaviors.We prove the optimality of the proposed policies by calculating the expected cost incurred and making a comparison with the other class of strategies.The effectiveness of the proposed policies is also verified through extensive simulations,from which we even disclose three extra intriguing findings:i)in a onering network,the cost will grow drastically with the number of designated nodes when the number is small and will grow slightly when that number is large;ii)in ring-based network,Depth First is optimal in detecting the connectivity between designated nodes;iii)the problem of multi-ring networks shares large similarity with that of two-ring networks,and a larger number of ties between rings will not influence the expected cost.

Batch Active Learning for Multispectral and Hyperspectral Image Segmentation Using Similarity Graphs

Graph learning,when used as a semi-supervised learning(SSL)method,performs well for classification tasks with a low label rate.We provide a graph-based batch active learning pipeline for pixel/patch neighborhood multi-or hyperspectral image segmentation.Our batch active learning approach selects a collection of unlabeled pixels that satisfy a graph local maximum constraint for the active learning acquisition function that determines the relative importance of each pixel to the classification.This work builds on recent advances in the design of novel active learning acquisition functions(e.g.,the Model Change approach in arXiv:2110.07739)while adding important further developments including patch-neighborhood image analysis and batch active learning methods to further increase the accuracy and greatly increase the computational efficiency of these methods.In addition to improvements in the accuracy,our approach can greatly reduce the number of labeled pixels needed to achieve the same level of the accuracy based on randomly selected labeled pixels.

GraphSTGAN:Situation understanding network of slow-fast high maneuvering targets for maritime monitor services of IoT data

With the rapid growth of the maritime Internet of Things(IoT)devices for Maritime Monitor Services(MMS),maritime traffic controllers could not handle a massive amount of data in time.For unmanned MMS,one of the key technologies is situation understanding.However,the presence of slow-fast high maneuvering targets and track breakages due to radar blind zones make modeling the dynamics of marine multi-agents difficult,and pose significant challenges to maritime situation understanding.In order to comprehend the situation accurately and thus offer unmanned MMS,it is crucial to model the complex dynamics of multi-agents using IoT big data.Nevertheless,previous methods typically rely on complex assumptions,are plagued by unstructured data,and disregard the interactions between multiple agents and the spatial-temporal correlations.A deep learning model,Graph Spatial-Temporal Generative Adversarial Network(GraphSTGAN),is proposed in this paper,which uses graph neural network to model unstructured data and uses STGAN to learn the spatial-temporal dependencies and interactions.Extensive experiments show the effectiveness and robustness of the proposed method.

On an Invariant of Tournament Digraphs

To date, it is unknown whether it is possible to construct a complete graph invariant in polynomial time, so fast algorithms for checking non-isomorphism are important, including heuristic algorithms, and for successful implementations of such heuristics, both the tasks of some modification of previously described graph invariants and the description of new invariants remain relevant. Many of the described invariants make it possible to distinguish a larger number of graphs in the real time of a computer program. In this paper, we propose an invariant for a special kind of directed graphs, namely, for tournaments. The last ones, from our point of view, are interesting because when fixing the order of vertices, the number of different tournaments is exactly equal to the number of undirected graphs, also with fixing the order of vertices. In the invariant we are considering, all possible tournaments consisting of a subset of vertices of a given digraph with the same set of arcs are iterated over. For such subset tournaments, the places are calculated in the usual way, which are summed up to obtain the final values of the points of the vertices;these points form the proposed invariant. As we expected, calculations of the new invariant showed that it does not coincide with the most natural invariant for tournaments, in which the number of points is calculated for each participant. So far, we have conducted a small number of computational experiments, and the minimum value of the pair correlation between the sequences representing these two invariants that we found is for dimension 15.

Maximal Resonance of{(3,4),4}-Fullerene Graphs

A{(3,4),4}-fullerene graph S is a 4-regular map on the sphere whose faces are of length 3 or 4.It follows from Euler s formula that the number of triangular faces is eight.A set H of disjoint quadrangular faces of S is called resonant pattern if S has a perfect matching M such that every quadrangular face in H is M-alternating.Let k be a positive integer,S is k-resonant if any i≤k disjoint quadrangular faces of S form a resonant pattern.Moreover,if graph S is k-resonant for any integer k,then S is called maximally resonant.In this paper,we show that the maximally resonant{(3,4),4}-fullerene graphs are S_6,S_8,S_(10)^(2),S_(12)^(2),S_(12)^(4),S_(12)^(5),S_(14)^(3),S_(14)^(5),S_(16)^(3),S_(18)^(5),S_(24)as shown in Fig.1.As a corollary,it is shown that if a{(3,4),4}-fullerene graph is 4-resonant,then it is also maximally resonant.

Independence Polynomials and the Merrifield-Simmons Index of Mono-Layer Cylindrical Grid Graphs

Research on the independence polynomial of graphs has been very active.However,the computational complexity of determining independence polynomials for general graphs remains NP-hard.Letα(G)be the independence number of G and i(G;k)be the number of independent sets of order k in G,then the independence polynomial is defined as I(G;x)=∑_(k=0)^(α(G))i(G;k)x^(k),i(G;0)=1.In this paper,by utilizing the transfer matrix,we obtain an analytical expression for I(CGn;x)of mono-cylindrical grid graphs CGn and present a crucial proof of it.Moreover,we also explore the Merrifield-Simmons index and other properties of CGn.

Weak External Bisection of Some Graphs

Let G be a graph. A bipartition of G is a bipartition of V (G) with V (G) = V1 ∪ V2 and V1 ∩ V2 = ∅. If a bipartition satisfies ∥V1∣ - ∣V2∥ ≤ 1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott. The conjecture is that every graph G has a bisection (V1, V2) such that ∀v ∈ V1, at least half minuses one of the neighbors of v are in the V2;∀v ∈ V2, at least half minuses one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.

Privacy Preserving Distributed Bandit Residual Feedback Online Optimization Over Time-Varying Unbalanced Graphs

This paper considers the distributed online optimization(DOO) problem over time-varying unbalanced networks, where gradient information is explicitly unknown. To address this issue, a privacy-preserving distributed online one-point residual feedback(OPRF) optimization algorithm is proposed. This algorithm updates decision variables by leveraging one-point residual feedback to estimate the true gradient information. It can achieve the same performance as the two-point feedback scheme while only requiring a single function value query per iteration. Additionally, it effectively eliminates the effect of time-varying unbalanced graphs by dynamically constructing row stochastic matrices. Furthermore, compared to other distributed optimization algorithms that only consider explicitly unknown cost functions, this paper also addresses the issue of privacy information leakage of nodes. Theoretical analysis demonstrate that the method attains sublinear regret while protecting the privacy information of agents. Finally, numerical experiments on distributed collaborative localization problem and federated learning confirm the effectiveness of the algorithm.

2-Factors with a Few Components in Balanced Bipartite Graphs

In this paper, a sufficient condition for a balanced bipartite graph to contain a 2-factor F is given. We show that every balanced bipartite graph of order 2n (n≥6)and e(G)>n2−2n+4contains a 2-factor with k components, 2d1-cycle, ⋯, 2dk-cycle, if one of the following is satisfied: (1) k=2, δ(G)≥2and d1−2≥d2≥2;(2) k=3, δ(G)≥d3+2and d1−2≥d2≥d3≥4. In particular, this extends one result of Moon and Moser in 1963 under condition (1).

On the (Δ + 2)-Total-Colorability of Planar Graphs with 7-Cycles Containing at Most Two Chords

The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.

On the Degree Resistance Distance of Unicyclic Graphs

Let Gbe a connected graph with vertex set V(G). Then the degree resistance distance of Gis defined as DR(G)=∑{ u,v }⊆V(G)(d(u)+d(v))R(u,v), where d(u)is the degree of the vertex u, and R(u,v)is the degree resistance distance between uand vin graph G. A unicyclic graph is a connected graph with a unique cycle. In this paper, we characterize the unique graph with the third-maximum degree resistance distance among all unicyclic graphs with nvertices.

Dynamic Multi-Graph Spatio-Temporal Graph Traffic Flow Prediction in Bangkok:An Application of a Continuous Convolutional Neural Network

The ability to accurately predict urban traffic flows is crucial for optimising city operations.Consequently,various methods for forecasting urban traffic have been developed,focusing on analysing historical data to understand complex mobility patterns.Deep learning techniques,such as graph neural networks(GNNs),are popular for their ability to capture spatio-temporal dependencies.However,these models often become overly complex due to the large number of hyper-parameters involved.In this study,we introduce Dynamic Multi-Graph Spatial-Temporal Graph Neural Ordinary Differential Equation Networks(DMST-GNODE),a framework based on ordinary differential equations(ODEs)that autonomously discovers effective spatial-temporal graph neural network(STGNN)architectures for traffic prediction tasks.The comparative analysis of DMST-GNODE and baseline models indicates that DMST-GNODE model demonstrates superior performance across multiple datasets,consistently achieving the lowest Root Mean Square Error(RMSE)and Mean Absolute Error(MAE)values,alongside the highest accuracy.On the BKK(Bangkok)dataset,it outperformed other models with an RMSE of 3.3165 and an accuracy of 0.9367 for a 20-min interval,maintaining this trend across 40 and 60 min.Similarly,on the PeMS08 dataset,DMST-GNODE achieved the best performance with an RMSE of 19.4863 and an accuracy of 0.9377 at 20 min,demonstrating its effectiveness over longer periods.The Los_Loop dataset results further emphasise this model’s advantage,with an RMSE of 3.3422 and an accuracy of 0.7643 at 20 min,consistently maintaining superiority across all time intervals.These numerical highlights indicate that DMST-GNODE not only outperforms baseline models but also achieves higher accuracy and lower errors across different time intervals and datasets.

Automated knowledge graphs for complex systems (AutoGraCS): Applications to management of bridge networks

With the ability to harness the power of big data,the digital twin(DT)technology has been increasingly applied to the modeling and management of structures and infrastructure systems,such as buildings,bridges,and power distribution systems.Supporting these applications,an important family of methods are based on graphs.For DT applications in modeling and managing smart cities,large-scale knowledge graphs(KGs)are necessary to represent the complex interdependencies and model the urban infrastructure as a system of systems.To this end,this paper develops a conceptual framework:Automated knowledge Graphs for Complex Systems(AutoGraCS).In contrast to existing KGs developed for DTs,AutoGraCS can support KGs to account for interdependencies and statistical correlations across complex systems.The established KGs from AutoGraCS can then be easily turned into Bayesian networks for probabilistic modeling,Bayesian analysis,and adaptive decision supports.Besides,AutoGraCS provides flexibility in support of users’need to implement the ontology and rules when constructing the KG.With the user-defined ontology and rules,AutoGraCS can automatically generate a KG to represent a complex system consisting of multiple systems.The bridge network in Miami-Dade County,FL is used as an illustrative example to generate a KG that integrates multiple layers of data from the bridge network,traffic monitoring facilities,and flood water watch stations.

基于改进GraphSAGE算法的浏览器指纹追踪

当前Web追踪领域主要使用浏览器指纹对用户进行追踪。针对浏览器指纹追踪技术存在指纹随时间动态变化、不易长期追踪等问题,提出一种关注节点和边缘特征的改进图采样聚合算法(An Improved Graph SAmple and AGgregatE with Both Node and Edge Features,NE-GraphSAGE)用于浏览器指纹追踪。首先以浏览器指纹为节点、指纹之间特征相似度为边构建图数据。其次对图神经网络中的GraphSAGE算法进行改进使其不仅能关注节点特征,而且能捕获边缘信息并对边缘分类,从而识别指纹。最后将NE-GraphSAGE算法与Eckersley算法、FPStalker算法和LSTM算法进行对比,验证NE-GraphSAGE算法的识别效果。实验结果表明,NE-GraphSAGE算法在准确率和追踪时长上均有不同程度的提升,最大追踪时长可达80天,相比其他3种算法性能更优,验证了NE-GraphSAGE算法对浏览器指纹长期追踪的能力。