利益相反取引をグラフで検出する

![sasun-bughdaryan-GQ5uX_BlfmY-unsplash_v04.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/5bda2e8a-0848-1e13-1d23-41eb193b62b8.jpeg)
利益相反取引にはいくつかのパターンがありますが、今回は組織のメンバーが自分に繋がりのある企業との取引を承認してしまう、というケースを考えてみます。例えば、企業のある社員が自分の家族が経営する店から通常よりも高い金額でオフィス機器を購入した場合、これは企業にとって不利益となります。同様のことが政府や公共サービスで起きていれば、より深刻な不正として調査される必要があります。
![Screen Shot 2022-11-10 at 16.34.09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/bbd174f0-abf6-bfe3-3ca4-593b1c304ed6.png)
このような「繋がり」はいつも単純ではなく、いくつかの関係性で発生することがあります。そのような「繋がり」は故意に隠されている場合もありますし、偶然に生じてしまうこともあります。そのため、システムによって利益相反になりうる取引を検出することができれば、それは組織とそのメンバーを不正や不利益から守ることができます。

今回はグラフを使ってそのような「繋がり」を検出する方法を紹介します。ここでは Oracle Autonomous Database (ADB) の Graph Studio を使った場合の実行画面を掲載しますが、同じシナリオを全ての Oracle Database で試すことができます。セットアップ方法の詳細は、以下を参照してください。

