Earticle

It is obvious that IoT devices are widely used more and more in many areas. However, due to limited resources (e.g., memory, CPU), the security mechanisms on many IoT devices such as IP-Camera, router are low. Therefore, botnets are an emerging threat to compromise IoT devices recently. To tackle this, a novel method for IoT botnets detection plays a crucial role. In this paper, we have some contributions for IoT botnet detection: first, we present a novel high-level PSI-rooted subgraph-based feature for the detection of IoT botnets; second, we generate a limited number of features that have precise behavioral descriptions, which require smaller space and reduce processing time; third, The evaluation results show the effectiveness and robustness of PSI-rooted subgraph-based features, as with five machine classifiers consisting of Random Forest, Decision Tree, Bagging, k-Nearest Neighbor, and Support Vector Machine, each classifier achieves more than 97% detection rate and low time-consuming. Moreover, compared to other work, our proposed method obtains better performance. Finally, we publicize all our materials on Github, which will benefit future research (e.g., IoT botnet detection approach).

After constructing graph representations for a set of web documents, there are several techniques to determine the similarity between same-type objects. This is achieved by graph matching. The measure of similarity may be based on the size of the maximum common subgraph. In this paper, we are interested in the problem of maximum common subgraph(MCS) and median graph computation for the purpose of graph clustering using backtracking search. Median of a graph helps in the extension of prevalent term frequency based clustering algorithms to graph based clustering.

The traditional PageRank algorithm can’t efficiently dispose large data Webpage scheduling problem. This paper proposes an accelerated algorithm named topK-Rank .It is based on PageRank on the MapReduce platform. Owing to this algorithm ,Top k nodes can be found efficiently for a given graph without sacrificing accuracy. It can iteratively estimate lower/upper bounds of PageRank scores, and construct subgraphs in each iteration by pruning unnecessary nodes and edges. Theoretical analysis shows that this method guarantees result exactness. Experiments show that it can find top k nodes much faster than the existing approaches.

Design Pattern Detection is a part of many solutions to Software Engineering difficulties. The usage of design patterns leads to benefits for new and young developers by enabling them to reuse the knowledge of their experienced colleagues. Mining of design pattern instances is important for program understanding and software maintenance. Hence a reliable design pattern mining is required. Here we are using the relational view of subgraph isomorphism to detect design patterns in the source code.

To lower the mapping complexity of designing analog decoders, a method to optimize the design of low-density parity-check (LDPC) analog decoders is proposed in this paper. Based on factor graphs and the sum-product algorithm, the LDPC decoding process on the factor graph and the construction of analog decoders are exploited. Then the frequent subgraph mining algorithm is introduced to search the isomorphic subgraphs in factor graphs. According to the output of the frequent subgraph mining algorithm which enumerates all the subgraphs in factor graphs, the mapping complexity of a LDPC analog decoder can be significantly reduced. Finally, a (40, 16) LDPC analog decoder is constructed using the proposed method. Simulation results show that the need to place gates and connections can be reduced 90% and 23%, respectively, and the ideal performance is obtained by carefully choosing unit currents and decoding time.

G = (V, E) 를 그래프라 하자. Maximum Bipartite Subgraph 문제는 주어진 그래프 G로부터 최소 개수의 간선을 제거함으로써 G 를 이분그래프로 변환시키는 문제이며 결합 최적화 문제들 중 대표적인 문제들 중의 하나로 알려 져 있다. 본 문제는 NP-complete 계열에 포함되는 문제로서 본 연구에서는 Tabu Search 및 GRASP 등을 조합한 새로운 메타휴리스틱 알고리즘을 제시하고자 한다.

Let G = (V, E) be a graph. Maximum Bipartite Subgraph Problem is to convert a graph G into a bipartite graph by removing minimum number of edges. This problem belongs to NP-complete; hence, in this research, we are suggesting a new metaheuristic algorithm which combines Tabu search and GRASP.

In real-world graphs like social networks, linguistics net and biological networks, every vertex typically contains wealthy info, which might be shapely by a group of tokens or parts. during this paper, we have a tendency to study a subgraph matching with set similarity (SMS2) question over an outsized graph information, that retrieves subgraphs that ar structurally isomorphous to the question graph, and in the meantime satisfy the condition of vertex try matching with the (dynamic) weighted set similarity. To with efficiency method the SMS2 question, this paper styles a unique lattice-based index for knowledge graph, and light-weight signatures for each question vertices and knowledge vertices. supported the index and signatures, we have a tendency to propose associate economical two-phase pruning strategy as well as set similarity pruning and structure-based pruning, that exploits the distinctive options of each (dynamic) weighted set similarity and graph topology. we have a tendency to conjointly propose associate economical dominating-set-based subgraph matching formula radio-controlled by a dominating set choice formula to realize higher question performance. in depth experiments on each real and artificial datasets demonstrate that our technique outperforms progressive strategies by associate order of magnitude.