- [Oracle Graph をクラウド上で構築（ADB 編）](https://qiita.com/ryotayamanaka/items/7769d1ed239bf997e3ff)
- [Oracle Graph をクラウド上で構築（DBCS 編）](https://qiita.com/ryotayamanaka/items/ef3c7bef872daf276979)

## 分析対象の表データ

以下のようなデータが表形式で入手可能であることを想定します。それぞれの表名には、便宜上 COI（= conflict of interest）というプレフィックスを付けておくことにします。各リンクを右クリックから保存できます。

- [COI_EMPLOYEE](https://raw.githubusercontent.com/ryotayamanaka/oracle-graph/main/conflict-of-interest/coi_employee.csv)（社員情報：社員の電話番号や住所）
- [COI_SUPPLIER](https://raw.githubusercontent.com/ryotayamanaka/oracle-graph/main/conflict-of-interest/coi_supplier.csv)（取引先企業情報：企業の電話番号や住所）
- [COI_PURCHASE](https://raw.githubusercontent.com/ryotayamanaka/oracle-graph/main/conflict-of-interest/coi_purchase.csv)（購買取引記録：取引先企業やどの社員がその購買取引を承認したか）
- COI_FORM（利益相反の申告：以下の表に正規化される）
  - [COI_FORM_MASTER](https://raw.githubusercontent.com/ryotayamanaka/oracle-graph/main/conflict-of-interest/coi_form_master.csv)（申告書マスター：申告書と社員の紐付け）
  - [COI_FORM_INTEREST](https://raw.githubusercontent.com/ryotayamanaka/oracle-graph/main/conflict-of-interest/coi_form_interest.csv)（申告された利害関係：複数の関係企業が申告される）

Autonomous Database (ADB) の場合は Database Actions からファイルをロードできます。以下のシナリオは Graph Studio のノートブックで再現できるので、[こちら](https://github.com/ryotayamanaka/oracle-graph/tree/main/conflict-of-interest) を参照して試してみてください。
![Screen Shot 2022-11-12 at 0.24.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/eaff508b-02c8-22dc-969b-28cd63b6849a.png)


## グラフの作成

Oracle Graph では、これらの表データからグラフを作成するために CREATE PROPERTY GRAPH 構文を使用します。

```
CREATE PROPERTY GRAPH coi_graph1
  VERTEX TABLES (
    coi_employee AS employee
      KEY (employee_id)
      PROPERTIES ARE ALL COLUMNS EXCEPT (postal)
  , coi_form_master AS form_master
      KEY (form_id)
  , coi_supplier AS supplier
      KEY (company_id)
  , coi_purchase AS purchase
      KEY (invoice_no)
  )
  EDGE TABLES (
    coi_form_interest_with_key
      KEY (id)
      SOURCE KEY(form_id) REFERENCES form_master
      DESTINATION KEY(company_id) REFERENCES supplier
      LABEL has_interest
  , coi_purchase AS approved_by
      KEY (invoice_no)
      SOURCE KEY (invoice_no) REFERENCES purchase
      DESTINATION KEY (approver_employee_id) REFERENCES employee
  , coi_purchase AS supplied_by
      KEY (invoice_no)
      SOURCE KEY (invoice_no) REFERENCES purchase
      DESTINATION KEY (company_id) REFERENCES supplier
  , coi_form_master AS declared_by
      KEY (form_id)
      SOURCE KEY (form_id) REFERENCES form_master
      DESTINATION KEY (employee_id) REFERENCES employee
  )
```

Graph Studio のノートブック上でこれを実行することで、データベース上の表データがメモリ上にグラフとして展開されます。

```python
%python-pgx
statement = """
CREATE PROPERTY GRAPH coi_graph1
  VERTEX TABLES (
    ...
  )
  EDGE TABLES (
    ...
  )
"""
session.prepare_pgql(statement).execute()
```

3800 ノードと 4759 エッジで構成されるグラフが作成されました。

```python
%python-pgx
graph2 = session.get_graph("COI_GRAPH1")
graph2

PgxGraph(name: GRAPH2, v: 3800, e: 4759, directed: True, memory(Mb): 3)
```

## パターンマッチング

グラフが用意できたら、パターンマッチングを使ったクエリを試してみましょう。

```sql
SELECT *
FROM MATCH (s1)<-[r1:has_interest]-(d)-[r2:declared_by]->(e)<-[r3:approved_by]-(p)-[r4:supplied_by]->(s2) ON coi_graph1
LIMIT 1
```
![Screen Shot 2022-11-11 at 16.52.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/1f8b6b5e-ba16-d271-69e1-c7c181732db0.png)
パターンが一行に長過ぎて読みにくいときは、次のように分割することもできます。ここで変数 s1 と s2 は同じサプライヤーを指していることもあれば異なることもありますが、パターンに二度出現する変数 e は同じ社員を指しています。

```sql
SELECT *
FROM MATCH (
  (s1)<-[r1:has_interest]-(d)-[r2:declared_by]->(e),
  (e)<-[r3:approved_by]-(p)-[r4:supplied_by]->(s2)
) ON coi_graph1
LIMIT 1
```

さらに、Graph Studio のノートブックでは、以下のような記法でテキストボックスを作成して、ユーザー入力によりクエリに与える条件を変更することができます。

```sql
SELECT *
FROM MATCH (
  (s)<-[r1:has_interest]-(d)-[r2:declared_by]->(e),
  (e)<-[r3:approved_by]-(p)-[r4:supplied_by]->(s)
) ON coi_graph1
WHERE e.first_name = '${First name}' AND e.last_name = '${Last name}'
```

![Screen Shot 2022-11-11 at 16.58.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/81331056-e323-9456-60f2-74e4019d5022.png)
この場合、ある社員 Cory Sims はサプライヤー Zachary Digital との関係を申告していますから、Zachary Digital からの購買の承認について、システムがアラートを上げる必要があるかもしれません。
![Screen Shot 2022-11-10 at 16.34.09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/bbd174f0-abf6-bfe3-3ca4-593b1c304ed6.png)
同様のパターンを網羅的に検出することも可能です。この 4 ホップの関係性がループになるパターンを表現するためには、始まりと終わりのノードであるサプライヤーが同じであることを示すため同じ (s) という変数にします。

```sql
SELECT *
FROM MATCH (s)<-[r1:has_interest]-(d)-[r2:declared_by]->(e)<-[r3:approved_by]-(p)-[r4:supplied_by]->(s) ON coi_graph1
```
![Screen Shot 2022-11-11 at 17.01.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/7945ba78-5089-56ec-dcdf-0a22bad09ada.png)

## 新しい関係性の追加

次に、社員やサプライヤーの間の新しい関係性に着目したい場合に、グラフ上にエッジを追加する方法について考えてみます。社員やサプライヤーのプロパティ情報から、新しい関係性を定義するというのはよくあるケースです。例えば、あまり現実的な状況ではないかもしれませんが、ある社員とあるサプライヤーが同じ電話番号（や緊急連絡先の電話番号）を共有していたら、ここには関係性があると考えてよいでしょう。
![Screen Shot 2022-11-10 at 16.37.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/00240d95-4c5b-f15b-2814-8c761a757bdb.png)
では、このような関係性を新しいエッジとして作成するために、効率の良い方法を考えてみます。電話番号という情報は社員ノードやサプライヤーノードのプロパティとして保持されていますので、これを基に PGQL クエリ（INSERT EDGE 構文）を用いてエッジを追加することが可能です。

その一方で、同じ値（ここでは電話番号）を網羅的に探し出すためには表のスキャンと結合操作が効率的です。グラフの元データが表に格納されているのであれば、その RDBMS 内で新たな表やビューとして関係性を定義しておくことができます。表の結合対象の列に索引を作成しておくのを忘れないようにしましょう。

```sql
CREATE VIEW coi_same_number_1 AS
SELECT ROWNUM AS id, e1.employee_id AS e1_id, e2.employee_id AS e2_id
FROM coi_employee e1, coi_employee e2
WHERE e1.EMERGENCY_CONTACT_PHONE = e2.phone;
```

```sql
CREATE VIEW coi_same_number_2 AS
SELECT ROWNUM AS id, e.employee_id, s.company_no
FROM coi_employee e, coi_supplier s
WHERE e.EMERGENCY_CONTACT_PHONE = s.phone;
```

これらのビューを入力として、新しい関係を含むグラフ（graph2）を作成します。

```
CREATE PROPERTY GRAPH coi_graph2
  VERTEX TABLES (
    ...
  )
  EDGE TABLES (
    ...
  , coi_emergency_contact_1
      KEY (id)
      SOURCE KEY(employee_id_1) REFERENCES employee
      DESTINATION KEY(employee_id_2) REFERENCES employee
      LABEL emergency_contact
      NO PROPERTIES
  , coi_emergency_contact_2
      KEY (id)
      SOURCE KEY(employee_id) REFERENCES employee
      DESTINATION KEY(company_id) REFERENCES supplier
      LABEL emergency_contact
      NO PROPERTIES
  )
```

クエリをかけてみると新しい関係性が作成されていることがわかります。
![Screen Shot 2022-11-11 at 17.02.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/63182a39-6fd4-9d28-bc16-812b08f31fe8.png)

## 空間的距離を基にした関係性

前項の方法で、新しい種類のエッジを次々に追加していくことができます。

ここでは、この手法を応用して、社員とサプライヤーの住所の空間的距離に着目してみましょう。もしもお互いの住所がとても近ければ、知り合いやお得意さんといった関係性があるかもしれません。
![Screen Shot 2022-11-10 at 16.38.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/e5267efd-696e-c34e-95cd-7658cf3b30c3.png)
効率的に距離を計算するために、社員とサプライヤーそれぞれの緯度経度情報をもとにジオメトリ列を作成し、この列に空間索引を作成しておきます。

```sql
CREATE TABLE coi_employee_geom AS
SELECT
  t.*,
  SDO_GEOMETRY(
    2001,       -- Geometry type (two-dementional point)
    4326,       -- Coordinate system ID (SRID) 
    SDO_POINT_TYPE(t.address_lon, t.address_lat, NULL), NULL, NULL
  ) AS address_geom
FROM coi_employee t;

INSERT INTO user_sdo_geom_metadata VALUES (
  'coi_employee_geom',
  'address_geom',
  SDO_DIM_ARRAY(
    SDO_DIM_ELEMENT('LONGITUDE', -180.0, 180.0, 0.05),
    SDO_DIM_ELEMENT('LATITUDE', -90.0, 90.0, 0.05)
  ),
  4326
);
COMMIT;

CREATE INDEX idx_coi_employee_geom
  ON coi_employee_geom (address_geom)
  INDEXTYPE IS mdsys.spatial_index_v2;
```

この索引を使用して「距離が 500m 以内」の社員とサプライヤーのペアをリストするようなビューを定義しておきます。

```
CREATE VIEW coi_within_500m AS
SELECT
  ROWNUM AS id,
  e.employee_id,
  s.company_no,
  SDO_GEOM.SDO_DISTANCE(e.address_geom, s.address_geom, 0.005, 'unit=M') AS dist
FROM
  coi_employee_geom e,
  coi_supplier_geom s
WHERE
  SDO_GEOM.SDO_DISTANCE(e.address_geom, s.address_geom, 0.005, 'unit=M') < 500;
```

```
CREATE PROPERTY GRAPH coi_graph2
  VERTEX TABLES (
    ...
  )
  EDGE TABLES (
    ...
  , v3_within_500m
      KEY (id)
      SOURCE KEY(employee_id) REFERENCES employee
      DESTINATION KEY(abn) REFERENCES supplier
      LABEL within_500m
  )
```

新しい関係性「within_500m」が追加されていることがわかります。この場合、Derek は住所が距離的に近い Kimberly Apparel からの購買を二度承認していることがわかります。
![Screen Shot 2022-11-11 at 17.03.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/81ebe1a9-8dd3-1278-1702-45b8fb43d331.png)
地図上に表示してみることも可能です。
![Screen Shot 2022-11-11 at 17.06.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/d4f2cec0-0d34-84ba-ae88-fba7dbc70783.png)

## 未知の長さのループの検出

ところで、PGQL には経路探索のためのシンタックスがあり、このようなクエリが実行されたとき、Oracle Graph はメモリ上のグラフに対してダイクストラ法などのアルゴリズムを用いることにより効率的に経路探索を実行することができます。

例えば、このクエリは二人の社員の間の最短経路を求めるものです。
```sql
SELECT a1, b, a2
FROM MATCH TOP 1 SHORTEST (e1) (-[r]-(v))+ (e2) ONE ROW PER STEP (a1, b, a2) ON graph2
WHERE e1.employee_id = '${Employee 1}' AND e2.employee_id = '${Employee 2}'
  AND COUNT(v) = COUNT(DISTINCT v)
```

Kelly と Jack が承認した購買のサプライヤーが（誰かの）申告書に記載されていたといったことがわかります。この情報はあまり有用ではありませんが、経路を求めることができました。
![Screen Shot 2022-11-11 at 17.12.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/4a89659a-c4d2-9937-dc50-ea728088eca1.png)

ここでいくつか補足しておきますと：

- `(-[r]-(v))+` というパターンは双方向のエッジを 1回以上辿ります。
- `ONE ROW PER STEP (a1, b, a2)` は得られたパスをステップごとに分解して、`a1, b, a2` という変数にマップしています。
- `COUNT(v) = COUNT(DISTINCT v)` という条件は同じノードを何度も通るようなパスを省くために追加しています。

そこで、以下のようなケースを考えてみましょう。このパターンは先に追加した「same_number」エッジも含まれた 5 ホップのループです。上記のパターンマッチでは決まったホップ数のループを検索していましたが、実際の分析ではこのパターンのように未知の長さのループを検出できると望ましいと考えられます。
![Screen Shot 2022-11-10 at 20.35.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/1532cbd0-6554-c9bc-0338-730e6aa2a49d.png)
そこで、先の経路検索を用いて道の長さのループを検出してみましょう。経路検索のはじめとおわりのノードを対象の社員としておき、同じエッジを一度だけ通るような経路を検索すればよいはずです。

```sql
SELECT a1, b, a2
FROM MATCH TOP 50 SHORTEST (e1) (-[r]-(v))+ (e2) ONE ROW PER STEP (a1, b, a2) ON graph2
WHERE e1.first_name = '${First name}' AND e1.last_name = '${Last name}'
  AND e1 = e2
  AND COUNT(v) = COUNT(DISTINCT v)
  AND COUNT(r) = COUNT(DISTINCT r)
```
このクエリを実行すると、期待通り 5 ホップのループが返されることがわかります。同時に「within_500m」を含むループも見つかっています。このように経路探索を使うことで、未知の長さの未知のパターンのループであっても検出できることがわかります。
![Screen Shot 2022-11-11 at 17.12.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/a9d75382-5fef-1c28-5ce8-c5d0b4dffdfe.png)

## まとめ

グラフを用いることで利益相反取引に特有のループを検出することができる事がわかりました。また、データベースを使って新しい関係性を定義することで、電話番号などの値の一致だけでなく、地理空間上の距離といったことも考慮に入れることができます。SQL には多くのファンクションがあるので、例えば、表記ゆれに対応するために文字列のファジーなマッチングをしたいといった場合にも多くの手法があるはずです。最後に、経路検索という Oracle Graph の強力な機能を使うことで、未知の長さの道のパターンでも検出できることを紹介しました。

この一連のシナリオは全ての Oracle Database（Oracle Graph は Oracle Database 12.2 以降に含まれています）で再現することができますが、 Autonomous Database に含まれる Graph Studio ノートブックを使えばセットアップも不要です。サンプルデータとノートブックは [こちら](https://github.com/ryotayamanaka/oracle-graph/tree/main/conflict-of-interest) に置いてあるのでぜひお試しください。Oracle Cloud の Always Free サービスでは Autonomous Database を無料でお使いいただけます。

※ 冒頭画像 Photo by [Sasun Bughdaryan](https://unsplash.com/@sasun1990?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)