In this paper, we will investigate the concept of the torsion-graph of an R-module M, in which the set $T(M)^*$ makes up the vertices of the corresponding torsion graph, ${\Gamma}(M)$, with any two distinct vertices forming an edge if $[x:M][y:M]M=0$. We prove that, if ${\Gamma}(M)$ contains a cycle, then $gr({\Gamma}(M)){\leq}4$ and ${\Gamma}(M)$ has a connected induced subgraph ${\overline{\Gamma}}(M)$ with vertex set $\{m{\in}T(M)^*{\mid}Ann(m)M{\neq}0\}$ and diam$({\overline{\Gamma}}(M)){\leq}3$. Moreover, if M is a multiplication R-module, then ${\overline{\Gamma}}(M)$ is a maximal connected subgraph of ${\Gamma}(M)$. Also ${\overline{\Gamma}}(M)$ and ${\overline{\Gamma}}(S^{-1}M)$ are isomorphic graphs, where $S=R{\backslash}Z(M)$. Furthermore, we show that, if ${\overline{\Gamma}}(M)$ is uniquely complemented, then $S^{-1}M$ is a von Neumann regular module or ${\overline{\Gamma}}(M)$ is a star graph.

In this paper, we consider a class of inhomogeneous random intersection graphs by assigning random weight to each vertex and two vertices are adjacent if they choose some common elements. In the inhomogeneous random intersection graph model, vertices with larger weights are more likely to acquire many elements. We show the Poisson convergence of the number of induced copies of a fixed subgraph as the number of vertices n and the number of elements m, scaling as $m={\lfloor}{\beta}n^{\alpha}{\rfloor}$ (${\alpha},{\beta}>0$), tend to infinity.

The goal of data mining is to extract new and useful knowledge from large scale datasets. As the amount of available data grows explosively, it became vitally important to develop faster data mining algorithms for various types of data. Recently, an interest in developing data mining algorithms that operate on graphs has been increased. Especially, mining frequent patterns from structured data such as graphs has been concerned by many research groups. A graph is a highly adaptable representation scheme that used in many domains including chemistry, bioinformatics and physics. For example, the chemical structure of a given substance can be modelled by an undirected labelled graph in which each node corresponds to an atom and each edge corresponds to a chemical bond between atoms. Internet can also be modelled as a directed graph in which each node corresponds to an web site and each edge corresponds to a hypertext link between web sites. Notably in bioinformatics area, various kinds of newly discovered data such as gene regulation networks or protein interaction networks could be modelled as graphs. There have been a number of attempts to find useful knowledge from these graph structured data. One of the most powerful analysis tool for graph structured data is frequent subgraph analysis. Recurring patterns in graph data can provide incomparable insights into that graph data. However, to find recurring subgraphs is extremely expensive in computational side. At the core of the problem, there are two computationally challenging problems. 1) Subgraph isomorphism and 2) Enumeration of subgraphs. Problems related to the former are subgraph isomorphism problem (Is graph A contains graph B?) and graph isomorphism problem(Are two graphs A and B the same or not?). Even these simplified versions of the subgraph mining problem are known to be NP-complete or Polymorphism-complete and no polynomial time algorithm has been existed so far. The later is also a difficult problem. We should generate all of 2$^n$ subgraphs if there is no constraint where n is the number of vertices of the input graph. In order to find frequent subgraphs from larger graph database, it is essential to give appropriate constraint to the subgraphs to find. Most of the current approaches are focus on the frequencies of a subgraph: the higher the frequency of a graph is, the more attentions should be given to that graph. Recently, several algorithms which use level by level approaches to find frequent subgraphs have been developed. Some of the recently emerging applications suggest that other constraints such as connectivity also could be useful in mining subgraphs : more strongly connected parts of a graph are more informative. If we restrict the set of subgraphs to mine to more strongly connected parts, its computational complexity could be decreased significantly. In this paper, we present an efficient algorithm to mine frequent subgraphs that are more strongly connected. Experimental study shows that the algorithm is scaling to larger graphs which have more than ten thousand vertices.

본 논문에서는 대규모 데이터베이스 그래프에서 주어진 질의 그래프와 동형인 모든 부분그래프들을 찾는 부분그래프 문제를 다룬다. 최근 빠른 부분그래프 매칭을 위해서 특징 인덱스를 기반으로 하는 기법들이 제안되었다. 이 기법들은 데이터베이스 그래프 정점들과 질의 그래프 정점들을 정점 특징을 사용하여 비교한 후 부분그래프 매칭 작업에서 고려할 필요가 없는 데이터베이스 그래프 상의 정점들을 걸러냄으로써 부분그래프 매칭 비용을 줄인다. 기존 기법들에서는 라벨 분포와 부분구조를 정점 특징으로 사용한다. 하지만 가지치기 능력과 추출비용 사이의 교환 비용을 적절히 고려하지 않았다. 본 논문에서는 빠른 부분그래프 매칭을 위한 F-Index라고 부르는 특징 인덱스를 제안한다. F-Index는 정점 특징의 가지치기 능력과 추출비용 사이의 균형을 고려한다. 제안하는 기법에서는 라벨 분포와 함께 정점 주변의 연결정보를 정점 특징으로 사용한다. 데이터베이스 그래프 상에서 적합하지 않은 정점들을 빠르게 걸러내기 위해 정점 특징을 추출한 후 인덱스를 구축한다. 본 논문에서는 다양한 실험을 통해 제안하는 기법이 기존 기법들에 비해서 질의 처리 시간과 인덱스 생성 시간 측면에서 우수함을 보인다.

In this paper, we study the subgraph matching problem in a large database graph, which finds all subgraphs in the database graph that are isomorphic to a query graph. Recently, feature index-based methods have been proposed for fast subgraph matching in a large database graph. They adopt the concept of vertex features to easily compare the vertices from a database graph with those from a query graph and filter out vertices in the database graph not eligible for subgraph matching. Previous approaches use various kinds of vertex features such as label distribution and discriminative substructures. However, they do not carefully consider the tradeoff between pruning power and extraction cost of vertex features. In this paper we propose a feature index called F-Index for fast subgraph matching. F-Index strikes a balance between pruning power and extraction cost. It uses the combination of label distribution and connectivity information of neighbors as vertex features. F-Index is constructed over the extracted vertex features for fast filtering of unqualified vertices. Experimental results show that our method outperforms the existing methods in terms of query processing time with comparable index build time.

A graph G is called to be a 2-degree integral subgraph of a q-tree if it is obtained by deleting an edge e from an integral subgraph that is contained in exactly q - 1 triangles. An added-vertex q-tree G with n vertices is obtained by taking two vertices u, v (u, v are not adjacent) in a q-trees T with n - 1 vertices such that their intersection of neighborhoods of u, v forms a complete graph $K_{q}$, and adding a new vertex x, new edges xu, xv, $xv_{1},\;xv_{2},\;{\cdots},\;xv_{q-4}$, where $\{v_{1},\;v_{2},\;{\cdots},\;v_{q-4}\}\;{\subseteq}\;K_{q}$. In this paper we prove that a graph G with minimum degree not equal to q - 3 and chromatic polynomial $$P(G;{\lambda})\;=\;{\lambda}({\lambda}-1)\;{\cdots}\;({\lambda}-q+2)({\lambda}-q+1)^{3}({\lambda}-q)^{n-q-2}$$ with $n\;{\geq}\;q+2$ has and only has 2-degree integral subgraph of q-tree with n vertices and added-vertex q-tree with n vertices.

본 논문에서는 GraphRAG의 다중 홉(multi-hop) 질의응답 성능 향상을 위해, LLM 에이전트가 지식 그래프를 자율적으로 확장하며 답변에 필요한 정보를 수집하는 에이전트 기반 서브그래프 탐색 기법을 제안한다. 구체적으로, 현재 서브그래프를 바탕으로 답변을 생성하거나 정보 부족을 반환하는 답변 에이전트와, 후보 노드 중 탐색할 노드를 선택하여 서브그래프를 확장하는 확장 에이전트를 설계하여 적용하였다. 그러나 본 실험에서 확장 에이전트에게 후보 필터링 없이 모든 후보를 전달한 결과, 쿼리당 평균 21,849개의 프롬프트 토큰이 소비되어 효율성 측면에서 한계가 확인되었다. 이를 해결하기 위해 쿼리와 노드 임베딩 간의 의미적 유사도와 쿼리와 연결 엣지 임베딩 간의 관계 유사도를 가중 합산하여 후보 노드들의 점수를 산출하고, 상위 k개만을 확장 에이전트에게 전달하는 후보 필터링 방법을 추가로 제안한다. HotpotQA 실험에서 제안 방법은 필터링 없는 확장 에이전트(F1 0.414) 대비 프롬프트 토큰을 4.5배 절감하면서 (4,858 vs. 21,849 토큰) F1 0.416, Exact Match 0.314를 달성하였다.

To improve the multi-hop question-answering performance of GraphRAG, this paper proposes an agent-based subgraph exploration technique in which LLM agents autonomously navigate a knowledge graph to retrieve query-relevant information.. Specifically, we designed a dual-agent architecture consisting of an Answer Agent, which generates responses or identifies information gaps based on the current subgraph, and an Expansion Agent, which selects the most relevant nodes from a pool of candidates to extend the subgraph. Our preliminary experiments revealed a significant efficiency bottleneck: providing all candidate nodes to the Expansion Agent without filtering resulted in an average consumption of 21,849 prompt tokens per query. To address this, we introduce a candidate filtering method that scores candidates by weight-averaging the semantic similarity of node embeddings and the relational similarity of edge embeddings, passing only the top-k candidates to the Expansion Agent. In evaluations using the HotpotQA dataset, the proposed method achieved an F1 score of 0.416 and an Exact Match of 0.314, while reducing prompt token consumption by approximately 4.5 times (4,858 vs. 21,849 tokens) compared to the unfiltered baseline (F1 0.414).

지식 그래프 및 단백질 상호 작용과 같은 실제 데이터에서 개체들과 개체들의 관계 및 구조를 나타내기 위해 레이블 그래프를 사용한다. IT의 급속한 발전과 데이터의 폭발적인 증가로 사용자에게 관심 있는 정보를 제공하기 위한 서브 그래프 매칭 기술이 필요하다. 본 논문은 레이블의 의미적 유사성과 그래프 구조 차이를 고려한 근사 Top-k 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 레이블 의미적 유사도를 고려하기 위하여 FastText을 활용한 학습 모델을 이용한다. 레이블 간 의미적 유사도를 미리 계산한 LSG(Label Similarity Graph)를 통해 처리 속도의 효율을 높인다. LSG를 통해 레이블이 정확하게 일치해야 확장이 가능한 기존 연구의 한계를 해결한다. 2-hop까지 탐색을 수행함으로써 질의 그래프에 대한 구조적 유사성을 지원한다. 매칭된 서브 그래프는 유사도 값 기반으로 Top-k 결과를 제공한다. 제안하는 기법의 우수성을 보이기 위하여 다양한 성능평가를 수행한다.

Labeled graphs are used to represent entities, their relationships, and their structures in real data such as knowledge graphs and protein interactions. With the rapid development of IT and the explosive increase in data, there has been a need for a subgraph matching technology to provide information that the user is interested in. In this paper, we propose an approximate Top-k labeled subgraph matching scheme that considers the semantic similarity of labels and the difference in graph structure. The proposed scheme utilizes a learning model using FastText in order to consider the semantic similarity of a label. In addition, the label similarity graph(LSG) is used for approximate subgraph matching by calculating similarity values between labels in advance. Through the LSG, we can resolve the limitations of the existing schemes that subgraph expansion is possible only if the labels match exactly. It supports structural similarity for a query graph by performing searches up to 2-hop. Based on the similarity value, we provide k subgraph matching results. We conduct various performance evaluations in order to show the superiority of the proposed scheme.

최근 빅데이터를 비롯한 각종 실험 장비의 발전에 따라 첨단 분야에서의 과학데이터가 급격히 증가하고 있는 가운데, 그래프 매칭은 컴퓨터 네트워크 모니터링, 소셜 네트워크의 진화 분석, 생물학 네트워크에서 모티프(motif) 탐지 등 네트워크 분석 및 데이터 마이닝 분야에서 널리 활용되고 있다. 이와 같이, 폭발적으로 증가하는 데이터에 대한 네트워크 모델링 및 유사 그래프 매칭 분석을 수행하기 위한 연구 및 기반 기술 개발은 필수적인 실정이다. 본 논문에서는 이미 확보된 대용량 그래프에서 유사한 형태의 서브 그래프를 매칭할 수 있는 GUI(Graphic User Interface)기반의 생성 도구를 제안한다.

본 논문은 주어진 두 주행로 의미정보간 부분그래프 매칭(subgraph matching)을 이용한 맵매칭 방법을 제안한다. 지도 주행로의 의미정보를 선택하여 그래프로 재구성하는 방법을 제시하고 재구성된 지도 그래프에서 부분그래프 매칭을 통한 두 지도간 맵매칭 방법을 제안한다. 실제 지도를 이용한 모의실험을 통해 제안한 방법을 검증한다.